RC4 NOMORE

Introduction

When you visit a website, and the browser's address bar contains a lock icon , the HTTPS protocol is used to protect your communication with this website (providing security and privacy). HTTPS supports several encryption techniques, one of them being the famous RC4 algorithm. At one point RC4 was used 50% of the time, with the estime around Februari 2015 being 30%. Our RC4 NOMORE attack exposes weaknesses in this RC4 encryption algorithm. More precisely, in most situations where RC4 is used, these weaknesses can be used to reveal information which was previously thought to be safely encrypted.

In particular we show that an attacker can decrypt web cookies, which are normally protected by the HTTPS protocol. Websites use these cookies to identify users and authorize actions they perform. By obtaining the cookie of a victim, an attacker can log into a website as if he were the victim. This means the attacker can perform actions under the victim's name (e.g. post status updates and send messages), gain access to personal information (e.g. to emails and chat history), and so on.

The research behind the attack has been presented at USENIX Security. Summarized, an attacker can decrypt a cookie within 75 hours. In contrast to previous attacks, this short execution time allows us to perform the attack in practice. When we tested the attack against real devices, it took merely 52 hours to successfully perform the attack. The attack consists of three steps:

When the victim visits an unencrypted website, the attacker inserts malicious JavaScript code inside the website. This code will induce the victim to transmit encrypted requests which contain the victim's web cookie. By monitoring numerous of these encrypted requests, a list of likely cookie values can be recovered. All cookies in this list are tested until the correct one is found.

Update October 2017: We are pleased to say that, together with other work on RC4, our work influenced major browsers to disable RC4. As a result, usage of RC4 has drastically decreased: less than 1% of all HTTPS and TLS connections still use RC4.

Demonstration

As a proof-of-concept we executed the attack in our lab, against a fictitious website and victim (to prevent harming real systems). In our demonstration the victim uses Internet Explorer, and we show how the attacker can take over an account of the victim. This is the first time weaknesses in RC4, when used in TLS and HTTPS, are exploited against real devices.

To successfully decrypt a 16-character cookie with a success probability of 94%, roughly 9⋅2²⁷ encryptions of the cookie need to be captured. Since we can make the client transmit 4450 requests per seconds, this amount can be collected in merely 75 hours. If the attacker has some luck, less encryptions need to be captured. In our demonstration 52 hours was enough to execute the attack, at which point 6.2⋅2²⁷ requests were captured. Generating these requests can even be spread out over time: they do not have to be captured all at once. During the final step of the attack, the captured requests are transformed into a list of 2²³ likely cookie values. All cookies in this list can be tested in less than 7 minutes.

Our attack is not limited to decrypting cookies. Any data or information that is repeatedly encrypted can be recovered. We focus on web cookies in HTTPS as it nicely illustrates the weaknesses in RC4 and the power of our attack.

Paper

Our research paper behind the attack is All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS. In the paper we not only present attacks against TLS/HTTPS, but also against WPA-TKIP. Our attack against WPA-TKIP takes only an hour to execute, and allows an attacker to inject and decrypt arbitrary packets. On this page we focused on HTTPS because it is used more than WPA-TKIP. The paper has been presented at USENIX Security 2015, and you can view the slides online.

We would also like to point out that there is an independent translation of our paper to Spanish.

Q&A

How does this attack compare to previous attacks?

The first attack against RC4 as used in TLS was estimated to take more than 2000 hours. It required 13⋅2³⁰ encryptions of a cookie to be able to decrypt it, and could make a victim generate 1700 requests per second (with each request containing the encrypted cookie). We require only 9⋅2²⁷ requests, and can make a victim generate 4450 requests per second. This means our attack takes merely 75 hours to execute. We have also tested the attack against real devices, while previous works only performed simulations.

The Bar Mitzvah attack relies on keystreams with predictable LSBs, which occur once every 2²⁴ connections. Only the first 100 keystream bytes are known to be weak. However, currently no systems are known which encrypt sensitive data at these positions.

Another attack targets passwords encrypted by RC4 and relies on statistical biases in the initial keystream bytes. It requires roughly 2²⁶ encryptions of a password to be able to decrypt it. However, generating many requests in this scenario proves to be difficult, as each request must be performed in a new TLS connection. They estimated the attack takes between 312 to 776 hours to execute.

Our work significantly reduces the execution time of performing an attack, and we consider this improvement very worrisome. Considering there are still biases which are unused, that more efficient algorithms can be implemented, and better traffic generation techniques can be explored, we expect further improvements in the future.

Which weaknesses in RC4 does the attack abuse?

It relies on two types of statistical biases present in the keystream. The first one is that two consecutive bytes are biased towards certain values. These are commonly called the Fluhrer-McGrew biases. The second type of biases is that a pair of consecutive bytes is likely to repeat itself. These are called the Mantin's ABSAB biases. Both types of biases are combined in our attack.

These biases allow us to decrypt repeated plaintext such as cookies.

What now?

The only good countermeasure is to stop using RC4. Nevertheless, we did observe that generating the required amount of traffic can be a bottleneck when executing the attack. Hence attacks can be made more expensive, though not prevented, by making it more difficult to generate traffic. One option is to prohibit browsers from making parallel connections when using RC4 (normally multiple connections are made to load websites faster). This reduces the speed at which clients can make requests, meaning they generate traffic more slowly. However, we stress that this would only increase the execution time of attacks, and not prevent them.

Is WPA-TKIP also vulnerable?

Yes. We can break a WPA-TKIP network within an hour. More precisely, after successfully executing the attack, an attacker can decrypt and inject arbitrary packets sent towards a client. In general, any protocol using RC4 should be considered vulnerable.

Resources

We provide more detailed versions of several graphs in our paper:

Distribution of keystream bytes 258 to 513 (per position).
Distribution of keystream bytes 258 to 513 (per value).
Detailed graph of the Fluhrer-McGrew biases in initial keystream bytes (figure 4 in the paper).
Detailed graph of the influence of the first two keystream bytes (figure 5 in the paper).

While full keystream statistics are too big to put online, we do provide datasets over most of our newly discovered biases:

Statistics of the initial 513 keystream bytes, computed using roughly 2^47.18 RC4 keys.
Statistics on the influence of the first keystream byte, and the influence of the second keystream byte, computed using roughly 2^44.19 RC4 keys. The format of these files, and code to easily read them, can be found in this Python file.
Statistics on the first 512 consecutive keystream bytes, computed using roughly 2^45.01 RC4 keys. The format of the file, and code to easily read it, can be found in this Python file.

Finally, you can also download our R implementation of the M-test by Fuchs and Kenett.