Crypto Talk at 27C3: New Key Recovery Attacks on RC4/WEP, Day 4, 17:15, Saal 2

The RC4 Stream Cipher could be the most common stream cipher used on the Internet. RC4 is the only Stream Cipher which is standardized for the SSL/TLS protocol, it is also used for WEP and WPA protected wireless networks. Initially, RC4 was designed to be a closed source commercial product, with the core algorithm kept secret. In 1994, the source code for RC4 was posted on the internet and the algorithm could be analyzed.

The first attack on RC4 was published by Fluhrer, Mantin, and Shamir in 2001. The attack is very effective, but can only be used against certain keys starting with a special sequence of bytes, (for example 3, 255…). This worked perfectly well against WEP, which generates a per packet key using a random initialization vector IV, and a static secret key K. K is kept secret and shared among all nodes in the network. IV is public, and transmitted with every packet in clear. The per packet is key simply the IV concatenated with K (IV | K). We would also say, that there is a correlation between the output of RC4 and a part of the key, if certain conditions apply (the per packet key starts with 3, 255 for example). Many more of these correlations where found later and implemented in a WEP attack tool by a person under the pseudonym KoreK, which made key recovery on WEP protected networks much faster.

The next level of WEP breaking tools was published in 2007, when a new correlation was used against WEP. This correlation had been previously been found by Jenkins and Klein independently, but was never used against WEP so far. The correlation was much weaker than the correlations used in previous attack, but needed effectively no additional conditions, so that nearly every packet could be used to assist key recovery.

Looking at all those previous WEP attacks, one logical idea would be to automate the search for correlations in the RC4 output, which can be used in key recovery attacks. This is exactly the approach taken by Martin Vuagnoux:

In this paper, we present several weaknesses in the stream cipher RC4. First, we present a technique to automatically reveal linear correlations in the PRGA of RC4.

With this method, 48 new exploitable correlations have been discovered. Then we bind these new biases in the PRGA with known KSA weaknesses to provide practical key recovery attacks. Henceforth, we apply a similar technique on RC4 as a black box, i.e. the secret key words as input and the keystream words as output. Our objective is to exhaustively find linear correlations between these elements. Thanks to this technique, 9 new exploitable correlations have been revealed. Finally, we exploit these weaknesses on RC4 to some practical examples, such as the WEP protocol. We show that these correlations lead to a key recovery attack on WEP with only 9,800 encrypted packets (less than 20 seconds), instead of 24,200 for the best previous attack.

One could ask, why one should still try to improve attacks on RC4/WEP. WEP ca be broken in less than a minute nowadays. The successor protocol to WEP, namely WPA TKIP still uses the RC4 cipher in a very similar mode as WEP does. An improvement on WEP attacks could also help us in breaking WPA. Attacking RC4 in SSL/TLS would also be very interesting: Using RC4 in SSL/TLS is very efficient, because it doesn’t need any padding compared to a block cipher and needs less bandwidth than SSL/TLS using a block cipher does. A good attack on RC4 could render SSL/TLS connections insecure.

Personally, I am very interested in this talk, because I worked on attacking WEP in my diploma thesis and the last generation of WEP attacking tools was one of the results of my diploma thesis. The new attack present here will definitely outperform the last generation of WEP attacks and supersedes my results.

See the talk, Day 4, 17:15, Saal 2

Autor: Erik Tews