Subject: AES and SHA-1 timing

From: Marcus Watts <[email-masked]>
Date: Tue, 01 Apr 2003 02:31:22 -0500

I'm still trying to understand Raeburn's claim that he can get do
pbkdf2 in slightly under 1 second don a 300 Mhz pentium II.  But I now
have a strong hunch.  I think he must be linking against a fairly
recent version of openssl, and using the sha-1 code from there.  That
is a super souped up assembler version (generated by a perl script)
which I believe is especially optimized for the pentium II.  My belief
is that if he were using the sha-1 code in the MIT kerberos 5
distribution, that he would see much more leisurely string to key
conversion times, like 4-5 seconds.

For what it's worth, in the process of understanding this,
I wrote an assembly version and compared the speed of various
versions of stuff.  My best assembly version is here:
	http://www-personal.umich.edu/~mdw/shs.tar
I got more interested in this after I discovered that the
latest heimdal snapshot had AES in it, and it's faster than
what I had.  How embarassing.

Here are timings I got for SHA-1 on various machines -- probably
more interesting for relative value since I don't know the
clock rates on some:

	SHA-1, microseconds to hash N bytes
	mdw assembler	k5 C		openssl 0.9.7a
N	16	8192	16	8192	16	8192
486	86	9147	141	17080	98	10350
pentII	6.36	607	8.83	1147	4.45	541
athlon	1.7	169			(2.4	280)*
pent4/M	1.21	101	4.08	526	1.59	168
	* = openssl 0.9.6

Time to hash 1 password to a 128 bit key on pent4/M, seconds:
k5 C		.531
mdw assembler	.20
heimdal		.21
Time to hash 1 password to a 256 bit key on pent4/M, seconds:
k5 C		1.068
mdw assembler	.41
heimdal		.423

Using the above, the pentium II I tried above "should" give a time of
about 1.0720 seconds to do one 128 bit aes string to key conversion,
using openssl 0.9.7a.  This seems to match Raeburn's figure exactly,
so I suppose my pentium II is also 300 Mhz (I wasn't able to
reach its owner tonight to confirm that...)

Presumably, if the iteration count is left alone, either MIT needs to
consider supplying an assembler version of SHA-1 (such as the one I
posted above), linking against openssl crypto (which I understand they
don't want to do), or folks running MIT kerberos-5 on linux and wanting
to do AES will need to consider either using heimdal, buying fast
machines, or living with very slow login times.

None of the above should be considered any sort of bound on an
attacker's compute speed.  For starters, an attacker could consider
writing SHA-1 code to do several conversions in parallel.  RISC
machines such as the powerpc, sparc, or perhaps hammer, which have
plenty of registers, might be easily capable of doing 2 or 4 SHA-1
conversions in parallel.  This speed advantage doesn't help the
legitimate user much [well, maybe with an assembler version of hmac
there's some room here...] but helps the attacker plenty.  Some of the
vector processing units in some modern CPU chips may be capable of even
more parallelism.  A more ambitious attacker could buy a bunch of chips
like
	http://www.hifn.com/products/8065.html
and build some sort of pipelined machine to run a lot of SHA-1
conversions very fast all at once.

				-Marcus

---

From: Ken Raeburn <[email-masked]>
Date: Fri, 04 Apr 2003 01:09:05 -0500

Marcus Watts <[email-masked]> writes:
> recent version of openssl, and using the sha-1 code from there.

I didn't keep my test setup around, and the 300MHz machine itself is
now powered off, but I believe that's correct.  Do you think it's
important that I reconstruct my test case and record the details for
future reference?  (Probably an appendix or footnote in the AES doc
would be the most suitable place.)

>  That

Yes, by comparison, our version would probably be slower.

I haven't looked much to see if they've made any interesting
higher-level changes.  There does seem to be something about reversing
the byte order of some data....

> what I had.  How embarassing.

:-)

Speeding up assembly code isn't easy, and often not too worthwhile.
Most of the time the effort may be better spent improving the
compiler.  There are exceptions, of course.

And after someone has done the work to speed up the assembly version
for a body of code, sometimes the optimizations can be put back into
the C code, or even taught to the compiler.  Bill Sommerfeld and I
(mostly Bill, I think) had some fun with the Vax GCC machine
description years ago, teaching it how to out-perform the mixed C and
assembly version of the DES code MIT was using....

> reach its owner tonight to confirm that...)

