Transcript IP - The Internet Protocol

W4140 Network Laboratory
Lecture 12
Dec 4 - Fall 2006
Shlomo Hershkop
Columbia University
Announcements
 Last week of classes
 Was going to have a wireless lab




DHCP – wireless
AP and peer wireless networks
Wireless eavesdropping
Wireless attacks
 Rather you start to wrap up phase II
 Will go over deliverables today
Overview
 Phase II
 Wireless technology
 Since we have been dealing with wired
network technology would like to
contrast it to wireless
 Lots to cover this is only a brief overview
of relevant technology
Final
 We will be having a short written final for
the lab course covering topics familiar from
the labs.
 Straightforward exam making sure you
understand what we have covered
 Will be enough if you look over your lab notes
 Either can have it next Monday during class
time or during final week when it would be
convenient for everyone
Phase II
 We will be having a pizza party for the
phase II presentations
 Sometime during final week when wont conflict
 Have lunch and every group will give a 15
minute overview of what they did
 Feedback
 Will work with you on wrapping up your report
and help you submit it to a conference
proceedings if you want to get published
Phase II
 Would also like to archive the work, so
please while generating the work capture
traffic (tcpdump/ethereal) and will post
them next to your reports
 Try to use visualization to show a point of
your work, as opposed to huge log and
some random point in the log
 Picture still worth 1000 words
Phase II Presentation
 Overview of project
 Who
 What
 why





Overview of background info and tools used
Experiments to show idea
Results
Explanation of the results
Where this work can be taken
Written report
 Should be pdf
 Outline a few paragraph on what the goal
and results of project
 Background info
 Tools
 Experiments
 Results
 Results explanation
 Future work
 References and code/tools/links etc
 Any Questions ??
Credit
 Some of the following slides were
taken from internet sources
 Uconn - Prof. Lili Qiu, Prof. Jim Kurose,
and Don Towsley
 Others
 Purdue - Pascal Meunier, Ph.D., M.Sc.,
CISSP
Wireless Applications
Why Wireless?




Flexible
Low cost
Easy to deploy
Support mobility
Wireless Technologies
BW
UWB
WiMax
WiFi
3G
Bluetooth
RFID
range
Basics of Wireless Communication





Signal
Frequency allocation
Signal propagation
Antennas
Multiplexing
Overview of Wireless Transmissions
sender
analog
signal
bit
stream
source coding
channel coding
modulation
receiver
bit
stream
source decoding
channel decoding
demodulation
Frequencies for Communication
twisted
pair
coax cable
1 Mm
300 Hz
10 km
30 kHz
VLF



100 m
3 MHz
MF
HF
1m
300 MHz
VHF
UHF
VLF = Very Low Frequency
LF = Low Frequency



LF
optical transmission
subs
MF = Medium Frequency
HF = High Frequency

Radio am/fm

TV
VHF = Very High Frequency
10 mm
30 GHz
SHF




EHF
100 m
3 THz
infrared
1 m
300 THz
visible light UV
UHF = Ultra High Frequency


Mobile phone
3G


Wifi
microwave
SHF = Super High Frequency
EHF = Extra High Frequency
UV = Ultraviolet Light
Frequencies and Regulations

ITU-R holds auctions for new frequencies, manages frequency bands worldwide (WRC, World
Radio Conferences)
Europe (MHz)
USA (MHz)
Japan (MHz)
Cellular
Phones
Cordless
Phones
Wireless
LANs
Others
GSM 450-457, 479486/460-467,489496, 890-915/935960,
1710-1785/18051880
UMTS (FDD) 19201980, 2110-2190
UMTS (TDD) 19001920, 2020-2025
CT1+ 885-887, 930932
CT2
864-868
DECT
1880-1900
IEEE 802.11
2400-2483
HIPERLAN 2
5150-5350, 54705725
RF-Control
27, 128, 418, 433,
868
AMPS, TDMA, CDMA
824-849,
869-894
TDMA, CDMA, GSM
1850-1910,
1930-1990
PDC
810-826,
940-956,
1429-1465,
1477-1513
PACS 1850-1910, 19301990
PACS-UB 1910-1930
PHS
1895-1918
JCT
254-380
902-928
IEEE 802.11
2400-2483
5150-5350, 5725-5825
IEEE 802.11
2471-2497
5150-5250
RF-Control
315, 915
RF-Control
426, 868
Ideal Signal Propagation Ranges
 Transmission range
 communication possible
 low error rate
 Detection range
 detection of the signal
possible
 no communication
possible
 Interference range
 signal may not be
detected
 signal adds to the
background noise
sender
transmission
distance
detection
interference
Signal Propagation
 Propagation in free space always like light (straight line)
 Receiving power proportional to 1/d²
(d = distance between sender and receiver)
 Receiving power additionally influenced by






