RC4 Weak Key checks

Greg Hudson ghudson at MIT.EDU
Thu Mar 24 12:44:20 EDT 2011

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.

More information about the krbdev mailing list