We present an advanced brute force attack on the A5/1 keystream generator, that is still widely used in modern GSM networks. To greatly reduce the search space, we use a well-known idea, introduced by R. Anderson more than 20 years ago. The main contribution of the present paper is the implementation of Anderson's attack on a GPU platform in bit-slice technique. The preliminary estimates of the attack's speed showed that, with the use of GPUs processing power, the attack could be performed in the real time on a modern computer cluster or in a volunteer computing project. To verify our estimates with the use of the BOINC technology we launched a volunteer computing project and executed our variant of Anderson's attack within it. As a result, 10 A5/1 cryptanalysis problems were solved in 7 days in the project. The results presented in this work provide yet another proof of A5/1's cryptographic weakness that shows that this generator is totally unsuitable for transmission of any kind of sensitive data through modern GSM networks.
The A5/1 keystream generator has a key length of 64 bits. It is used to encrypt voice and SMS traffic in 2nd generation (2G) GSM networks. A5/1 is one of the most publicly recognized cryptographic algorithms.
The growth of the computational power of GPUs and FPGAs made it possible to put into practice the attack on A5/1, which was described by R. Anderson in 1994 [And]. This attack is based on reduction of the search space size from 264 to 253. The FPGA-based variant of Anderson’s attack was already performed in 2008 in the COPACOBANA project [GNR08]. So, the primary goal of our work is to demonstrate the viability of GPUbased variant of the attack. Let us note that GPUs are much easier to operate than FPGAs. Besides, the former belong to the class of consumer-grade devices and could be found in any modern PC, while the latter belong to the class of specialized equipment. With the usage of the BOINC software platform [And04], these qualities of GPUs allowed us to implement the attack in the form of a volunteer computing project using idle computational 41 40 39 38 37 36 35 34 33 32 31 3029 28 27 26 25 2423 22 21 20 capabilities of the project members home PCs. Our estimates of the attack’s speed were based on our previous work[BS16].
Let us make a brief outline of the article’s contents. In Section 2 we describe the A5/1 algorithm along with some advanced brute force attacks on it. Section 3 introduces bit-slicing technique and goes through important details of implementing Anderson’s attack. Section 4 provides a look into the internal organization of the volunteer project which was launched by us to perform the attack. Section 5 contains the retrospective of A5/1 cryptanalysis works related to our study. 2
The A5/1 keystream generator consists of 3 linear feedback shift registers (LFSRs [MVO96]), defined by the following primitive polynomials:
LF SR1 : X19 + X18 + X17 + X14 + 1;
LF SR2 : X22 + X28 + 1;
LF SR3 : X23 + X22 + X21 + X8 + 1.
The outputs of the LFSRs are mixed by a linear function (addition modulo 2), that provides the best correlation immunity. Non-linearity of the cryptanalysis equations is achieved by clocking the registers asynchronously — on each clocking of the generator any of it’s LFSR can be shifted or it can retain its current state. LFSR with index j ∈ {1, 2, 3} is shifted if the following Boolean function χj takes the value of 1:
χj = (bj ≡ majority(b1, b2, b3)); majority(A, B, C) = (A ∧ B) ∨ (A ∧ C) ∨ (B ∧ C).
Here b1, b2, b3 denote clocking bits marked at Figure 1 by black wedges. Conversely, if at some moment χj = 0, LFSRj is not shifted (it remains in its last state).
Further, we will focus on the idea of the attack that was suggested by R. Anderson in 1994 in a small essay on the A5/1 cryptographic resistance [And]. Next we describe the details of Anderson’s attack.
Anderson’s attack is a typical example of a guess and determine attack (see, for example, [Bar09]). Suppose that we know the bits filling LFSR1 and LFSR3, and bits of LFSR2 from the beginning of the register to the clocking bit (bits 31 to 41, see Figure 2). Next, suppose that we know 64 bits of the keystream. It was shown by R. Anderson, that 11 unknown bits of LFSR2 can be figured out without any additional guesses. This is possible because the following data is known: • the clocking bits (so, the clocking schedule for the next 11 shifts of LFSR2 is also known); • 2 out of 3 LFSRs output bits, which are used as input for the XOR operation; 41 40 39 38 37 36 35 34 33 32 31 3029 28 27 26 25 2423 22 21 20 • the result of the XOR operation (from the keystream).
Therefore, one can efficiently derive the unknown bits of LFSR2 one by one, by clocking the generator and applying XOR operation to corresponding keystream bits and output bits of LFSR1 and LFSR3.
The considered algorithm, that is used to determine the unknown 11 bits of LFSR2, makes it possible to mount a brute force attack on the A5/1 generator over the search space with the size of 253. The simplicity of the algorithm provides an opportunity to implement it on a specialized computational architecture. One such implementation was built with FPGAs by authors of [GNR08]. In the following sections we describe our implementation of this attack for modern GPUs. 3
The efficiency of a brute force attack is defined by two parameters: the speed of checking of the key candidates and the size of the search space. R. Anderson’s idea described in the previous section gives us the search space with the size of 253. Instead of using the “naive” implementation of the A5/1 generator, to speed up the key candidates checking procedure one can opt to use more sophisticated alternatives. In [BS16] we evaluated the performance of two different fast implementations of A5/1 generator. The first one was based on an idea of precomputation of the states of LFSR1-3, and keeping these states in PC’s memory. This approach demonstrated a considerable speed-up against “naive” implementation. A similar method of precomputation of LFSRs was described in [BSW00]. However, in [BS16] we found its performance inferior to another one implementation, that is based on bit-slicing technique. Next we briefly describe the idea of this technique, and its application to Anderson’s attack.
Consider an arbitrary total Boolean function f : {0, 1}n → {0, 1}. This function can be represented in the form of the Boolean circuit C(f ) over some complete basis B. A common example of such basis is B = {∧, ∨, ¬}, but we will use the basis B = {∧, ∨, ¬, ⊕} instead, since it better fits our goals.
Now consider the problem of calculating the arbitrary total Boolean function f : {0, 1}n → {0, 1} over all 2n possible inputs. For each input X ∈ {0, 1}n one can calculate the value of f as a superposition of the basis functions, according to the circuit C(f ). We can select a fixed order of calculation of basis functions from C(f ), that results in getting the value of f . Let m be the number of internal nodes in C(f ). Assuming that the calculation of one basis function takes one processor instruction, the computation of f over all inputs from {0, 1}n will take m · 2n instructions.
SIMD(Single Instruction, Multiple Data) architecture calculates many copies of the same function over many different memory cells with a single instruction. When a modern computational device executes a bitwise logical instruction on its general-purpose registers (GPRs), it effectively acts as a SIMD device, in which individual bits of GPRs play the role of the individual memory cells. The calculation order of functions in the circuit C(f ) always stays the same. This makes it possible to compute this function over as many inputs, as there are bits in the device’s GPR. If D is the device’s GPR capacity, we can simultaneously process D instances of the circuit C(f ), calculating the value of f for inputs X1, ..., XD.
Consider the arbitrary basis function g with arity 2, and the corresponding internal node of the circuit C(f ). We denote it as G(x1, x2), meaning that it has a single output and two inputs, which values are determined by Boolean variables x1, x2. Next, let us link g with three GPRs denoted R1(g), R2(g), R3(g), each of which is comprised of D single-bit memory cells, filled in the following way: • register R1 contains D values of the variable x1, corresponding to X1, ..., XD; • register R2 contains D values of the variable x2, corresponding to X1, ..., XD; • register R3 contains D matching values of the function g.
Suppose that all D instances of g can be computed as a result of a single bitwise instruction applied to registers R1(g), R2(g), while their result is put into register R3(g). If this fact holds for every basis function in the circuit C(f ), the computation of f for all inputs from {0, 1}n will require m · 2Dn instructions. This is the key idea of bit-slicing technique.
We will call the process of computation of the function f (represented by the circuit C(f ) with m inner nodes) on a single input from {0, 1}n a thread, by analogy with the computational threads in a SIMD device. Thus, with the use of bit-slicing technique, it takes m instructions to execute D threads.
Now we describe the details of bit-slicing implementation of the A5/1 generator. Suppose that a computational device is able to calculate D instances of any function from the basis B = {∧, ∨, ¬, ⊕}. Each generator’s cell with number n, n ∈ {1, ..., 64} gets a corresponding word Wn ∈ {0, 1}D:
In bit-slicing technique, the shifting of the LFSR register (LFSR1 in this example) will take the following form: where ⊕ is the bitwise addition modulo 2 of Boolean vectors of length D. The calculation of the keystream bit will look like:
The conditional clocking is somewhat more complex to implement in bit-slicing technique. First, to know if the LFSRs should be shifted or not, one needs to calculate the corresponding shifting flags F1, F2, F3 using the majority function:
Wmaj = maj(W9, W30, W52) = (W9 ∧ W30) ∨ (W9 ∧ W52) ∨ (W30 ∧ W52),
LF SR1 : W1, ..., W19; LF SR2 : W20, ..., W42;
LF SR3 : W43, ..., W64.
W10 = W19 ⊕ W18 ⊕ W17 ⊕ W14,
Wn0 = Wn−1, n ∈ {2, ..., 19}, Wout = W19 ⊕ W41 ⊕ W64.
F1 = W9 ⊕ ¬Wmaj , F2 = W30 ⊕ ¬Wmaj , F3 = W52 ⊕ ¬Wmaj .
a, b, c ∈ {0, 1}; BS(a, b, c) = b, a = 1, c, a = 0.
BS(a, b, c) = (a ∧ b) ∨ (¬a ∧ c).
To implement the conditional shifting of an LFSR one can use the bitwise counterpart of the bitselect function of arity 3:
If the computational architecture lacks the hardware implementation of this function, it can be emulated with the usage of the standard bitwise functions corresponding to the matching functions from the basis B: 1. calculation of the values of 11 bits of LFSR2 lying left of the clocking bit using the information from the guessed 53 bits and the known keystream; 2. clocking the generator as normal to check if the guessed filling of the generator matches the known keystream.
The irregular clocking of the A5/1 generator makes it generally impossible to predict how many clockings of the generator (bits of keystream) would be needed to shift 11 times LFSR2 to complete Stage 1 of the attack. Therefore, we again put to use the bitselect function to implement the split of the attack into 2 stages. Each individual thread should be able to advance from Stage 1 to Stage 2 independently of other threads. To achieve this, we introduce the special Boolean vector φ = (φ1, ..., φD), called attack stage flag. The thread with number i, i ∈ {1, ..., D} being in Stage 1 of the attack corresponds to φi = 0, and Stage 2 of the attack corresponds to φi = 1. Let y1, ..., y64 be the bits of the keystream analyzed. Now the shifting of LFSR2 takes into account the stage of the attack through the usage of the attack stage flag:
W4∗1 = BS(φ, W41, (y ⊕ W19 ⊕ W64));
W200 = BS(F2, (W4∗1 ⊕ W40), W20);
Wn0 = BS(F2, Wn−1, Wn), n ∈ {21, ..., 41}.
Here W4∗1 is a helper vector holding temporary data, y is the current bit of the keystream, in the form of a vector consisting of D copies of the corresponding bit of the keystream. The goal of Stage 1 is to calculate all 11 unknown bits of LFSR2 by using known keystream and guessed last bits of LFSR1 and LFSR3. At Stage 2 the whole generator’s state is known, and the generator is clocked as normal. For the i-th thread the attack stage flag φi is set to 1 after LFSR2 of this thread was shifted 11 times. To count the number of LFSR2 shifts individually for each thread, the bit-slicing implementation of an incremental counter is used.
Anderson’s attack described above was implemented on an NVIDIA GPU with the use of CUDA SDK 8.01. The comparison of the performance of a GPU to a CPU in execution of bit-slicing and LFSR precomputationbased implementations of Anderson’s attack is shown in Table 1. The last row of Table 1 corresponds to the case, in which the bitselect function is implemented using the LOP3.LUT2 instruction.
Data provided in Table 1 tells us that even one mid-range consumer GPU is enough to make Anderson’s attack runtime practical (it will take around 250 hours). A modern computational cluster outfitted with GPUs will perform the attack in mere minutes. Anderson’s attack’s advantage over the rainbow-tables attack [Noh10] is the former’s ability to restore the secret key from 64 bits of keystream with the 100% probability. Its advantge over the attack described in [GNR08] is in the usage of a consumer-grade off-the-shelf hardware. 1https://developer.nvidia.com/cuda-toolkit 2LOP3.LUT is a special instruction that implements arbitrary bitwise functions of arity 3 in hardware. 0xae9590560c26e9ed 0xdd4b3ab7f6cf8224 0x93cd42d97eb75fd9
In order to solve 10 cryptanalysis problems for the A5/1 keystream generator we launched the volunteer computing project AndersonAttack@home. This project is based on BOINC (Berkley Open Infrastructure for Network Compuitng [And04]). The client (computing) application of this project is based on the CUDA implementation, which was described in the previous section.
In the first stage of our experiment, a family of workunits was generated on the project server. In each workunit values of 12 out of 53 guessing bits (see Figure 2) were fixed. Thus, 40960 workunits were generated for 10 cryptanalysis problems in total. In the next stage, all generated workunits were processed in a desktop grid formed by the project’s hosts. This took about 7 days. As a result, solutions for all considered problems were successfully found (see Table 2). It should be noted, that for 7 out of 10 problems the collisions were found.
Usually, the value of deadline for workunits in BOINC projects is 10-14 days. In our case, we used a deadline of 1 day, because the experiment was quite small. That is why all workunits were processed quickly. The same effect could be achieved by task scheduling (see, e.g., [MNI15]). In the considered experiment the project’s performance was comparable to that of a computational cluster equipped with 30 modern GPUs. According to the BOINC statistics, 143 active hosts belonging to 90 volunteers participated in the experiment. Here by active host we mean a host which correctly processed at least one task. 5
It seems that the first practical attack on A5/1 was presented in [GNR08]. Its authors implemented the optimized variant of Anderson’s attack on a specialized computational device of their own design, assembled from 120 “Xilinx Spartan 3” FPGAs. They state that the attack took about 6 hours. [GKN+08].
In [SZBP11] using SAT-based cryptanalysis 3 instances of the A5/1 cryptanalysis were solved in a service grid. In SAT@home [ZMK+16] volunteer computing project several dozens cryptanalysis problems for the A5/1 generator were solved (only one burst — 114 bits of keystream — was used each time)[SZ16].
The A5/1 Cracking Project put rainbow-tables (2 Tb in total) for A5/1 into public domain at the end of 2009 [Noh10]. By analyzing 2 frames (912 bits) of known keystream with the help of these tables one can restore the secret key with probability of success over 85%.
In this paper, we presented a GPU-based implementation of Anderson’s attack on the A5/1 keystream generator. The meticulous adaptation of this attack to the SIMD architecture made it possible to solve several cryptanalysis problems in a BOINC-based desktop grid.
The authors would like to thank Stepan Kochemazov for helpful discussions and valuable comments. We also thank all volunteers, whose computers took part in the experiment.
Ross Anderson. A5 (was: Hacking digital phones). Newsgroup Communication, 1994.
David P. Anderson. BOINC: A system for public-resource computing and storage. In Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, GRID’04, pages 4–10, Washington, DC, USA, 2004. IEEE Computer Society.
Gregory V. Bard. Algebraic Cryptanalysis. Springer Publishing Company, Incorporated, 1st edition, 2009.
Vadim Bulavintsev and Alexander Semenov. Inverting A5/1 cryptographic function on a GPU with alternative A5/1 algorithm software implementations. In 10th Annual International Scientific Conference on Parallel Computing Technologies Arkhangelsk, Russia, March 29-31, 2016, volume 1576 of CEUR-WS, pages 472–481, 2016.
Alex Biryukov, Adi Shamir, and David Wagner. Real time cryptanalysis of A5/1 on a PC. In Bruce Schneier, editor, Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA, April 10-12, 2000, Proceedings, volume 1978 of Lecture Notes in Computer Science, pages 1–18.
Springer, 2000. [GKN+08] Tim Gu¨neysu, Timo Kasper, Martin Novotny´, Christof Paar, and Andy Rupp. Cryptanalysis with COPACOBANA. IEEE Trans. Comput., 57(11):1498–1513, November 2008.
Timo Gendrullis, Martin Novotny´, and Andy Rupp. A real-world attack breaking A5/1 within hours. In Elisabeth Oswald and Pankaj Rohatgi, editors, Cryptographic Hardware and Embedded Systems - CHES 2008, 10th International Workshop, Washington, D.C., USA, August 10-13, 2008. Proceedings, volume 5154 of Lecture Notes in Computer Science, pages 266–282. Springer, 2008. Vladimir V. Mazalov, Natalia N. Nikitina, and Evgeny E. Ivashko. Task scheduling in a desktop grid to minimize the server load. In Proceedings of the 13th International Conference on Parallel Computing Technologies - Volume 9251, pages 273–278, New York, NY, USA, 2015. Springer-Verlag New York, Inc.
Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 1996.
Alexander Semenov and Oleg Zaikin. Algorithm for finding partitionings of hard variants of Boolean satisfiability problem with application to inversion of some cryptographic functions. SpringerPlus, 5(1):1–16, 2016. [ZMK+16] Oleg Zaikin, Maxim Manzyuk, Stepan Kochemazov, Igor Bychkov, and Alexander Semenov. A volunteer-computing-based grid architecture incorporating idle resources of computational clusters. In Ivan Dimov, Istv´an Farag´o, and Lubin G. Vulkov, editors, Numerical Analysis and Its Applications - 6th International Conference, NAA 2016, Lozenetz, Bulgaria, June 15-22, 2016, Revised Selected Papers, volume 10187 of Lecture Notes in Computer Science, pages 769–776, 2016.