Muli Ben-Yehuda's journal

Rough and partial notes from Elad Barkan‘s Security
Weaknesses in the GSM Cellular System talk. For most of the
excellent talk, I was too busy listening to take notes. Any mistakes
here are more than likely mine, not Elad’s.

GSM uses algorithms called A3/A8 for authentication and key exchange,
and an algorithm called A5 for encryption.

Most operators use COMP128 for A3 and A8, COMP128 is not a trapdoor
function (one way function), and was thoroughly broken.

A5 is a PRNG, input is Kc and Frame#, output is a one time pad used as
keystream. There are several versions of A5:

• A5/0 – no encryption
• A5/1 – strong encryption
• A5//2 – weak encryption
• A5/3 – newest algorithm based on KASUMI – not used yet, believed
  to be safe. Based on sound cryptographic protocols and open for
  review.

All of the previous attacks against A5 are known plaintext attack, and
it is not clear how can an attacker gain the known plaintext.

Elad et al present a cyphertext only attack, with less than a second
of cyphertext required!

The GSM design flow is that is uses error correction codes, but
wrong. The usual way is message -> cyphertext -> coded cyphertext, the
GSM way: message -> coded message -> encrypted-coded-message. GSM
introduces HUGE redundancy into every message – basically every bit is
repeated again at a known location. Gives us plenty of info for an
algebraic attack against the cyphertext.

Attack is less than a second on a pc, against cyphertext only, on
A5/2. A5/1 is less trivial, but doable, given enough pre-computation
and storage.

Another flaw: the session initiation stage uses any of the A5 protocols
the base station tells the phone to use, and the base station is never
required to authenticate to the phone. Simple man-in-the-middle attack
allows us to tell the phone to use weak A5/2 for session initiation
stuff, and get all of the phone’s secret information. Even if the
network uses A5/1, by the time the phone switches to A5/1, we know its
secret and can decrypt everything.