Subject: aes draft changes: iteration count

From: Ken Raeburn <[email-masked]>
Date: Wed, 18 Jun 2003 18:38:25 -0400

Here are the updates I'm working on for the next submission.

 - changed the no-s2k-params-default value to 4096 as per discussions
   on the WG list

 - clarified that it's *only* the no-s2k-params value, not intended as
   a default for anything else

 - added sample calculations of an attacker's required work to process
   a dictionary given certain assumptions

 - recommended increasing the iteration count over time per Paul's
   email

 - recommended randomly generating salt strings when changing
   passwords, in combination with high iteration counts, as a defense
   against letting the attacker re-use some intermediate results to
   attack the user's new password

 - updated acknowledgements

I'll probably add something about erring on the side of caution when
guessing iteration counts for optimistic preauth (would "preemtive
preauth" be a better phrase?), but given the recommendation for
time-varying counts, and non-precise nature of the increases, I think
it would be silly to suggest any specific number.

Unless there are objections, I'll write something non-specific and
leave it for the implementors to figure out how to handle.  Let me
know soon, I'm aiming to get the revision submitted by the end of the
week.

Ken

@@ -118,10 +118,17 @@
 and it might be wise for implementations to permit interruption of
 this operation by the user if the environment allows for it.
 
-If the string-to-key parameters are not supplied, the default value to
-be used is 00 00 b0 00 (decimal 45056, indicating 45056 iterations,
-which takes slightly under 1 second on a 300MHz Pentium II in tests
-run by the author).
+If the string-to-key parameters are not supplied, the value used is 00
+00 10 00 (decimal 4096, indicating 4096 iterations).
+
+Note that this is NOT a requirement, nor even a recommendation, for
+this value to be used in "optimistic preauthentication" (e.g.,
+attempting timestamp-based preauthentication using the user's
+long-term key, without having first communicated with the KDC) in the
+absence of additional information, nor as a default value for sites to
+use for their principals' long-term keys in their Kerberos database.
+It is simply the interpretation of the absence of the string-to-key
+parameter field when the KDC has had an opportunity to provide it.
 
 Sample test vectors are given in the appendix.
 
@@ -175,7 +182,7 @@
 PBKDF2+DK with variable iteration count (see above)
 T}
 
