# A New Guess-and-Determine Method for Cryptanalysis of the GSM Encryption

Authors: Ashish Jain; Inderjeet Kaur; Akhilesh Kumar Sharma; Nirmal Kumar Gupta; Partha Chakraborty
Journal: Complexity
 (2023)

---

## Abstract

Cryptanalysis is the process of finding flaws or oversights in an encryption algorithm. Nearly, all encryption algorithms are carefully examined through cryptanalysis to determine the security of the system in which the encryption algorithm has been employed. A5/1 is a well-known encryption algorithm which is inbuilt in mobile phone for securing GSM communication, and therefore, cryptanalysis of this algorithm is also important. A5/1 consists of three linear feedback registers of lengths 23, 22, and 19 bits. Due to the nonlinear clocking mechanism of A5/1, cryptanalytic attacks of guess-and-determine (GD) nature are efficient and more successful. In this paper, we propose a new low keystream GD attack on GSM encryption algorithm A5/1. The basic idea of GD attack is guessing some portion of the registers of A5/1 and determining remaining portion of the registers via the relationship between the register’s state and the known intercepted keystream. The guessed and determined register’s state is validated by running the cipher forward from that state. If the intercepted keystream matches the generated keystream, we accept it. Otherwise, we discard and try the attack again. The computational complexity and the success rate of the proposed attack are O252 and 96.6%, respectively.


---

## Body

## 1. Introduction

There are two categories of encryption algorithm (or cipher), namely, symmetric cipher and asymmetric cipher. Symmetric ciphers are further classified as stream cipher and block cipher. A stream cipher is an approach of encrypting data one bit at a time using an encryption algorithm and a secret key. As opposed to a stream cipher, block cipher encrypts data simultaneously in fixed-size blocks.Cryptanalysis is the process of finding flaws or oversights in an encryption algorithm. Nearly, all encryption algorithms are carefully examined through cryptanalysis to determine the security of the system. A5/1 is a well-known synchronous stream cipher which is implemented on the hardware of GSM mobile phones for providing over-the-air communication privacy [1–5], and therefore, cryptanalysis of A5/1 stream cipher is also important.For the construction of synchronous stream ciphers, linear feedback shift registers (LFSRs) are often used because these registers can be easily implemented in hardware, have good statistical properties, and can produce keystream bits at or near the clock speed. Historically, stream ciphers were designed to be employed in real-time systems because of their high-speed encryption capability. However, modern block ciphers are also capable of encrypting at high data rates, e.g., AES, PRESENT [6], and 3DES [7]. Nevertheless, some important applications where the computational resources are limited still prefer stream ciphers to encrypt large quantities of fast streaming data [8]. Due to such important applications, security analysis of stream ciphers is very important.Nearly, all cryptographic and security algorithms undergo security analysis process and are carefully examined to establish the practical security of the system. In other words, the goal of the cryptanalyst is to find flaws or insecurities in a cryptography system so that the system can be upgraded. Typically guess-and-determine (GD) attacks, time-memory-data trade-off (TMDTO) attacks, correlation attacks, and statistical distinguishing attacks are few methods to cryptanalyze stream ciphers. In 1994, when the approximate design of A5/1 was leaked, it was cryptanalyzed by Anderson [1], Babbage [9], and Golić [10]. The exact design of A5/1 was revealed when it was reverse engineered by Briceno et al. [11] from GSM telephone [12]. In the literature, several attacks have been studied on the “exact design of A5/1” (for example, [4, 5, 13–22]). However, previous proposed attacks (except [16, 21]) are of interest from the theoretical aspects because of their deficiency in practicality due to needs of large amount of keystream, lot of precomputation, high computational demands, huge storage requirements, and/or deficiency in considering asynchronous (or irregular) clocking of A5/1. It should be noted that irregular clocking of A5/1 is very important. If irregular clocking of A5/1 is not considered, then the randomness characteristics of the A5/1 generator weakens. Consequently, cryptanalysis of A5/1 becomes simple and can be performed in less computation. It is worth pointing that due to the irregular clocking of A5/1, GD attacks are often mounted on it. Moreover, such types of attacks are common and are very successful against stream ciphers. The basic idea of such type of attack is guessing some portion of the internal state and determining remaining portion via the relationship between the internal state and the known intercepted keystream. The guessed and determined internal state is validated by running the cipher forward from that state. If the intercepted keystream matches the generated keystream, we accept it. Otherwise, we discard the current candidate and try the attack again [22–24]. In this work, we present a new low keystream GD attack of A5/1 and compare our attack with previously proposed GD and TMDTO class of attacks. The remainder of the work is organized as follows. In Section 2, we present the design of A5/1. In Section 3, we present a new low keystream attack on the GSM encryption algorithm A5/1. In Section 4, a review on the previous A5/1 attacks is presented followed by conclusion in Section 5.


## 2. Description of A5/1: A GSM Stream Cipher

For GSM conversation between two communication parties, e.g.,A and B, a sequence of the frame is transmitted. Each frame is transmitted in 4.615 milliseconds that contains 228 bits, where 114 bits represent the communication from A to B and the remaining 114 bits represent return communication. Each frame also contains a frame counter Fn of 22 bits which is publicly known. For each GSM conversation, a new 64-bit session key k is generated. The session key followed by a frame counter is used to set the initial state of A5/1 [4, 5]. Three LFSRs REG1, REG2, and REG3 of lengths 19, 22, and 23 bits, respectively, are used to design A5/1 keystream generator (see Figure 1).Figure 1
A5/1 stream cipher.Figure1 shows that each register has a clocking tap at 8th position in REG1, at 10th position in REG2, and at 10th position in REG3. Each register also has a primitive feedback polynomial (see Section 3, Paragraph 1, for details). All LFSRs are clocked in a stop/go fashion according to the majority rule, i.e., the registers that have the same clocking bit must be clocked simultaneously. It should be noted that at each clock, either two or three registers are clocked, i.e., each register moves with probability 3/4 and stops with probability 1/4.A5/1 operates as follows: the first step is an initialization step in which all LFSRs are set to “0” and then all are clocked 64 times linearly, and in parallel, successive bits of the session key are XORed to the feedback of each register. In the second step, all LFSRs are clocked 22 times (again linearly), and in parallel, consecutive bits of the frame counter are XORed to the feedback of each register. In this way, at the end of 86th (64 + 22) clock cycle, an initial stateSi is obtained. In other words, a linear operation for 86 clock cycles is performed for loading key and frame on the A5/1 keystream generator. Finally, on the use of initial state Si, A5/1 carries out the warm-up phase. In this phase, all LFSRs are clocked in a nonlinear way (according to the majority rule) for 100 clock cycles and the output is discarded. Afterward, A5/1 is clocked nonlinearly for 228 clock cycles that produce 228-bit keystream. The keystream combines with 228 bits of the plaintext, and in this way, the ciphertext of 228 bits is generated. For more details about A5/1, the readers can refer [4, 5, 15].