fading (frequency dependent)
shadowing
reflection at large obstacles
refraction depending on the density of a medium
scattering at small obstacles
diffraction at edges
shadowing
reflection
refraction
scattering
diffraction
Multipath Propagation
 Signal can take many different paths between sender and
receiver due to reflection, scattering, diffraction
LOS pulses
multipath
pulses
LOS: Line Of Sight
signal at sender
signal at receiver
 Time dispersion: signal is dispersed over time
 interference with “neighbor” symbols, Inter Symbol
Interference (ISI)
 The signal reaches a receiver directly and phase shifted
 distorted signal based on the phases of different parts
Fading
 Channel characteristics change over time &
location
 e.g., movement of receiver and/or scatters
quick changes in the powerpower
received (short term/fast fading)
 Additional changes in

 distance to sender
 obstacles further away
short term fading
slow changes in the average power
received (long term/slow fading)

long term
fading
t
Typical Picture
Received
Signal
Power
(dB)
path loss
shadow fading
Rayleigh fading
log (distance)
Real world example
Scanning in 802.11
 Goal: find networks in the area
 Passive scanning
 Not require transmission
 Move to each channel, and listen for Beacon
frames
 Active scanning
 Require transmission
 Move to each channel, and send Probe Request
frames to solicit Probe Responses from a
network
Association in 802.11
1: Association request
2: Association response
3: Data traffic
Client
AP
Reassociation in 802.11
1: Reassociation request
3: Reassociation response
5: Send buffered frames
Client
6: Data traffic
New AP
2: verify
previous
association
Old AP
4: send
buffered
frames
Time Synchronization in 802.11
 Timing synchronization function (TSF)
 AP controls timing in infrastructure networks
 All stations maintain a local timer
 TSF keeps timer from all stations in sync
 Periodic Beacons convey timing
 Beacons are sent at well known intervals
 Timestamp from Beacons used to calibrate local
clocks
 Local TSF timer mitigates loss of Beacons
Power Management in 802.11
 A station is in one of the three states
 Transmitter on
 Receiver on
 Both transmitter and receiver off (dozing)
 AP buffers packets for dozing stations
 AP announces which stations have frames buffered
in its Beacon frames
 Dozing stations wake up to listen to the beacons
 If there is data buffered for it, it sends a poll frame
to get the buffered data
Network Security
 Pascal Meunier, Ph.D., M.Sc., CISSP
 May 2004, updated July 30, 2004
 Developed thanks to the support of Symantec
Corporation,
 NSF SFS Capacity Building Program (Award Number
0113725) and the Purdue e-Enterprise Center

Copyright (2004) Purdue Research Foundation. All rights reserved.
Outline








Architecture
Physical and link layer
Network layer
Transport layer
Application layer: DNS, RPC, NFS
Application layer: Routing
Wireless networks
More secure protocols: DNSSEC, IPSEC, IPv6
Wireless Networks
Wireless Threats
Antennas
Directionality
Range
Gain
Design Weaknesses
Implementation Weaknesses
Automated WEP crackers and sniffers
Alternatives to WEP
Interesting Wireless Uses
Burlington Northern and Santa Fe Railway Company
(BNSF) US railroad uses Wi-Fi to run 'driverless' trains
(Smith 2003).
Home Depot (Luster 2002), BestBuy (Computerworld
2002) and Lowes (Ashenfelter 2003) were famous for
being targetted by hackers sitting in the parking lots
and eavesdropping on traffic to cash registers, and
even accessing their networks through their wireless
access points.
The Navy was reportedly interested in deploying
802.11b technology to control warships (Cox 2003).
Wireless Threats
Medium is open to most attackers in the
neighborhood of a wireless node
Near-impossibility of establishing a clear physical
security boundary
Higher gain antennas can be used to overcome
distance or a weak signal
Remote attackers can aim at:
The physical layer
The link layer
Media Access Control (MAC)
Logical link
The network layer
Threats
DoS attacks
Jamming
Fake collisions (Request to send, see slides on
CSMA/CA)
Amplification
Integrity attacks
Packets captured, modified and reinjected
Confidentiality attacks
Capture passwords, authentication tokens, etc...
Authentication and Accountability attacks
Anonymity for attacker
Reassign accountability to network or account owners
Physical Layer
CIA - confidentiality, integrity,
availability
Coverage vs Risk
Antenna gain vs transmission power
Question
Which property of “CIA”
(confidentiality, integrity, availability)
can’t you guarantee in any wireless
network?
How about a warship that is steered
and controlled through wireless
networks. What could happen?
Answer
You can’t guarantee availability,
because wireless networks can be
jammed.
A warship controlled through a
wireless network could stop responding
and continue on a bad course (collision
or otherwise)
Wireless Coverage is Risk
The potential number of locations from
which attackers can operate is proportional to
the area covered.
Areas you physically control may not be as
risky
The size of the area is not completely under
your control, because attackers can use
arbitrarily large antennas.
However, you can control the amount of
power used. How does that affect the risk?
Wireless Power
Area of a sphere = 4π r2
Total power is constant
Power/area decreases ≈ 1/r2
Big antennas capture more power (more area)
Analogy: Lenses
The bigger the lens, the more light is captured
Source
Receiving
Antenna
Wireless Power
Antenna gain is measured in dB
(decibels) as the ratio of power
captured compared to a reference
antenna.
Gain usually comes at the cost of
increased directionality
Power is concentrated in (and captured
from) a narrower field
Antenna Gain (dB)
Where P2 is the power captured by the reference
antenna
A gain of 3 dB means captured power is doubled.
A gain of 10 dB means captured power is increased
10 times.
A gain of 20 dB means captured power is increased
100 times.
Variable Power
Some access points and cards can use varying
amounts of power
Uncommon feature (Cisco, Apple Airport Ex)
How is the range changed by power?
2
1
2
2
P1 r

