Mar2008

Intercepting GSM traffic

Mar2008

Agenda• Receiving GSM signals• Security• Cracking A5/1

Mar2008

GSM Network

Mar2008

BTSMar2008

Camouflage BTS

Mar2008

Summary GSM• GSM is old• GSM is big• GSM / 3G / UMTS / EDGE / WCDMA / .
• Base stations all over the placeMar2008

Receiving• Nokia 3310 / Ericsson / TSM• USRP• TI's OMAP dev kit• Commercial Interceptor

Mar2008

Example 1

Mar2008

Example 2

Mar2008

Summary Receiving• It's cheap• It's easy
• It's getting easierMar2008

Security

Mar2008

Security

Mar2008

SecurityMar2008

Commercial Interception• Active Equipment:– $70k - $500k. Order via internet.

• Passive Equipment:– $1M

Mar2008

Radio Security• A5/0, A5/2, A5/1. All broken in 1998.
• Some algorithms proprietary• IMSI / Location Information clear-text• Key is artificially weakened• Key material is reused• No indication to user
• Key Recovery Systems available

Mar2008

SIM Toolkit• There is a JVM on your SIM!
• The Operator can install programs via
OTA (== remotely, without you knowing)• Scary standard: Invisible flags, binary
updates, call-control, proprietary, ....

Mar2008

Security Summary• NoneMar2008

A5/1 Cracking

A8(Ki)

Authenticate

Kc

A5(Kc)

A8(Ki)

Kc

Conversation

A5(Kc)

Mar2008

A5/1 Cracking
Conversation
Phone Sending to BTS

Frame

A5(Kc,Frame)

Plain-text

Frame++A5(Kc,Frame)

Plain-text

Mar2008

A5/1 Cracking• Clock in 64-bit Kc and 22-bit frame number• Clock for 100 cycles• Clock for 114 times to generate 114-bits

Mar2008

Cracking A5/1
• Other attacks are academic BS.
• 3-4 Frames. Fully passive.
• Combination of Rainbow Table attackand others.

Mar2008

Cracking A5/1
• 4 frames of known-plaintext• A5/1 is a stream cipher• We can derive 4 frames of keystream
outputMar2008

Sliding Window[0|1|1|0|1|0………………………....….…....….|1|0|1|1][ 64 bit Cipherstream 0 ……….][ 64 bit Cipherstream 1 ……......][ 64 bit Cipherstream 2 ..……….]………………………….
[ 64 bit Cipherstream 50 ..……….]

Mar2008

Sliding Window• Total of 4 frames with 114-bits• 114 – 64 + 1 = 51 keystreams per frame• 51 x 4 frames = 204 keystreams total

Mar2008

Rainbow Table64-bits keystream

Password

Lanman Hash

Mar2008

Rainbow Table• Build a table that maps 64-bits ofkeystream back to 64-bits of internal
A5/1 state• 204 data points means we only need
1/64th of the whole keyspace• 258 = 288,230,376,151,711,744• About 120,000 times larger than thelargest Lanman Rainbow Table

Mar2008

How do we do this??
• 1 PC– 550,000 A5/1's per second– 33,235 years• Currently using 68 Pico E-16 FPGAs– 72,533,333,333 A5/1's per second– 3 months• Building new hardware to speed this up

Mar2008

HardwareMar2008

Rainbow Table• Cheap Attack (~30 min)– 6 350GB Hard Drives (2TB)– 1 FPGA (or a botnet)• Optimal Attack (~30 sec)
– 16 128GB Flash Hard Drives (2TB)– 32 FPGAs– Can speed it up with more FPGAs

Mar2008

Rainbow Table• 204 data points will give us 204 / 64 = 3
A5/1 internal states• So what do you do now?

Mar2008

Reverse Clocking• Load A5/1 internal state• Reverse clock with known keystream back toafter Kc was clocked in• Will resolve to multiple possible A5/1 statesMar2008

Reverse Clocking• Reverse all 3 A5/1 internal states• The common state will be the correct one• Use the internal state and clock forward
to decrypt or encrypt any packet• Can solve linear equations to derive key• But isn't really necessary

Mar2008

Conclusions• Tables will be finished in March• Commercial version in Q2/08• Will be scalable to whatever decryption
time period is required

Mar2008

Threats & Future• GSM security has to become secure.
• Data/Identity theft, Tracking• Unlawful interception• Attacks on GSM Infrastructure• Receiving and cracking GSM will
become cheaper and easierMar2008

Thank You!
• Steve– http://wiki.thc.org/gsm• David Hulton– http://www.picocomputing.com– http://www.openciphers.org• Questions?