Subject: Re: WG Last Call: Clarifications and AES - End of Last Call

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

"Steven M. Bellovin" <[email-masked]> writes:
> Default iteration count for what?  AES itself?

For PBKDF2 (from PKCS5), used for generating AES keys from pass
phrases.  (In the current Kerberos crypto framework, key generation
from pass phrases is part of the cryptosystem specification.)

The protocol can specify the iteration count, but there's also a
default specified in the draft.  The current default value was chosen
based on some timing tests I had done and a recommendation from John
Brezak of Microsoft, to aim for a 1 second delay on a 300MHz Pentium
II system, and I forget which key size, probably 128 bits.  Rounding
off (in binary representation), I came up with 45056 (0xb000)
iterations.

More recently, Marcus Watts and I have done some timing tests on
various versions and platforms, and it looks like the value I had
arrived at may produce a delay of several seconds on some types of
systems currently in use (yesterday's good machines, not today's
high-end machines), at least without specially tuned assembler SHA1
implementations.  That's for legitimate user ticket acquisition; as
Marcus points out, greater parallelism may be available to an attacker
trying a brute-force approach.  Legitimate users are, I suspect, more
likely to get stuck with whatever machine is at hand, compared with an
attacker logging in remotely to multiple machines to get the best
available CPU power.

So, I was suggesting we consider changing the default from 45056 to
something lower, perhaps 4096, and let paranoid sites specify higher
values and suffer with the longer delays.  Unfortunately, I only got
the suggestion submitted last night, and there hasn't been time to get
any responses; I'm particularly interested in getting feedback from
the current participants from Microsoft....

Ken

---

From: Jeffrey Altman <[email-masked]>
Date: Thu, 10 Apr 2003 09:08:42 -0400

Ken:

Any clue what the delay would be on a somewhat smaller device such as 
the Intel PXA250 200MHz? (HP iPaq/Sharp Zaurus) Or TI OMAP 1510 (Palm 
Tungsten)?
We certainly want this class of devices to be secure.  Granted that 
hardware gets faster every year. 

Perhaps what we need is to write a default value that is relative to the 
amount of CPU power that may be purchased at a certain price point. 

- Jeff

---

From: Ken Raeburn <[email-masked]>
Date: Thu, 10 Apr 2003 17:36:31 -0400

