A5/1
|
|
A5/1 is a stream cipher used to provide over-the-air voice privacy in the GSM cellular telephone standard. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weakness in the cipher have been identified.
| Contents |
History and usage
A5/1 is used in Europe; a weaker cipher, A5/2, is used elsewhere. Both ciphers, developed in 1989, were initially kept secret. However, the general design was leaked in 1994, and the algorithms were entirely reverse engineered in 1999 by Marc Briceno from a GSM telephone. In 2000, around 130 million GSM customers relied on A5/1 to protect the confidentiality of their voice communications.
Security researcher Ross Anderson reported in 1994 that "there was a terrific row between the NATO signals agencies in the mid 1980's over whether GSM encryption should be strong or not. The Germans said it should be, as they shared a long border with the Evil Empire; but the other countries didn't feel this way, and the algorithm as now fielded is a French design. [1] (http://groups.google.com/groups?selm=2ts9a0%2495r%40lyra.csx.cam.ac.uk)
Description
A5-1.png
GSM phone conversations are sent as sequences of frames. One frame is sent every 4.6 milliseconds and is 228 bits in length — 114 bits for the communication in each direction. A5/1 is used to produce 228 bits of key stream which is XORed with the frame. A5/1 is initialised using a 64-bit key together with a publically-known 22-bit frame number. In fielded GSM implementations 10 of the key bits are fixed at zero, resulting in an effective key length of 54 bits.
A5/1 is based around a combination of three linear feedback shift registers (LFSRs) with irregular clocking. The three shift registers are specified as follows:
| LFSR number | Length in bits | Characteristic polynomial | Clocking bit | Tapped bits |
|---|---|---|---|---|
| 1 | 19 | <math>x^{19} + x^5 + x^2 + x + 1<math> | 8 | 13, 16, 17, 18 |
| 2 | 22 | <math>x^{22} + x + 1<math> | 10 | 20, 21 |
| 3 | 23 | <math>x^{23} + x^{15} + x^2 + x + 1<math> | 10 | 7, 20, 21, 22 |
The bits are indexed with the least significant bit (LSB) as 0.
The registers are clocked in a stop/go fashion using a majority rule. Each register has an associated clocking bit. At each cycle, the clocking bit of all three registers is examined and the majority bit is determined. A register is clocked if the clocking bit agrees with the majority bit. Hence at each step two or three registers are clocked, and each register steps with probability 3/4.
Initially, the registers are set to zero. Then for 64 cycles, the 64-bit secret key is mixed in according to the following scheme: in cycle <math>0\leq{i}<64<math>, the ith key bit is added to the least significant bit of each register using XOR —
- <math>R[i] = R[i] \oplus K[i].<math>
Each register is then clocked.
Similarly, the 22-bits of the frame number are added in 22 cycles. Then the entire system is clocked using the normal majority clocking mechanism for 100 cycles, with the output discarded. After this is completed, the cipher is ready to produce 228 bits of output key-stream.
Security
A number of attacks on A5/1 have been published. Some require an expensive preprocessing stage after which the cipher can be attacked in minutes or seconds. Until recently, the weaknesses have been passive attacks using the known plaintext assumption. In 2003, more serious weaknesses were identified which can be exploited in the ciphertext-only scenario, or by an active attacker.
Known-plaintext attacks
In 1997, Golic presented an attack based on solving sets of linear equations which has a time complexity of 240.16 (the units are in terms of number of solutions of a system of linear equations which are required).
In 2000, Alex Biryukov, Adi Shamir and David Wagner showed that A5/1 can be cryptanalysed in real time using a time-memory tradeoff attack, based on earlier work by Golic (1997). One tradeoff allows an attacker to reconstruct the key in minutes from two second's worth of known plaintext, but he must first complete an expensive preprocessing stage which requires 248 steps to compute around 300 GB of data. Several tradeoffs between preprocessing, data requirements, attack time and memory complexity are possible.
The same year, Eli Biham and Orr Dunkelman also published an attack on A5/1 with a total work complexity of 239.91 A5/1 clockings given 220.8 bits of known plaintext. The attack requires 32 GB of data storage after a precomputation stage of 238.
Ekdahl and Johannson (2003) published an attack on the initialisation procedure which breaks A5/1 in a few minutes using 2–5 minutes of conversation plaintext. This attack does not require a preprocessing stage. In 2004, Maximov et al improved this result to an attack requiring "less than one minute of computations, and a few seconds of known conversation".
Attacks on A5/1 as used in GSM
In 2003, Barkan et al published several attacks on GSM encryption. The first is an active attack. GSM phones can be convinced to use the much weaker A5/2 cipher briefly. A5/2 can be broken easily, and the phone uses the same key as for the stronger A5/1 algorithm. A second attack on A5/1 is outlined, a ciphertext-only time-memory tradeoff attack which requires a large amount of precomputation.
See also
References
- Elad Barkan, Eli Biham and Nathan Keller, Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication, CRYPTO 2003, pp600–616 (PDF) (http://cryptome.org/gsm-crack-bbk.pdf).
- Eli Biham and Orr Dunkelman, Cryptanalysis of the A5/1 GSM Stream Cipher. INDOCRYPT 2000, pp43–51.
- Alex Biryukov, Adi Shamir and David Wagner, Real Time Cryptanalysis of A5/1 on a PC, FSE 2000, pp1–18 (HTML) (http://cryptome.org/a51-bsw.htm).
- Patrik Ekdahl and Thomas Johansson: Another attack on A5/1. IEEE Transactions on Information Theory 49(1), pp284–289, 2003 (PDF) (http://www.it.lth.se/patrik/papers/a5full.pdf).
- Jovan Dj. Golic, Linear Statistical Weakness of Alleged RC4 Keystream Generator, EUROCRYPT 1997, pp226–238 (HTML) (http://jya.com/a5-hack.htm).
- Greg Rose, A precis of the new attacks on GSM encryption, QUALCOMM Australia, 10 September 2003, (PDF) (http://www.qualcomm.com.au/PublicationsDocs/GSM_Attacks.pdf).
- Alexander Maximov, Thomas Johansson and Steve Babbage, An Improved Correlation Attack on A5/1, Selected Areas in Cryptography 2004, pp1–18.
External links
- A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms (http://www.mirrors.wiretapped.net/security/cryptography/algorithms/gsm/a5-1-2.c)
- Ross Anderson's 1994 post (http://groups.google.com/groups?selm=2ts9a0%2495r%40lyra.csx.cam.ac.uk)