Subject: some more AES pkcs5 timings

From: Marcus Watts <[email-masked]>
Date: Fri, 14 Mar 2003 05:09:55 -0500

I wrote perl and java implementations of pkcs5 and
the proposed k5/aes string to key function.

They are here:
	http://www.umich.edu/~umich/pkcs5.perl.tar
	http://www.umich.edu/~umich/pkcs5.java.tar
The perl module needs a copy of Crypt:AES .  You might
be best off using Crypt:Rijndael, here:
	http://www.mirrors.wiretapped.net/security/cryptography/libraries/perl/crypt-aes/Crypt-Rijndael-0.05.tar.gz
(and no doubt many other places)
but I was offline at the time so wrote my own:
	http://www.umich.edu/~umich/Crypt-AES-0.0.tar

The timings I got were, well, a bit bizarre.

				C	perl	java
obsd3.2 thinkpad a31p, 1.7Ghz	11.3	74.0	443.2
sol2.6 sun ultra 5, 270Mhz	77.0	641.0	191.0

These were the number of seconds to run 14 test cases from Raeburn's
draft 03 but with an iteration count of 45056, half 128 & half 256 bit
keys.  So, divide by 630784 to get the "average" per iteration delay,
or divide by 20 to get an approximation for one 128 bit password to
compare to Raeburn's figure.

Raeburn reports he was able to run this function in "slightly less than
one second on a pentium II at 300 Mhz.".  Unfortunately, he doesn't say
which tools he used.  In my case, openbsd 3.2 and gcc 2.95.3 doesn't
take full advantage of a pentium 4/mobile; it took me about 533 ms to
do the same.  The code spends most of its time in SHSTransform, which
in my case was built using the C code from MIT kerberos 5.  An
assembler version of shs might get better performance, and some
versions of openssl do have such a beast (built using a perl script as
a sort of macro preprocessor...)

Openbsd doesn't support true kernel threads, and perl there is not
linked using threads.  Without threads, perl is surprisingly efficient,
so my not particularly clever perl code ran well enough I didn't bother
to investigate improving it.  It doesn't run nearly so well under
solaris.  As best I could determine, that's because when linked with
threads, perl made a *lot* of pthread locking calls, which was silly
because there was only ever one thread running.  Of course, with perl,
if performance were an issue it's easy enough to make perl modules with
C code...

However, with java, writing C code is sort of pointless.  The whole
point of Java is that it's machine agnostic, but you only get that if
you write in pure Java.  Kaffe on openbsd is apparently not
particularly efficient, and there seems to be something particularly
bad about the SHS logic.  I was able to improve execution time by about
1% in speed, by being more clever about reusing MessageDigest
instances.  The same improvments made stuff run about 4 times faster on
Solaris (my original slightly less clever Java code took 980 seconds on
sparc -- that works out to maybe 49 seconds per password!)

So what did I learn?  Pkcs5 performance is extremely dependent on
optimal tuning of the execution environment.  It is easy to obtain
suboptimal execution timing.  Suboptimal results, especially in other
languages, will probably lead to unacceptable performance, which means
it's likely only optimized C or equivalent native compiled code
(running on a fast and otherwise idle machine) will be useful for the
proposed iteration count of 45056 with AES in kerberos 5.

I would be quite interested to hear of anybody who is able to get
faster results from either perl or java -- send me diffs if you think I
botched it and didn't get fair timing results.  I would also be
interested in what range of results people get with other software or
hardware.  I had circulated a copy of the C code privately earlier, but
I could package that up as well for more general circulation if there
is interest.

Considering the current MicroSoft push towards using C#, it surprises
me to hear MicroSoft pushing algorithms that may not work well with
hardware agnostic interpreters such as C#.  Here at the University of
Michigan, there are definitely plenty of environments where even 1
second of CPU is going to make AES a very hard thing to sell, so would
prolong the existance of DES and 3DES longer than we would like (there
are of course plenty of other issues here as well...)

				-Marcus Watts
				UM ITCS Umich Systems Group
[
More detail on the hardware and software I used:
== obsd3.2 thinkpad a31p, 1.7Ghz
	Host is:
		Intel Pentium 4 ("GenuineIntel" 686-class) 1.70 GHz
		OpenBSD plush-rabbit 3.2 PLUSH-RABBIT#1 i386
	C test program compiled using;
		egcc -O2 -mcpu=pentium4
		egcc (GCC) 3.1
	K5 libraries compiled using:
		gcc -g -O2
		2.95.3
	perl is
		This is perl, v5.6.1 built for i386-openbsd
	Perl packages include:
		Digest::SHA1 2.01
		which includes its own sha code (run through the C compiler.)
	java (jvm and runtime libraries) is
		Kaffe Virtual Machine
		Engine: Just-in-time v3   Version: 1.0.6   Java Version: 1.1
		(Also includes built-in sha-1, I *think* written in C.)
	java test code was compiled using:
		jikes
		Version 1.15 - 26 Sept 2001
		( The "javac" (really kjc I think) that came
		with kaffe 1.0.6 wasn't capable of building a
		working Rijndael.class . )

== sol2.6 sun ultra 5, 270Mhz
	On Sun Ultra-5 workstation; Solaris 2.6; 270 Mhz cpu
	compiled with gcc
		2.7.2
	K5 libraries using same version of gcc,
		-mv8
	perl is
		This is perl, v5.6.0 built for sun4-solaris-thread
	Perl packages include:
		Digest::SHA1 1.02
	The java distributed with 2.6 was used:
		java version "1.1.3"
	(I also tried the jikes output, which in this case
		was very slightly slower.)
]