P2 r
How much power do you need to double the
range?
"r" is the range

Power Calculations
Double range needs 4x power
Equivalent statement:
An increase in power of 6 dB doubles the range
Triple range needs 9x power
Lower the power to decrease the risk area
Cisco Aironet Antennas Reference Guide
http://www.cisco.com/warp/public/cc/pd/witc/ao3
50ap/prodlit/agder_rg.htm
Question
Your wireless network usually has a
range of 100 feet. However you are
having a (confidential) meeting in a 10’
diameter (circular) room but want to
use a wireless access point in the room.
By how much can you decrease the
power to diminish the threats?
Answer
A 10’x10’ room approximately fits
inside a 5’ radius sphere.
100/5 = 20x range reduction
Power =1/(20x20) = 1/400
So if the power was 400 mW, 1 mW
should now be sufficient.
Question
If you want to spy on the meeting
mentioned previously, from 100 feet
away, what is the gain (in dB) of the
antenna you need?
Answer
Gain (dB) = 10 log(400)
= 10 log(4) + 10 log(100)
= 6+20
= 26 dB
Link Layer
802.11b security is focused at the link layer
Media Access Control
MAC address-based access control lists
Refer to the slides on Media Access Control in the
link layer
CSMA/CA (Collision avoidance)
Refer to the slides on spurious RTS (request to
send)
Logical Link
Logical organization of stations and access points
WEP encryption
Network Management frames
Logical Link
Wireless networks have two possible
architectures
Ad-hoc networks
Similar concept: Peer-to-Peer
Access-point-based networks (a.k.a. infrastructure
mode)
All traffic goes through the access point.
A station is a member of which network?
Association concept
Definitions
BSS (Basic Service Set)
A collection of stations (a.k.a. nodes)
communicating wirelessly together
To differentiate between closeby BSS and their
own, they use a BSSID, which has the format of a
MAC address.
All stations in one BSS use the same BSSID to
communicate
Company A's ?
Network
Company B's
Network
Infrastructure Mode
The BSSID is usually the MAC address of the
AP (Access Point)
Sophisticated APs have the capability of
handling several BSSes with different BSSIDs,
and appear as several virtual APs.
Stations using
the same BSSID
AP
Wired Network
Ad-hoc Mode
The stations use a random number as
the BSSID
The first station selects the BSSID and the
others use it
Stations using
the same BSSID
Definitions (cont.)
ESS: Extended Service Set
Composed of several BSSes joined together.
SSID: Service Set ID
Commonly known as the network name
Human-readable name
"ESSID" is sometimes used to refer to the SSID used in
the context of an ESS
Transparent for the end user
Only aware of the SSID
Traffic in an ESS may be using several different
BSSIDs if there are several APs in it.
Question
The MAC address of an access point is
used for:
a) SSID
b) ESSID
c) BSS
d) BSSID
Question
The MAC address of an access point is
used for:
a) SSID
b) ESSID
c) BSS
d) BSSID
Beacon Frames
Beacon Frames broadcast the SSID
Help users locate available networks
Layer 2 Management frames
Networks without BFs are called "closed networks"
Simply means that the SSID is not broadcast
anymore
Weak attempt at security through obscurity, to
make the presence of the network less obvious
BSSIDs are revealed as soon as a single frame
is sent by any member station
Mapping between SSIDs and BSSIDs is
revealed by several management frames that are
not encrypted
Is the SSID a Secret?
Stations looking for an access point send the SSID
they are looking for in a "probe request"
Access points answer with a "probe reply" frame,
which contains the SSID and BSSID pair
Stations wanting to become part of a BSS send an
association request frame, which also contains the
SSID/BSSID pair in clear text
So do re-association requests (see next slides) and
their response
Therefore, the SSID remains secret only on closed
networks with no activity
Conclusion: Closed networks mainly inconvenience
legitimate users
Authentication and Association
To become part of a BSS, a station must first
authenticate itself to the network
Then request association to a specific access point
The access point is in charge of authentication and
accepting the association of the station
Unless an add-on authentication system (e.g., Radius)
is used
MAC address is trusted as giving the correct identity
of the station or access point
How can this be abused?
Abusing MAC Addresses
A station doesn't know if it is talking
to a real access point, or to the same
access point every time
Access points are not authenticated by
stations
Even if they were, the MAC address can be
faked
An access point doesn't know if it is
talking to the same station every time
Authentication and
(Dis)Association Attacks
Any station can impersonate another station or
access point and attack or interfere with the
authentication and association mechanisms.
As these frames are not encrypted, the difficulty is
trivial
Disassociation and deauthentication frames
A station receiving one of those frames must redo the
authentication and association processes
With a single short frame, an attacker can delay the
transmission of data and require the station and real
access point to redo these processes
takes several frames to perform.
Disassociation Exploit
Efficiency was demonstrated by
Bellardo (2003)
Seems to have been used in the
"Black Hat" community prior to that
report
The tool "KisMAC" implements it
Availability is affected
can be selective against specific users
Authentication Modes
Authentication is done by:
a station providing the correct SSID
or through "shared key authentication"
Access point and all base stations share a secret
encryption key
Hard to deploy
Hard to change
Hard to keep secret
No accountability
Requires a station to encrypt with WEP (see next slides) a
challenge text provided by the access point
An eavesdropper gains both the plaintext and the
cyphertext
Perform a known plaintext attack
This authentication helps to crack WEP encryption!
802.11b and WEP
Remind yourself through this
presentation that 802.11b was designed
by professional software and hardware
engineers and reviewed by many such.
Be extremely careful and skeptical
about “home-brewed” security and
encryption solutions.
This is an often repeated mistake
WEP: Wired Equivalent Privacy
Cryptographic mechanism used to defend against
threats
Developed without
Academic or public review
Review from cryptologists
Has significant vulnerabilities and design flaws
Only about a quarter to a third of wireless access
points use WEP
Tam et al. 2002
Hamilton 2002
Pickard and Cracknell 2001, 2003
WEP
WEP is a stream cipher
Uses RC-4 to produce a stream of bytes that are XORed
with the plaintext
The input to the stream cipher algorithm is an "initial
value" (IV) sent in plaintext, and a secret key
IV is 24 bits long
Length of the secret is either 40 or 104 bits, for a total
length for the IV and secret of 64 or 128 bits
Marketing publicized the larger number, implying that
the secret was a 64 or 128 bit number, in a classical case
of deceptive advertising
How else can you call a protection that is 16.8
million times weaker than advertised?
XOR Encryption
0 XOR 0 = 0
1 XOR 0 = 1
1 XOR 1 = 0
(z XOR y) XOR z = y
(z XOR y) XOR y = z
Works independently of which of z or y
is the “plaintext”, "pad" or the
“ciphertext”
Stream Cipher
Given an IV and secret key, the stream of bytes (pad)
produced is always the same
Pad XOR plaintext = ciphertext
If an IV is ever reused, then the pad is the same
Knowing all the pads is equivalent to knowing the secret
Application to WEP:
The pad is generated from the combination between the IV
and the WEP key passed through RC4
Knowing all the pads is equivalent to knowing the 40 or 104bit secret
"Weak" IVs reveal additional information about the secret
Pad-Collection Attacks
There is (should be) a different pad for every
encrypted packet that is sent between AP and a station
By mapping pads to IVs, we can build up a table and
skip the RC4 step
The stream is never longer than 1500 bytes (the
maximum Ethernet frame size)
The 24 bit-IV provides 16,777,216 (256^3) possible
streams, so all the pads can fit inside 25,165,824,000
bytes (23.4 GB)
We never have to have the WEP Key
Once we have a complete table, it's as good as having
the WEP key.
Cracking WEP
Passive attacks
The presence of the attacker does not change
traffic, until WEP has been cracked
Active attacks
Active attacks increase the risk of being detected,
but are more capable.
If an active attack is reasonable (i.e., the risk of
detection is disregarded), the goal is to stimulate
traffic
Collect more pads and uses of weak IVs
Some attacks require only one pad.
How Authentication Helps
Collecting Pads
Access point sends the plaintext
Station returns ciphertext
Mallory computes
plaintext XOR ciphertext = pad
The IV was in plain text in the packet
Mallory now has a pad and matching IV
Mallory can now authenticate!
Access point sends another plaintext challenge
Mallory chooses to use the same IV and pad
Returns Pad XOR plaintext = ciphertext
Disassociation Attack to Collect
Pads
Active attack
Keep forcing stations to reauthenticate and reveal more pads by
using different IVs
Faking Being an Access Point
An attacker can also pretend to be an
access point
Run a cycle of authentication and
deauthentication to collect all the pads
from other stations
Works even if the real access points
do not require shared key
authentication
Attacker can require it while faking being
an access point
"Single Pad" Attacks
Exploits based on knowing a single
encryption pad and IV
Smurf
TCP SYN flood
UDP attacks
Defeating Firewalls with Single
Pad Attacks
Access Point behind a firewall
Mallory sends packets to Victim, who believes
they come from Mallory's accomplice (replies)
Mallory's accomplice forwards packets to Mallory
Mallory's
Victim
Accomplice
Firewall
Mallory
AP
Internet
Wired Internal Network
Results
UDP replies can be obtained unencrypted
TCP sessions can be established with
sensitive services intended to be protected by
the firewall
Intrusion detection systems will most likely
ignore responses originating from internal
hosts
the attacks can proceed undetected at this level
For all practical purposes, in this
configuration WEP has been completely
defeated.
Defenses
Provide a firewall for the wireless
network with a rule to refuse packets
that do not contain source addresses
part of the wireless network's range
Connect access points outside the
internet firewall (as if they were part of
the internet).
Can also negate some advantages of the
wireless network for legitimate users
Administrative Access
Some access points allow administrative
access from the wireless network
Or offer services on a UDP port (e.g., Apple
base stations listen on UDP port 192)
One-packet attacks directed against these
services could exploit vulnerabilities
disable the access point or make it difficult to use
Administrative access to access point should
be disabled from the wireless network
Not all access points support this feature.
More Pad Collection Attacks
Pads collected by disassociation attacks have a
limited length
Mallory sends packets to himself (or to another
wireless station) through an internet accomplice
Mallory gets the matching encrypted version
Mallory's
Accomplice
Firewall
Mallory
AP
Internet
Wired Internal Network
Defense
Requires a stateful firewall
will distinguish and block fake responses by
keeping track of wether the destination host really
made a prior request to the source IP of the
packets
A variation of the attack allows a more
sophisticated attacker to launch chosen
plaintext attacks against the encryption itself
this attack may be useful against encryptions
superseeding WEP as well
Weak Keys (a.k.a. Weak IVs)
Due to how RC4 is used in WEP, some IVs can reveal
information about the secret key
Mathematical details out of the scope of this material
Attack
FMS (Fluhrer et al. 2001) cryptographic attack on WEP
Practicality demonstrated by Stubblefield et al. (2001)
Collection of the first encrypted octet of several million
packets.
Exploits
WEPcrack (Rager 2001)
Airsnort (Bruestle et al. 2001)
Key can be recovered in under a second (after
collecting the data).
Defenses
Some wireless cards no longer generate
weak IVs (given a secret, weak IVs can be
listed; WEPcrack can do this)
Some Lucent devices are known to have
stopped generating weak IVs (binaervarianz
2003)
Other vendors should be able to do the
same, and make this attack ineffective
Integrity Attacks
What if Mallory modified a captured packet and
resent it on the wireless network?
IP destination address always in the same location
Modify packet so a copy is sent to Mallory's accomplice
Accomplice receives the decrypted packet
Based on a CRC checksum weakness (Borisov 2001)
Given the knowledge of (part of) the plaintext, a WEPprotected message can be changed at will
Mallory needs only to guess the relevant IP address
Or part of it, if Mallory's accomplice can sniff traffic
on destination network
Defenses
Use another encryption layer, such as
SSL (https) or ssh
Implementation Weaknesses
Restricted IV selection
Some access points (old Cisco firmware, notably)
produced IVs using only 18 of the 24-bit space
Lowered the storage requirement for all pads from
23.4 GB to a mere 366 MB (Meunier et al. 2002)
Poor randomness for IVs
IVs being used more often (reuses of the same
pad)
Sequential generation allow complete collection
faster
Newsham 21-bit attack
Implementation Issues
Newsham 21-bit attack
Some manufacturers generate WEP keys from text, in an
effort to increase ease-of-use
But the algorithm used produces only keys in a 21-bit space
instead of 40-bit
Brute force cracking of WEP is 2^19 (524,288) times
faster
Takes less than a minute on commodity hardware
(Newsham 2001)
Exploits
The tool KisMAC implements this attack
According to the tool's documentation, Linksys and Dlink products seemed to be vulnerable, but not 3Com
and Apple
Automated WEP Crackers and
Sniffers
AiroPeek (Commercial)
Easy-to-use, flexible and sophisticated analyzer
WEPCrack, AirSnort
Implementations of the FMA attack
NetStumbler
This is a popular network discovery tool, with GPS support. It
does not perform any cracking. A MacOS equivalent is named
"iStumbler".
KisMAC
This is a MacOS X tool for network discovery and cracking
WEP with several different methods
Kismet
swiss-army knife
LEAP: The Lightweight Extensible
Authentication Protocol
Proprietary, closed solution
was stated (without much details) by Cisco as unaffected by
WEP vulnerabilities (Cisco 2002).
LEAP conducts mutual authentication
client is assured that the access point is an authorized one
Uses per-session keys that can be renewed regularly
Makes the collection of a pad or weak IVs more difficult
Secret key can be changed before the collection is
complete
The user is authenticated, instead of the hardware
MAC address access control lists are not needed
LEAP requires an authentication server (RADIUS) to support
the access points
LEAP Attacks
Dictionary attacks
Password-based scheme
Requires user passwords be guessable
(Wright 2003)
LEAP access points don't use weak IVs
Use MS-CHAP v2, show the same
weaknesses as MS-CHAP (Wright 2003)
There are many variants of the Extensible
Authentication Protocol, such as EAP-TLS
and PEAP.
WPA
Wi-Fi Protected Access
stop-gap solution that solves issues related to the WEP
encryption itself
IVs are larger (48 bits instead of 24)
Shared key is used more rarely
Used to negotiate and communicate "temporal
keys"
"Temporal keys" are used to encrypt packets instead
Doesn't solve issues with the management frames
Collision Avoidance mechanism can still be exploited
Can be supported by most of the 802.11b hardware
 Questions ??
