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
