Transcript lecture

Cryptography in Public Wireless Networks
Mats Näslund
Communication Security Lab
Ericsson Research
[email protected]
Feb 27, 2004
Outline
•
•
•
•
Overview of GSM Cryptography
Some possible “attacks” on GSM
Overview of WLAN Cryptography
How problems in one technology can spread
to another
• How can you in practice fix a crypto problem
when thousands of devices are out there
• Overview of “3G” UMTS Cryptography
GSM Security Overview
History – GSM Security
• Use of a smart card SIM – Subscriber Identity Module,
tamper resistant device containing critical subscriber
information, e.g. 128-bit key shared with Home Operator
• SIM is the entity which is authenticated, basis for roaming
• Initial GSM algorithms (were) not publicly available and
under the control of GSM-A, new (3G) algorithms are open
• GSM ciphering on “first hop” only: stream ciphers using
54/64 bit keys, future 128 bits
• One-sided challenge-response authentication
• Basic user privacy support (“pseudonyms”)
• No integrity/replay protection
History – GSM Security
Access security
GPRS - Confidentiality:
GEA1
GEA2
GEA3 (new, open)
RBS
SGSN
Base Station Controller
CS - Confidentiality,
A5/1
A5/2
A5/3 (new, open)
Radio Base Station
MSC
Authentication:
A3 Algorithm
GSM Authentication: Overview
Home Network
Ki
Req(IMSI)
RAND
RAND, Kc
RES
RAND, XRES, Kc
MSC/VLR
RBS
Ki
Visited Network
RES = XRES ?
AuC/HLR
GSM Autentication: Details
A3 and A8: Authentication and key derivation (proprietary)
A5: encryption (A5/1-4, standardized)
(No netw auth, no integrity/replay protection)
Radio i/f
Phone
rand (128)
SIM Ki
(128) A3
A8
res (32)
frame#
data/speech
Kc (64)
A5/x

encr frame
Cryptographic Transforms in Wireless
Wireless is subject to
• limited bandwidth
• bit-errors (up to 1% RBER)
As consequence, most protocols:
• use stream ciphers (no padding, no error-propagation)
• do not use integrity protection (data expansion, loss)
GSM Encryption I: A5/1
Sizes: 23, 22, 19 bit (i.e. 64 bit keys)
L1
L2
cc

output
L3
“shift Li if middle bit of Li agrees with
majority of middle bits in L1 L2 L3”
Status of A5/1
All Ax algorithms initially secret.
A5/1 ”leaked” in mid 90’s. A few attacks found.
[Biryukov, Wagner, Shamir 01]: 300Gb precomputed
data and 2s known plaintext  retrieve Kc  1min.
Little “sister”, A5/2 (reverse-engineered @Berkeley)
GSM Encryption II: A5/2 (Export Version)
majority(a, b, c) = ab + bc + ca
August 2003…
Let’s take a closer look…
A5/2 (clock control)
R4 controls
clocking
Ri (i =1,2,3) is
clocked iff its
”associated”
bit agrees with
majority of the
3 bits
(At least two
clocked)
3 ”associated”
bits, one per
R1-R3
The A5/2 Algorithm (details)
First, set all four Ri to zero.
1. Kc (64 bits) bitwise sequentially XORed onto each Ri
2. frame # (21 bits) bitwise sequentially XORed onto each Ri
3. Force certain bit in each Ri to ”1”
4. Run for 99 ”clocks” ignoring output
5. Run for 228 ”clocks” producing output
}
exploited
by attack…
Idea behind the attack
A5/2 is highly ”linear”, can be expressed as linear equation
system in 660 unknowns 0/1 variables, of which 64 are Kc
If plaintext known, each 114-bit frame gives 114 equations
Only difference between frames is that frame number
increases by one.
After 6 frames (in reality only 4) we have > 660 equations
 can solve!
