Posted by Virus Bulletin on Jul 20, 2015
No good reason to continue using the stream cipher, yet attacks remain impractical.
Researchers from the KU Leuven have presented a new attack against the RC4 stream cipher called 'NOMORE', which is short for Numerous Occurrence MOnitoring & Recovery Exploit. While it is really good research, and while it re-emphasises the point that the cipher should be avoided wherever possible, the attack against HTTPS is of little to no practical use.
Bruce Schneier has called RC4 a 'too-good-to-be-true' cipher: the algorithm is very short — it can be implemented in fewer than 200 characters of code — and easy to implement, especially in software. It is still widely used in HTTPS and is extremely common in protocols used by botnets to communicate with their command and control servers.
In the algorithm, a key is turned into a keystream of seemingly random bytes. This keystream is then XORed with the plaintext, which can be of arbitrary length, to generate a ciphertext of equal length.
RC4 has long been known to contain a number of biases in the keystream. The most obvious one is found in the second byte, which for a random key has a probability of 1/128 of being equal to zero — as opposed to 1/256 for a truly random keystream.
Should an adversary be interested in the second byte of the plaintext and should he/she be in a position to get a large number of RC4-encrypted ciphertexts (for different keys), a few thousand such ciphertexts should suffice for him/her to be all but certain of this second byte.
In practice, an adversary would like to be able to decrypt the full ciphertext, or if that isn't possible, a significant chunk of it, say that of an authentication cookie, which can be used to automatically log into a website. Fortunately for the adversary, and unfortunately for the longevity of the RC4-protocol, there are other biases in the keystream: consecutive and non-consecutive pairs of bytes whose values aren't truly randomly distributed.
The authors of the paper, Mathy Vanhoef and Frank Piessens from the KU Leuven in Belgium, have found more such biases than were previously known about. Using these, they were able to greatly reduce the number of ciphertexts required to decrypt an authentication cookie — something which they demonstrated in a proof-of-concept.
The idea behind their proof-of-concept is to use JavaScript injection to force the user's browser to make a large number of requests, each of which includes the authentication cookie at a known position within the ciphertext, and each of which is RC4-encrypted with a different key. After some time, the known biases in the ciphertext can be used to generate a relatively small list of likely candidates for the cookie, from which the correct one can then be found through a brute-force attack.
It is important to note that 'some time' in this case actually means 75 hours and that the bottleneck is the Internet connection between the target and the website they're accessing, not the computation power used by the attacker; hence the attack can't simply be sped up by using a very fast computer.
This, as well as a number of other criteria that have to be met, makes the attack still rather theoretical, despite the proof-of-concept. An adversary who finds himself in the position to be able to inject JavaScript into the target's browser for more than three days is likely to be able to do far more damage than decrypting one authentication cookie.
This doesn't mean that the research isn't any good. The paper is well worth reading and the attack is quite clever. It re-emphasises the point that RC4 is a cipher that is to be avoided; thankfully there are better alternatives. But the real reason for avoiding RC4 remains that we want our crypto-protocols to adhere to very high standards, not that anyone can actually break RC4 in practice.
In the paper, the same technique is applied against the deprecated WPA-TKIP protocol used for securing wireless networks.
The NOMORE attack doesn't have a logo, but it does have its own website. The paper, which will be presented at the USENIX security conference next month, can be downloaded here as a PDF. There is also a video demonstrating the attack.