## 3. Proposed Attack

Figure1 shows that tapping bits, i.e., {13, 16, 17, 18}, {20, 21}, and {7, 20, 21, 22}, are involved in primitive polynomials of REG1, REG2, and REG3, respectively. Whenever a register is clocked, its output is feedback at the least significant bit (LSB) position of the respective register. However, before storing the output at the LSB, bits below the LSB position are shifted downwards, i.e., REGi[j]←REGi[j−1] (i indicates the register number and j > 0). In our method of attack, we guess all bits of REG1 and then determine the contents of REG2 and REG3 using 64 known keystream (KES) bits. The attacks that use very small amount of KES bits, e.g., 64 bits, are called low keystream attacks. In contrast to previously known low keystream attacks on the exact design of A5/1, computational complexity of the proposed attack is 252 which is comparatively better. Also, the rate of success is 96.6% which is remarkable.


### 3.1. Determination Phase

This phase determines the initial internal state for all possible state candidates. SinceREG1 is guessed, we determine REG2 and REG3 which are unknown. Firstly, we compute the MSB of REG2 and REG3 by substituting MSB of REG1 and the first KES bit in the following equation:(1)REG221⊕REG322=REG118⊕KES0.Initially, MSB ofREG2 and REG3 is unknown, and obviously four possibilities exist together. However, we reduce four possibilities to two possibilities by applying following two conditions:(2)1IfREG118=KES0thenREG221=REG322=0orREG221=REG322=1,2IfREG118≠KES0thenREG221=0,REG322=1orREG221=1,REG322=0.The above condition {1} or {2} reduces the amount of possible state candidates to half. Afterward, by replication (for example, [25, 26]) of possible state candidates, we determine REG2 and REG3. For this purpose, first we concentrate on the clocking bit of REG2 and REG3 registers. Since we need to guess all possible combinations of clocking bit of REG2 and REG3, there are three possibilities that are as follows:(1)
IfREG2[10] and REG3[10] are unknown, then the state candidate is replicated as follows: load first copy by REG2[10] = 0, REG3[10] = 0; second copy by REG2[10] = 0, REG3[10] = 1; third copy by REG2[10] = 1, REG3[10] = 0; and finally fourth copy by REG2[10] = 1, REG3[10] = 1.(2)
IfREG2[10] is known and REG3[10] is unknown, then state candidate is replicated as follows: load first copy by REG3[10] = 0 and second copy by REG3[10] = 1.(3)
IfREG2[10] is unknown and REG3[10] is known, then the state candidate is replicated as follows: load first copy by REG2[10] = 0 and second copy by REG2[10] = 1.We consider the second most significant bit ofREG2 and REG3, i.e., REG2[20] and REG3[21]. If REG2 and REG3 are clocked together, then REG2[20] and REG3[21] are shifted downwards and turn out to be new MSB (all possibilities of clocking and un-clocking of REG2 and REG3 are described in Algorithm 1). There are four possibilities for these new bits, but equations (3) and (4) reduce them in two possibilities. That is, equations (3) and (4) reduce the amount of possible state candidates to half. Moreover, as we are considering the initialization of tapping bit REG3[20], in further rounds of attack when REG3 is clocked, REG3[21] remains known and REG3[20] becomes unknown, since downwards shifting REG3[21]←REG3[20].(3)REG220=REG321⊕REG117⊕KESi+1,(4)REG220=REG321⊕REG118⊕KESi+1.Consider the remaining tapping bits ofREG3, i.e., REG3[20] and REG3[7]. At the time of initialization, for each bit position, we make two replicas and each one is initialized by both possibilities (0 and 1). Now, we are in the situation of finding unknown bits of REG2 and REG3 by nonlinear clocking of A5/1. In every clocking of REG2, two bits become known: one in the lower part of the clocked register and another in the upper part of the clocked register, which implies that two bits become unknown. However, in the case of REG3, during first three rounds of clocking, three bits become known and three bits become unknown. For instance, REG3 is clocked just after initialization of REG1. As a result, bits of register REG3 are shifted downwards, i.e., REG3[22], REG3[21], REG3[11], and REG3[8] are assigned known value of REG3[21], REG3[20], REG3[10], and REG3[7], respectively, and the XORing result of feedback polynomial is set to REG3[0]. In this way, REG3[0], REG3[8], and REG3[11] become known and REG3[7], REG3[10], and REG3[20] become unknown and the remaining positions of REG3 remain unknown since downwards shifting is done by an unknown value. Here, the counter associated with REG3 is increased by 1. Afterward, REG3[7], REG3[10], and REG3[20] are guessed again for executing further rounds of attack, but after three rounds of clocking, we need not to guess REG3[10] because the number of bits after the 7th index is three (i.e., 8th, 9th, and 10th). A complete iteration-based determination algorithm for determining contents of REG2 and REG3 is shown in Algorithm 1.Algorithm 1: Determining registers REG2 and REG3.
Input: 64-bit known keystream KES and initial state candidates.Initialize clock counters:c2 = 0 and c3 = 0.Repeat for each instance of state candidatestep1: computation based on majority ruleif all three registers are clocked then compute REG2[20] using equation (5), increment counters c2++, c3++, and go to step2else if registers REG1 and REG2 are clocked then compute REG2[20] using equation (6), increment counter c2++, and go to step3else if registers REG2 and REG3 are clocked then compute REG2[20] using equation (7), increment c2++, c3++, and go to step2else increase counter c3++, and go to step2end ifstep2:ifc3 < 8 thenassign both possibility (i.e., 0 and 1) toREG3[20] and REG3[7] by replicating REG3else if 8 ≤c3 < 10 then assign both possibility to REG3[20] by replicating REG3end ifstep3:if clocking bit of REG2 is known and unknown for REG3 then make two replicas: copy 1: REG3[10] = 0; copy 2: REG3[10] = 1;else if clocking bit of REG3 is known and unknown for REG2 then make two replicas:copy 1:REG2[10] = 0; copy 2: REG2[10] = 1;else make four replicas:copy 1:REG2[10] = REG3[10] = 0; copy 2: REG2[10] = REG3[10] = 1;copy 3:REG2[10] = 0, REG3[10] = 1; copy 4: REG2[10] = 1, REG3[10] = 0;end ifUntil (c2 ≥ 10 and c3 ≥ 10)Algorithm1, which is the determination algorithm, determines all bits of REG2 and REG3 by utilizing input, i.e., consecutive 64 bits of KES and guessing bits of REG1. Let REG2 and REG3 be clocked c2 and c3 times, respectively. Whenever registers are clocked, we update the associated counter by one. Since the partial length between clocking tap and MSB of REG2 is “10” as well as between clocking tap and second MSB of REG3 is “10”, Algorithm 1 is repeated till c2 and c3 reach 10. In this way, both registers (i.e., REG2 and REG3) need to be clocked at least ten times. At this moment, REG2 and REG3 are completely determined. We observed that for obtaining a reasonable number of complete state candidates (a state candidate with all bits is known can be referred to as a complete state candidate), minimum 10 KES bits are required, which is only possible when both registers REG2 and REG3 are clocked together for 10 consecutive rounds. An important question is that in how many rounds, counters c2 and c3 will reach 10, which is the highest probability (about 90% to 100%) of determining the key. We will see the answer to this question in Section 3.3.2.


