Stream ciphers

[ciphergoth]

I recently discovered Helger Lipmaa's excellent page on stream ciphers:

http://www.tcs.hut.fi/~helger/crypto/link/stream/index.html

and sent Helger an email correcting a small error (though I hadn't noticed the reference to "Paul McCrowley" until later!). His reply asked what stream cipher I had most confidence in. Here's what I said:

Interesting question!

If I was specifying a new application now, and encryption needed to be faster than any block cipher could manage, I would if I could use RC4 after discarding 1024 bytes of output. There are efficient distinguishers for RC4, but it has probably seen more cryptanalysis than all the other CPRNGs put together, and it's hard to think of circumstances where the RC4 distinguishers lead to a useful attack.

More modern designs are still faster and have clearer design principles. An attack on the PANAMA hash function was of course presented at FSE 2001, but I know of no attacks on the PANAMA stream cipher. If I felt that my requirements called either for strict non-distinguishability or greater speed, I think that PANAMA would be my next choice.

But overall there seems to be much more stream cipher cryptography than cryptanalysis, and we don't seem to have design principles to guide the design of stream ciphers as we do for block ciphers. One problem seems to be that stream ciphers have many fewer rounds (if they have the concept of rounds at all), so attacking reduced-round variants doesn't tell you very much. But it's this very property that makes them so fast... it would be very useful to have a stream cipher with more scalable security, so we can learn more about the limits of where cryptanalysis stops working.

I'm sort of hoping that the standardisation on AES reduces the "market" for new block ciphers, and so attention at FSE and suchlike turns to the design of other symmetric primitives, like stream ciphers and hash functions. Mainly because the stream cipher I really want doesn't exist yet.

Thanks for asking!

Comments

[ciphergoth.livejournal.com]

This is right. There are cryptosystems on the market (eg "UBE98") that make this beginners mistake; all files are encrypted with exactly the same RC4 key, so you can gain information about them in exactly the way you describe.

The solution is to send a "nonce" (sometimes called an "initialisation vector" or "IV") in the clear along with each message, and use the nonce to vary the encryption; so long as you never use the same nonce twice, the scheme is secure. Some stream ciphers (eg LEVIATHAN, SEAL) are explicitly designed to take a nonce as a parameter when performing encryption.

For RC4, it was common practice to simply concatenate the secret key and the nonce to make the RC4 key. This is how WEP encryption works in 802.11 wireless Ethernet cards, and it was this aspect of WEP that Fluhrer, Mantin and Shamir attacked in their famous paper wholly destroying the security of that scheme with RC4. It's now recommended to use a secure hash function to generate the RC4 key from the key and nonce, thus:

ciphertext = nonce | RC4(SHA(key | nonce)) XOR plaintext

where "|" represents concatenation and SHA is the Secure Hash Algorithm.

Incidentally, a nonce is required for security even with schemes that don't have this (A+X) - (B+X) = A-B property, such as using a block cipher in CBC or CFB mode. It's considered a flaw in a stream cipher if there's a way of deducing that the same plaintext has been encrypted twice, so there has to be a way of getting different ciphertexts from the same plaintext.

Incidentally incidentally, most modern interest is in block ciphers still. Stream ciphers of any kind still get far too little study.

Incidentally^3, RC4 is the simplest decent cipher in the world. If you're curious about the guts of how cryptosystems work, I recommend looking at how RC4 works, it's very neat.