If plaintext unknown, can still attack thanks to redundancy
of channel coding (SACCH has 227 redundant bits per
each 4-frame message).
Attack efficiency
Off-line stage (done once):
Storage for ”matrices”: approx 200MB
Pre-processing time: less than 3 hrs on a PC
On-line attack stage:
Requires 4-7 frames sent from UE on SACCH.
Retrieving Kc then takes less than 1 second.
Hardware requirement: normal PC and GSM capable receiver
Consequence 1: Passive attacks in A5/2 Network
(Eavesdropping)
1 RAND, RES (and Kc)
2 Cipher start A5/2
< 1 sec of traffic
New attack
PC
Kc, Plaintext
< 1 sec
Consequence 2: Active attacks in any Network
(False base-station/man-in-the-middle attacks)
2
3
6
8
9
RAND
RES
Cipher start A5/2
Cipher stop
Cipher start A5/1
1 RAND
4 RES
5 Cipher start A5/1
7 Attack:: Kc
Consequence 3: Passive + Active attack
1 RAND, RES (and Kc)
2 Cipher start A5/1
Record
1 RAND, RES (and Kc)
2 Cipher start A5/2
Kc
WLAN (IEEE 802.11b) Security Overview
Wireless LAN (802.11b, WEP) Security
24 bits
random/per packet
Will repeat:
- for sure, after 224 msgs
-after 5000 msgs (average)
 “two-time pad”
40-104 bits
Network fixed!
IV k
RC4
CRC
keystream

msg
CRC(msg)
cipher
WLAN Security Problem No 2
CRC is linear: CRC(msg  ) = CRC(msg)CRC)
and so is any stream cipher:
Encr(k, msg ) = Encr k, msg)  
Alice

Bob
keystream
m
CRC(m)

CRC()
c’

keystream
m
c
Eve: 
c’
CRC(m )
WLAN Security Problem No 3
RC4 has only one “input”, the key.
This is “solved” by:
k
IV
k
IV
RC4
IV || k
append
RC4
[Fluhrer, Mantin, Shamir, 2001]:
The first bits of the RC4 key have significant “influence”
on the RC4 ouput. Even if k is 1000 bits, knowing IVs
makes it possible to break the WLAN encryption.
WLAN Security Problem No 4
Authentication protocol:
chall
res
keystream
k

k
chall = res
RC4
Observing a single “authentication”
enables impersonation…
WLAN-Cellular Interworking Architecture
Node B
UTRAN
3GPP
Home
Network
SGSN
RNC
Gn
Iu
Gr(MAP) HSS
Node B
GGSN/FA
AuC
HLR
E.g. SIM access
over Bluetooth
or SIM reader
Subscriber Mgmt
AAA
Charging/Billing
AP
Radius/
Diameter
WRAN
WSN/FA
Proxy
AAA
AP
“HOTSPOT”
Motive: Mobile operators
want to offer “hot-spots”
for subscriber base.
IP
Internet/
Intranet
3GPP
Visited
Network
Signalling Data
Signalling and
User Data
WLAN/GSM Interworking Problems
GSM Security is not perfect, but “astronomically”
better than WLAN (WEP). Can SIM re-use in
WLAN threaten also GSM (and conversely)?
WLAN improvements under way, but will take
some time.
Major GSM upgrades not feasible (expensive,
and we will soon have 3G anyway…)
Security Placement in Protocol Stack
L5 (application)
“TLS/SSL”
L4 (transport)
L3 (networking)
“IPsec”
WLAN sec L2 (media access control)
L1 (physical)
GSM sec
Fix by “gluing” on
higher layers, invisible
to lower layers
Security problems,
risk of bad “interaction”
Problem 1: Bad WLAN Encryption/Integrity
Awaiting WLAN fix, use e.g. IPsec and keys
derived from SIM
Problem 2: Key Material Need
SIM can only provide one 64-bit key, good
encryption + integrity might need e.g. 256 bits.
Solution: bootstrap on top of SIM procedure
SIM/Terminal
K1 = f(A8(RAND1) )
K2 = f(A8(RAND2) )
…
Network
RAND1, RAND2,…
Problem 2: WLAN Replay Attacks
Anybody can put up a “fake” WLAN AP at a very
modest cost.
Record-GSM-then-WLAN-replay attacks possible.
 Network authentication must be added.
SIM/Terminal
Network
RAND0
RAND1, RAND2,…, MAC(k, RAND0,…)
Check MAC
K1 = f(A8(RAND1))
K2 = f(A8(RAND2))
…
Problem 3: GSM Replay Attacks
GSM has no replay protection either.
Record-WLAN-then-GSM-replay attacks possible.
Too expensive to add GSM network authentication.
 Previous A5/2 problems must be fixed
