<div dir="ltr"><div><div><div><br>Hello everyone,<br><br></div>I'm not sure that entering this discussion with questions about RC4 (or Arcfour or how you like it) is generally a good idea, but well, why not.<br><br></div>
I've used RC4 quite extensively in one of my projects, for it is a "best fit" - wonderfully simple, and secure if used correctly. Since that, I have been experiencing reluctant comments from all sides of users, cryptographers, programmers and so, all of which had the common "RC4 is broken, is it not?" part. This opinion is generally supported by all "first-google" sources that can be found about RC4, led by wikipedia that has sources that "argue against its use in new systems". That's quite FUD.<br>
<br></div><div>From all sources I have ever seen I can say that RC4 itself is not broken. I'm usually proving and explaining that fact to everyone quite successfully, but it's always better if you ask someone else about his opinion. That is, as you can now probably see, roughly the whole purpose of this post. If you find any errors in following statements, please report them.<br>
<br></div><div>General statement: There's no effective known attack against reasonable RC4 usage that doesn't use related IVs and discards first 1024 outputs.<br><br></div><div>All attacks I've been able to find that somehow break traditional RC4 are:<br>
<br></div><div>- WEP-like related-key attacks [google rc4 wep]<br></div><div>- newer statistical attacks against random distribution of outputs in first bytes (for example [1] looks good)<br></div><div>- quite similar attacks against special usage, see [2]<br>
</div><div>- malleability (which shall not be discussed here as the simple solution depends only on the strength of hash functions)<br></div><div><br></div><div>Claim: These attacks don't apply if you<br></div><div>- have good IV choices (read more below)<br>
</div><div>- discard enough of the keystream<br></div><div>- are reasonable and don't output gigatons of your keystreams all around<br></div><div><br></div><div>The "enough" of discarded keystream is usually determined from the amount of keystream needed for the distinguisher (similarly as in [3]), 1024 is more than enough for most real purposes.<br>
<br></div><div>"Good IV choices" are a bit harder to create. I use RC4 for two main purposes:<br><br></div><div>- CCA2 padding for QD-McEliece usually called Fujisaki-Okamoto padding, the IV there is completely random for each usage.<br>
<br></div><div>- as a traditional cipher for generating keystreams for i=1,2,3.... and some common shared key. Best approach I've seen so far is to run the RC4's KSA twice: First time with the shared key, and then with the (somehow padded) nonce.<br>
<br></div><div>Questions:<br><br></div><div>- are there any other known attack types that I missed?<br></div><div><br></div><div>- Is running KSA algorithm for "squeezing more data in" reasonable? Clearly not fo "added security", but possibly for<br>
</div><div>  * IV scheduling usage, as above<br></div><div>  * big keys from weird key sources (without relying on a hash function to scale the key data down)<br></div><div>  * other weird RC4 usage (RC4-based hash function etc.)<br>
<br></div><div>- Sci-Fi: Modern CPUs are big and have lots of cache. Is there any material that deals with RC4 that would use 16-bit internal permutation? (65536 16-bit numbers of internal state, key input/output on 16bit words, everything else the same. Because of large memory requirement (128kB) and relatively slow initialization phase I guess that it could be a nice candidate for, say, password crypt()-ing or ASIC-resistant stuff; OTOH, because byte operations are usually equally fast as 2-byte word operations on modern CPUs, this could (very theoretically) just increase keystream generation speed twice).<br>
</div><div><br><br></div><div>Thanks for opinions on all this,<br></div><div>-mk<br></div><div><br><br>Refs.:<br>[1] <a href="http://www.isg.rhul.ac.uk/tls/biases.pdf">http://www.isg.rhul.ac.uk/tls/biases.pdf</a><br>[2] <a href="http://home.hiroshima-u.ac.jp/ohigashi/rc4/Full_Plaintext_Recovery%20Attack_on%20Broadcast_RC4_pre-proceedings.pdf">http://home.hiroshima-u.ac.jp/ohigashi/rc4/Full_Plaintext_Recovery%20Attack_on%20Broadcast_RC4_pre-proceedings.pdf</a><br>
[3] <a href="http://eprint.iacr.org/2013/176.pdf">http://eprint.iacr.org/2013/176.pdf</a><br></div></div>