About These Slides

You are free to copy, distribute, display, and perform the work;
and to make derivative works, under the following conditions.





You must give the original author and other contributors credit
The work will be used for personal or non-commercial educational
uses only, and not for commercial activities and purposes
For any reuse or distribution, you must make clear to others the
terms of use for this work
Derivative works must retain and be subject to the same
conditions, and contain a note identifying the new contributor(s)
and date of modification
For other uses please contact the Purdue Office of Technology
Commercialization.
 Developed thanks to the support of Symantec
Corporation
Pascal Meunier
[email protected]
 Contributors:
 Jared Robinson, Alan Krassowski, Craig
Ozancin, Tim Brown, Wes Higaki, Melissa
Dark, Chris Clifton, Gustavo RodriguezRivera
 Questions ??
Multiplexing
Multiplexing in 4 dimensions
 space (si)
 time (t)
 frequency (f)
 code (c)
Goal: multiple use of a shared
medium
Important: guard spaces needed!
Space Multiplexing
channels ki
 Assign each region a channelk1
 Pros
c
 no dynamic coordination
necessary
 works also for analog signals
 Cons
k2
k4
k3
k6
k5
t
c
t
s1
f
s2
 Inefficient resource
utilization
f
c
t
s3
f
Frequency Multiplexing
 Separation of the whole spectrum into smaller