What OS?  Linux has speed info in /proc/cpuinfo.  I don't see anything
at first glance in NetBSD, but my last set of boot-time messages are
long gone.  I think Solaris may have something but I'd have to
research it.  Windows probably has something in the system tools...

> machines, or living with very slow login times.

Yes, we need to look at that.  (And check performance on our Solaris
boxes too; both sparc and i386 will be important around MIT.)  Right
now, we're still finishing up the implementation; performance tweaks
can wait a little, but having an assembly version ready to drop in is
great news.

> attacker's compute speed. [....]

Very good points.

> there's some room here...]

Hmm, maybe.  Start hashing the key-xor-pad for the second hash, while
doing some of the processing of the first hash...it gets tricky,
considering the hash works on a block at a time, and we don't have a
fixed size for the key in the string2key case.  Let's leave that one
for later. :-)

Ken

---

From: Ken Raeburn <[email-masked]>
Date: Wed, 09 Apr 2003 05:46:59 -0400

I've done some timing tests of my own, with some of the systems I've
got available now, and the results are below.  (The "per test" time is
the interesting one.)  Based on these numbers, I do think it would be
reasonable to lower the default iteration count; I don't think we
should be assuming higher-end hardware dominates.  We certainly won't
want to deploy it around MIT using 45056 iterations.  Maybe something
like 4096 (1/11 of 45056) would be a better default?

system: Pentium 4 2GHz
compiler: gcc-2.96 -O2
OS: Linux 2.4.18

    Testing krb5 pkbdf2 and sha1....
    10 loops of 5 tests (45056 iterations) took 48.962646 seconds
    average 0.979253s per test, 2.173413e-05s per iteration

    Testing openssl PKCS5_PBKDF2_HMAC_SHA1....
    10 loops of 5 tests (45056 iterations) took 50.266525 seconds
    average 1.005330s per test, 2.231291e-05s per iteration

    Testing krb5 pkbdf2 and openssl sha1....
    10 loops of 5 tests (45056 iterations) took 25.330676 seconds
    average 0.506614s per test, 1.124409e-05s per iteration

system: Sun Ultra 10 Model 300, UltraSPARC-IIi 300MHz
compiler: gcc-2.95.3 -O2
OS: Solaris 8

    Testing krb5 pkbdf2 and sha1....
    10 loops of 5 tests (45056 iterations) took 267.681964 seconds
    average 5.353639s per test, 1.188219e-04s per iteration

system: SGI IP32, MIPS R5000 200MHz
compiler: gcc-2.95 -O2
OS: IRIX 6.5.?? 32-bit

    Testing krb5 pkbdf2 and sha1....
    10 loops of 5 tests (45056 iterations) took 430.697025 seconds
    average 8.613941s per test, 1.911830e-04s per iteration

system: COMPAQ XP1000, Alpha EV6 21264, 500MHz?
compiler: cc -O2
OS: Tru64 5.1A

    Testing krb5 pkbdf2 and sha1....
    10 loops of 5 tests (45056 iterations) took 32.145709 seconds
    average 0.642914s per test, 1.426922e-05s per iteration

These tests were run on the test cases from the AES draft,
string-to-key test vectors, with all iteration counts changed to
45056, the generated intermediate key size set to 256 bits since
that's the required size to support in the current Clarifications
draft, the final AES encryption omitted, and duplicate cases removed,
leaving 5 test cases.

Ken