[16725] in Kerberos_V5_Development
Re: RC4 Weak Key checks
daemon@ATHENA.MIT.EDU (Greg Hudson)
Thu Mar 24 12:44:26 2011
From: Greg Hudson <ghudson@mit.edu>
To: "jaltman@secure-endpoints.com" <jaltman@secure-endpoints.com>
In-Reply-To: <4D8B5641.3020103@secure-endpoints.com>
Date: Thu, 24 Mar 2011 12:44:20 -0400
Message-ID: <1300985060.10465.28.camel@t410>
Mime-Version: 1.0
Cc: "'krbdev@mit.edu'" <krbdev@mit.edu>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: krbdev-bounces@mit.edu
I want to hear from Sam and/or Ken before making a decision, but here's
what I can tell from a bit of research:
* Weak key checks have been in our code since it appeared in our tree in
October 2001. The code was committed by Sam but was probably written by
someone else. I wasn't able to find any discussion of RC4 weak keys on
the lists, although I could easily have missed it.
* The weak key checks are probably based on
http://impic.org/papers/WeakKeys-report.pdf appendix A.
* The attack based on these weak keys reduces the search space by 11
bytes, and requires about 2^26 messages with known plaintexts to succeed
with 50% probability.
* The use of confounders in rc4-hmac appears to foil this attack,
although I can't say that with high confidence.
If the attack is not foiled by confounders, it's pretty bad for
rc4-hmac-exp (you get a 2^53 work factor to recover a key after scanning
about 61 million messages with known plaintexts) but isn't very
interesting for rc4-hmac; 2^117 is still a very high work factor for an
attack on a legacy enctype.
I agree that simply erroring out on weak keys without any standards
support for avoiding them is not a great solution, especially when one
in 2^24 keys is weak.
_______________________________________________
krbdev mailing list krbdev@mit.edu
https://mailman.mit.edu/mailman/listinfo/krbdev