> the Intel PXA250 200MHz? (HP iPaq/Sharp Zaurus) Or TI OMAP 1510 (Palm

Not for those devices.  You might be able to estimate for the PXA250
by scaling the numbers Marcus and I came up with for the change in CPU
speed, but other factors like memory speed and cache size may affect
it as well.  Does the Tungsten use a 68k or ARM processor?

My Handspring Visor Platinum (33MHz? 68k family chip) will do 20000
invocations of a sha-1 hash of a 78-byte string in about 46s.  (That
happens to be the test program I had lying around.)  That's about
2.3ms per invocation.

For N iterations in PBKDF2 with SHA-1, if I recall correctly, we need
N invocations of HMAC, or 2N invocations of SHA-1, to get up to 160
bits, and 4N invocations of SHA-1 to get 320 bits.  For 45056
iterations and a 256-bit key, that's 180224 invocations of SHA-1,
mostly on the pass phrase plus a previous hash.  Calling that about 32
bytes, and assuming that running SHA-1 on it will take about 1/2 as
long as indicated above (since SHA-1 operates on input in 64-byte
blocks), or 1.15ms per invocation, for 180224 invocations we're
looking at about 207s -- over 3 minutes.

And 4096 iterations in PBKDF2 would mean 16384 invocations of SHA-1,
or about 19s.

These are estimates, of course; if anyone cares, I can try to put
together a PBKDF2 test program using the same inputs as I used on the
UNIX platforms.

As John has pointed out, it would be possible to precompute the key,
and store a version encrypted or even just xor'ed with a key derived
from the same pass phrase but with a much smaller iteration count.
(Or a different pass phrase.  Or a different key generation algorithm.
Lots of variations on the basic idea.)

The work of an attacker could be reduced if they got their hands on
the device, assuming it didn't use tamper-resistant storage, but the
legitimate user of the device would not suffer the excessive delays.

> hardware gets faster every year. Perhaps what we need is to write a
> default value that is relative to the amount of CPU power that may be
> purchased at a certain price point. - Jeff

For what class of machine, handheld or workstation?  The latter would
get more CPU power for the dollar.  In the former, the money goes into
miniaturization, integration with cell phones or bar code scanners or
whatever, power conservation technology, etc.  And at what point in
time?  I've got machines several years old that I use daily.

Ken

---

From: Jeffrey Altman <[email-masked]>
Date: Thu, 10 Apr 2003 18:39:22 -0400

>it as well.  Does the Tungsten use a 68k or ARM processor?

The Tungsten uses an ARM.

>together a PBKDF2 test program using the same inputs as I used on the
15 seconds might be an acceptable delay on a palm-top.  3 minutes would 
get application developers fired.  :(

>legitimate user of the device would not suffer the excessive delays.
Of course, but unless we outline how to do this securely I doubt many 
developers will do it right.  I am assuming the crypto and kerberos 
libraries and the applications are being developed by different groups 
with different skill sets.

>time?  I've got machines several years old that I use daily.
It is exactly this range of capabilities that makes the choice 
difficult.  It is also the reason why we most likely do not want to 
choose a fixed number.  We hope that we will not have to alter the 
KCRYPTO AES RFC once it is published.  If we are lucky AES will survive 
ten years.  Therefore, we should give some indication of a good value to 
use.

The question is which number is more important:

    * the maximum amount of time a low-end desktop/laptop or high-end
      palmtop should take to compute the value, OR
    * the minimum amount of time a high-end desktop/laptop/workstation

????

- Jeff

---

From: Marcus Watts <[email-masked]>
Date: Thu, 10 Apr 2003 19:56:26 -0400

>     * the minimum amount of time a high-end desktop/laptop/workstation

I don't think that's quite the way I would phrase it.

Here are 5 possible increments to consider:

[1] the minimal iteration count, if any, that client software might
	want when doing some forms of preauth with mallet's kdc.
[2] the minimal hardware that a real user might use, and the max time
	they are willing to wait.
[3] the default iteration count
[4] the maximal hardware that a real user might use, and how
	fast things can be for him.
[5] the best hardware that mallet can buy, borrow, or steal, and how
	quickly it can guess keys.

Of these, I don't think 4 is nearly as interesting as 5.

Since, with 5, mallet is allowed to use parallel sha-1 and RISC machine
registers, whereas bob in 2 may be lucky to be using C instead of Java,
there's a big difference in performance here.  Passwords probably
aren't even distributed even within a 40 bit key space, a further
convenience for mallet.

2 defines the minimal platform below which people invent horrible
kludges or decide to stick with DES or RC4.  The recent suggestion to
store an intermediate key sounds pretty horrible for instance -- why
not just store a keytab on your PDA?

1 and 3 define what mallet has to break.  3 defines what he gets with a
passive snoop; 1 defines what he can get with an active attack.

I think it's pretty clear microsoft is mainly interested in dedicated
workstations with recent hardware and optimized software.  4 above
mainly guarantees these users won't be too annoyed.  I think though
that we should also be considering less otimized software, such as pure
C (like current MIT distributions), and hardware that is not as recent
or that can necessarily dedicated to one person.  It would also be nice
to think that security did not depend on the use of C+assembler instead
of Java or Perl.

The whole idea of expensive password computation is based on 1970's
assumptions: that computers cost at least $20K, networks are most often
based on dialup modems, and both resources are scarce enough that some
system administrator will quickly notice people running "crack".  I
don't think any of these assumptions are true anymore.  We already have
people running SETI as a screen saver; if vandals haven't already
deployed a virus that runs a distributed "crack" it's surely only a
question of time.  Even hardware accelleration isn't out of the
question for mallet.  Unfortunately the flip side is that biology
hasn't kept pace: people still aren't as willing to wait >1s, and can't
easily remember passwords >40bits of entropy.  I think the result is we
don't have an intersection between the two that is "acceptable"
security anymore.  This can't be solved by increasing computational
complexity; real security pretty much requires using preath and
additional secrets.

					-Marcus Watts
					UM ITCS Umich Systems Group

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 15 Apr 2003 12:29:26 +0200

> the Intel PXA250 200MHz? (HP iPaq/Sharp Zaurus) Or TI OMAP 1510 (Palm

I'm not Ken, but FWIW, Shishi running on iPAQ H3600 (SA-1110 v4l
206MHz) needs slightly over 20 seconds to perform a normal kerberos
logon with 256 bit AES keys using the default iteration count.