Subject: RE: AES and SHA-1 timing

From: "Paul Leach" <[email-masked]>
Date: Fri, 11 Apr 2003 14:11:53 -0700

Even though 256 bits is mandatory to implement, 128 bits is quite adequate
to deploy in practice. Doesn't that mean that all these numbers should be
halved?

If so, and if I read the rest of these numbers correctly, then worst case
a person, running on a MIPS R5000 200mhz, would add 4.3 seconds to their
logon time.

Given all the other stuff that probably happens at logon time, I don't see
that as terrible.

>
> -----Original Message-----
> From: Ken Raeburn [mailto:[email-masked]]
> Sent: Wednesday, April 09, 2003 2:47 AM
> To: [email-masked]
>
>
> 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
>
>
>
>

---

From: Ken Raeburn <[email-masked]>
Date: Sat, 12 Apr 2003 19:35:27 -0400

> to deploy in practice. Doesn't that mean that all these numbers should be

We could have different defaults for the two versions.

> Given all the other stuff that probably happens at logon time, I don't see

Actually, I think "all the other stuff that probably happens at logon
time" is getting to be pretty terrible already, on some systems.  I
typed my correct password; I want to start working *now*.  (Or, for
those more resigned to slow logins, I want to get some confirmation so
I can go make my coffee now.)

At least in most of the UNIX login GUIs I've seen, this would be 4.3s
(or 8.6s, whatever) where the window appears frozen, because the
single-threaded process is entirely devoted to SHA-1 calculations.
The "other stuff" tends to happen in other processes, after some
indication has been given that the login sequence is actually
progressing.

While I don't object to a small delay if it makes the Microsoft
security folks happy (and really, it's mainly MS that's been in favor
of this), I think Marcus has much more compelling arguments concerning
the larger delays.

Ken

---

From: Michael Thomas <[email-masked]>
Date: Sat, 12 Apr 2003 19:19:34 -0700 (PDT)

Ken,

I haven't been paying very close attention to this
thread so forgive me, but I am mystified as to how
Kerberos crypto operations could possibly take 8
or even 4 seconds on any vaguely modern processor
these days due to SHA1, AES or even DH/RSA for
that matter. The timings that I've seen have SHA1
and AES at 25MB/sec and 11MB/sec respectively on a
PIII Celeron @~400 Mhz. The hundreds of bytes in
tickets/authenticators should be *way* down in the
noise.

Have I missed something dreadfully pertinent in
this thread?

	Mike

---

From: Marcus Watts <[email-masked]>
Date: Sat, 12 Apr 2003 23:26:59 -0400

To: Michael Thomas <[email-masked]>
> Have I missed something dreadfully pertinent in

I'm not Ken, but I think you missed the iteration count.  The suggested
iteration count of 45056 was deliberately selected to be about 1 second
on one particular platform.

You may be quoting speeds for SHA1 and AES for bulk hashing/encryption,
perhaps using openssl "speed".  Speeds for smaller block sizes go down
because start & end overhead becomes more important.  For openssl on a
pentium 3, I meausre a factor of 13 difference in per-byte speed
between 16 and 8192 byte blocks.  In addition, hmac does an extra hash
on the result, so for small block sizes is only half as fast as a
straight digest.  So, in theory, if you got 25 MB/sec using 8192 byte
blocks, for hmac(sha1) on 16 bytes, you should see about 1 Mb/s
throughpout (approximately 62500/second).  An iteration count of 45056
ought to give you a delay of at least 720 milliseconds for your
hardware, perhaps more with longer passwords, salt, or key.

If you're ambitious, you could verify this yourself; the latest
snapshot of heimdal includes most of the necessary code, and links
against openssl which will give you better performance than with with
the pure C sha-1 implementation in MIT (but with the pentium 3 the
difference is less marked.)

				-Marcus Watts
				UM ITCS Umich Systems Group

---

From: Sam Hartman <[email-masked]>
Date: Mon, 14 Apr 2003 14:57:52 -0400

>>>>> "Paul" == Paul Leach <[email-masked]> writes:

    Paul> Even though 256 bits is mandatory to implement, 128 bits is
    Paul> quite adequate to deploy in practice. Doesn't that mean that
    Paul> all these numbers should be halved?

No, because you cannot guarantee that the client will support the
enctype.