### 3.2. Processing Phase

This phase of the attack searches for the key by verifying complete state candidates. In the verification process, we encrypt each complete state candidate by A5/1 and match the generated output bit with the corresponding knownKES bit. This process (i.e., clocking and bit-wise matching) continues till a contradiction occurs. When no contradiction occurs, it implies that the cipher’s internal state after the warm-up phase has been obtained because this time 64 bits of a complete state candidate are matched with 64 KES bits. Afterward, we run the A5/1 in reverse direction to discover the key.


### 3.3. Attack Analysis

After initialization, we have state candidates with all bits ofREG1 (guessed register), three bits of REG2 (i.e., REG2[10], REG2[20], and REG2[21]), and five bits of REG3 (i.e., REG3[7], REG3[10], REG3[20], REG3[21], and REG3[22]). Out of these eight bits, three bits: MSB of REG2, MSB of REG3, and second MSB of REG3, remain known in further rounds of attack. However, determination algorithm determines full contents of REG2 and REG3 for those state candidates whose counters c2 and c3 have been reached to 10. An important factor in determination algorithm is the saving of 50% state candidates in each round since second MSB of REG2 becomes available by the applicability of one of the equations in equations (5)–(7). That is, whenever REG2 is clocked, there is a one-half reduction of state candidates in each round. In equations (5)–(7), i is initialized to “0” and increases by “1” in every additional clocking.(5)REG220=REG117⊕REG321⊕KESi+1,(6)REG220=REG117⊕REG322⊕KESi+1,(7)REG220=REG118⊕REG321⊕KESi+1.An interesting point aboutREG2 is that whenever it is clocked, its clocking bit and 20th bit (simultaneously) become unknown. Therefore, we need to assign both (0 and 1) possibility to REG2[10] by replicating the register REG2 and this concept is repeated till 1 ≤ c2 < 10, while in the case of REG3, during the first two rounds of clocking, we guess index bits 7, 10, and 20. During and in between 3rd to 8th clocking, we guess index bits 7 and 20. After 8th and before 10th clocking, we guess only REG3[20]. Here, we assign both (0 and 1) possibilities to index bits by replicating REG3. Table 1 shows all possible cases for 10th and 20th index bits of REG2 and REG3 being known. The attacking phenomenon saves 50% cases for almost all possible cases. Since cases such as REG2[10] is known and REG2[20] is unknown, and REG2 [10] is unknown and REG2 [20] is known are not applicable during 1 ≤ c2 < 10, such cases need not to be mentioned in Table 1.Table 1
Percentage saving in finding unknown bit.
REG2[10]REG2[20]REG3[10]REG3[20]Number of casesValid casesSaving cases (%)KnownKnownKnownKnown000KnownKnownUnknownUnknown4250UnknownUnknownKnownKnown4250UnknownUnknownUnknownUnknown16850UnknownUnknownKnownUnknown8450KnownKnownKnownUnknown220


#### 3.3.1. Time Complexity

The computational complexity of the proposed attack depends on the number of replications of registers after each A5/1 clocking, where one replication of state candidate takes one unit of time. Without loss of generality, we assume thatREG2 and REG3 are clocked 10 times simultaneously.(a)
Due to the condition {1} or {2}, we save 50% state candidates, and due to equation (3) or equation (4), we again save 50% state candidates. In this way, we get 28∗1/22=26 initial state candidates. During the run of determination algorithm, in the first two rounds, 24 replicated copies are created, 23 replicate copies are needed after 3rd and before 8th round, and 22 replicated copies are created before 10th clock. Consequently, the time complexity for each guess of REG1 is computed as 26∗242∗235∗222=233. Finally, the worst case time complexity = 219∗233=O252, where 219 is associated with guessing of 219 possible state candidates of REG1.(b)
Time complexity can be computed in a different way as well. As shown in Table1, in each round, either REG2 is clocked with REG3 or not, we are saving half of the possible cases over exhaustive search. Since REG2 needs to be clocked 10 times, we save 1/210 cases. Moreover, initially, due to condition {1} or {2}, we save 50% state candidates, and due to equation (3) or equation (4), we again save 50% state candidates. In this way, we get the reduction in state candidates by 1/22. Hence, the worst case time complexity to get the key = 264∗1/22∗1/210=O252.From (a) and (b), we conclude that the computational complexity of the proposed attack in the worst case is O(252).


