Block Ciphers and Stream Ciphers

Question

I understand that block ciphers are more popular in software as opposed to stream ciphers which are typically hardware based. However, why can't a key be reused in stream ciphers? Is it because of patterns that may form?

Solution

A stream cipher is an encryption system which works over a given sequence of input bits. Most stream ciphers work by generating from the key a long sequence of random-looking bits, which are then combined (by bitwise XOR) with the data to encrypt. This is a (crude) emulation of one-time pad.

A block cipher is a generic cryptographic element which works over "blocks" which are sequences of bits with a fixed length (e.g. 128 bits for AES). The block cipher is a permutation of the blocks; the key selects which permutation we are talking about. A block cipher alone cannot process an arbitrary long message; the block cipher and the data must be used within an elaborate construction called a mode of operation (also often called a "chaining mode").

There is a chaining mode for block ciphers called "CTR" as "counter mode": in this mode, the block cipher is used to encrypt successive values of a counter (the counter having the size of a block). The resulting encrypted blocks are then concatenated, resulting in an arbitrarily long sequence of bits which depend only on the key. It suffices then to XOR that sequence with the data to encrypt. In other words, CTR mode turns a block cipher into a stream cipher. Another popular chaining mode is CBC, which does not fit the model of a stream cipher.

With stream ciphers, what must be avoided at all costs is reusing the same key-dependent sequence of bits for two distinct messages; this would yield the infamous "two-times pad" which can be broken quite easily (by exploiting redundancies in the two encrypted messages). With a block cipher in CTR mode, this translates to reusing the same counter values. This is why CTR mode requires a random Initial Value (IV) which is the counter value you begin encryption with. By choosing a new random IV, with sufficiently large blocks, you avoid with very high probability any overlap in the sequences of counter values that you use.

The concept of IV is not specific to block ciphers; some stream ciphers also use an IV (e.g. the one in the eSTREAM portfolio). When a stream cipher has an IV, reusing the key is no problem -- provided that you use proper IV (i.e. IV generated with a cryptographically strong RNG in the complete space of possible IV, with uniform probability). However, some other stream ciphers do not have an IV, in particular the widely used RC4. Reusing the same key would mean reusing the exact same sequence of generated bits, and that's bad.

Note that some chaining modes other than CTR also need an IV, which should be unique for each message encrypted with a given key. Block ciphers do not alleviate the need for that.

Comments

[Joeblackdev]

Wow, that's more than I was looking for. Thanks for such a detailed response. Best regards