All Your Biases Belong To Us:
Breaking RC4 in WPA-TKIP and TLS
Mathy Vanhoef and Frank Piessens, KU Leuven
USENIX Security 2015

RC4Intriguingly simple stream cipher

WEP
WPA-TKIP

SSL / TLS

PPP/MPPEAnd others ...
2

RC4

Intriguingly simple stream cipher
KeyRC4

Keystream

Plaintext

Ciphertext3

Is RC4 still used?!
ICSI Notary: TLS connections using RC460%

50%

50%

40%

30%30%20%

13%

10%0%

March 2013

Februari 2015

July 2015

RC4 fallback not taken into account!
4RC4 Fallback
ServerClient
ClientHello: without RC4Browser first tries without RC4ServerHello: use AES

5

RC4 Fallback
ServerClient
ClientHello: without RC4Browser first tries without RC4

Alert: Handshake Failed

If that fails …

6

RC4 Fallback
ServerClientClientHello: without RC4Browser first tries without RC4

Alert: Handshake Failed

If that fails …

ClientHello: with RC4… fallback to RC4ServerHello: use RC47

RC4 Fallback
ServerClientClientHello: without RC4Browser first tries without RC4

Alert: Handshake Failed

Forgeable by attacker!

ClientHello: with RC4… fallback to RC4ServerHello: use RC4

 13% estimate is a lower bound Force connection (which weassumed secure) to use RC48

Our Goal: further kill RC4

New Biases

Plaintext Recovery

Break WPA-TKIP

Attack HTTPS
9

First: Existing Biases
Distribution keystream byte 2Pr 𝒁𝟐 = 𝟎𝟐= 𝟐𝟓𝟔[MS01]

10

First: Existing Biases
Distribution keystream byte 1 (to 256)11

First: Existing Biases

Short-term biases

Distribution keystream byte 1 (to 256)

AlFardan et al. ‘13:
first 256 bytes biased

12

Long-Term Biases
Fluhrer-McGrew (2000):
 Some consecutive values are biased
Examples: 0, 0 and (0, 1)
Mantin’s ABSAB Bias (2005):
 A byte pair (𝐴, 𝐵) likely reappears
ABSAB
13

Search for new biases
Traditional emperical approach: Generate large amount of keystreams
 Manually inspect data or graph

Fluhrer-McGrew: only 8 outof 65 536 pairs are biased
How to automate
the search?
14

Search for new biases
Traditional emperical approach: Generate large amount of keystreams
 Manually inspect data or graph
Hypothesis tests!
 Uniformly distributed: Chi-squared test.
 Correlated: M-test (detect outliers = biases) Allows a large-scale search,
revealing many new biases
15

Biases in Bytes 258-513
Example: keystream byte 258

16

Biases in Bytes 258-513
Example: keystream byte 320

17Biases in Bytes 258-513
Example: keystream byte 352

Biases quickly
become quite weak18

New Long-term Bias
(𝑍256∙𝑤 , 𝑍256∙𝑤+2 ) = (128, 0)−16with probability 21280−8(1 + 2 )...

Every block of 256 bytes

19Additional Biases

See paper!

20

Our Goal: further kill RC4

New Biases

Plaintext Recovery

Break WPA-TKIP

Attack HTTPS21Existing Methods [AlFardan et al. ‘13]
Plaintext encrypted under
several keystreams

Verify guess: how close toreal keystream distribution?
Ciphertext Distribution

Plaintext guess 𝜇

Induced keystream
distribution
22

Example: Decrypt byte 1
Ciphertext Distribution

23

Example: Decrypt byte 1
RC4 & Ciphertext distribution

24

Example: Decrypt byte 1
If plaintext byte 𝜇 = 0x28: RC4 & Induced

𝜇 = 0x28 has low likelihood

25

Example: Decrypt byte 1
If plaintext byte 𝜇 = 0x5C: RC4 & Induced

𝜇 = 0x5C has higher likelihood26

