Slashdot Mirror
John the Ripper Cracks Slow Hashes On GPU
solardiz writes "A new community-enhanced version of John the Ripper adds support for GPUs via CUDA and OpenCL, currently focusing on slow-to-compute hashes and ciphers such as Fedora's and Ubuntu's sha512crypt, OpenBSD's bcrypt, encrypted RAR archives, WiFi WPA-PSK. A 5x speedup over AMD FX-8120 CPU per-chip is achieved for sha512crypt on NVIDIA GTX 570, whereas bcrypt barely reaches the CPU's speed on an AMD Radeon HD 7970 (a high-end GPU). This result reaffirms that bcrypt is a better current choice than sha512crypt (let alone sha256crypt) for operating systems, applications, and websites to move to, unless they already use one of these 'slow' hashes and until a newer/future password hashing method such as one based on the sequential memory-hard functions concept is ready to move to. The same John the Ripper release also happens to add support for cracking of many additional and diverse hash types ranging from IBM RACF's as used on mainframes to Russian GOST and to Drupal 7's as used on popular websites — just to give a few examples — as well as support for Mac OS X keychains, KeePass and Password Safe databases, Office 2007/2010 and ODF documents, Firefox/Thunderbird/SeaMonkey master passwords, more RAR archive kinds, WPA-PSK, VNC and SIP authentication, and it makes greater use of AMD Bulldozer's XOP extensions."
I find it kind of odd that all of the analyses linked to in this article go on about SHA512-Crypt, BCrypt, SCrypt, etc, and the slideshow even talks about "Key Derivation Functions"... yet there doesn't seem to be any mention or comparision of PBKDF2-HMAC-SHA512 as a valid password-hashing key derivation function, despite it's widespread use, and that it's one of the core architectural components used in the design of SCrypt.
The fact that not every password is likely to be cracked is precisely what makes password security audits with John the Ripper useful. If every password would be getting cracked, there would be fewer legitimate uses for the tool. ;-)
Memorizing one 16-digit mixed-case alphanumeric password is realistic, but it does not help you all that much unless it's a "master password" (e.g., used to access an encrypted password manager database or to generate other passwords from or to access an encrypted filesystem where you store other passwords in plaintext), because you'd have difficulty memorizing a large number of unique and dissimilar passwords of this kind. Either way, if you're developing a server application or administering a server where users can register with passwords (maybe as one of the authentication options, not necessarily the only one), it becomes sort of your responsibility to make your users' passwords less likely to be cracked, even if the server security is temporarily compromised (you should assume that this might happen). Note that many of your users' passwords might be weaker than you would have liked them to be, and you don't want to enforce too strict a password policy (as that's a tradeoff). This is where the choice of hashing method to use matters, letting you use a less strict password policy for the same level of security or/and resulting in fewer passwords getting cracked (even with no enforced policy, since some people will choose medium complexity passwords on their own).
I've been using passphrases for about 12 years (and more than that if we count those passphrases on PGP and SSH keys as well), and I'm not growing out of it yet. I often use mixed-character-type passwords as well, and my phrases often use weird word separators, misspelled and/or partial words (less typing, same or better security if you do it right), different languages, etc. The number of words also varies (but with too few words other bits of complexity have to be introduced). For me, what is easier or harder to memorize varies depending on what kind of suitable idea I happen to have at a given time. Besides, the variety in password/phrase types buys me a few extra bits of entropy. Even an attacker who has read this comment or cracked a few of my passwords somewhere doesn't come up with one single pattern on password type that I use - because there are many. Thus, let your users choose between short but complicated passwords and longer but less complicated phrases. Similarly, let them choose between server-generated strings and user-chosen ones (the latter may be subject to policy enforcement). Our passwdqc tool set (PAM module, library, program for use from scripts) gives all of these options by default (but they can be disabled in any combination...) For server-generated strings, passwdqc uses 3-word phrase-like ones, with non-whitespace separators (out of a set of 8) and random word capitalization by default - that's 47 bits, which is currently sufficient in most user authentication contexts when used along with bcrypt hashes. With 4 words and the same approach, it's 64 bits ("pwqgen random=64" will do that) - but that is rarely needed with a decent password hash. (It is reasonable for data encryption keys, though - plus some 20 bits of stretching with a decent KDF.)
The real issue isn't so much the hashing algorithm used than it is the bloggers.
An adaptive algorithm (one that can be made to go slower by tuning the number of cycles) such as bcrypt, and as opposed to sha, is arguably much better.
In the end, however, the real problem is the huge number of self-proclaimed experts with an opinion ranging from wrong to hopelessly wrong -- and a very big mouth. It wouldn't matter much if they were at least partially right (apart from the facts that, yes, do hash, and yes, do salt), but computer security is one of those fields where nearly no one actually understands what they're talking about. Don't believe me? Have the next security experts you meet explain encryption to you for a few good laughs.
I like to compare this to PHP/MySQL. The MySQL module has been deprecated in favor of MySQLi for so long I dare not even think about it. Yet, pretty much every tutorial/answer out there uses the mysql_*() set of functions including, of all places, Stack Overflow. So here we are, with newbie coders learning from horrific examples, and then viewing spaghetti code bases like WordPress as best practice. And then they write their own PHP/MySQL tutorial on their own blog, and the 5 years later some newbie reads it, perpetuating the vicious circle. The next step is the same PHP/MySQL newbie wanting to secure his app, learning from poor examples and advices, and propagating them in the exact same way.
Anyway, the "use sha to hash passwords" BS and the inane salting strategies that invariably accompany them are here to stay for a long time, because the Internet has a very, very, very, very long memory.
The existing password hashing methods won't run on GPU well for user authentication, even when they do run well for cracking passwords. They lack sufficient parallelism within one hash computation. This is an issue I first raised in 1998, in pre-GPU context (it applies to recent CPUs as well, and the problem is getting worse with time).
A solution is to define a new password hashing method with sufficient (configurable) parallelism within one instance. We could then consider running it on GPU, unless it is GPU-unfriendly by other criteria. Do we really want to, though? GPUs in servers are not yet common, except in computing clusters. Their reliability may be lower than that of other typical server components. The drivers are currently relatively unreliable as well (although they may be reliable enough if running the same code, with no upgrades). Sure, computing clusters use them anyway, and get them to run reliably enough for their needs, but the extra hurdle and/or risk is there. Will we get embedded GPUs in typical servers soon? Will they be similar to current gamers' or HPC GPUs or not? This is not clear. Then there's Intel MIC, which delivers GPU-like performance, but is a lot closer to a CPU - it will require a lot of parallelism in the algorithm too, but it may run certain types of otherwise GPU-unfriendly code. Is this possibly a better target?
For current GPUs, a better strategy might be to make them inefficient - by using GPU-unfriendly hashes (for cracking, and for validation as well - as a side-effect).
We had a project last summer to research this kind of possibilities, focusing on use of FPGA boards in authentication servers. This could optionally buy us GPU-unfriendliness (if we want to make things more difficult for attackers with GPUs, but not FPGAs, and for botnets, which almost surely will lack FPGAs). We even considered some moderate CPU-unfriendliness of the component that we'd put on FPGA. Specifically, we experimented with bcrypt on FPGA, as well as with much smaller Blowfish-like "non-crypto" cores (not actual Blowfish), so that we could hopefully fit hundreds or thousands of those per chip (and have them somewhat CPU-unfriendly as well). Yuri, our GSoC 2011 student working on this project, did have some of this implemented in an experimental fashion, and some of it even worked (on FPGA boards kindly provided by Pico Computing), but an outcome of the summer project was that this would be time-consuming to bring to desired levels of performance and reliability. At that point, the project was put on hold.
A simpler and cheaper alternative (if there are only a handful of customers for this) may be to use dedicated servers, existing HSMs, or microcontrollers for just the password hashing. Indeed, microcontrollers are super slow, so their only function would be to hold and apply a local parameter, with the rest of the hashing method implemented on the host's CPU and RAM. If dedicated servers are used, they would need to be separate from authentication servers - that is, they won't know usernames, won't have access to any database, won't have any persistent storage except for the local parameter, and the OS and software indeed. They will accept password, salt, and parameters (such as the configurable per-hash processing and memory cost settings), and provide the hash. Thus, their attack surface would be minimal and they'd provide an extra layer of security against network-based attacks. We'd do this with FPGA boards as well, and we'd also have the greater/unusual computational complexity as a security layer (in case the local parameter or its backup copy is leaked/stolen), but well - using typical and pre-existing server hardware, drivers, etc. is just simpler and cheaper unless we start a new business and expect to have plenty of customers (although that might be possible).