[Cryptography] RC4 again (actual security, scalability and other discussion)

[Miroslav Kratochvil]

Hello everyone,

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.

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.

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

General statement: There's no effective known attack against reasonable RC4
usage that doesn't use related IVs and discards first 1024 outputs.

All attacks I've been able to find that somehow break traditional RC4 are:

- WEP-like related-key attacks [google rc4 wep]
- newer statistical attacks against random distribution of outputs in first
bytes (for example [1] looks good)
- quite similar attacks against special usage, see [2]
- malleability (which shall not be discussed here as the simple solution
depends only on the strength of hash functions)

Claim: These attacks don't apply if you
- have good IV choices (read more below)
- discard enough of the keystream
- are reasonable and don't output gigatons of your keystreams all around

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.

"Good IV choices" are a bit harder to create. I use RC4 for two main
purposes:

- CCA2 padding for QD-McEliece usually called Fujisaki-Okamoto padding, the
IV there is completely random for each usage.

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

Questions:

- are there any other known attack types that I missed?

- Is running KSA algorithm for "squeezing more data in" reasonable? Clearly
not fo "added security", but possibly for
  * IV scheduling usage, as above
  * big keys from weird key sources (without relying on a hash function to
scale the key data down)
  * other weird RC4 usage (RC4-based hash function etc.)

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


Thanks for opinions on all this,
-mk


Refs.:
[1] http://www.isg.rhul.ac.uk/tls/biases.pdf
[2]
http://home.hiroshima-u.ac.jp/ohigashi/rc4/Full_Plaintext_Recovery%20Attack_on%20Broadcast_RC4_pre-proceedings.pdf
[3] http://eprint.iacr.org/2013/176.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140308/4204d7ef/attachment.html>