#### 3.3.2. Success Probability

Since the amount of complete state candidates rises with increasing rounds, the success probability of the attack also rises. Consequently, as all the state candidates are complete, the probability of successful determining the whole key becomes high. An important factor in success analysis is that during each clocking of A5/1, at least two registers are clocked, i.e., a register is clocked 3 out of 4 times.(1) Probabilistic Analysis. In this analysis, we find the “number of expected rounds” for achieving a higher rate of success (about 90% to 100%).Formally, we denoten1⟶an event when REG2 and REG3 are clocked together.n2⟶an event when REG1 is clocked either with REG2 or REG3.Prob(n1)⟶probability of event n1 occurs which is (1/2).Prob(n2) ⟶probability of event n2 occurs which is (1/2).LetProbn2=Probn2′+Probn2″=1/4+1/4 = 1/2, where Probn2′ is the probability of occurring the event: REG1 is clocked with REG2 Probn2″ is the probability of occurring the event:REG1 is clocked with REG3 Thus, Probn1+Probn2′+Probn2″=1.During attack analysis, we observed that to determine all bits ofREG2 and REG3, both registers must be clocked 10 times (at least). This implies that x2 = 10 and x3 = 10. Let us consider x1 = 10. Thus, the expectation E[Y] can be given as follows:(8)EY=x1∗Probn1+x2∗Probn2′+x3∗Probn2″Probn1+Probn2′+Probn2″,EY=10∗1/2+2∗10∗1/4+10∗1/41/2+1/4+1/4=15,where we abbreviate expected number of rounds by E[Y] and x1, x2, and x3 are counts of clocking cycles for events n1, n′2, and n″2, respectively.(2) Experimental Analysis. Number of round estimation (as per above calculation) is rough for achieving a higher rate of success; it may be a little bit less or more. Theoretically, it seems impossible to evaluate the exact number of rounds to achieve 100% successful attack. Therefore, we performed some experiments by generating random keys and frames. We mounted the proposed attack for each guess of REG1. Also, tapping bits were guessed whenever required during the cryptanalytic attack. The attack was tested on A5/1 for 15 rounds and in parallel, all replicated 233 state candidates were determined and verified. We found that the experimental results corroborate with our probabilistic analysis. Table 2 shows that the success rate of the attack is on average 96.6% in 15 clocking rounds. We performed the experiments on an Intel Quad-Core PC i7@3.40 Ghz 1000 times, and results demonstrated that the session key can be obtained in an average of 12 seconds (7 seconds are required to derive 233 state candidates and 5 seconds are required to verify the search candidates).Table 2
Statistical results for the successful attacks based on the experimental analysis (ηtsc: mean of total state candidates; ηcsc: mean of complete state candidates).
Number of roundsηtscηcsc(ηtsc/ηcsc) ∗ 1000 (%)10228.21224.125.8711229.50226.4512.0712230.3022820.3013231.80230.2032.9814232.12231.4562.8515233232.9596.60


### 3.4. Space Complexity

For each guess,233 state candidates are needs to be verified. For verification, memory requirement can be determined as 233 ∗ 64 bits = 236 bytes = 26 GB, i.e., 64 GB RAM. If the key is not matched for this choice, in the next guess of 19 bits of REG1, previous guess is discarded, and the verification of the new state candidate is initiated. In this way, the proposed attack requires a total of only 64 GB RAM.


## 3.1. Determination Phase

