Transcript RC4(v,k)

Csci388 Wireless and Mobile Security
– Wireless LAN: Introduction, WEP
Xiuzhen Cheng
[email protected]
Outline
Challenges in Wireless Communications
Introduction to IEEE 802.11 Wireless LAN
Break (5 minutes)
Intercepting Mobile Communications: The Insecurity
of 802.11
Wireless Security’s Future
Uniqueness of Wireless Communication
Uniqueness of Wireless Communication
Interference and Noise; Full connectivity can not be assumed; Battery
usage; Security
Requirements of a wireless MAC standard:
Single MAC to support multiple PHY mediums
Robust to interference
Need to deal with the hidden/exposed terminal problem
Need provision for time bounded services
Support for power management to save battery power
Ability to operate world wide: ISM band
Problems of wireless networks
Hidden Terminal
Decrease throughput
Increase delay
A
Exposed Terminal
Decrease channel
utilization
Limited energy
B
C
At B: Transmission from C collides
with transmission from A
Network partition
Mobility
Security
D
A
B
C
C unnecessarily defers its transmission
to D
802.11 System Architecture
Two basic system
architectures
Ad hoc
Infrastructure based
Access Point
Stations select an AP
and “associate” with it
Support roaming
Provide other functions
time synchronization
(beaconing); power
management, PCF;
802.11 Protocol Stack
802.11 MAC Layer
Three basic access mechanisms
CSMA/CA; DCF(CSMA/CA+RTS/CTS); PCF
DIFS: lowest priority, asynchronous data
PIFS: media priority, time-bounded service
SIFS: highest priority, short control message
Carrier sense at two levels
Physical carrier sense: done by physical layer
Virtual carrier sense at MAC layer using Network Allocation
Vector (NAV) set while RTS/CTS/Data/Ack are overheard: solves
problem of Hidden and Exposed terminal
Reduces collision by deferring transmission if any of the carrier
sense mechanisms sense the channel busy
DCF Basic Access
Basic Access
When a STA has data to send, it senses medium
The STA may transmit a MAC Protocol Data Unit (MPDA)
when medium idle time is greater or equal to DIFS
If medium is busy, wait for a random backoff time
DCF
Backoff Procedure
Backoff procedure is invoked for a STA to transfer a frame but the medium is busy
Set Backoff Timer to be random backoff time
Backoff Timer start decreasing after an idle time of DIFS following the medium
busyness
Backoff Timer is suspended when medium is busy, and won’t resume until the
medium is idle for DIFS
A frame may be transmitted immediately when Backoff Timer is 0
DCF
Recovery procedures
Collision may happen during contention
When collision happens, retransmission with a new random
selection of the backoff time, contention window is doubled.
No special rights for retransmission
DCF
Random backoff
time=random()xaSlotTime
aSlotTime: the value of the
correspondingly named PHY
characteristic (20s for DSSS)
Random(): a random integer
uniformly distributed over [0, CW]
CW (contention window)
Increases exponentially after each
retry fails (so does average backoff
time. Why to do this?)
Keep constant after reaching the
maximum
Reset after a successful
transmission
DCF RTS/CTS Scheme
RTS/CTS Scheme
Four way handshake: RTS-CTS-DATA-ACK
NAV (Network Allocation Vector)
An indicator, maintained at each STA, for the period that transmission will not be initiated
Setting and resetting NAV according to “Duration” in MAC header when
receiving a valid frame
DCF – Fragmentation
Control of the channel
Once the STA has contented for the channel, it shall continue to send
fragments until
All fragments of a MSDU or MMPDU have been sent
An ACK is not received
STA is restricted from sending additional fragments by PHY layer
Duration field
RTS/CTS: time till the end of ACK0
Fragments/ACK: time till the end of the ACK for the next fragment
Last fragment/ACK: length of ACK/0
PCF
Only available for infrastructured architecture, why?
PCF is on top of DCF
Super frame contains a contention-free period and a contention
period
Procedure (assume the media is just free):
Point coordinator (PC) polls s1 after PIFS; s1 replied with data
PC continues to poll other stations
After no reply from a station, PC waits for PIFS time, then continues to poll
other stations
After finishing, send CFE message. Then contention period starts.
Question: how time-bounded service is provided?
Other Considerations
Syschronization
Beacon signal
Power-Control
Sleep and awake states
Wakeup periodically every TIM interval
Roaming
Association request and response
Break
The WEP Protocol
Security goals of the WEP (Wired Equivalent
Privacy) protocol:
Confidentiality: Prevent an adversary from learning the
contents of your wireless traffic.
Access Control: Prevent an adversary from using your wireless
infrastructure.
Data Integrity: Prevent an adversary from modifying your
data in transit.
WEP Protocol was designed to protect the
confidentiality of user data from eavesdropping
Part of 802.11
It has been integrated by manufacturers into their
802.11 hardware.
Widespread in use.
The WEP Protocol (cont.)
Sender and receiver
share a secret key k.
Two classes of WEP
implementation:
classic WEP as documented in
standard (40-bit key)
extended version developed
by some vendors (128-bit
key)
The WEP Protocol (cont.)
In order to transmit a message M:
P = <M, c(M)>
pick Initial Vector(IV) v and generate RC4(v,k)—is a keystream
C = P  RC4(v,k)
A -> B: v, (P  RC4(v,k))
Upon receipt:
generate RC4(v,k)
P’
= C  RC4(v,k)
= P  RC4(v,k)  RC4(v,k)
=P
check if c=c(M)
If so, accept the message M as being the one transmitted
WEP, Pictorially
An Example
P
sender
C
receiver
P
Attack Practicality
Access to the transmitted data.
Need equipment capable of monitoring 2.4 GHz
frequencies.
Need to understand the physical layer of 802.11
protocol.
For active attacks, need equipment capable to
transmit at the same frequencies.
High cost, but not impractical:
“corporate espionage can be a highly profitable business.”
Passive attacks possible with off-the-shelf
equipment by modifying driver settings (Lucent
PCMCIA Orinoco wireless card).
The “Two-Time Pad” Problem
You must never encrypt two messages with the same
keystream K.
Suppose P1 and P2 are both encrypted with the
same K.
Then C1 = P1  K, and C2 = P2  K.
But then
C1  C2 = P1  K  P2  K = P1  P2
So the adversary learns the XOR of two plaintexts!
Does he know (or can guess) parts of one plaintext?
Usually, just knowing the XOR of two plaintexts is
enough to recover them.
What Does WEP Do?
The keystream for WEP is RC4(v,k).
k is a fixed shared secret, that changes rarely, if ever (in
many setups, every user shares the same k).
 If two packets ever get transmitted with the same value of v,
