'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
twitter.png
fb.png
linkedin.png
googleplus.png
reddit.png

 

Latest posts:

Test your technical and mental limits in the VB2017 foosball tournament

As has become tradition, VB2017 will once again see a security industry table football tournament. Register your team now for some great fun and adrenaline-filled matches in between sessions in Madrid!

The case against running Windows XP is more subtle than we think it is

Greater Manchester Police is one of many organizations still running Windows XP on some of its systems. This is bad practice, but the case against running XP is far more subtle than we often pretend it is.

Hot FinSpy research completes VB2017 programme

Researchers from ESET have found a new way in which the FinSpy/FinFisher 'government spyware' can infect users, details of which they will present at VB2017 in Madrid.

Transparency is essential when monitoring your users' activities

Activity monitoring by security products in general, and HTTPS traffic inspection in particular, are sensitive issues in the security community. There is a time and a place for them, VB's Martijn Grooten argues, but only when they are done right.

VB2017 preview: Android reverse engineering tools: not the usual suspects

We preview the VB2017 paper by Fortinet researcher Axelle Apvrille, in which she looks at some less obvious tools for reverse engineering Android malware.