Project

General

Profile

A5-GMR-1 Cipher

Description

The cipher is heavily inspired from A5/2 and is based on 4 LFSR that are irregularely clocked and whose output is combined through a non linear function. See the schema below :

A5-GMR-1 Cipher schematic

  • M is the majority function
  • Clocking is entirely controlled by R4. The 3 clock bits are compared to their majority and if they match, the corresponding register is clocked.
    • Bit 15 for R1
    • Bit 6 for R2
    • Bit 1 for R3

The initialization of the cipher from the Key and Frame number. Basically the frame number bits are xored with the key, then the cipher is forcefully clocked for 64 cycles, each time xoring one bit of the (Key xor FN) with each of the feedback path of the LFSR.

Then comes the mixing stage where the cipher is run normally for 250 cycles, just discarding the output.

And finally keystream is ready to be produced. First for the downlink and then for the uplink. Actual length depends on channel type but for FACCH3 for example you'd produce 96 bits for the downlink direction (Sat -> Phone) and then 96 bits for the uplink direction (Phone -> Sat). Note that the role of uplink and downlink can be reversed when dealing with "Terminal-to-Terminal" calls.

Credits goes to Benedikt Driessen, Ralf Hund, Carsten Willems, Christof Paar, and Thorsten Holz for their reversing work, extracting this from the Thuraya_SO2510 firmware.

Implementation

You can find the actual implementation here : http://cgit.osmocom.org/cgit/osmo-gmr/tree/src/l1/a5.c

Cryptanalysis

RUB Attack on TCH3

In addition to reversing the cipher, the team at RUB also has developed a cipher text only attack on the TCH3 channel (used to transport voice frames). Their work is available at http://gmr.crypto.rub.de/paper/paper-2.pdf .

A quick summary of the results:
  • 350 Gb of offline data
  • Requires 32 consecutive TCH3 frames received without errors
  • Online phase took ~ 40 min on a decent machine

FACCH3 known plaintext

When looking at real world data (see Example_Data), it appears quickly that the first 3 L2 frames transmitted right after a CIPHER MODE COMMAND are ciphered LAPSat acknowledgements. The only variable fields in those is the N(R) field which is only a few bits long. Also value N(R) can be deduced from the last acknowledgement before ciphering was turned on.

Theses known frames yield a total of 12 known burts, right after ciphering is turned on.

Attack on FACCH3

Introduction

Although the attack presented by the RUB team works, TCH3 doesn't appear as an ideal candidate for attack, especially when compared with the FACCH3 channel used for the control channel during call establishment:

  • There is relatively little redundancy in TCH3 frames, therefore requiring a high number of frames to gain enough equations. Especially when compared with FACCH3 where each bit of payload is quadrupled before being transmitted.
  • TCH3 uses pi/4-DQPSK which is harder to demodulate than the pi/4-DBPSK used by FACCH3. This yields more bit errors and those can prevent the attack from working.
  • TCH3 has no known plaintext, preventing any kind of known-plaintext attack. FACCH3 has some very predictable bursts (see above).
  • FACCH3 is also used to negotiate TCH6/TCH9 channels for CSD calls, making the attack work for CSD as well while TCH3 is specific to voice calls.

Since A5-GMR-1 is heavily based on A5/2, it makes sense to look at the existing attacks on A5/2 and adapt them to GMR-1. The most interesting paper on the subject is "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication" by Elad Barkan, Eli Biham and Nathan Keller. It can be found here: http://cryptome.org/gsm-crack-bbk.pdf . Some explanations can be found in this report: http://www.daimi.au.dk/~rwl/crypto/report.pdf although it's not entirely correct, it can help to read it.

Attack description

FIXME: Write this

Results

Both known-plaintext and ciphertext-only variants have been implemented.

The first variant uses the known FACCH3 plaintext. If you have at least 8 consecutive known bursts (or just 4 burts but with the right alignment of frame numbers), the key can be recovered with as little as 42 Mo of offline storage and in no more than 500 ms. If only 4 known plaintext bursts are available, offline tables are required for every possible FN-XOR, raising the offline storage requirement to 2.1 Go.

The second variant uses the redundancy within FACCH3 to build a ciphertext only attack. It requires 8 consecutive ciphered bursts belonging to two L2 frames. It requires about 5 Go of offline table and takes roughly 1 second to recover the key.

The offline tables for both of theses takes only a few hours to be computed on a decent machine. It's also possible to reduce this time and the storage space by focusing only on the most frequent FN-XORs. The offline tables depend on the XOR between the frame numbers of each of the bursts collected, and some XOR combinations are much more likely than others, so if you have more than the minimum of data available, you have the freedom to pick which burts to use and chances are one of the combinations will have one of the most common FN-XOR sequence.

Add picture from clipboard (Maximum size: 48.8 MB)