Password cracking benchmarks

[Alan Amesbury <amesbury () OITSEC UMN EDU>]

OK, folks, bad news:  This is a looong posting.  This topic comes up in
discussion locally between academic units all the time, and I see we're
skirting around it on EDUCAUSE.  However, the last time I looked at this
in detail was several years ago, and on/with much slower systems.  Call
this the semi-decade update.  The good news is the math is pretty
straightforward.  My apologies if this seems overly basic to you; I just
want to make sure everyone has all the information.

When I talk about search space below, I'm referring to all possible
passwords given the character set (more specifically, keyboard)
limitations and the algorithms involved.  My notes below use "^" to
represent an exponent and "Enn" to represent scientific notation,
neither of which renders very well in plain text.  As an original work,
I claim all the mistakes made below; let me know if (when) you find
one.  Yes, some systems can use extended characters; use of those is a
bit out of scope here, except for the fact they can be considered
additional characters in a search space.




THE ALGORITHMS
--------------
Since it's come up on EDUCAUSE very recently, I'll pick on LANMAN.
LANMAN's weak for several reasons.  First, it's not case-sensitive,
which significantly reduces password search space.  This is important,
as lack of case dramatically reduces the number of possible passwords.
I *think* LANMAN can use the following character set for its passwords:

    count   class
    -----   ------------------------------------------------
      26    all letters (upper and lower combined)
      10    digits
      10    shifted symbols from digit keys
      22    remaining symbols and their shifted counterparts
    +  1    space
    -----   ------------------------------------------------
      69    total


