WEP Security
“connected” scanning on
each channel
STA
association request
association response
AP
beacon
STA (Station could be any device that uses 802.11 e.g. laptop, cell phone, etc. )
AP (Access Point)
2
Internet
AP
3
4
5
6
wireless traffic can be monitored by any radio
in range, not physically connected
original 802.11 spec had security features
◦ Wired Equivalent Privacy (WEP) algorithm
◦ but found this contained major weaknesses
802.11i task group developed capabilities to
address WLAN security issues
◦ Wi-Fi Alliance Wi-Fi Protected Access (WPA)
◦ final 802.11i Robust Security Network (RSN)
part of the IEEE 802.11 specification
goal
◦ make the WiFi network at least as secure as a
wired LAN (that has no particular protection
mechanisms)
◦ WEP was never intended to achieve strong
security
services
◦ access control to the network
◦ message confidentiality
◦ message integrity
9
•Although Wi-Fi Protected Access (WPA) and WPA2 have
been available for some time, and given the fact WEP has
serious security flaws,
10
before association, the STA needs to authenticate itself to the
AP
authentication is based on a simple challenge-response
protocol:
STA AP: authenticate request
AP STA: authenticate challenge (r)
STA AP: authenticate response (eK(r))
AP STA: authenticate success/failure
once authenticated, the STA can send an association request,
and the AP will respond with an association response
if authentication fails, no association is possible
11
STA AP
Shared secret distributed out of
band
Challenge
(Nonce)
Response (Nonce RC4 encrypted under shared
key)
Decrypted nonce OK?
802.11 Authentication Summary:
•Access Point generates a “randomly generated” challenge
• Station encrypts challenge using pre-shared secret
• Access Point decrypts response and verifies that it is the same nonce
12
WEP encryption is based on RC4 (a stream cipher developed in 1987
by Ron Rivest for RSA Data Security, Inc.)
◦ operation:
for each message to be sent:
RC4 is initialized with the shared secret (between STA and AP)
RC4 produces a pseudo-random byte sequence (key stream)
this pseudo-random byte sequence is XORed to the message
reception is analogous
◦ it is essential that each message is encrypted with a different key stream
the RC4 generator is initialized with the shared secret and an IV (initial value)
together
shared secret is the same for each message
24-bit IV changes for every message
WEP integrity protection is based on an encrypted CRC value
◦ operation:
ICV (integrity check value) is computed and appended to the message
the message and the ICV are encrypted together
13
message + ICV
K
IV secret key RC4
encode
IV message + ICV
decode
K
IV secret key RC4
K: pseudo-random sequence message + ICV
14
Two kinds of keys are allowed by the standard
◦ default key (also called shared key, group key, broadcast key)
◦ key mapping keys (also called individual key, per-station key, unique key)
id:X | default key id:X | key:def key mapping key
key:abc
id:Y | id:Y | key:ghi
key:abc
id:Z | id:Z | key:jkl
key:abc key:abc id:X | key:def
id:Y | key:ghi
id:Z | key:jkl
In practice, often only default keys are supported
◦ the default key is manually installed in every STA and the AP
◦ each STA uses the same shared secret key in principle, STAs can decrypt
each other’s messages
15
The default key is a group key, and group keys
need to be changed when a member leaves the
group
◦ e.g., when someone leaves the company and shouldn't
have access to the network anymore
It is practically impossible to change the default
key in every device simultaneously
16
Flaws in Authentication and Access Control
Flaws in Integrity and Replay Protection
Flaws in Confidentiality
17
Flaws in Authentication and Access Control
Flaws in Integrity and Replay Protection
Flaws in Confidentiality
18
Authentication is one-way only
◦ AP is not authenticated to STA
◦ STA is at risk to associate to a rogue AP
The same shared secret key is used for authentication and
encryption
◦ no session key is established during authentication
◦ weaknesses in any of the two protocols can be used to
break the key
STA can be impersonated?????
19
STA AP
Challenge
(Nonce)
Response (Nonce RC4 encrypted under
shared key)
Decrypted nonce OK?
Record one challenge/response with a sniffer
Use the challenge to decrypt the response and recover the key stream
Use the recovered key stream to encrypt any subsequent challenge
Does the IV mechanism mitigate the problem?
◦ No. The IV is selected by the sender of the message, i.e., the attack in
this case.
20
recall that authentication is based on a challenge-response
protocol:
…
AP STA: r
STA AP: IV | r K
…
where K is a 128 bit RC4 output on IV and the shared secret
an attacker can compute r (r K) = K
then it can use K to impersonate STA later:
…
AP attacker: r’
attacker AP: IV | r’ K
…
21
The 802.11 standard identifies this scenario and
discourages stations for re-using the IV from this
handshake, since future traffic using it may be
decrypted.
What it fails to mention is that an attacker may
transmit indefinitely by using that keystream.
The response to this attack was to discourage the
use of this authentication scheme and to use
mechanisms such as MAC address filters.
22
Ethernet MAC Address Access Control Lists
◦ In theory, access control lists provide a reasonable level of
security when a strong form of identity is used. Unfortunately, this
is not the case with MAC addresses for two reasons.
◦ First, MAC addresses are easily sniffed by an attacker since they
MUST appear in the clear even when WEP is enabled, and second
most all of the wireless cards permit the changing of their MAC
address via software.
◦ As a result, an attacker can easily determine the MAC addresses
permitted access via eavesdropping, and then subsequently
masquerade as a valid address by programming the desired
address into the wireless card.
23
Flaws in Authentication and Access Control
Flaws in Integrity and Replay Protection
Flaws in Confidentiality
24
There’s no replay protection at all
◦ IV is not mandated to be incremented after each message
The attacker can manipulate messages despite the ICV
mechanism and encryption
◦ CRC is a linear function wrt to XOR:
CRC(X Y) = CRC(X) CRC(Y)
- attacker observes (M | CRC(M)) K where K is the RC4 output
- for any DM, the attacker can compute CRC(DM)
- hence, the attacker can compute:
((M | CRC(M)) K) (DM | CRC(DM)) =
((M DM) | (CRC(M) CRC(DM))) K =
((M DM) | CRC(M DM)) K
25
Payload CRC-32
011010010100…………………………………… 10110…………
RC4 101101110101…………………………………………………………
XOR
110111100001…………………………………… 11011…………
010000000000…………………………………… 00110…………
XOR
100111100001…………………………………… 11101…………
Modified Packet
RC4(k,CRC(XY)) = RC4(k,CRC(X)) CRC(Y)
Flaws in Authentication and Access Control
Flaws in Integrity and Replay Protection
Flaws in Confidentiality
27
WEP uses a long-term secret key: K
RC4 is a stream cipher, so each packet
must be encrypted using a different key
◦ Initialization Vector (IV) sent with packet
◦ Sent in the clear (IV is not secret)
Actual RC4 key for packet is (IV,K)
◦ That is, IV is pre-pended to K
28
WEP uses 24-bit (3 byte) IV
◦ Each packet gets a new IV
◦ RC4 packet key: IV pre-pended to long-term key,
K
Long term key K seldom changes
If long-term key and IV are same, then
same keystream is used
◦ This is bad!
29
Encrypting two messages with the same part
of RC4 keystream is disastrous:
◦ C1 = P1 RC4(key)
◦ C2 = P2 RC4(key)
◦ C1 C2 = P1 P2
◦ Keystream cancels out!
Use initialization vector to augment the key
◦ Key = base_key || IV
◦ Different IVs produce different keystreams
Include IV (unencrypted) in header
What if two messages use the same IV?
Same IV same keystream!
C1 C2 = P1 P2
If P1 is known, P2 is immediately available
Otherwise, use expected distribution of P1
and P2 to discover contents
◦ Much of network traffic contents predictable
◦ Easier when three or more packets collide
Assume 1500 byte packets, 11 Mbps link
Suppose IVs generated in sequence
◦ Then 1500 8/(11 106) 224 = 18,000 seconds
◦ Implies IV must repeat in about 5 hours
Suppose IVs generated at random
◦ By birthday problem, some IV repeats in
seconds
Again, repeated IV (with same K) is bad!
32
If Eve can insert traffic and observe
corresponding ciphertext
◦ Then she will know keystream for that IV
◦ And she can decrypt next massege that uses
that IV
If Eve knows destination IP address
◦ She can change IP address in ciphertext
◦ And modify CRC so it is correct
◦ Then access point will decrypt and forward
packet to the Eve’s selected IP address!
◦ Requires no knowledge of the key K!
33
WEP data encrypted using RC4
◦ Packet key is IV and long-term key K
◦ 3-byte IV is pre-pended to K
◦ Packet key is (IV,K)
IV is sent in the clear (not secret)
◦ New IV sent with every packet
◦ Long-term key K seldom changes (maybe
never)
Assume Eve knows IVs and ciphertext
Eve wants to find the key K
34
3-byte IV pre-pended to key
We denote the RC4 key bytes…
◦ …as K0,K1,K2,K3,K4,K5,…
◦ Where IV = (K0,K1,K2), which Eve knows
◦ Eve wants to find K3,K4,K5,…
Given enough IVs, we show that Eve can
recover the long-term key
◦ Regardless of the length of the key!
◦ Provided Eve knows first keystream byte
◦ Known plaintext attack (1st byte of each packet)
35
Recall that RC4 initialization is…
Si = i for i = 0,1,2,…,255
j=0
for i = 0 to 255
j = j + Si + Ki
swap(Si,Sj)
next i
36
Attack due to Fluher, Mantin and Shamir
Eve watches IVs until she sees 3-byte IV of
the form: IV = (3,255,V)
Where V can be anything (Eve knows V)
Then RC4 key for this packet is
key = (3,255,V,K3,K4,K5,…)
Eve wants to find (K3,K4,K5,…)
37
IV = (3,255,V)
Key = (3,255,V,K3,K4,…)
Eve knows K0 = 3, K1 = 255, K2 = V
Other Ki are long-term key
◦ Which is unknown to Eve
Recall RC4 initialization: first, set S to…
38
IV = (3,255,V)
Key = (3,255,V,K3,K4,…)
RC4 initialization: let j = 0 then
for i = 0 to 255
j = j + Si + K i
swap(Si,Sj)
next i
At i = 0 step we have
i=0
j = j + S0 + K0 = 0 + 0 + 3 = 3
swap(Si,Sj) = swap(S0,S3)
39
From previous slide…
At i = 0 step we have
i=0
j = j+S0+K0 = 0+0+3 = 3
swap(Si,Sj) = swap(S0,S3)
After this step, the table S is…
40
IV = (3,255,V)
Key = (3,255,V,K3,K4,…)
Continuing, at i = 1 step
i=1
j = j+S1+K1 = 3+1+255 = 3 (mod 256)
swap(Si,Sj)
After this step, the table S is…
41
IV = (3,255,V)
Key = (3,255,V,K3,K4,…)
Continuing, at i = 2 step
i=2
j = j+S2+K2 = 3+2+V = 5+V
swap(Si,Sj)
After this step, the table S is…
42
IV = (3,255,V)
Key = (3,255,V,K3,K4,…)
Continuing, at i = 3 step
i=3
j = j+S3+K3 = 5+V+1+K3 = 6+V+K3
swap(Si,Sj)
Assuming 6+V+K3 > 5+V (mod 256), the table is
Otherwise 6+V+K3 will be to the left of 5+V
43
Note that we have only considered the first
4 steps of initialization, i = 0,1,2,3
◦ In reality, there are 256 steps
For now, assume that initialization stops
after i = 3 step
Then S is
Next, we consider RC4 keystream
algorithm
44
After initialization, let i = j = 0
Then for each keystream byte
i = i+1
j = j+Si
swap(Si,Sj)
t = Si+Sj
keystreamByte = St
45
Suppose initialization stopped with
First keystream byte
Let i = j = 0
Then
i = i+1 = 1
j = j+S1 = 0
t = Si+Sj = S1+S0 = 0+3 = 3
keystreamByte = St = S3 = 6+V+K3
46
Note: keystreamByte = 6+V+K3
If keystreamByte is known, we can solve for K3
since
K3 = (keystreamByte6V) mod 256
But initialization does not stop at i=3
So can this “attack” really work?
47
After i=3 initialization step, S is
If elements at 0,1 and 3 not swapped in
remaining initialization steps, attack works
For remaining initialization steps…
o We have i = 4,5,6,… so index i will not affect anything at indices
0,1 or 3
o But what about index j?
48
Pretend index j selected at random
o At each step, probability is 253/256 that j
{0,1,3}
o There are 252 steps after i = 3
Probabilitythat 0,1 and 3 not affected by
j index after i=3 step is
(253/256)252 = 0.0513
49
Can be shown that with about 60 IVs of
the form (3,255,V) can find K3
o Not so easy to prove that 60 is correct
o Easy to verify empirically
This is enough to show that a shortcut
attack on WEP/RC4 exists
Can Eve really recover the key?
If she sees enough IVs she gets K3
50
Suppose Eve has found K3
Then how to find K4?
Consider IVs of the form: IV = (4,255,V)
Then after initialization step i=4, we have
51
If we now generate first keystream byte
i=1
j = Si = 0
t = S1+S0 = 4
keystreamByte = S4 = 10+V+K3+K4
Then K4 = (keystreamByte-10-V-K3) mod 256
Probability of this is also about 0.05
52
If enough IVs are available
◦ And corresponding 1st keystreamBytes are known
Then Eve can recover the key
◦ Finds K3 then K4 then K5 and so on…
Get entire key, regardless of length!
53
Can reduce number of IVs Eve needs
Consider again key K3
Suppose IV = (2,253,0)
Then after i=3 initialization step
IVs other than (3,255,V) can work!
Easy to determine which IVs are useful
54
Engineering security protocols is difficult
◦ One can combine otherwise strong building
blocks in a wrong way and obtain an insecure
system at the end
Example 1:
stream ciphers alone are OK
challenge-response protocols for entity authentication are
OK
but they should not be combined
Example 2:
encrypting a message digest to obtain an ICV is a good
principle
but it does not work if the message digest function is
linear with respect to the encryption function
55
[DN96] E. Dawson and L. Nielsen. “Automated
cryptanalysis of XOR plaintext strings”. Cryptologia,
(2):165–181, Apr. 1996.
[Wal00] Jesse R. Walker, “Unsafe at any key size; an
analysis of the WEP encapsulation”, 2000.
[ASW01] William A. Arbaugh, Narendar Shankar, and Y.C.
Justin Wan, “Your 802.11 Wireless Network has No
Clothes”, IEEE Wireless Communications, March, 2001.
[BGW01] Nikita Borisov, Ian Goldberg, and David Wagner,
“Intercepting Mobile Communications: The Insecurity of
802.11”, MobiCom’01, July, 2001.
[FMS01] Scott Fluhrer, Itsik Mantin, and Adi Shamir,
“Weaknesses in the Key Scheduling Algorithm of RC4”, the
8th Workshop on Selected Areas in Cryptography, 2001.
56
[New01] Tim Newsham, “Cracking WEP Keys: Applying known
techniques to WEP Keys”, 2001,
http://www.lava.net/~newsham/wlan/.
[Kor04] Korek. “chopchop (Experimental WEP attacks)”, 2004.
http://www.netstumbler.org/showthread.php?t=12489.
[BHL06] Andrea Bittau, Mark Handley, and Joshua Lackey.
“The Final Nail in WEP’s Coffin”. IEEE S&P, 2006.
[TWP07] Erik Tews, Ralf-Philipp Weinmann and Andrei
Pyshkin. “Breaking 104 Bit WEP in Less Than 60 Seconds”,
WISA, 2007.
57