frequency bands
 A channel gets a certain band of the spectrum for the
whole time
k1
k2
k3
k4
k5
 Pros:
c
 no dynamic coordination
necessary
 works also for analog signals
 Cons:
 waste of bandwidth
if the traffic is
distributed unevenly
 Inflexible
t
 guard spaces
k6
f
Time Multiplex
 A channel gets the whole spectrum for a
certain amount of time
 Pros:
 only one carrier in the
medium at any time
 throughput high even
for many users
 Cons:
c
f
 precise
synchronization
necessary
t
Time and Frequency Multiplexing
 Combination of both methods
 A channel gets a certain frequency band for a certain
amount of time (e.g., GSM)
 Pros:
k1
k2
k3
k4
 better protection against
tapping
c
 protection against frequency
selective interference
 higher data rates compared to
code multiplex
 Cons:
t
 precise coordination
required
k5
k6
f
Code Multiplexing



Each channel has a unique code
All channels use the same spectrum
simultaneously
Pros:




bandwidth efficient
no coordination and
synchronization necessary
good protection against
interference and tapping
f
Cons:



c
lower user data rates
more complex signal regeneration
Implemented using spread spectrum
technology
t
MAC Layer
 Coordinate access to a shared
medium
 Requirements





Efficiency
Reliability
Fairness
Support priority
Support group communication
MAC Layer (Cont.)
Base technologies
 Frequency division multiple access (FDMA)
 Time division multiple access (TDMA)
 Code division multiple access (CDMA)
