RC4 Weak Key checks

[Jeffrey Altman]

On 3/24/2011 12:44 PM, Greg Hudson wrote:
> 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. 

The code in MIT Kerberos was written by David Cross <crossd at cs.rpi.edu>.

The implementation for Heimdal which does not contain RC4 weak key
checks was written by Luke Howard.

I can find no evidence that Microsoft Kerberos SSP performs weak key
checks.  Perhaps the consortium can obtain an explicit answer from
Microsoft.

> I wasn't able to find any discussion of RC4 weak keys on
> the lists, although I could easily have missed it.

I have found no discussions on either krbdev or the ietf working group
mailing list.  The Informational RFC was published as an individual
submission.  As far as I can tell there was no comparison of the RFC
submission with the MIT implementation prior to publication.  There
certainly was no discussion on the kerberos wg list.

> * The weak key checks are probably based on
> http://impic.org/papers/WeakKeys-report.pdf appendix A.

Sure.  The keys match.

> * 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.

My reading of the security considerations section of 4757 is that a new
key is generated for each message transmitted using the gss context in
order to address the key weakness.  However, the statements are far from
explicit.

> 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.

The way the code exists today RC4-HMAC is not a usable enc-type in
combination with GSS when one side of the connection is MIT.
Recommending that RC4-HMAC not be used is not practical in an AD centric
environment.

Jeffrey Altman
Secure Endpoints, Inc.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: OpenPGP digital signature
Url : http://mailman.mit.edu/pipermail/krbdev/attachments/20110325/ae0ad70d/attachment.bin