Stream cipher attacks

Stream ciphers are vulnerable to attack if the same key is used more than once (a depth of two or greater).

Suppose messages A and B of the same length are both encrypted using the same key, K. The stream cipher produces a string of bits C(K) of the same length as the messages. The encrypted versions of the messages are:

E(A) = A xor C

E(B) = B xor C

where xor is performed bit by bit.

If an adversary intercepts E(A) and E(B), they can compute:

E(A) xor E(B)

Because xor is commutative and has the property that X xor X = 0 (self-inverse):

E(A) xor E(B) = (A xor C) xor (B xor C) = A xor B xor C xor C = A xor B

If one message is longer than the other, the adversary can truncate the longer message to the size of the shorter one, revealing only that portion. In other words, if two messages are encrypted with the same key, an attacker can recover A xor B, which is a form of running key cipher. Even if neither message is known, as long as both are in a natural language, such a cipher can often be broken by hand methods. During World War II, British cryptanalyst John Tiltman accomplished this with the Lorenz cipher (dubbed "Tunny"). With an average personal computer, such ciphers can usually be broken in minutes. If one message is known, the solution is trivial.

Another situation where recovery is trivial is when traffic-flow security measures require each station to send a continuous stream of cipher bits, with null characters (e.g. LTRS in Baudot) transmitted when there is no real traffic. This is common in military communications. In that case, if the transmission channel is not fully loaded, there is a high likelihood that one of the ciphertext streams will consist only of nulls. The NSA has taken extensive measures to prevent keys from being reused. In the 1960s, encryption systems often included a punched card reader for loading keys. The mechanism would automatically cut the card in half when it was removed, preventing reuse.

One way to avoid this problem is to use an initialization vector (IV), sent in the clear, that is combined with a secret master key to create a one-time key for the stream cipher. This is done in several systems that use the popular stream cipher RC4, including Wired Equivalent Privacy (WEP), Wi-Fi Protected Access (WPA), and Ciphersaber. One of the problems with WEP was that its IV was too short (24 bits). This meant there was a high likelihood that the same IV would be reused if more than a few thousand packets were sent with the same master key (see birthday attack), subjecting those packets to the key reuse attack. This problem was addressed in WPA by changing the "master" key frequently.