-default string-to-key parameters        00 00 b0 00
+default string-to-key parameters        00 00 10 00
 
 T{
 key-generation seed length
@@ -283,6 +290,64 @@
 protection of the user's long-term key.  Use of such mechanisms is
 out of scope for this document.
 
+If a site does wish to use this means of protection against a
+brute-force attack, the iteration count should be chosen based on the
+facilities expected to be available to an attacker, and the amount of
+work the attacker should be required to perform to acquire the key or
+password.
+
+As an example:
+
+.in 6
+The author's tests on a 2GHz Pentium 4 system indicated that in one
+second, nearly 90000 iterations could be done, producing a 256-bit
+key.  This was using the SHA-1 assembly implementation from OpenSSL,
+and a pre-release version of the PBKDF2 code for MIT's Kerberos
+package, on a single system.  No attempt was made to do multiple
+hashes in parallel, so we assume an attacker doing so can probably do
+at least 100000 iterations per second -- rounded up to 2**17, for ease
+of calculation.  For simplicity, we also assume the final AES
+encryption step costs nothing.
+
+Paul Leach estimates [LEACH] that a password-cracking dictionary may
+have on the order of 2**21 entries, with capitalization, punctuation,
+and other variations contributing perhaps a factor of 2**11, giving a
+ballpark estimate of 2**32.
+
+Thus, for a known iteration count N and a known salt string, an
+attacker with some number of computers comparable to the author's
+would need roughly N*2**15 CPU seconds to convert the entire
+dictionary plus variations into keys.
+
+An attacker using a dozen such computers for a month would have
+roughly 2**25 CPU seconds available.  So using 2**12 (4096) iterations
+would mean an attacker with a dozen such computers dedicated to a
+brute-force attack against a single key (actually, any
+password-derived keys sharing the same salt and iteration count) would
+process all the variations of the dictionary entries in four months,
+and on average, would likely find the user's password in two months.
+
+Thus, if this form of attack is of concern, an iteration count a few
+orders of magnitude higher should be chosen, and users should be
+required to change their passwords every few months.  Perhaps several
+orders of magnitude, since many users will tend to use the shorter and
+simpler passwords (as much as they can get away with, given a site's
+password quality checks) that the attacker would likely try first.
+
+Since this estimate is based on currently available CPU power, the
+iteration counts used for this mode of defense should be increased
+over time, at perhaps 40%-60% each year or so.
+
+Note that if the attacker has a large amount of storage available,
+intermediate results could be cached, saving a lot of work for the
+next attack with the same salt and a greater number of iterations than
+had been run at the point where the intermediate results were saved.
+Thus, it would be wise to generate a new random salt string when
+passwords are changed.  The default salt string, derived from the
+principal name, only protects against the use of one dictionary of
+keys against multiple users.
+
+.in 3
 If the PBKDF2 iteration count can be spoofed by an intruder on the
 network, and the limit on the accepted iteration count is very high,
 the intruder may be able to introduce a form of denial of service
@@ -311,8 +376,9 @@
 .ne 4
 .Se acks "Acknowledgements"
 
-Thanks to John Brezak, Gerardo Diaz Cuellar and Marcus Watts for
-feedback on earlier versions of this document.
+Thanks to John Brezak, Gerardo Diaz Cuellar, Ken Hornstein, Paul
+Leach, Marcus Watts and others for feedback on earlier versions of
+this document.
 
 .ne 4
 .Ap testvec "Sample test vectors"
@@ -523,6 +589,9 @@
 
 .Us "Informative References"
 
+[LEACH] Leach, P., email to IETF Kerberos working group mailing list,
+5 May 2003, ftp://ftp.ietf.org/ietf-mail-archive/krb-wg/2003-05.mail.
+
 [PECMS] Gutmann, P., "Password-based Encryption for CMS", RFC 3211,
 December 2001.

---

From: Ken Raeburn <[email-masked]>
Date: Fri, 20 Jun 2003 17:30:06 -0400

Okay, here are the additional updates going into the -05 draft I've
just sent in.  Copy available at
http://www.mit.edu/~raeburn/draft-raeburn-krb-rijndael-krb-05.txt
also.

Ken

--- aes.ms	2003/06/18 22:51:43	1.9
+++ aes.ms	2003/06/20 21:21:23
@@ -8,7 +8,7 @@
 expand;
 l r .
 Kerberos Working Group  K. Raeburn
-Document: draft-raeburn-krb-rijndael-krb-04.txt MIT
+Document: draft-raeburn-krb-rijndael-krb-05.txt MIT
         \*(tS
         expires \*(eS
 .TE
@@ -355,10 +355,33 @@
 causing the client to spend a great deal of CPU time computing an
 incorrect key.
 
+An intruder spoofing the KDC reply, providing a low iteration count,
+and reading the client's reply from the network may be able to reduce
+the work needed in the brute-force attack outlined above.  Thus,
+implementations may wish to enforce lower bounds on the number of
+iterations that will be used.
+
+Since threat models and typical end-user equipment will vary widely
+from site to site, allowing site-specific configuration of such bounds
+is recommended.
+
 Any benefit against other attacks specific to the HMAC or SHA-1
 algorithms is probably achieved with a fairly small number of
 iterations.
 
+.Sn keyrep
+In the "optimistic preauthentication" case mentioned in section \*S,
+the client may attempt to produce a key without first communicating
+with the KDC.  If the client has no additional information, it can
+only guess as to the iteration count to be used.  Even such heuristics
+as "iteration count X was used to acquire tickets for the same
+principal only N hours ago" can be wrong.  Given the recommendation
+above for increasing the iteration counts used over time, it is
+impossible to recommend any specific default value for this case;
+allowing site-local configuration is recommended.  (If the lower and
+upper bound checks described above are implemented, the default count
+for optimistic preauthentication should be between those bounds.)
+
 Cipher text stealing mode, since it requires no additional padding in
 most cases, will reveal the exact length of each message being
 encrypted, rather than merely bounding it to a small range of possible