A case-sensitive algorithm (which includes the password hashing
algorithm on most Unix variants, and MSFT's NTLM) would give us an
additional 26 characters, for a total of 95.  This difference alone
doesn't seem like much, until you consider how much it affects total
password space.  The total number of seven character passwords (just
seven characters, ignoring shorter possibilities for the moment, and
remembering that seven characters is the effective limit for LANMAN) is
7,446,353,252,589 (69^7), while the total number of possibilities with
the full 95 character set is 69,833,729,609,375 (95^7, or close to an
order of magnitude more).  So, total number of possibilities is
69+69^2+69^3... and so on, up to 69^7.  Here's the totals for 69
characters and 95 characters:

                69
              4761
            328509
          22667121
        1564031349
      107918163081
   + 7446353252589
   ---------------
     7555858447479 or about 7.556E12

                  95
                9025
              857375
            81450625
          7737809375
        735091890625
    + 69833729609375
    ----------------
      70576641626495 or about 7.058E13


You also start to get some idea of why algorithms that can use more
characters are better, which leads us to another problem with LANMAN:
it uses too few characters.  Even if it were limited to the same
character set as LANMAN, the old DES-based crypt() function's eight
character limit still increased search space dramatically.  69^8 is
about 5.138E14 (actually 513,798,374,428,641), a substantial gain in
search space.  Modern password hashing algorithms can use more than
eight characters, so the password space rapidly becomes--to put it
mildly--VERY LARGE.

LANMAN's third weakness is that it's computationally cheap, at least
compared with other password algorithms.  Here's some password
calculation rates for several algorithms as implemented in John the
Ripper (a well known password cracker) on an Athlon64 and a Xeon.  Note
that this instance of John has been patched to be able to crack "NT MD4"
(NTLM):

                        "crypts/sec"
    Hashing algo   Athlon64     Pentium 4
    ------------   --------     ---------
    DES, one salt    556.9K        315.2K

    FreeBSD MD5       4,052         9,014

    OpenBSD             291           447
       Blowfish

    NT MD4 (NTLM)    1,095K        985.1K

    LM DES (LANMAN)  5,174K        4,545K


DES is only a tenth as fast as LANMAN (remembering that this is one area
where speed is *BAD*).  OpenBSD's Blowfish-based hashing algorithm gets
the tortoise prize; its computational expense makes it a very
undesirable target for brute-force attacks.

Finally, LANMAN uses no salt.  This is essentially a random value tossed
into the computational mix when generating a password hash.  The idea is
that this random value perturbs the output of the hash function, making
it much more difficult to simply compare hashes to determine if
passwords are identical.  For example, the value "testing" hashes as
"jyOCKiECE7Q" when using the salt "Hf" and hashes as "joVBHOq2SNk" when
using the salt "3R".  So, if two users happen to pick the same password,
an algorithm that uses salts will make it harder for an attacker to
detect that.  It also means that an attacker has to calculate a hash for
*each* salt belonging to a target account.  If there's ten accounts
(each with a different salt) that an attacker is interested in, then the
workload required just increased by an order of magnitude.  LANMAN,
unfortunately, lacks this feature; a maximum of one computation per
possible password value is all that's required.



BRUTE-FORCE ATTACKS
-------------------
Now that we know something about algorithms, their speeds, etc., we can
figure out real-world attack speeds.  (I'll get to Rainbow in a bit.)
I'll continue to pick on LANMAN here for a bit.

We've already determined the total number of possible passwords with
LANMAN is something like 7.556E12.  We also know that an Athlon64 can
chew through these possibilities at a rate of around 5.174E6/second.
Simple math says it's going to take about 1.460E6 seconds to check them
all.  That works out to about sixteen days.

The Unix crypt() function is more expensive (slower), so it takes longer
to attack it.  It's also case-sensitive, which drastically increases the
password search space.  For example, counting *only* all possible eight
character passwords results in a password space of 6,634,204,312,890,625
(~6.634E15, or 95^8).  So, brute-force attacks for *HALF* the available
password space (assume the attacker gets lucky and guesses correctly in
the first 50%) for a couple algorithms using the Athlon64 benchmarked
above would be:

    For LANMAN:   3,777,929,223,739 words
                    / 5,174,000 crypts/sec
                    = 730175 seconds (~8.5 days)

    For NTLM:     3,352,390,477,258,560 words
                    / 1,095,000 crypts/sec
                    = 3,061,543,814 seconds (~97 years)

    For crypt():  3,352,390,477,258,560 words
                    / 556,900 crypts/sec
                    = 6,019,735,100 seconds (~190 years)


Most users change their passwords often enough that crypt(), even though
it's definitely showing its age, still provides quite a bit of
protection against brute-force attacks.  It's also pretty clear that a
smaller password search space plays a *BIG* role in successful attacks.




DICTIONARY ATTACKS
------------------
Arguably brute-force attacks are simply dictionary attacks with a really
huge dictionary.  However, when I speak of dictionary attacks, I'm
referring to attempts at guessing passwords which are based, at least in
part, on a "dictionary" word.  (Note that the dictionary in which the
word appears doesn't *have* to be English, nor do they have to be common
words.  In this sense, "dictionary" simply refers to a list of words,
common or otherwise.)  I don't recall how many words there are in the
English language, but I think I've seen collegiate dictionaries with
100K.  Let's call it an even million words, then double that to include
words from other languages (Vietnamese, German, the Star Trek and
Tolkien universes, etc.).  Now, since users are smart enough to perturb
dictionary words by doing things like replacing "s" with "$", spelling
the word backwards, etc., let's say that we'll try up to a thousand of
these variations per word, giving us a list of two billion "words" to
check.  Time needed to brute-force this dictionary:

    For LANMAN:   2.000E9 words / 5.174E6 crypts/sec = 386 seconds
    For DES:      2.000E9 words / 5.569E5 crypts/sec = 3591 seconds
    For NTLM      2.000E9 words /
    For BSD-MD5:  2.000E9 words / 4,052 crypts/sec = 493583 seconds
                                                    (<6 days)


Keep in mind this would be likely to catch passwords like
"di$est4bl!shmen7ar1an" even though that's more than eight characters.

Where attacks against LANMAN *really* help is in reducing the search
space for attacking NTLM.  A smart attacker will brute-force the LANMAN
hash, then use all the possible case substitutions as a drastically
reduced dictionary attack against NTLM.  Since LANMAN and NTLM inputs
only differ in terms of letter case, a worst-case scenario would be
finding a LANMAN hash whose input was all letters.  An attacker would
have to try all possible combinations of the letters in upper- and
lower-case.  However, that's *EASY*; it essentially becomes a
brute-force attack against a password which has two possibilities per
letter for each each of the seven character slots.  2^7 is *not* a very
large number.  A number of tools have been using this approach for years
(L0phtcrack being probably the most famous), and this is why most
security experts recommend disabling LANMAN at the earliest opportunity.

It's for this reason that I believe passphrases (strings of words, as
opposed to single words) are far more resistant to attack.  Not only are
they relatively easy to remember (at least compared to something like
"8>'G:4/w?q"), but they take advantage of a fairly large search space.
I suppose the next-gen attacker will have grammar-aware cracking
software which might make grammatically correct passphrases an increased
risk, but I think passphrase use alone raises the bar sufficiently that
an attacker will find it more profitable to pick another avenue of
attack or (better still) move on to a more appealing target somewhere
else.  (Hopefully that won't be any of you.)



RAINBOW TABLES
--------------
The thread discussing this on EDUCAUSE is what sparked my writing this.
This isn't password cracking; it's a database lookup.  The idea is that
an attacker only has to compute hashes once (or buy a copy of them
pre-computed), rather than attacking passwords through computational
power.  While the speed at which you can look up a hash in a table is
arguably a factor here, that sort of thing is pretty well understood.  I
think the big limiter is storage.  Consider this rather simplistic view
for all possible values for LANMAN:

     chars                   bytes
      in       number of      per
    passwd   possibilities  passwd     total bytes
    ------   --------------  ------  --------------
       1                 69    2                138
       2               4761    3              14283
       3             328509    4            1314036
       4           22667121    5          113335605
       5         1564031349    6         9384188094
       6       107918163081    7       755427141567
       7      7446353252589    8     59570826020712
                                     --------------
                                          ~56,200GB


Limiting search space certainly helps; a table containing passwords with
*only* letters and numbers comes out to around 600GB.  Conversely, a
table built around the full 95 character set would be somewhere around
half a petabyte.  There's also the computational expense to consider, as
the hashes have to all be computed at least *once* to create such a table.

So, while storage is definitely getting cheaper, I think this sort of
thing is also not too much of a threat, at least where sites that don't
use LANMAN are concerned.  The longer your password/passphrase, the
larger the possible password space.  I believe that, combined with
making routine password changes (thus making your password a moving
target) will continue to make other avenues of attack (social
engineering, for example) much more lucrative than attacks directly on
reusable passwords.





Again, I *think* my numbers are correct.  If not, I'd appreciate
corrections.  (Also, keep in mind that any idiocy I demonstrate here is
not intended to reflect upon my coworkers or employer.)  For reference,
some benchmarks from John the Ripper appear below my sig.  Note that the
numbers drifted a bit from my examples above; the original test runs
scrolled and the machines in question aren't completely idle.


--
Alan Amesbury
University of Minnesota


Host #1:  Athlon64 2800+
Host #2:  3.2GHz Xeon

Both hosts:  FreeBSD 5.4-RELEASE-p8

The Athlon64 is running the "amd64" version of FreeBSD, while the Xeon
is running the "i386" version.


---------- John the Ripper output from host #1 ----------
% john -test
Benchmarking: Traditional DES [64/64 BS]... DONE
Many salts:     616375 c/s real, 621368 c/s virtual
Only one salt:  568710 c/s real, 573571 c/s virtual

Benchmarking: BSDI DES (x725) [64/64 BS]... DONE
Many salts:     18611 c/s real, 18694 c/s virtual
Only one salt:  18447 c/s real, 18549 c/s virtual

Benchmarking: FreeBSD MD5 [32/64 X2]... DONE
Raw:    4079 c/s real, 4099 c/s virtual

Benchmarking: OpenBSD Blowfish (x32) [32/64]... DONE
Raw:    292 c/s real, 294 c/s virtual

Benchmarking: Kerberos AFS DES [48/64 4K]... DONE
Short:  251313 c/s real, 252733 c/s virtual
Long:   693589 c/s real, 701749 c/s virtual

Benchmarking: NT LM DES [64/64 BS]... DONE
Raw:    5180K c/s real, 5212K c/s virtual

Benchmarking: NT MD4 [TridgeMD4]... DONE
Raw:    1076K c/s real, 1104K c/s virtual

-------- End John the Ripper output from host #1 --------


---------- John the Ripper output from host #2 ----------
% john -test
Benchmarking: Traditional DES [24/32 4K]... DONE
Many salts:     351399 c/s real, 356403 c/s virtual
Only one salt:  326246 c/s real, 328298 c/s virtual

Benchmarking: BSDI DES (x725) [24/32 4K]... DONE
Many salts:     11528 c/s real, 12590 c/s virtual
Only one salt:  10569 c/s real, 12317 c/s virtual

Benchmarking: FreeBSD MD5 [32/32]... DONE
Raw:    8436 c/s real, 9120 c/s virtual

Benchmarking: OpenBSD Blowfish (x32) [32/32]... DONE
Raw:    435 c/s real, 454 c/s virtual

Benchmarking: Kerberos AFS DES [24/32 4K]... DONE
Short:  307404 c/s real, 311789 c/s virtual
Long:   706531 c/s real, 712085 c/s virtual

Benchmarking: NT LM DES [32/32 BS]... DONE
Raw:    4566K c/s real, 4623K c/s virtual

Benchmarking: NT MD4 [TridgeMD4]... DONE
Raw:    1000K c/s real, 1014K c/s virtual

-------- End John the Ripper output from host #2 --------