This phase determines the initial internal state for all possible state candidates. SinceREG1 is guessed, we determine REG2 and REG3 which are unknown. Firstly, we compute the MSB of REG2 and REG3 by substituting MSB of REG1 and the first KES bit in the following equation:(1)REG221⊕REG322=REG118⊕KES0.Initially, MSB ofREG2 and REG3 is unknown, and obviously four possibilities exist together. However, we reduce four possibilities to two possibilities by applying following two conditions:(2)1IfREG118=KES0thenREG221=REG322=0orREG221=REG322=1,2IfREG118≠KES0thenREG221=0,REG322=1orREG221=1,REG322=0.The above condition {1} or {2} reduces the amount of possible state candidates to half. Afterward, by replication (for example, [25, 26]) of possible state candidates, we determine REG2 and REG3. For this purpose, first we concentrate on the clocking bit of REG2 and REG3 registers. Since we need to guess all possible combinations of clocking bit of REG2 and REG3, there are three possibilities that are as follows:(1)
IfREG2[10] and REG3[10] are unknown, then the state candidate is replicated as follows: load first copy by REG2[10] = 0, REG3[10] = 0; second copy by REG2[10] = 0, REG3[10] = 1; third copy by REG2[10] = 1, REG3[10] = 0; and finally fourth copy by REG2[10] = 1, REG3[10] = 1.(2)
IfREG2[10] is known and REG3[10] is unknown, then state candidate is replicated as follows: load first copy by REG3[10] = 0 and second copy by REG3[10] = 1.(3)
IfREG2[10] is unknown and REG3[10] is known, then the state candidate is replicated as follows: load first copy by REG2[10] = 0 and second copy by REG2[10] = 1.We consider the second most significant bit ofREG2 and REG3, i.e., REG2[20] and REG3[21]. If REG2 and REG3 are clocked together, then REG2[20] and REG3[21] are shifted downwards and turn out to be new MSB (all possibilities of clocking and un-clocking of REG2 and REG3 are described in Algorithm 1). There are four possibilities for these new bits, but equations (3) and (4) reduce them in two possibilities. That is, equations (3) and (4) reduce the amount of possible state candidates to half. Moreover, as we are considering the initialization of tapping bit REG3[20], in further rounds of attack when REG3 is clocked, REG3[21] remains known and REG3[20] becomes unknown, since downwards shifting REG3[21]←REG3[20].(3)REG220=REG321⊕REG117⊕KESi+1,(4)REG220=REG321⊕REG118⊕KESi+1.Consider the remaining tapping bits ofREG3, i.e., REG3[20] and REG3[7]. At the time of initialization, for each bit position, we make two replicas and each one is initialized by both possibilities (0 and 1). Now, we are in the situation of finding unknown bits of REG2 and REG3 by nonlinear clocking of A5/1. In every clocking of REG2, two bits become known: one in the lower part of the clocked register and another in the upper part of the clocked register, which implies that two bits become unknown. However, in the case of REG3, during first three rounds of clocking, three bits become known and three bits become unknown. For instance, REG3 is clocked just after initialization of REG1. As a result, bits of register REG3 are shifted downwards, i.e., REG3[22], REG3[21], REG3[11], and REG3[8] are assigned known value of REG3[21], REG3[20], REG3[10], and REG3[7], respectively, and the XORing result of feedback polynomial is set to REG3[0]. In this way, REG3[0], REG3[8], and REG3[11] become known and REG3[7], REG3[10], and REG3[20] become unknown and the remaining positions of REG3 remain unknown since downwards shifting is done by an unknown value. Here, the counter associated with REG3 is increased by 1. Afterward, REG3[7], REG3[10], and REG3[20] are guessed again for executing further rounds of attack, but after three rounds of clocking, we need not to guess REG3[10] because the number of bits after the 7th index is three (i.e., 8th, 9th, and 10th). A complete iteration-based determination algorithm for determining contents of REG2 and REG3 is shown in Algorithm 1.Algorithm 1: Determining registers REG2 and REG3.
Input: 64-bit known keystream KES and initial state candidates.Initialize clock counters:c2 = 0 and c3 = 0.Repeat for each instance of state candidatestep1: computation based on majority ruleif all three registers are clocked then compute REG2[20] using equation (5), increment counters c2++, c3++, and go to step2else if registers REG1 and REG2 are clocked then compute REG2[20] using equation (6), increment counter c2++, and go to step3else if registers REG2 and REG3 are clocked then compute REG2[20] using equation (7), increment c2++, c3++, and go to step2else increase counter c3++, and go to step2end ifstep2:ifc3 < 8 thenassign both possibility (i.e., 0 and 1) toREG3[20] and REG3[7] by replicating REG3else if 8 ≤c3 < 10 then assign both possibility to REG3[20] by replicating REG3end ifstep3:if clocking bit of REG2 is known and unknown for REG3 then make two replicas: copy 1: REG3[10] = 0; copy 2: REG3[10] = 1;else if clocking bit of REG3 is known and unknown for REG2 then make two replicas:copy 1:REG2[10] = 0; copy 2: REG2[10] = 1;else make four replicas:copy 1:REG2[10] = REG3[10] = 0; copy 2: REG2[10] = REG3[10] = 1;copy 3:REG2[10] = 0, REG3[10] = 1; copy 4: REG2[10] = 1, REG3[10] = 0;end ifUntil (c2 ≥ 10 and c3 ≥ 10)Algorithm1, which is the determination algorithm, determines all bits of REG2 and REG3 by utilizing input, i.e., consecutive 64 bits of KES and guessing bits of REG1. Let REG2 and REG3 be clocked c2 and c3 times, respectively. Whenever registers are clocked, we update the associated counter by one. Since the partial length between clocking tap and MSB of REG2 is “10” as well as between clocking tap and second MSB of REG3 is “10”, Algorithm 1 is repeated till c2 and c3 reach 10. In this way, both registers (i.e., REG2 and REG3) need to be clocked at least ten times. At this moment, REG2 and REG3 are completely determined. We observed that for obtaining a reasonable number of complete state candidates (a state candidate with all bits is known can be referred to as a complete state candidate), minimum 10 KES bits are required, which is only possible when both registers REG2 and REG3 are clocked together for 10 consecutive rounds. An important question is that in how many rounds, counters c2 and c3 will reach 10, which is the highest probability (about 90% to 100%) of determining the key. We will see the answer to this question in Section 3.3.2.


## 3.2. Processing Phase

This phase of the attack searches for the key by verifying complete state candidates. In the verification process, we encrypt each complete state candidate by A5/1 and match the generated output bit with the corresponding knownKES bit. This process (i.e., clocking and bit-wise matching) continues till a contradiction occurs. When no contradiction occurs, it implies that the cipher’s internal state after the warm-up phase has been obtained because this time 64 bits of a complete state candidate are matched with 64 KES bits. Afterward, we run the A5/1 in reverse direction to discover the key.


## 3.3. Attack Analysis

After initialization, we have state candidates with all bits ofREG1 (guessed register), three bits of REG2 (i.e., REG2[10], REG2[20], and REG2[21]), and five bits of REG3 (i.e., REG3[7], REG3[10], REG3[20], REG3[21], and REG3[22]). Out of these eight bits, three bits: MSB of REG2, MSB of REG3, and second MSB of REG3, remain known in further rounds of attack. However, determination algorithm determines full contents of REG2 and REG3 for those state candidates whose counters c2 and c3 have been reached to 10. An important factor in determination algorithm is the saving of 50% state candidates in each round since second MSB of REG2 becomes available by the applicability of one of the equations in equations (5)–(7). That is, whenever REG2 is clocked, there is a one-half reduction of state candidates in each round. In equations (5)–(7), i is initialized to “0” and increases by “1” in every additional clocking.(5)REG220=REG117⊕REG321⊕KESi+1,(6)REG220=REG117⊕REG322⊕KESi+1,(7)REG220=REG118⊕REG321⊕KESi+1.An interesting point aboutREG2 is that whenever it is clocked, its clocking bit and 20th bit (simultaneously) become unknown. Therefore, we need to assign both (0 and 1) possibility to REG2[10] by replicating the register REG2 and this concept is repeated till 1 ≤ c2 < 10, while in the case of REG3, during the first two rounds of clocking, we guess index bits 7, 10, and 20. During and in between 3rd to 8th clocking, we guess index bits 7 and 20. After 8th and before 10th clocking, we guess only REG3[20]. Here, we assign both (0 and 1) possibilities to index bits by replicating REG3. Table 1 shows all possible cases for 10th and 20th index bits of REG2 and REG3 being known. The attacking phenomenon saves 50% cases for almost all possible cases. Since cases such as REG2[10] is known and REG2[20] is unknown, and REG2 [10] is unknown and REG2 [20] is known are not applicable during 1 ≤ c2 < 10, such cases need not to be mentioned in Table 1.Table 1
Percentage saving in finding unknown bit.
REG2[10]REG2[20]REG3[10]REG3[20]Number of casesValid casesSaving cases (%)KnownKnownKnownKnown000KnownKnownUnknownUnknown4250UnknownUnknownKnownKnown4250UnknownUnknownUnknownUnknown16850UnknownUnknownKnownUnknown8450KnownKnownKnownUnknown220