Access schemes
 Centralized
 GSM
 IS-95
 Distributed
 CSMA/CD (Ethernet)
 CSMA/CA (wireless LAN)
Example MAC Protocols
 Pure ALOHA
 Transmit whenever a message is ready
 Retransmit when ACK is not received
 Slotted ALOHA




Time is divided into equal time slots
Transmit only at the beginning of a time slot
Avoid partial collisions
Increase delay, and require synchronization
Problem: do not listen to the channel.
Example MAC Protocols
 Carrier Sense Multiple Access (CSMA)
 Listen before transmit
 Transmit only when no carrier is detected
 Variants
 1-persistent CSMA: transmit once no
carrier is detected
 CSMA/CD: abort the transmission when
collision is detected (Ethernet)
 Non-persistent CSMA: when carrier is
detected, wait a random time before a retry
(WLAN)
Hidden Terminal Problem
A
B
C
 B can communicate with both A and C
 A and C cannot hear each other
 Problem
 When A transmits to B, C cannot detect the
transmission using the carrier sense mechanism
 If C transmits, collision will occur at node B
 Solution
 Hidden sender C needs to defer
Solution for
Hidden Terminal Problem: MACA
A
B
C
 When A wants to send a packet to B, A first sends a
Request-to-Send (RTS) to B
 On receiving RTS, B responds by sending Clear-toSend (CTS), provided that A is able to receive the
