The following interview was originally published by SecurityFocus. It is made available off the Openwall website with permission.
John the Ripper 1.7, by Solar Designer
Federico Biancuzzi, February 22, 2006
Story continued from Page 1
John is not new to 64-bit architectures. It was made to run on Alphas taking advantage of their 64-bitness back in 1997. In 1998, John 1.5 reached 200k c/s at traditional crypt(3) on an Alpha 21164A 600 MHz with pure C code, whereas a Pentium Pro 200 MHz (no MMX) would only do 20k c/s. With the initial MMX support, John would do 50k c/s on a Pentium 2 at 350 MHz (the fastest available) - still 4 times slower than the Alpha. Due to further improvements, John 1.7, if it were around at the time, would have achieved 250k c/s on that same old Alpha and over 100k c/s on that same old Pentium 2 (or 50k c/s on something as slow as Pentium MMX 166 MHz).
Now John 1.7 supports AltiVec on PowerPCs - welcome to 128-bit vectors and c/s rates in excess of 1 million. :-)
For a comparison against some historical 32-bit CPUs, a 386DX 40 MHz used to do around 1k c/s with Cracker Jack (a DOS program specifically optimized for 386s) and less than that with Crack. A MicroVAX 3100-80 (KA47 50 MHz) does a little below 1k c/s with the current John. Apparently, the original VAX-11/780 could do around 4 c/s. So with the newest PowerPCs and with the new John the Ripper we've got roughly 400,000 times better password cracking speed these days.
We have been using passwords for decades. What do you suggest in choosing a good one that is hard to crack?
Solar Designer: This is a seemingly simple question, but the answer depends on the specific circumstances and the kind of attacks the password is meant to resist.
Some people would say that passwords are obsolete. But we're continuing to use passwords anyway, for a variety of reasons. In fact, even many authentication systems designed to replace the old-fashioned password authentication do nevertheless use passwords (or passphrases). For example, the private keys used with SSH RSA or DSA authentication are encrypted using a passphrase as the encryption key. S/Key uses a passphrase to generate a sequence of one-time passwords (and Dug Song has contributed a patch to John the Ripper to crack those passphrases).
With some vendors re-inventing password hashing and doing it wrongly (or trying to be compatible with something ancient), and with increasing CPU performance, it is not possible to have passwords that are stored using certain hash types withstand offline attacks, even if the most stringent password policy is followed. That is, if someone would steal LM hashes from a Windows system (or capture them on the wire), those passwords would be relatively easily cracked, no matter what. The entire printable US-ASCII keyspace (that is, all possible passwords consisting of the 95 printable US-ASCII characters only) can be searched against any number of LM hashes within a couple of weeks on a single modern CPU, and most passwords would fall within the first hour. Of course, John takes advantage of the fact that LM hashes are case-insensitive and that the first 7 characters of passwords are processed separately from characters 8-14. (So-called rainbow tables can be even more effective against LM hashes, but John does not implement them.)
Why crack LM hashes with the purpose of detecting and eliminating "weak" passwords at all, then?
Solar Designer: One possible reason would be to ensure that the passwords are not as weak as to be easy to guess from the remote (or from a local login prompt, for that matter). Another reason would be to ensure that the not-so-weak NTLM hashes of the same passwords (that Windows systems use along with or instead of LM hashes) would be strong enough to withstand certain offline attacks. Someone who is into Windows security (I am not) could explain those subtle reasons better.
What is the situation in the Unix world?
Solar Designer: Speaking of Unix passwords, even the ancient traditional crypt(3) hashes can withstand John runs on a single CPU if extremely complicated passwords are chosen. Although it would be taking over 100 years to exhaustively search the printable US-ASCII keyspace against traditional crypt(3) hashes on a single CPU (that is currently available), in practice it is common to crack 20% to 60% of such hashes within a reasonable time (days, weeks, or months). When attacking individual password hashes (e.g., root's), the chances of success can be much higher (90% is a reasonable estimate) since all processing power can be directed against that one salt.
The newer crypt(3) hashing methods are generally better, resulting in password hashes that are stronger (given the same passwords), and they also don't have the 8-character limitation of traditional crypt(3).
The FreeBSD-style MD5-based hashes that are so popular nowadays (they're used on FreeBSD, on many (most?) Linux systems, and on Cisco IOS for "enable" passwords) are significantly better, but they aren't quite state of the art. The OpenBSD-style Blowfish-based (bcrypt) hashes are a whole lot better, adding variable iteration counts (such that a system administrator can proceed to adjust the processing cost for hashes that would be used for newly set or changed passwords as CPUs become faster).
Those multiple iterations of an underlying cryptographic primitive (such as modified DES, MD5, or Blowfish) are used to implement so-called "password stretching". bcrypt hashes can reasonably be configured to be, say, 15,000 times slower than traditional crypt(3) hashing on a given CPU. This is equivalent to passwords (or passphrases) containing 14 bits of additional entropy compared to what one has to actually remember and type in at a login prompt. That's roughly two words less to type in a passphrase.
So, do you suggest to use passphrases instead?
Solar Designer: Yes, for operating systems, applications, etc. which do not have a low limit on the length of passwords they accept, I recommend the use of passphrases instead of passwords. For even better security and/or to have fewer characters to type, both approaches can be combined: separate some words with punctuation rather than spaces, embed numbers and other characters, etc. Ideally, the passphrase should be something you can remember or derive again, but it must not be based on information that is known to others (e.g., your name, a quotation, a piece of the output of a Unix shell command, etc. - those are all to be avoided).
The shortest reasonable "passphrase" consists of a cryptographically random combination of three words (picked from a list of a few thousand) separated by unusual punctuation, and its length is no less than, say, 12 characters. This corresponds to roughly 40 bits of entropy, which, combined with a decent password hashing method such as bcrypt, gives a fairly strong password hash. Since a human cannot be expected to truly pick words at random, a passphrase you might think up would need to be longer than that. Older/weaker password hashing methods will require longer passphrases, too.
Care should be taken to see if long "passwords" are indeed fully processed by the target system rather than silently truncated at a certain length. For the traditional Unix crypt(3), that length would be 8 characters - so only those first 8 characters would need to be guessed by an attacker. A way to test for this is to set your password to something longer, then try to login to the system using only the first 8 characters.
On those older systems, in order for your password hash to be hard to crack, you have to use an unusual combination of lowercase and uppercase letters, digits, and other characters - making use of the maximum supported length (usually 8 characters). And I really mean "unusual" - just starting with a capital letter and/or ending with a number doesn't count. Needless to say, the password must not be based on your personally identifiable information or a dictionary word in any known language. (Some older papers on password security recommended picking the first letter of each word of a phrase to form short and easy to remember, yet unusual passwords. Unfortunately, this results in a highly non-uniform distribution of characters used - which John is able to take advantage of. So I do not recommend it.)
Story continued on Page 3