This page is about the security of RC4 encryption in TLS and WPA/TKIP. For details of the Lucky 13 attack on CBC-mode encryption in TLS, click here.
The Transport Layer Security (TLS) protocol aims to provide confidentiality and integrity of data in transit across untrusted networks like the Internet. It is widely used to secure web traffic and e-commerce transactions on the Internet. Around 50% of all TLS traffic is currently protected using the RC4 algorithm. It has become increasingly popular because of recent attacks on CBC-mode encryption on TLS, and is now recommended by many commentators.
We have found new attacks against TLS that allows an attacker to recover a limited amount of plaintext from a TLS connection when RC4 encryption is used. The attacks arise from statistical flaws in the keystream generated by the RC4 algorithm which become apparent in TLS ciphertexts when the same plaintext is repeatedly encrypted.
We have carried out experiments to demonstrate the feasibility of the attacks.
The most effective countermeasure against our attack is to stop using RC4 in TLS. There are other, less-effective countermeasures against our attacks and we have worked with a number of TLS software developers to prepare patches and security advisories.
One of the attacks also applies to WPA/TKIP, the IEEE's successor protocol to WEP. The most effective countermeasure against our attack against WPA/TKIP is to stop using WPA/TKIP and upgrade to WPA2.
Part of our work was presented at USENIX Security 2013, Washington DC, USA, 14th-16th August, 2013.
Who are we?
The team behind this research comprises Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering and Jacob Schuldt. Nadhem is a PhD student in the Information Security Group at Royal Holloway, University of London. Dan is a Research Professor at the University of Illinois at Chicago and a Professor at the Eindhoven University of Technology. Kenny is a Professor of Information Security and an EPSRC Leadership Fellow in the Information Security Group at Royal Holloway, University of London. Bertram and Jacob are postdocs in the Information Security Group.
What is affected?
Which versions of SSL and TLS are affected?
The attack applies to all versions of SSL and TLS that support the RC4 algorithm.
Which TLS ciphersuites are affected?
All TLS ciphersuites which include RC4 encryption are vulnerable to our attack.
Which TLS implementations are affected?
All TLS implementations which support RC4 are affected.
Which WPA/TKIP implementations are affected?
All WPA/TKIP implementations are affected.
How severe are the attacks?
Our first attack is a multi-session attack, which means that we require a target plaintext to be repeatedly sent in the same position in the plaintext stream in multiple TLS connections or sessions. It exploits single-byte biases in the initial 256 bytes of RC4 keystreams. For details of these biases, see this slide-deck showing the distributions of the first 256 output bytes from the RC4 generator (based on 244 random 128-bit keys).
Since the first 36 bytes of plaintext are formed from an unpredictable Finished message when SHA-1 is the selected hashing algorithm in the TLS Record Protocol, these first 36 bytes cannot be recovered. This means that the single-byte bias attack can recover 220 bytes of TLS-encrypted plaintext.
The number of connections/sessions needed to reliably recover these plaintext bytes is around 230, but already with only 224 connections/sessions, certain bytes can be recovered reliably.
The connections/sessions needed for our single-byte bias attack can be generated in various ways. The attacker could cause the TLS session to be terminated, and some applications running over TLS then automatically reconnect and retransmit a cookie or password. In a web environment, the sessions may also be generated by client-side malware, in a similar way to the BEAST attack.
This attack also applies directly to WPA/TKIP, with similar success rates, because of its use of per-packet keys for RC4. Here, the particular structure of WPA/TKIP keys means that a different set of biases are obtained in the first 256 bytes of RC4 keystream. For details, see this slide-deck showing the distributions of the first 256 output bytes from the RC4 generator (based on 241 WPA/TKIP keys).
Our second attack applies to TLS and can be carried out in a single connection or session (but tolerates multiple connections/sessions). It exploits certain double-byte biases in RC4 keystreams (the Fluhrer-McGrew biases). It targets plaintext bytes located at any position in the TLS plaintext stream. The number of encryptions needed to reliably recover a set of 16 consecutive targeted plaintext bytes is around 10⋅230, but already with only 6⋅230 sessions, these target bytes can be recovered with 50% reliability. Since this double-byte bias attack does not require the TLS Handshake Protocol to be rerun, it can in practice be more efficient than our single-byte bias attack.
In contrast to the recent Lucky 13 attack, there is no need for sophisticated timing of error messages, and the attacker can be located anywhere on the network path between client and server in our attacks.
How does this work relate to known attacks, like BEAST, CRIME and Lucky 13?
TLS in CBC-mode has been the subject of several attacks over the years, most notably padding oracle attacks, the BEAST attack and the recent Lucky 13 attack. For more details of prior attacks, see the Lucky 13 research paper. There are now countermeasures for the BEAST and Lucky 13 attacks, and TLS in CBC-mode is believed to be secure against them once these countermeasures are applied. By contrast, the new attack targets the RC4 algorithm in TLS.
But isn't RC4 already broken?
There have been many attacks on RC4 over the years, most notably against RC4 in the WEP protocol. There, the known attacks crucially exploit the way in which the algorithm's secret key is combined with public information (the WEP IV) during the algorithm's initialisation step. These attacks do not apply to RC4 in TLS, and new attack ideas are needed. Certain bytes of the RC4 keystream are already known to have biases that assist cryptanalysis; in our work, we identify the complete set of biases in the first 256 keystream bytes and combine these using a particular statistical procedure to extract plaintext from ciphertext.
How do the attacks relate to BEAST, CRIME and Lucky 13?
The attacks are quite different from BEAST, CRIME and Lucky 13. BEAST exploits the inadvisable use of chained IVs in CBC-mode in SSL and TLS 1.0. CRIME cleverly exploits the use of compression in TLS. Lucky 13 defeats existing RFC-recommended countermeasures for padding oracle attacks against CBC-mode. Our attacks are against the RC4 algorithm and are based on analysing statistical weaknesses in the RC4 keystream. However, our attacks can be mounted using BEAST-style techniques.
Why don't the attacks have cool names?
In Western culture, naming one's attacks after obscure Neil Young albums is now considered passé.
What are the countermeasures?
For TLS, there are several possible countermeasures against our attacks. Some of these are more effective than others:
- Switch to using CBC-mode ciphersuites. This is a suitable countermeasure provided previous CBC-mode attacks such as BEAST and Lucky 13 have been patched. Many implementations of TLS 1.0 and 1.1 now do have patches against these attacks.
- Switch to using AEAD ciphersuites, such as AES-GCM. Support for AEAD ciphersuites was specified in TLS 1.2, but this version of TLS is not yet widely supported. We hope that our research will continue to spur support for TLS 1.2 in client and server implementations.
- Patch TLS's use of RC4. For example, one could discard the first output bytes of the RC4 keystream before commencing encryption/decryption. However, this would need to be carried out in every client and server implementation of TLS in a consistent manner. This solution is not practically deployable given the large base of legacy implementations and the lack of a facility to negotiate such a byte discarding procedure. Furthermore, this will not provide security against potential future improvements to our attack. Our recommendation for the long term is to avoid using RC4 in TLS and to switch to using AEAD algorithms.
- Modify browser behaviour. There are ways to modify the manner in which a browser using TLS handles HTTP GET requests to make the attack less effective. However, care is needed to avoid potential future improvements to our attack. Our recommendation for the long term is to avoid using RC4 in TLS and to switch to using AEAD algorithms.
For WPA/TKIP, the only reasonable countermeasure is to upgrade to WPA2.
Patches, advisories and press
We worked with the IETF TLS Working Group and affected vendors to disclose the attacks on TLS. We will continue to update the information here as this process continues.
- Google is focussing on implementing TLS 1.2 and AES- GCM in Chrome.
- Microsoft has modified their code so that RC4 is no longer enabled by default for TLS in Windows 8.1 Preview.
- Opera has implemented a number of countermeasures to modify browser behaviour.
- CVE: The US NIST National Vulnerability Database has accorded our single-byte bias attack on TLS CVE-2013-2566.
Selected media coverage:
- heise.de (in German)
- golem.de (in German)
- Ars Technica
- Xakep (in Russian)
- Network World
- The Register (boffin alert)
- Matthew Green's blog
- Ivan Ristic's Qualys blog
- Bruce Schneier's blog
- Wikipedia article on RC4 with mention of the attack
Is it still safe to use RC4 ?
The attacks can only be carried out by a determined attacker who can generate sufficient sessions for the attacks. They recover a limited amount of plaintext. In this sense, the attacks do not pose a significant danger to ordinary users of TLS or WPA/TKIP in their current form. However, it is a truism that attacks only get better with time, and we anticipate significant further improvements to our attacks. In addition, because of their extremely widespread use, any attacks against TLS or WPA/TKIP require careful evaluation.
We have no plans to make our source code generally available. If you are a researcher interested in replicating or extending our work, then please contact us.
Isn't it irresponsible to publish attacks on such important protocols?
In short, no. Our long-term aim is to ensure that weak encryption options are eliminated from TLS, to the eventual benefit of all users of TLS. Likewise with WPA/TKIP. Experience shows that the only way to make this happen is to make the attacks as powerful as possible and build proof-of-concept implementations of them. We have expended significant research effort to develop and prototype our attacks. We disclosed the attacks to affected vendors in advance of making our research public, and we are working with all vendors who request our assistance in assessing the attacks and implementing countermeasures.
For more information
The single-byte bias attack on RC4 was announced on 12th March 2013 during Dan Bernstein's invited talk at FSE 2013. Further information about biases in the RC4 keystream can be found in this slide-deck showing the distributions of the first 256 output bytes from the RC4 generator (based on 244 random 128-bit keys). Raw data for 245 random 128-bit keys can be found in this file. Further information about biases in the RC4 keystream for WPA/TKIP keys can be found in this slide-deck showing the distributions of the first 256 output bytes from the RC4 generator (based on 241 WPA/TKIP keys). Full details of our attacks can be found in our research paper. A high-level overview of the results can be obtained by reading our USENIX Security 2013 presentation. Video for this talk is available on the USENIX Security 2013 website. If you have remaining questions after having studied these resources, please contact us via e-mail.