packet
 When C overhears a CTS, it keeps quiet for the
duration of the transfer
 Transfer duration is included in both RTS and CTS
Reliability
 Wireless links are prone to errors.
High packet loss rate detrimental to
transport-layer performance.
 Mechanisms needed to reduce packet
loss rate experienced by upper layers
A Simple Solution to
Improve Reliability
 When B receives a data packet from
A, B sends an Acknowledgement
(ACK) to A.
 If node A fails to receive an ACK, it
will retransmit the packet
A
B
C
IEEE 802.11 Wireless MAC
 Support broadcast, multicast, and
unicast
 Uses ACK and retransmission to achieve
reliability for unicast frames
 No ACK/retransmission for broadcast or
multicast frames
 Distributed and centralized MAC
access
 Distributed Coordination Function (DCF)
 Basic CSMA/CA
 RTS/CTS extension
 Point Coordination Function (PCF)
IEEE 802.11 DCF
 CSMA/CA
 Wireless MAC protocols often use
collision avoidance techniques, in
conjunction with a (physical or virtual)
carrier sense mechanism
 Uses RTS-CTS exchange to avoid
hidden terminal problem
 Any node overhearing a CTS cannot
transmit for the duration of the transfer
 Once channel becomes idle, the node
waits for a randomly chosen duration
before attempting to transmit.
IEEE 802.11
RTS = Request-to-Send
RTS
A
B
C
D
E
F
Pretending a circular range
IEEE 802.11
RTS = Request-to-Send
RTS
A
B
C
D
E
F
NAV = 10
NAV = remaining duration to keep quiet
IEEE 802.11
CTS = Clear-to-Send
CTS
A
B
C
D
E
F
IEEE 802.11
CTS = Clear-to-Send
CTS
A
B
C
D
E
NAV = 8
F
IEEE 802.11
•DATA packet follows CTS. Successful data reception
acknowledged using ACK.
DATA
A
B
C
D
E
F
IEEE 802.11
ACK
A
B
C
D
E
F
CSMA/CA
Carrier sense
 Physical carrier sense
 Carrier sense threshold
 Virtual carrier sense using Network Allocation
Vector (NAV)
 NAV is updated based on overheard
RTS/CTS/DATA/ACK packets
 Nodes stay silent when carrier sensed
(physical/virtual)
 Collision avoidance
 Backoff intervals used to reduce collision
probability
Backoff Interval
 When transmitting a packet, choose a
backoff interval in the range [0, CW]
 CW is contention window
 Count down the backoff interval when
medium is idle
 Count-down is suspended if medium
becomes busy
 Transmit when backoff interval reaches 0
DCF Example
B1 = 25
wait
B1 = 5 (leftover)
data
data
B2 = 20
cw = 31
wait
B2 = 15
B2 = 10
(leftover)
B1 and B2 are backoff intervals
at nodes 1 and 2
Backoff Interval
 The time spent counting down backoff
intervals is a part of MAC overhead
 Important to choose CW
appropriately
 large CW  large overhead
 small CW  may lead to many collisions
(when two nodes count down to 0
simultaneously)
 Dynamically change CW depending on
Binary Exponential Backoff
in DCF
 When a node fails to receive CTS in
response to its RTS, it increases the
contention window
 CW is doubled (up to an upper bound)
 More collisions  longer waiting time to
reduce collision
 When a node successfully completes
a data transfer, it restores CW to
CWmin
MILD Algorithm in MACAW
 MACAW uses exponential increase
linear decrease to update CW
 When a node successfully completes a
transfer, reduces CW by 1
 In 802.11 CW is restored to CWmin
 In 802.11, CW reduces much faster
than it increases
 MACAW can avoid wild oscillations of
CW when many nodes contend for
the channel
802.11
Overhead
Random
backoff
RTS/CTS
Data Transmission/ACK
 Channel contention resolved using
