Subject: AES pw hash performance numbers

From: Marcus Watts <[email-masked]>
Date: Sat, 08 Dec 2001 19:38:18 -0500

The interesting question about pw hashing is, can one make it
"expensive" enough on a low-end device that even someone with a high
powered array of devices can't hope to mount a dictionary attack? In
very rough terms, a reasonable randomly generated 10-12 character
password probably has about 40 bits of entropy in it.  A low-end
machine is probably about the power of a Mac IIci.  I haven't done any
work to compute just how slow a Mac IIci would be, or how long a room
full of high end machines (ie, any university computing lab) might take
to crunch through 2**40 passwords.   While I can't answer that
definitively, I made some educated guesses at the end of this.

There is no guarantee that the machine won't be busy doing other things
(a multi-user machine, a router, or something doing real-time video or
sound processing, where a drop-out is tolerable, but not necessarily
appreciated), or that the algorithm will be implemented in the most
efficient manner possible (and not, say Java).  I don't know how to
quantify any of these.  These do make it harder to say what is "too
slow".

I ran my tests on 2 machines, an elderly and obselete RS/6000 and the
considerably faster sun workstation on my desk which itself is just
starting to become obselete.  I make 2 sets of numbers, one for
straight Unix authentication, and 1 for k5 based algorithms.  At the
very least, this gives some indication of what people have in the past
considered acceptable performance.

		1. === "crypt" ===

The first set of numbers I have is for various present-day non-K5
hashes.  These are all used for Unix authentication more or less
directly, with no network delays, & little other CPU overhead
in the rest of the authentication.

In the below, I compared, where relevant, 4 character, 16 character,
and 64 character paswords.  1b crypt = the original AT&T Unix crypt
algorithm, which works 1 bit at a time.  bsd crypt(newsalt) = what's in
current versions of netbsd, openbsd, etc.  1b crypt(newsalt) is a copy
of AT&T Unix I hacked up to do newsalt in a fit of madness, so is
probably unreasonably slow.  md5 and blowfish are also from openbsd and
family.  "grex" is a password hash I came up with a while back,
described at the end of
	http://www.cyberspace.org/staffnote/passwd.html

RS/6000 530H, 33.3 Mhz SGR 3064
==> rs_aix32/,timings <==
in all cases, md5 rounds = 1000 (hardwired)
 newsalt rounds = 7250 (min)
 blowfish rounds = 4 (min)
crypt (4 letter password)
       libc crypt : 19797.571 us (count=247)
         1b crypt : 11941.748 us (count=412)
   bsd crypt(old) : 544.403 us (count=9166)
 1b crypt(newsalt) : 3385000.000 us (count=2)
 bsd crypt(newsalt) : 152424.242 us (count=33)
          bsd old : 544.425 us (count=9184)
      bsd newsalt : 153750.000 us (count=32)
          bsd md5 : 39840.000 us (count=125)
     bsd blowfish : 156562.500 us (count=32)
             grex : 679.173 us (count=7303)
crypt (16 letter password)
      bsd newsalt : 153030.303 us (count=33)
          bsd md5 : 52291.667 us (count=96)
     bsd blowfish : 156875.000 us (count=32)
             grex : 680.365 us (count=7349)
crypt (64 letter password)
      bsd newsalt : 153030.303 us (count=33)
          bsd md5 : 82131.148 us (count=61)
     bsd blowfish : 156562.500 us (count=32)
             grex : 798.908 us (count=5495)

Ultra-5, 270 Mhz
==> sun4x_56/,timings <==
in all cases, md5 rounds = 1000 (hardwired)
 newsalt rounds = 7250 (min)
 blowfish rounds = 4 (min)
crypt (4 letter password)
       libc crypt : 1914.242 us (count=2612)
         1b crypt : 1589.567 us (count=2517)
   bsd crypt(old) : 114.682 us (count=43599)
 1b crypt(newsalt) : 599950.000 us (count=10)
 bsd crypt(newsalt) : 31847.197 us (count=157)
          bsd old : 114.832 us (count=43542)
      bsd newsalt : 31847.261 us (count=157)
          bsd md5 : 8417.508 us (count=594)
     bsd blowfish : 19684.882 us (count=254)
             grex : 97.420 us (count=51324)
crypt (16 letter password)
      bsd newsalt : 31847.261 us (count=157)
          bsd md5 : 10683.761 us (count=468)
     bsd blowfish : 19531.250 us (count=256)
             grex : 97.656 us (count=51200)
crypt (64 letter password)
      bsd newsalt : 32051.282 us (count=156)
          bsd md5 : 17730.319 us (count=282)
     bsd blowfish : 19531.289 us (count=256)
             grex : 109.680 us (count=45587)

		2. === possible "aes" alternatives ===