Example: Decrypt byte 1
If plaintext byte 𝜇 = 0x5A: RC4 & Induced

𝜇 = 0x5A has highest likelihood!

27

Types of likelihood estimates
Previous works: pick value with highest likelihood.
Better idea: list of candidates in decreasing likelihood: Most likely one may not be correct!
 Prune bad candidates (e.g. bad CRC)
 Brute force cookies or passwords
How to calculate list of candidates?
28

1st idea: Generate List of Candidatess
Gist of the Algorithm: Incremental approachCalculate candidates of length 1, length 2, ...

1122𝑛𝑛...

12𝑛29

2nd idea: abusing the ABSAB biasABS

Known Plaintext

A’B’

Unknown Plaintext!

Assume there’s surrounding known plaintext
 Derive values of A, B
 Combine with ABSAB bias to (probablisticly) predict A′, B′ Ordinary likelihood calculation over only (A′, B′)
Likelihood estimate:
30

Our Goal: further kill RC4

New Biases

Plaintext Recovery

Break WPA-TKIP

Attack HTTPS
31

TKIP BackgroundHow are packets sent/received?
IVDataMIC

CRC

Encrypted

1. Add Message Integrity Check (MIC)
2. Add CRC (leftover from WEP)
3. Add IV (increments every frame)
4. Encrypt using RC4 (per-packet key)32

Flaw #1: TKIP Per-packet Key
KeySender MAC

𝐼𝑉Key-Mixpacket key(𝐼𝑉0 , 𝐼𝑉1 )Anti-FMS

Avoid weak keys which broke WEP 𝐼𝑉-dependent biases in keystream[Gupta/Paterson et al.]33

Flaw #2: MIC is invertible
IV

DataMICCRC

If decrypted, reveals MIC key

 With the MIC key, an attacker can inject anddecrypt some packets [AsiaCCS ‘13]

34

Goal: decrypt data and MIC
IVDataMIC

CRC

If decrypted, reveals MIC key
Generate identical packets (otherwise MIC changes): Assume victim connects to server of attacker
 Retransmit identical TCP packet
 List of plaintext candidates (unknown MIC and CRC)
 Prune bad candidates based on CRC
35

Evaluation
Simulations with 230 candidates: Need ≈ 224 captures to decrypt with high success rates

Emperical tests:
 Server can inject 2 500 packets per second Roughly one hour to capture sufficient traffic
 Successfully decrypted packet & found MIC key!
36

Our Goal: further kill RC4New Biases

Plaintext Recovery

Break WPA-TKIP

Attack HTTPS
37

TLS Background
Negotiate keys

Handshake protocol
Record protocol

ClientEncrypt dataServer

 Focus on record protocol with RC4 as cipher

38

Targeting HTTPS Cookies
Previous attacks only used Fluhrer-McGrew (FM) biases
We combine FM bias with the ABSAB bias
Must surround cookie with known plaintext
1. Remove unknown plaintext arround cookie
2. Inject known plaintext arround cookie
39

Example: manipulated HTTP request
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
Trident/7.0; rv:11.0) like Gecko
Host: a.site.com
Headers are
Connection: Keep-Alive
predictable
Cache-Control: no-cache
Cookie: auth=????????????????; P=aaaaaaaaaaaaaaaaa

Surrounded by known
plaintext at both sides
40Preparation: manipulating cookies
a.site.com

ClientHTTPS

fake.site.com
insecure

Remove & inject
secure cookies!
41Performing the attack!

JavaScript: Cross-Origin requests in WebWorkers

42Performing the attack!

Keep-Alive connection to generate them fast43Performing the attack!

Combine Fluhrer-McGrew and ABSAB biases

44Decrypting 16-character cookie

Takes 75 hours with 4450 requests / second

Ciphertext copies times 227

45Decrypting 16-character cookie

DEMO!
rc4nomore.com
46

Questions?
May the bias be ever in your favor