backoff
 Nodes choose random backoff interval
from [0, CW]
 Count down for this interval before
transmission
 Backoff and (optional) RTS/CTS
handshake before transmission of
data packet
802.11 Frame Priorities
Busy
DIFS
PIFS
SIFS
content
window
Frame transmission
Time
 Short interframe space (SIFS)
 For highest priority frames (e.g., RTS/CTS, ACK)
 PCF interframe space (PIFS)
 Used by PCF during contention free operation
 DCF interframe space (DIFS)
 Minimum medium idle time for contention-based
services
802.11 Management Operations




Scanning
Association/Reassociation
Time synchronization
Power management
Scanning in 802.11
 Goal: find networks in the area
 Passive scanning
 Not require transmission
 Move to each channel, and listen for
Beacon frames
 Active scanning
 Require transmission
 Move to each channel, and send Probe
Request frames to solicit Probe
Responses from a network
Association in 802.11
1: Association request
2: Association response
3: Data traffic
Client
AP
Reassociation in 802.11
1: Reassociation request
3: Reassociation response
5: Send buffered frames
Client
6: Data traffic
New AP
2: verify
previous
association
Old AP
4: send
buffered
frames
Time Synchronization in 802.11
 Timing synchronization function (TSF)
 AP controls timing in infrastructure
networks
 All stations maintain a local timer
 TSF keeps timer from all stations in sync
 Periodic Beacons convey timing
 Beacons are sent at well known intervals
 Timestamp from Beacons used to
calibrate local clocks
 Local TSF timer mitigates loss of Beacons
Power Management in 802.11
 A station is in one of the three states
 Transmitter on
 Receiver on
 Both transmitter and receiver off (dozing)
 AP buffers packets for dozing stations
 AP announces which stations have frames
buffered in its Beacon frames
 Dozing stations wake up to listen to the
beacons
 If there is data buffered for it, it sends a
poll frame to get the buffered data
Wired Equivalent Privacy (WEP)
 Specified in 802.11 standard for
WLAN MAC
 Protocol goals:
 Confidentiality: prevent
eavesdropping
 Access control: prevent unauthorized
access
 Data integrity: prevent tampering of
messages
 Failure: None of the security goals
are attained
WEP Authentication
 authentication procedure:
 host requests authentication from AP
 AP sends 128 bit nonce
 host encrypts nonce using shared
symmetric key
 AP decrypts nonce, authenticates host
 no key distribution mechanism
 authentication: knowing the shared key
is enough
WEP data encryption
 Host/AP share 40 bit symmetric key
(semi-permanent)
 Host appends 24-bit initialization
vector (IV) to create 64-bit key
 64 bit key used to generate stream of
keys, kiIV
IV
 ki used to encrypt i-th byte, di, in
frame:
IV
ci = di XOR ki
 IV and encrypted bytes, ci sent in
802.11 WEP encryption
IV
(per frame)
KS: 40-bit
secret
symmetric
key
plaintext
frame data
plus CRC
key sequence generator
( for given KS, IV)
k1IV k2IV k3IV … kNIV kN+1IV… kN+1IV
d1
d2
d3 …
dN
CRC1 … CRC4
c1
c2
c3 …
cN
cN+1 … cN+4
Figure 7.8-new1:
802.11encryption
WEP protocol
Sender-side
WEP
802.11
IV
header
WEP-encrypted data
plus CRC
Breaking 802.11 WEP encryption
Security hole:
 24-bit IV, one IV per frame, -> IV’s eventually
reused
 Common PCMCIA cards sets IV to zero and
increment it by 1 for each packet
 IV transmitted in plaintext -> IV reuse
detected
 Attack:
 Trudy causes Alice to encrypt known
plaintext d1 d2 d3 d4 …
 Trudy sees: ci = di XOR kiIV
 Trudy knows ci di, so can compute kiIV
802.11i: improved security
 numerous (stronger) forms of
encryption
 provides key distribution
 uses authentication server separate
from access point
802.11i: four phases of operation
STA:
client station
AP: access point
AS:
Authentication
server
wired
network
1 Discovery of
security capabilities
2 STA and AS mutually authenticate, together
generate Master Key (MK). AP servers as “pass through”
3 STA derives
Pairwise Master
Key (PMK)
4 STA, AP use PMK to derive
Temporal Key (TK) used for message
encryption, integrity
3 AS derives
same PMK,
sends to AP
EAP: extensible authentication protocol
 EAP: end-end client (mobile) to
authentication server protocol
 EAP sent over separate “links”
 mobile-to-AP (EAP over LAN)
 AP to authentication server (RADIUS over
UDP)
wired
network
EAP TLS
EAP
EAP over LAN (EAPoL)
IEEE 802.11
RADIUS
UDP/IP