Shamir (The S of RSA) once predicted that the use of Stream Ciphers, like RC4, would inevitably decline over time. Stream Ciphers, while less secure than block ciphers, are faster and simpler to implement than block ciphers. However, with the increasing processing power of computers and the increasing understanding and adoption of Block Ciphers, Stream Ciphers are fast on the decline. Additionally, the weaknesses of Stream Ciphers like RC4 have also left administrators rushing to replace it with Block Ciphers.
1. Implications of Bar Mitzvah
Recently a new discovered attack on an RC4 implementation of TLS, dubbed Bar Mitzvah, may be the final nail in the coffin for RC4 and also for TLS versions 1.0 and 1.1. Whilst the RC4 weaknesses exploited in this attack were first published two years ago, a practical attack wasn’t feasible until a security researcher, Itsik Mantin from Imperva, discovered Bar Mitzvah.
2. RC4 basics
The RC4 algorithm is a Stream cipher that encrypts each plaintext value with a pseudorandom string of bits, known as the keystream. To generate the keystream, a secret key is combined with an initial array of values to form a permuted state, which then goes through more permutation before it is XOR’ed with the plaintext to create the ciphertext. To increase the randomness of the first permuted state, the combination of the key and initial value is done one character at a time and the result is used in the combination of the next value and so on. As the length of the initial array is fixed (e.g. at 256 bytes) and the key length is variable (e.g. may only be 128 bytes), the key is repeated to make up the bytes of the array.
3. RC4 weaknesses
The RC4 algorithm has a few known weaknesses. Due to the way RC4 is initialised, there are single byte biases found in first few bytes of the keystream where the probability of a certain value occurring is statistically higher than average. Another problem is the invariance weakness, which is a key pattern that appears when using weak RC4 keys. This makes its possible to detect specific patterns in the cipher when weak keys are used (e.g. the Least Significant Byte of weak 16 byte keys have statistical biases e.g. even number/multiple of four have a higher probability of occurring etc.)
4. RC4 attacks
RC4 weaknesses have been used to break encryption before. WEP (Wired Equivalent Privacy) used small-sized fixed length (40 bit) keys that were shared across internal networks and never changed. Additionally it also concatenated a small-sized (24 bit) Initialisation Vector (IV) before the key. This made WEP a prime candidate for brute force attacks and a reason why the new Wireless standards enforce the use of AES block ciphers.
5. Bar Mitzvah
For more information