### 3.3.1. Time Complexity

The computational complexity of the proposed attack depends on the number of replications of registers after each A5/1 clocking, where one replication of state candidate takes one unit of time. Without loss of generality, we assume thatREG2 and REG3 are clocked 10 times simultaneously.(a)
Due to the condition {1} or {2}, we save 50% state candidates, and due to equation (3) or equation (4), we again save 50% state candidates. In this way, we get 28∗1/22=26 initial state candidates. During the run of determination algorithm, in the first two rounds, 24 replicated copies are created, 23 replicate copies are needed after 3rd and before 8th round, and 22 replicated copies are created before 10th clock. Consequently, the time complexity for each guess of REG1 is computed as 26∗242∗235∗222=233. Finally, the worst case time complexity = 219∗233=O252, where 219 is associated with guessing of 219 possible state candidates of REG1.(b)
Time complexity can be computed in a different way as well. As shown in Table1, in each round, either REG2 is clocked with REG3 or not, we are saving half of the possible cases over exhaustive search. Since REG2 needs to be clocked 10 times, we save 1/210 cases. Moreover, initially, due to condition {1} or {2}, we save 50% state candidates, and due to equation (3) or equation (4), we again save 50% state candidates. In this way, we get the reduction in state candidates by 1/22. Hence, the worst case time complexity to get the key = 264∗1/22∗1/210=O252.From (a) and (b), we conclude that the computational complexity of the proposed attack in the worst case is O(252).


### 3.3.2. Success Probability

Since the amount of complete state candidates rises with increasing rounds, the success probability of the attack also rises. Consequently, as all the state candidates are complete, the probability of successful determining the whole key becomes high. An important factor in success analysis is that during each clocking of A5/1, at least two registers are clocked, i.e., a register is clocked 3 out of 4 times.(1) Probabilistic Analysis. In this analysis, we find the “number of expected rounds” for achieving a higher rate of success (about 90% to 100%).Formally, we denoten1⟶an event when REG2 and REG3 are clocked together.n2⟶an event when REG1 is clocked either with REG2 or REG3.Prob(n1)⟶probability of event n1 occurs which is (1/2).Prob(n2) ⟶probability of event n2 occurs which is (1/2).LetProbn2=Probn2′+Probn2″=1/4+1/4 = 1/2, where Probn2′ is the probability of occurring the event: REG1 is clocked with REG2 Probn2″ is the probability of occurring the event:REG1 is clocked with REG3 Thus, Probn1+Probn2′+Probn2″=1.During attack analysis, we observed that to determine all bits ofREG2 and REG3, both registers must be clocked 10 times (at least). This implies that x2 = 10 and x3 = 10. Let us consider x1 = 10. Thus, the expectation E[Y] can be given as follows:(8)EY=x1∗Probn1+x2∗Probn2′+x3∗Probn2″Probn1+Probn2′+Probn2″,EY=10∗1/2+2∗10∗1/4+10∗1/41/2+1/4+1/4=15,where we abbreviate expected number of rounds by E[Y] and x1, x2, and x3 are counts of clocking cycles for events n1, n′2, and n″2, respectively.(2) Experimental Analysis. Number of round estimation (as per above calculation) is rough for achieving a higher rate of success; it may be a little bit less or more. Theoretically, it seems impossible to evaluate the exact number of rounds to achieve 100% successful attack. Therefore, we performed some experiments by generating random keys and frames. We mounted the proposed attack for each guess of REG1. Also, tapping bits were guessed whenever required during the cryptanalytic attack. The attack was tested on A5/1 for 15 rounds and in parallel, all replicated 233 state candidates were determined and verified. We found that the experimental results corroborate with our probabilistic analysis. Table 2 shows that the success rate of the attack is on average 96.6% in 15 clocking rounds. We performed the experiments on an Intel Quad-Core PC i7@3.40 Ghz 1000 times, and results demonstrated that the session key can be obtained in an average of 12 seconds (7 seconds are required to derive 233 state candidates and 5 seconds are required to verify the search candidates).Table 2
Statistical results for the successful attacks based on the experimental analysis (ηtsc: mean of total state candidates; ηcsc: mean of complete state candidates).
Number of roundsηtscηcsc(ηtsc/ηcsc) ∗ 1000 (%)10228.21224.125.8711229.50226.4512.0712230.3022820.3013231.80230.2032.9814232.12231.4562.8515233232.9596.60


## 3.3.1. Time Complexity

The computational complexity of the proposed attack depends on the number of replications of registers after each A5/1 clocking, where one replication of state candidate takes one unit of time. Without loss of generality, we assume thatREG2 and REG3 are clocked 10 times simultaneously.(a)
Due to the condition {1} or {2}, we save 50% state candidates, and due to equation (3) or equation (4), we again save 50% state candidates. In this way, we get 28∗1/22=26 initial state candidates. During the run of determination algorithm, in the first two rounds, 24 replicated copies are created, 23 replicate copies are needed after 3rd and before 8th round, and 22 replicated copies are created before 10th clock. Consequently, the time complexity for each guess of REG1 is computed as 26∗242∗235∗222=233. Finally, the worst case time complexity = 219∗233=O252, where 219 is associated with guessing of 219 possible state candidates of REG1.(b)
Time complexity can be computed in a different way as well. As shown in Table1, in each round, either REG2 is clocked with REG3 or not, we are saving half of the possible cases over exhaustive search. Since REG2 needs to be clocked 10 times, we save 1/210 cases. Moreover, initially, due to condition {1} or {2}, we save 50% state candidates, and due to equation (3) or equation (4), we again save 50% state candidates. In this way, we get the reduction in state candidates by 1/22. Hence, the worst case time complexity to get the key = 264∗1/22∗1/210=O252.From (a) and (b), we conclude that the computational complexity of the proposed attack in the worst case is O(252).