In the 2nd round, I tried various k5 string to key functions,
including the present-day des and afs variants, dk
which I think is what is used with des3, and various
flavours built on pkdbf2.

RS/6000 530H, 33.3 Mhz SGR 3064
==> rs_aix32/,timings <==
k5 keygen tests
          des (4) : 1079.578 us (count=7611)
         des (16) : 1310.728 us (count=5633)
         des (64) : 2425.318 us (count=3381)
          afs (4) : 83003.297 us (count=101)
         afs (16) : 1283.253 us (count=6403)
         afs (64) : 2376.200 us (count=3507)
           dk (4) : 8040.364 us (count=1024)
          dk (16) : 10514.116 us (count=791)
          dk (64) : 20612.929 us (count=397)
     pbdkf2 (md5) : 2292.356 us (count=3628)
    pbdkf2 (sha1) : 2540.079 us (count=3202)
  pbdkf2 (sha256) : 1618.249 us (count=5129)
  pbdkf2 (sha384) : 5359.477 us (count=1530)
  pbdkf2 (sha512) : 5354.839 us (count=1550)
     rijndael 128 : 2149.123 us (count=3800)
     rijndael 192 : 6184.799 us (count=1342)
     rijndael 256 : 6275.562 us (count=1304)
 sha256 16 char pw : 1669.765 us (count=4841)
 sha256 64 char pw : 1892.453 us (count=4333)
      serpent 128 : 2215.723 us (count=3761)
      twofish 128 : 2952.140 us (count=2772)
   sha256 iter=10 : 7816.415 us (count=1064)
  sha256 iter=100 : 78412.695 us (count=105)
 sha256 iter=1000 : 777272.727 us (count=11)

ultra-5 270 Mhz.
==> sun4x_56/,timings <==
k5 keygen tests
          des (4) : 65.360 us (count=76346)
         des (16) : 78.191 us (count=63818)
         des (64) : 132.466 us (count=37670)
          afs (4) : 4573.786 us (count=1091)
         afs (16) : 87.431 us (count=56273)
         afs (64) : 147.293 us (count=33878)
           dk (4) : 1133.576 us (count=4402)
          dk (16) : 1569.182 us (count=3180)
          dk (64) : 3324.450 us (count=1501)
     pbdkf2 (md5) : 121.017 us (count=41234)
    pbdkf2 (sha1) : 172.414 us (count=28942)
  pbdkf2 (sha256) : 140.147 us (count=35320)
  pbdkf2 (sha384) : 419.222 us (count=11903)
  pbdkf2 (sha512) : 418.554 us (count=11922)
     rijndael 128 : 207.174 us (count=24086)
     rijndael 192 : 526.205 us (count=9483)
     rijndael 256 : 531.134 us (count=9395)
 sha256 16 char pw : 145.485 us (count=34299)
 sha256 64 char pw : 167.058 us (count=29391)
      serpent 128 : 208.547 us (count=23400)
      twofish 128 : 263.574 us (count=18970)
   sha256 iter=10 : 681.013 us (count=7342)
  sha256 iter=100 : 6765.900 us (count=739)
 sha256 iter=1000 : 67567.568 us (count=74)

When John Brezak was specifying "about 1 second", he hasn't indicated
the class of machine he's talking about.  At any given time there's
probably at least an order of magnitude difference between the fastest
and slowest machines in common use.  I'll assume John was actually
trying to say "about as fast as the slower Unix algorithms".  If that's
what he meant, then I predict an iteration count of about 500 would
satisfy him; perhaps a bit more if he only means "new" hardware today.
If he means *literally* 1 second, on my ultra-5 270 Mhz, then that
would be an iteration count of 39000.  On the RS/6K in my office, which
is still the machine my mail shows up on, that will take about 30
seconds of CPU time to compute.  I don't know about John, but I would
regard that as very annoying.

The obselete RS/6K is probably still 2-4 times faster than a Mac IIci
or motorola Startac.  The workstation on my desk is probably 1/4th the
speed of the fastest workstations commonly made today.  So 4*30*4 =
performance factor of 480.  If the good guy is willing to wait 1 second
on his slow box (iteration count = 325?) the bad guy can make tries in
2 milliseconds.  That means he needs an average of 35 years (2199023255
seconds /2) of fast computer time to try for 2**40 passwords.  Given a
lab of 100 machines, that drops down to 127 days average.  Making
everyone change their password once a year may not be good enough to
protect against this.  A distributed crack attack, say, using a virus
to do the thinking, might drop this down farther.  On the other
hand, these numbers may be all wrong.

				-Marcus Watts
				UM ITCS Umich Systems Group