'NOMORE' attack makes RC4 a little weaker again

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.

  Diagram of the JavaScript-injection. Source: rc4nomore.com.

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.

Posted on 20 July 2015 by Martijn Grooten


Latest posts:

VB2016 video: Last-minute paper: A malicious OS X cocktail served from a tainted bottle

In a VB2016 last-minute presentation, ESET researchers Peter Kalnai and Martin Jirkal looked at the OS X malware threats KeRanger and Keydnap, that both spread through a compromised BitTorrent client. A recording of their presentation is now…

Consumer spyware: a serious threat with a different threat model

Consumer spyware is a growing issue and one that can have serious consequences: its use is increasingly common in domestic violence. But do our threat models consider the attacker with physical access to, and inside knowledge of the victim?

VB2016 paper: Debugging and monitoring malware network activities with Haka

In their VB2016 paper, Stormshield researchers Benoît Ancel and Mehdi Talbi introduced Haka, an open-source language to monitor, debug and control malicious network traffic. Both their paper and the video recording of their presentation are now…

VB2017: a wide ranging and international conference programme

We are proud to announce a very broad and very international programme for VB2017, which will take place in Madrid, 4-6 October 2017.

John Graham-Cumming and Brian Honan to deliver keynote addresses at VB2017

Virus Bulletin is excited to announce John-Graham Cumming and Brian Honan as the two keynote speakers for VB2017 in Madrid.