## 3.3.2. Success Probability

Since the amount of complete state candidates rises with increasing rounds, the success probability of the attack also rises. Consequently, as all the state candidates are complete, the probability of successful determining the whole key becomes high. An important factor in success analysis is that during each clocking of A5/1, at least two registers are clocked, i.e., a register is clocked 3 out of 4 times.(1) Probabilistic Analysis. In this analysis, we find the “number of expected rounds” for achieving a higher rate of success (about 90% to 100%).Formally, we denoten1⟶an event when REG2 and REG3 are clocked together.n2⟶an event when REG1 is clocked either with REG2 or REG3.Prob(n1)⟶probability of event n1 occurs which is (1/2).Prob(n2) ⟶probability of event n2 occurs which is (1/2).LetProbn2=Probn2′+Probn2″=1/4+1/4 = 1/2, where Probn2′ is the probability of occurring the event: REG1 is clocked with REG2 Probn2″ is the probability of occurring the event:REG1 is clocked with REG3 Thus, Probn1+Probn2′+Probn2″=1.During attack analysis, we observed that to determine all bits ofREG2 and REG3, both registers must be clocked 10 times (at least). This implies that x2 = 10 and x3 = 10. Let us consider x1 = 10. Thus, the expectation E[Y] can be given as follows:(8)EY=x1∗Probn1+x2∗Probn2′+x3∗Probn2″Probn1+Probn2′+Probn2″,EY=10∗1/2+2∗10∗1/4+10∗1/41/2+1/4+1/4=15,where we abbreviate expected number of rounds by E[Y] and x1, x2, and x3 are counts of clocking cycles for events n1, n′2, and n″2, respectively.(2) Experimental Analysis. Number of round estimation (as per above calculation) is rough for achieving a higher rate of success; it may be a little bit less or more. Theoretically, it seems impossible to evaluate the exact number of rounds to achieve 100% successful attack. Therefore, we performed some experiments by generating random keys and frames. We mounted the proposed attack for each guess of REG1. Also, tapping bits were guessed whenever required during the cryptanalytic attack. The attack was tested on A5/1 for 15 rounds and in parallel, all replicated 233 state candidates were determined and verified. We found that the experimental results corroborate with our probabilistic analysis. Table 2 shows that the success rate of the attack is on average 96.6% in 15 clocking rounds. We performed the experiments on an Intel Quad-Core PC i7@3.40 Ghz 1000 times, and results demonstrated that the session key can be obtained in an average of 12 seconds (7 seconds are required to derive 233 state candidates and 5 seconds are required to verify the search candidates).Table 2
Statistical results for the successful attacks based on the experimental analysis (ηtsc: mean of total state candidates; ηcsc: mean of complete state candidates).
Number of roundsηtscηcsc(ηtsc/ηcsc) ∗ 1000 (%)10228.21224.125.8711229.50226.4512.0712230.3022820.3013231.80230.2032.9814232.12231.4562.8515233232.9596.60


## 3.4. Space Complexity

For each guess,233 state candidates are needs to be verified. For verification, memory requirement can be determined as 233 ∗ 64 bits = 236 bytes = 26 GB, i.e., 64 GB RAM. If the key is not matched for this choice, in the next guess of 19 bits of REG1, previous guess is discarded, and the verification of the new state candidate is initiated. In this way, the proposed attack requires a total of only 64 GB RAM.


## 4. Related A5/1 Attacks and Their Comparison