you reuse the keystream.
Since v gets transmitted in clear for each packet, the
adversary can even easily tell when a value of v is reused (a
"collision").
How many possible values of v are there?
v only occupies 24 bits of the header = at most there are 2^24
(about 16 million of v).
After 16 million packets, you have to repeat one!
Birthday paradox for random 24-bit v
Many 802.11 cards reset their IV counter to 0 every time they
were activated, and incremented by 1 for each packet
transmitted.
What Does WEP Do? (cont.)
This means that low IV values get reused at the beginning of
every wireless session.
Usually use the same secret k, and often many different
people use the same k.
So you can find collisions between packets sent by different people!
This makes collisions much more common.
Decryption Dictionaries
Adversary knows both the C and the P for some packets
encrypted with a given IV v.
Easy if he knows the P (pings, or spam email!).
He can also do it passively by watching for collisions.
RC4(k,v) = P  C
Note: no need to know the value of the shared secret k.
Store keystream in a table, indexed by v.
Next time a packet with an IV stored in the table passes by,
look up the keystream, XOR it against the packet, and read
the data!
Table is at most 1500 * 2^24 bytes = 24 GB
If the cards that are being used have the IV-reset-to-0
property, then most IV's will be small, and the dictionary will
be even smaller!
Message Authentication in WEP
An 802.11 receiver will accept a packet if, after decryption,
it contains a correct checksum of the plaintext.
The checksum algorithm used is CRC-32.
CRC's are used to detect random errors; they are useless
against malicious errors.
There is already a CRC at a lower layer of the protocol to
detect random bit errors in transmission.
CRC-32 Has the following properties:
It is independent of the shared secret and the IV.
It is linear: c(M  D) = c(M)  c(D)
We can make a controlled modification and get unnoticed.
Message Modification
Assume a message M was transmitted, and the
ciphertext was C and the IV was v (i.e. C and v are
known to the adversary).
C = RC4(v,k)  <M,c(M)>
A -> B: <v,C>
Possible to find C’ such that it decrypts to M’ and M’ = M  D
D = arbitrarily chosen by the attacker
Adversary -> B: <v,C’>
C’= C  <D,c(D)>
= RC4(v,k)  <M,c(M)>  <D,c(D)>
= RC4(v,k)  <M  D, c(M)  c(D)>
= RC4(v,k)  <M’, c(M  D)>
= RC4(v,k)  <M’, c(M’)>
Receiver checks that c’ = c(M’)
Accept message M’ as the one transmitted.
Message Injection
The adversary just needs to know a single
plaintext, and its corresponding encrypted packet.
A -> B: <v,C>
P  C = P  RC4(v,k)  P = RC4(v,k)
Construct M’ and P’ = <M’,c(M’)>
C’ = RC4(v,k)  P’
“A” -> B: <v,C’>
Authentication Protocol
Goal: the base station verifies that a client joining
the network really knows the shared secret key k.
The base station sends a challenge string to the
client
B->A: M
The client sends encrypted challenge:
A -> B: v, <M,c(M)>  RC4(v,k)
The base station checks if the challenge is correctly
encrypted, and if so, accepts the client.
Adversary sees a challenge/response pair for a given
key k; he can extract v and RC4(v,k).
Adversary can execute authentication protocol
himself!
Authentication Protocol (cont.)
Adversary connects to the network himself:
The base station sends a challenge string M' to the
adversary.
The adversary replies with
v, <M',c(M')>  RC4(v,k)
This is the correct response, so the base station
accepts the adversary.
Success even though he never did learn the value of
k.
Message Decryption
Useful symmetry property: the operation of
encryption is the same as the operation of
decryption with the same key.
An adversary can decrypt packets with the help of
the base station! Ways to do it:
Double-encryption
IP Redirection
Reaction attacks
Double Encryption
Join the network.
Use a second Internet connection to send the
packet to his computer over the wireless network.
The base station will encrypt this packet a second
time:
C’ = (P  RC4(v,k))  RC4(v,k) = P
Timing important to get the same IV, but not so
difficult because the base station uses sequential
IV’s.
IP Redirection
Join the network (authentication spoofing)
Take the packet to be decrypted, modify the IP
address as being his.
Transmit the modified packet to the base station
for decryption.
Base station will send the plaintext on its merry
way, straight to the adversary's machine.
IP Redirection (cont.)
The only headache: find the original destination IP
address.
Not difficult: all the incoming traffic has a
destination IP address on the wireless subnet, easy
to determine.
Fix the IP checksum.
IP Redirection (cont.)
Suppose original IP address = DH, DL
Modified IP address = DH’, DL’
newCRC = oldCRC + DH’+ DL’- DH - DL
Trick: we only know to do XOR!
Ways to go around this:
IP CRC is known: do arithmetic
IP CRC not known: get lucky
arrange that newCRC = oldCRC: change other fields.
Reaction Attacks
“Drawback”: the packet to be decrypted needs to
be a TCP packet.
Useful property: a TCP packet with TCP checksum
invalid is silently dropped.
Otherwise, get back an ACK packet (easy to
identify by its size).
Monitor the reaction of a recipient of a TCP packet
and use that to infer info about the unknown
plaintext.
Intercept <v,C>
Flip a few bits in C, recompute checksum, wait
(patiently) to see if an ACK is sent back.
Reaction Attacks (cont.)
A clever choice of what bits to flip ensures TCP checksum
remains undisturbed exactly when
Pi  Pi+16 = 1
holds.
Each time we check the reaction of the recipient to a
modified packet, we learn one more bit of the plaintext.
TCP CRC = 1’s complement addition of the 16-bit words of
message M.
1’s complement addition ~ modulo 2^16 -1
C’ = C  D, D = bit positions to flip.
We choose D: pick i arbitrarily, set positions i and i+16 of D
to 1 and the rest to 0.
Convenient property: P  D = P mod 2^16-1 holds when Pi 
Pi+16 = 1
Countermeasures
Just don't assume it's secure.
Treat your wireless network as a public network.
Put the wireless network outside your firewall.
Use another authentication protocol for packets
coming from the wireless network to internal
intranet (e.g. VPN, IPSec, ssh).
Long IV's which never repeat for the lifetime of
the shared secret (and are never duplicated across
machines sharing the same secret).
Replace the shared key more often.
Use a strong Message Authentication Code (instead
of the CRC) which depends on the key and IV.
Conclusions
Attacks on the Wired Equivalent Privacy protocol
which defeat each of the security goals of:
Confidentiality: We can read WEP-protected traffic.
Access Control: We can inject traffic on WEP-protected
networks.
Data Integrity: We can modify WEP-protected traffic in
transit.
Wireless Security’s Future
IEEE 802.11i
Phased deployment process due to the large number of 802.11
users
Three major parts of 802.11i:
Temporal Key Integrity protocol (TKIP), enhancing and replacing
WEP
Counter mode CBC-MAC for link-layer data confidentiality and
integrity
802.1x for access control
Temporal Key Integrity Protocol
Immediate replacement of WEP
Uses 48-vit vectors
Uses 128-bit encryption key
Uses per-packet keying
A shared base key, a client’s MAC address, and a packet’s
sequence number create a unique key for each packet
Avoid data-harvesting problem
Periodically rotates the broadcast key
Avoid data-harvesting problem
Uses a message integrity code (MIC)
A cryptographically protected one-way hash
Immediate packet tampering detection
TKIP is a part of WPA by the WiFi Alliance
Counter Mode with CBC-MAC
Design goals: confidentiality, integrity and
authentication
128-bit AES
48-bit IV
128-bit cipher block chaining with MAC
A required component of any 802.11i implementation
802.1x
A port-based authentication protocol
Before a successful 802.1x authentication, a wireless
client is only allowed access to the authentication
server. All other traffics are blocked at the AP
After a successful 802.1x authentication, the client is
granted access to the network
UMD researchers found that 802.1x suffers from two
attacks: session hijacking and man-in-the-middle
Readings and Homeworks
Readings for the lecture in Sep 9. Submit your reading report for
the papers on DOMINO and DoS Attack:
C.D.J. Welch and M.S. D. Lathrop, A survey of 802.11a wireless
security threats and security mechanisms, 2003.
M. Raya, J. P. Hubaux,, and I. Aad DOMINO: A System to Detect
Greedy Behavior in IEEE 802.11 Hotspots, Proceedings of the
Second International Conference on Mobile Systems, Applications,
and Services, Boston, June 2004
J. Bellardo and S. Savage, 802.11 Denial-of-Service Attacks: Real
Vulnerabilities and Practical Solutions, Proceedings of USENIX
Security Symposium, August 2003.
2 SepReadings for the lecture in Sep 2:
M.J. Hanson and D. McNamee, Efficient Reading of Papers in
Science and Technology.
N. Borisov, I. Goldberg, and D. Wagner, Intercepting Mobile
Communications: The Insecurity of 802.11, MobiCom 2001, pp. 180188.
B. Potter, Wireless Security's Future, IEEE Security and Privacy
Magazine 01(4), pp. 68-72, July-Aug. 2003.
Questions?