New RC4 Attack

New research: "All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS," by Mathy Vanhoef and Frank Piessens:

Abstract: We present new biases in RC4, break the Wi-Fi Protected Access Temporal Key Integrity Protocol (WPA-TKIP), and design a practical plaintext recovery attack against the Transport Layer Security (TLS) protocol. To empirically find new biases in the RC4 keystream we use statistical hypothesis tests. This reveals many new biases in the initial keystream bytes, as well as several new long-term biases. Our fixed-plaintext recovery algorithms are capable of using multiple types of biases, and return a list of plaintext candidates in decreasing likelihood.

To break WPA-TKIP we introduce a method to generate a large number of identical packets. This packet is decrypted by generating its plaintext candidate list, and using redundant packet structure to prune bad candidates. From the decrypted packet we derive the TKIP MIC key, which can be used to inject and decrypt packets. In practice the attack can be executed within an hour. We also attack TLS as used by HTTPS, where we show how to decrypt a secure cookie with a success rate of 94% using 9*227 ciphertexts. This is done by injecting known data around the cookie, abusing this using Mantin's ABSAB bias, and brute-forcing the cookie by traversing the plaintext candidates. Using our traffic generation technique, we are able to execute the attack in merely 75 hours.

News articles.

We need to deprecate the algorithm already.

Posted on July 28, 2015 at 12:09 PM • 12 Comments

Comments

Nicholas WeaverJuly 28, 2015 12:59 PM

Although (plugging my own work here), if I as an attacker am in a position to perform this attack, namely able to inject content into the target's cookie store for the site and cause the victim to repeatedly generate fetches, I can do a LOT more damage, more easily.

https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/zheng

Abstract:

A cookie can contain a “secure” flag, indicating that it should be only sent over an HTTPS connection. Yet there is no corresponding flag to indicate how a cookie was set: attackers who act as a man-in-the-middle even temporarily on an HTTP session can inject cookies which will be attached to subsequent HTTPS connections. Similar attacks can also be launched by a web attacker from a related domain. Although an acknowledged threat, it has not yet been studied thoroughly. This paper aims to fill this gap with an in-depth empirical assessment of cookie injection attacks. We find that cookie-related vulnerabilities are present in important sites (such as Google and Bank of America), and can be made worse by the implementation weaknesses we discovered in major web browsers (such as Chrome, Firefox, and Safari). Our successful attacks have included privacy violation, online victimization, and even financial loss and account hijacking. We also discuss mitigation strategies such as HSTS, possible browser changes, and present a proof-of-concept browser extension to provide better cookie isolation between HTTP and HTTPS, and between related domains.

SteveJuly 28, 2015 4:59 PM

What is www.schneier.com's ip address?

I'm now getting 67.205.21.185 with an occasional 204.11.247.93 (which was it was).

siddJuly 28, 2015 5:50 PM

what key fingerprints are people seeing ?

Perspectives is seeing different ssl key fingerprints for this site.

6 notaries (perspectives1,2,3,4 at schulte.org, nine-eyes.herokuapp.com, de.yano.nu) saw a change on the 24th from

a8:e7:d6:39:cc:26:27:0a:c1:07:3e:b3:b3:5f:63:f7

to

bf:99:f3:4a:21:f4:3f:fb:41:67:b0:73:29:07:f5:ae

but heimdal.herokuapp is seeing

7f:06:03:da:9e:a3:1d:22:10:00:5a:84:d5:06:aa:3c

that last one has been seen by others earlier

interesting fingerprint history for this site, i see several appear and vanish

sidd

Clive RobinsonJuly 28, 2015 5:53 PM

Hmm one of those fashion style questions,

    Is RC4 the new FEAL? ;-)

On another note 9*2^27 is an odd way of saying 1.2 billion...

@ Bruce,

Any thoughts on how relevant these new attacks are to Solitaire?

P.S. For those to young to remember FEAL or the Fast Encryption ALgorithm, was a crypto algorithm that got ripped apart many times over and died the death of a thousand cuts. It became the academic "whipping boy" of block cipher research and thus was instrumental in breaking ground on new attacks. Thus it's major claim to fame was that it gave a nasty shock to the NSA, of which one unamed source said "we didn't think you'ld get there that quickly".

I don't know what Ron thinks about the way his code number four has been attacked, but the pluss point is it's moved practical crypto attacks on stream ciphers using "card shuffling algorithms" forward quite a lot...

Mathy VanhoefJuly 28, 2015 6:18 PM

@ Nicholas Weaver,

The attack doesn't require the injection of cookies. It's simply the easiest method to assure the targeted cookie is surrounded by known plaintext. If you can't inject cookies the attack is still possible: just remove the unknown (secure) cookies, and then include POST data instead of injecting cookies. And if you can't manipulate cookies at all (so you can't even remove them), the attack is again still possible. However, it would take somewhat longer, with the exact time depending on how much plaintext is unknown.

PetterJuly 28, 2015 7:16 PM

The site moved, as announced previously, to dreamhost.com a few days ago and then a new cert for the site was generated.

Nicholas WeaverJuly 28, 2015 8:21 PM

@Mathy Vanhoef

Agreed its an interesting attack, and RC4 Must Die In The Fires of Hell. I'm really looking forward to your presentation in a couple of weeks, and, if you want, I'll buy you a beer for giving your paper a hard time in this forum.

You really don't have to worry about the "no cookie" case in practice: if you can still remove cookies you can inject cookies, since removal is simply a "delete-set" opreation.

The critical condition where you can't set cookies is a site which is both RC4 and sets HSTS on the domain and all subdomains. But how often does that occur?


Really, it comes down to I'm lazy and no good at math, so I tend believe in the XKCD approach rather than a crypto attack when breaking a system. https://xkcd.com/538/

CzernoJuly 29, 2015 8:51 AM

@Sidd :


This blog's server certificate fingerprint :
I get a different one yet : EE:6C:74:CA:C3:CF:6B:69:B9:8B:72:09:1D:D5:1F:D6:53:C3:8B:4E

... confirmed as viewed from Steve Gibson's www.grc.com/fingerprints.htm test page.

The certificate issuer is Comodo and valid from 7-20-2015 until 07-21-2016. It thus appears the cert was changed/renews just one week ago, which might explain variations in notaries results.


The IP address returned by DNS here is the 67.* one.

Clive RobinsonJuly 29, 2015 9:04 PM

@ RNSA,

The bias in RC-4 would seem to be an early contribution from the guys who brought you Dual_EC_DRBG and extended random.

Probably not, back when Ron came up with his forth code, he would probably not have had the computing resources to find the bias, nor for obvious reasons the new techiques that have come from the very many eyes and minds foucused on it.

In that respect RC4 is like the earlier FEAL, which brought forth new techniques then unknown in the academic community, but not the NSA (see Don Copersmiths comments http://www.research.ibm.com/journal/rd/383/coppersmith.pdf ).

rgaffJuly 29, 2015 9:54 PM

RNSA's link is quite appropriate and makes a lot of sense in my opinion... The suggestion about RC-4 is a separate subject.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.