In this section, we discussed only those previous attacks that were proposed on the exact design of A5/1, practically efficient, and which belong to the GD class of attacks.For attacking A5/1, Biham and Dunkelman’s [13] idea is to wait for an event that can leak a huge volume of information about the key and then exploit it. The basic attack assumes that the register REG3 has not been clocked for 10 consecutive rounds. The idea is that if we know the clocking bit of REG3, we can get the information about clocking bit of REG1 and REG2 for all 10 rounds because both registers are considered the complement of REG3[10]. Formally, KES[i] ⊕REG3[22] is equal to the output bits of REG1 ⊕REG2. In this way, guessing of following bits uncover all bits of REG1 and REG2: REG3 [22], REG2 [0], REG1 [9] to REG1 [12], and REG1 [14] to REG1 [18]. In brief, the total complexity is the sum of the cost of guessing 11 bits as mentioned above, the cost of guessing 11 bits of REG3 (i.e., REG3[0] to REG3[10]), and the cost of continuous clocking of the third register, so that the attacker receives all unknown bits of REG3. Additionally, the attacker needs to probe about 220 different locations by hit and trial to find information revealing events where REG3 is not clocked 10 times consecutively. The computational complexity of the attack is 247, but the attack needs 220.8 KES bits. This basic attack was further improved in [13] that reduces the time complexity to 239.91, but it also requires a lot of precomputed data, big amount of known KES bits, and large space. Hence, practically such attacks are very difficult to implement.Biryukov et al. [15] proposed two similar nongeneric TMDTO class attacks on the A5/1 by exploiting low sampling resistance properties of A5/1. Since these attacks belong to TMDTO class, there are many possible choices of trade-off, and three of them are summarized in Table 3, where the success probability of each attack is 60%. Even though the random subgraph attack has less data complexity than biased birthday attack, fetching keystream for 2 seconds, i.e., the requirement of approximately 25000 known KES bits, is a big obstacle to practically implement such an attack. Barkan et al. [17] proposed “ciphertextonly” attack which is an important contribution in the TMDTO class. An important fact about GSM is that before encryption, GSM employs error correction, and such weakness has been exploited by the authors to attack A5/1. However, this attack requires precomputation of the huge volume of data, and those data must be stored in secondary storage; therefore, it is very difficult to make such attacks practical. It is noteworthy that simple forms of TMDTO class of attacks have been independently proposed by Babbage [9] and Golić [10]. Keller and Seitz [16] demonstrated a hardware-based attack which differs from previous approaches in two aspects. First, the attack needs a very small amount of plaintext (only 64 bits). Second, the attack is not solely based on the software because its crucial part is implemented on field-programmable gate array (FPGA). A relation between S, S′, and S″ is shown in Figure 2.Table 3
Comparison of related attacks (PW: precomputation workload; CC: computational complexity).
AttackPWCCKnown keystreamSuccess probability (%)Memory requirementTime to recover keyProposed in [12]238239.91220.8 bits6364 GBImpractical attackBiased birthday attack 1 [14]2481 second220.5 bits60146 GBImpractical attackBiased birthday attack 2 [14]2421 second220.5 bits60292 GBImpractical attackSubgraph attack [14]2483–6 minutes214.7 bits60146 GBImpractical attackProposed in [15]0251.24Only 64 bits1807 hoursProposed in [20]0254.04Only 64 bits10007 hoursProposed in [4]NANAOnly 64 bits81984 GB9 secondsProposed in [5]NANAOnly 64 bits80.083.84 TB33 secondsProposed in this paper0252Only 64 bits96.664 GB12 secondsLarge amount of keystream requirements makes first four attacks impractical; needing of lot of precomputation data is also a big obstacle in practicality of these four attacks.Figure 2
Relation betweenS, S′, and S″.Keller and Seitz’s algorithm is a two-phase backtracking algorithm, where the first phase tries to generate stateS′ from few states of S and then generates output keystream. Afterward, the second phase computes state S″ corresponding to state S′. The state S″ can be easily generated because the frame number is known, and all registers were clocked linearly. It should be noted that the basic part of Keller and Seitz’s algorithm is like Anderson’s [1] algorithm. Unlike Anderson’s approach, the asynchronous clocking of A5/1 is also considered by Keller and Seitz. The basic strategy is to guess all possible, i.e., 241 states of REG1 and REG2, and then deduce the largest register REG3 as follows. Foremost, i.e., at time t = 0, the MSB of REG3 is obtained by XORing MSB of REG1, MSB of REG2, and first known KES bit.Afterward, Keller and Seitz guessed the clocking bit ofREG3 by inspecting clocking bit of REG1 and REG2. If clocking bit of REG1 and REG2 is not equal, then REG3 is clocked either with REG1 or REG2, i.e., both possibilities of REG3 clocking bit are checked. However, if clocking bit of REG1 and REG2 is the same, then at least these two registers are clocked, i.e., all three registers may have been clocked. Nevertheless, during extensive analysis of this attack, Gendrullis et al. [21] observed that Keller and Seitz’s algorithm reduces the complexity of a simple GD attack by identifying contradiction early that can occur by guessing the REG3 clocking bit so that REG3 will not be clocked. In other words, the authors discard a substantial fraction of potential candidates at an early stage of the verification process. Moreover, Keller and Seitz claim that their attack technique reduces the worst case complexity to 251.24 including expected 14 clock cycles per guess. Unfortunately, the approach given by Keller and Seitz [16] not only eliminates wrong candidates but also restricts the search for correct candidates. It should be noted that Keller and Seitz did not mention this fact. Furthermore, no complete analysis of the attack has been performed. The expected computing time for a guess is slightly higher than that stated by Keller and Seitz. The number of all valid state candidates for one fixed guess of REG1 and REG2 is (1+(3/4))11 = (7/4)11 = 28.88 = 471. Also, the success rate of the attack is only 18% ((86/471) = 0.18) [21].A significant modification to the above-stated attack is presented by Gendrullis et al. [21]. Unlike Keller and Seitz, they checked all possibilities of clocking bit of REG3. It implies that they have considered the cases of clocking and un-clocking of REG3 to find the correct state candidates. This decreases 0.25 of all cases and the number of choices from two to one. In this way, the expected number of possibilities for REG3 that needs to be verified is roughly 471 for each of the fixed guesses of REG1 and REG2. The attack has computational complexity of 254.02. The attack was tested on the Cost-Optimized Parallel COde Breaker (COPACOBANA) with the knowledge of only 64 KES bits [20]. As a result, the machine can recover the corresponding 64-bit internal state of the cipher in about 6 hours. In this way, the attack procedure significantly reduces the search space over exhaustive search (O 264. The attack is practically efficient with 100% success. The only limitation is that the COPACOBANA hardware is very expensive and specifically designed for mounting such an attack.A comparison table for above-discussed attacks is shown in Table3. It can be clearly observed from the table that there is competition between low keystream attacks which is practically possible, i.e., between those attacks that are proposed by Keller and Seitz [16], Gendrullis et al. [21], Lu et al. [4], Li [5], and the one which is presented in this work. Table 3 shows that the proposed low keystream attack requires 64 GB memory to save replicated state candidates; however, a considerable amount of computational time is reduced. Memory requirement is also very less as compared to the attack proposed by Lu et al. [4] and Li [5]. It should be noted that we are guessing very fewer state candidates, and for each guess, the proposed practical attack takes lesser time, i.e., only 12 seconds with high rate of success (96.6%) which is better as compared to the recently proposed attack by Lu et al. [4] and Li [5].


## 5. Conclusion and Future Work

In this work, we have presented a new low keystream GD attack on the GSM encryption algorithm. The worst case computational complexity of the proposed attack is O252 which is much better than the brute force (O264). As evident from the results, the proposed attack is comparable to previous A5/1 attacks in terms of computational complexity and success probability. Since we have considered all the valid state candidates, the probability of containing the secret key by the final set of complete state candidates is high. Through probabilistic analysis and experimental test, we demonstrate that the success rate of the proposed attack is 96.6% and the proposed algorithm is practical and able to recover the key in 12 seconds. The proposed algorithm uses only very small amount of information (64 bits of keystream) to mount the attack. Therefore, the proposed algorithm can be used as a valid and efficient alternative for cryptanalyzing A5/1 and the similar stream ciphers, for example, 64-bit GMR-2 stream cipher which is used in satellite phones. As a future work, we plan to test the proposed algorithm on GMR-2 stream cipher.



---

*Source: 7249127-2023-02-18.xml*