A few days ago, a new attack against SSL/TLS has been published by Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering and Jacob Schuldt. Many attacks on SSL/TLS in the past relied on the protocol design itself, broken implementations leaking side channels, or the X.509 certificate system and improper issuing of certificates. In contrast to these, the new attack is focused on the RC4 stream cipher, that can be used against SSL/TLS.

RC4 usage in SSL/TLS

SSL/TLS doesn’t rely on a single cryptographic primitive. Instead when a new SSL/TLS session is established, both parties negotiate a ciphersuite. A ciphersuite consists of a key exchange algorithm, an encryption method and an integrity protection method. To agree on a common ciphersuite, the SSL/TLS client sends a list of all ciphersuites it supports, and the server choses one of the methods from the list, usually the first one which is also supported by the server. The RC4 stream cipher is one of the possible choices for the encryption method, and also wildly supported and used. Compared to many other encryption methods, RC4 is very fast in software, very easy to implement, and also very efficient because it doesn’t require any padding as many encryption methods based on block ciphers do.

What makes RC4 a bad stream cipher

So what would be expect from a (secure) stream cipher? A stream cipher should take a key, and transform this key into a (pseudo-) random sequence of bytes, chosen from a uniform distribution. However, RC4 has also serious weaknesses. For example, RC4 is also used in the famous WEP protocol, to protect WiFi networks. Here, many similar RC4 keys are used that differ only in the first 3 bytes. These 3 bytes of the key are used as an initialization vector for the cipher, and are transmitted in clear with the encrypted packet. The remaining bytes of the key are shared among all packets, but should only be known to the operator of the network. What has been shown for WEP is, that an attacker, who knows the first 3 bytes of the key, and also has access to some bytes of the key stream can predict the next bytes of the key. The probability for predicting a single byte correct is only slightly above a random guess, but repeating the procedure for many packets (like 10.000) will reveal the secret key that protects the network with almost 100% probability. In a nutshell, if you know a part of an RC4 key, and some bytes of the keystream, then you can predict parts of the remaining key better than just guessing.

How can this be applied to SSL/TLS

But for SSL/TLS, the situation is entirely different. Here, a new key is chosen almost randomly for every new connection and no parts of the key are shown to an attacker. As a result, the methods used to attack RC4 in WEP cannot be applied for SSL/TLS connections. But there are more problems in RC4:  Even if a key for RC4 is randomly chosen, the keystream bytes of RC4 have some biases. For example the second by of output will be 0 with a probability of more than 1/256. What recently has been discovered is, that much more of such biases exist. If a plaintext is transmitted over SSL/TLS, one gets a small hint about the plaintext. If the same plaintext is transmitted over and over again using TLS with RC4 encryption, one can recover the first bytes of the plaintext using these biases in the keystream generated by RC4. No assumptions about other plaintext or keystream bytes must be made, and no knowledge of parts of the key is required. Also this works independant of the implementation used, because it doesn’t require any timings or similar side channels from the implementation.

Consequences of the attack

The number of sessions required depends on how much is known about the plaintext, and what should be recovered. A full plaintext can be recovered using $latex 2^{30}$ sessions. If only a single byte needs to be recovered, about $latex 2^{24}$ sessions might be sufficient, depending on the position of the byte in the plaintext. If one only wants to distinguish two plaintexts only, then less than $latex 2^{24}$ sessions might be enough.

Countermeasures

One may ask now how to counter the attack. One of the best solutions would be to just simply disable RC4 support on a client or on a server. As long as a client and a server still share another common ciphersuite, they will still operate properly. Alternatively, both the server and the client can be patched to send empty application layer records, until the first 256 or 512 bytes of output of RC4 have been used. Currently, the attack works best with the first bytes of output of RC4, but less well with the following bytes.

Final remarks

I have also previously been active in research on RC4 and WEP attacks.