(As seen, also needed for GSM security as such)
Ideas for GSM (A5/2) Improvements
Requirements
There are millions of mobile phones and SIMs and
Thousands of network side equipment that potentially
need upgrades to fix A5/2 problems. Need to affect
as little as possible.
Recall the “security-relevant” nodes:
MSC/VLR
AuC/HLR
RBS
Visited Network
Home Network
Possible fix I
Home net (HLR/AuC) signals ”special RAND”
(fixed 32-bit prefix) and algorithm policy in
RAND: A5/x allowed iff xth bit of RAND = 1
1 RAND, RES (and Kc)
2 Cipher start A5/x
+ Simple (Home net+phone)
- 40 bits of RAND ”stolen”,
impact on security?
Possible fix II (Ericsson)
A5/x
Phone
New alg: A5/x’
SIM
RAND
Alg_id
f
+ Simple (visited net+phone)
+ Security ”understood”,
key separation
- Relies more on visited net
A5/x
A5/x

encr frame
UMTS Security Overview
3G Security – UMTS, Improvements to GSM
• Mutual Authentication with Replay Protection
• Protection of signalling data
– Secure negotiation of protection algorithms
– Integrity protection and origin authentication
– Confidentiality
• Protection of user data payload
– Confidentiality
• “Open” algorithms (block-ciphers) basis for security
– AES for authentication and key agreement
– Kasumi for confidentiality/integrity
• Security level (key sizes): 128 bits
• Protection further into the network
UMTS – Security
Integrity & Confidentiality
UIA & UEA algorithms (based on KASUMI)
Node B
SGSN
Radio Network Controller
Node B
MSC
UMTS – Authentication and Key Agreement AKA
Home Network
Looks a lot like GSM, but…
Ki
Req(IMSI)
RAND, AUTN
RAND, AUTN
RES
RAND, XRES, CK, IK, AUTN
MSC/VLR
Ki
RBS
Allows check of
authenticity and
“freshness”
AuC/HLR
Visited Network
RES = XRES ?
Integrity protection
key
UMTS AKA Algorithms
AUTN
XRES
CK
IK
Ek = AES
UMTS Encryption: UEA/f8
COUNT || BEARER || DIR || 0…0 (64 bits)
Kasumi
m
(const)
CK
(128 bits)

“Masked” offset avoids
known input/output pairs

Kasumi
“Counter” avoids
short cycles
c=1
Kasumi

c=2
Kasumi
keystream

c=B
Kasumi
Inside Kasumi (actually: MISTY)
8 rounds of:
32 bits
+
32 bits
FO
k
security  s8
(3 rounds)
16 bits
16 bits
9 bits
FI
S9
+
+
FI
S7
+
+
FI
S9
+
+
security  s4
7 bits
security  s2
sec.
s
UMTS Integrity Protection: UIA/f9
COUNT || FRESH
Kasumi
IK
m’
M1
M2
MB



Kasumi
Kasumi
Kasumi




Variant of CBC-MAC
(Used only on signaling, not on user data)
Kasumi
MAC
(left 32 bits)
Comparison of Security Mechanisms
GSM
GPRS
WCDMA
Confidentiality
- Algorithm
- Key length
- Public review
- Signalling
- User data
- Deployed
Integrity
- Algorithm
- Key length
- Tag length
- Public review
- Signalling
- User data
- Deployed
A5/1 &
A5/2
64 (54)
No
Yes
Yes
Yes
64 (128)
“Yes”
Yes
Yes
No
GEA1 &
GEA2
64 (40)
No
Yes
Yes
Yes
64 (128)
No
Yes
Yes
No
128
Yes
Yes
Yes
ongoing
-
-
-
-
-
-
-
-
UIA (f9)
128
32
Yes
Yes
No
ongoing
A5/3
GEA3
UEA (f8)
Any Public Key Techniques?
So far, only mentioned symmetric crypto, but public
key is also used, typically for key-exchange (RSA,
Diffie-Hellman, elliptic curves…):
• on “application level”, e.g. WAP
• for inter-operator signaling traffic
In general, too heavy for “bulk” use.
Summary
• Despite some recent attacks on GSM security,
“2G” security is so far pretty much a success story
Main reason: convenience and invisibility to user
• Insecurity in one system can affect another when
interacting
• “Fixing” bad crypto is easier said than done,
practical cost is an issue
• “3G” crypto significantly more open and
well-studied  higher confidence