Christof Beierle

Patrick Derbez
email: patrick.derbez@irisa.fr

Gregor Leander

Gaëtan Leurent
email: gaetan.leurent@inria.fr

Håvard Raddum
email: haavardr@simula.no

Yann Rotella
email: yann.rotella@uvsq.fr

David Rupprecht

Lukas Stennes

Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2

Keywords: GPRS Encryption, Stream Cipher, Algebraic attacks, GEA

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

General Packet Radio Service (GPRS) is a mobile data standard based on the GSM (2G) technology. With its large deployments during the early 2000s worldwide, GPRS (including EDGE) was the technology for many of us, which provided us the first mobile Internet connection. While some countries are about to sunset 2G technology (or have already done so), other countries rely on GPRS as a fallback data connection. Consequently, the security of those connections was and still is relevant for a large user base. In the wireless medium, an attacker conducts an eavesdropping attack by merely sniffing the traffic in the victim's vicinity. To protect against eavesdropping GPRS between the phone and the base station, a stream cipher is used and initially two proprietary encryption algorithms GEA-1 and GEA-2 were specified.

Design Process of the GPRS Encryption Algorithm. A dedicated encryption algorithm for GPRS, now known as GEA-1, was designed by ETSI Security Algorithms Group of Experts (SAGE) in 1998. A technical report on the design process is available at [START_REF]Security algorithms group of experts[END_REF]. The total budget spent was 429 man days and six organizations have been involved in the process. As seen in [15, Section 8], the following requirements were set for the design:

The algorithm should be a stream cipher which gets a 64-bit key (Kc), a 32-bit IV, and a 1 bit flag to indicate the transfer direction as inputs and outputs a stream of 1,600 bytes.

It was explicitly mentioned as a design requirement that "the algorithm should be generally exportable taking into account current export restrictions" and that "the strength should be optimized taking into account the above requirement" [15, p. 10]. The report further contains a section on the evaluation of the design. In particular, it is mentioned that the evaluation team came to the conclusion that, "in general the algorithm will be exportable under the current national export restrictions on cryptography applied in European countries" and that "within this operational context, the algorithm provides an adequate level of security against eavesdropping of GSM GPRS services" [15, p. 13].

A successor algorithm, called GEA-2, was designed later. An official requirement specification by ETSI as for GEA-1 is not publicly available. According to Charles Brookson in 2001, "GEA2 was defined about a year later than GEA1 and was an improvement, which was allowed by the easing of export control legislation" [8, p. 4].

The particular restrictions that GEA-1 should fulfill in order to be exportable are not specified in the requirements.

Export Regulations. For a detailed survey on national and international regulations concerning the use, supply, import and export of cryptographic algorithms in the '90s, we refer to the Crypto Law Survey of Bert-Jaap Koops [START_REF] Koops | Crypto law survey[END_REF]. In France, rather strict regulations have been in place. In particular, until the late '90s, the use, supply, import and export of cryptography for providing confidentiality was subject to authorization by the prime minister. The requirements for obtaining such an authorization were not publicly available. To quote from [START_REF] Koops | Crypto law survey[END_REF], "It was unclear to what extent the restrictive regulation was enforced in practice; it was rumoured to be widely ignored. It seemed impossible for individuals or enterprises to obtain authorisation for 'strong' cryptography. Even for state-owned industry, cryptography that does not serve military or high-grade security purposes had to be breakable. SCSSI, the office dealing with authorisation, rendered decisions without motivation."

In 1998, the French Decrees1 98-206 and 98-207 were announced, in which exceptions from such authorization or declaration have been defined. The three most interesting exceptions defined in Decree 98-206 with regard to our work can be translated as follows:

-Means and services of Cryptology for "mobile phones for civil use that do not implement end-to-end encryption" are exempt from authorization or declaration for supply, use, import and export. -Means and services of Cryptology for "Commercial civil base towers with the following characteristics: a) Limited to connection with cell phones that cannot apply cryptographic techniques to traffic between terminals, excepted on the direct link between cell phones and base stations b) And not allowing the use of cryptographic techniques to traffic excepted on the radio interface" are exempt from authorization or declaration for supply, use and import (but not export). -Means and services of Cryptology in which "exhaustive search of all possible keys does not require more than 2 40 trials with a simple test" are exempt from authorization or declaration for use and import (but not for supply and export).

Interestingly enough, we will show later in Section 3 that GEA-1 offers only 40-bit security.

Related Work and Reverse Engineering

In 2011, Nohl and Melette analyzed the security of GPRS traffic and showed that GPRS signals could easily be eavesdropped [START_REF] Nohl | GPRS intercept: Wardriving your country[END_REF]. This was reported as a serious weakness, especially since some providers did not activate encryption at all. However, according to the authors, most operators at that time employed the proprietary encryption algorithms GEA-1 or GEA-2 for encrypting the GPRS traffic.

In the same talk, Nohl and Melette also reported the reverse-engineering of those encryption algorithms. Without presenting all of the specification details, the following properties of the design of GEA-1 have been shown:

-It is a stream cipher which works on an internal state of 96 bits and uses a 64-bit key. -A non-linear function is employed for initialization. 2 -The state is kept in three registers of sizes 31, 32, and 33 bits.3 -The state update function is linear, i.e., the registers are LFSRs.

-The function that generates the output stream has algebraic degree 4.

The structure of the GEA-1 stream cipher as known from [START_REF] Nohl | GPRS intercept: Wardriving your country[END_REF] is depicted in Figure 1. For GEA-2, it was reported that it employs a similar algebraic structure to its predecessor GEA-1. While the key size for GEA-2 is 64 bits as well, the internal state was reported to be of size 125 bits. Fig. 1: The structure of the GEA-1 stream cipher with its 96 bit state known from [START_REF] Nohl | GPRS intercept: Wardriving your country[END_REF]. The algebraic degree of the output function is 4.

In their talk, the authors claimed that GEA-1 has severe weaknesses against algebraic attacks, mainly due to the nonlinearity of the state update function and the availability of a long keystream to the adversary. Live on stage, a staterecovery attack was performed that took less than 15 minutes using "a Gaussian equation solver based on some SAT solver ideas" (minute 48:40 of the recorded talk). 4 However, details of this attack are not available.

Interestingly, the ETSI prohibited the implementation of GEA-1 in mobile phones in 2013, while GEA-2 and the non-encrypted mode are still mandatory to be implemented today [START_REF]ETSI: Digital cellular telecommunications system ([END_REF].

Despite the hints of deliberately weakening GEA-1 for export and a demonstrated attack, a public cryptanalysis of GEA-1 and GEA-2 is still missing to date. This puts us in a position where we are uncertain about the algorithm's security guarantees. In this paper, we fill this gap with the first public cryptanalysis of GEA-1 and GEA-2. As part of this we also describe the design of those two proprietary algorithms, which we obtained from a source that prefers to stay anonymous.

Our Contribution

After describing the stream ciphers GEA-1 and GEA-2 and their internal building blocks, we start by analyzing the security of GEA-1.

The main observation is that after the linear initialization process the joint initial state of 64 bits of two of the three LFSRs is guaranteed to be in one of only 2 40 states (rather than close to 2 64 as should be expected).

This property immediately allows to conduct a Divide-and-Conquer staterecovery attack in time 2 40 GEA-1 evaluations by using only 65 bits of known keystream (with at least 24 bits in the same frame). The attack needs the precomputation of a (sorted) table of size 44.5 GiB, which can be done in time of roughly 2 37 GEA-1 evaluations. Once this table has been computed, the attack can be performed in time of roughly 2 40 GEA-1 evaluations for each new 64-bit session key.

Further, we experimentally show that for randomly chosen LFSRs, it is very unlikely that the above weakness occurs. Concretely, in a million tries we never even got close to such a weak instance. Figure 2 shows the distribution of the entropy loss when changing the feedback polynomials of registers A and C to random primitive polynomials. This implies that the weakness in GEA-1 is unlikely to occur by chance, indicating that the security level of 40 bits is due to export regulations. As a last part of this work, we look into the security of the successor algorithm GEA-2. We conduct a state-recovery attack that does not target the initialization process, but rather the keystream generation itself. The idea is to mix a list merging algorithm, combined with algebraic techniques. The attacks works in time equivalent to 2 45.1 GEA-2 evaluations. The required memory is roughly 32 GiB. Rather than only 65 bit of known keystream as for GEA-1, this attacks needs all of the keystream available per frame, i.e., 1,600 bytes, and it cannot exploit information coming from multiple frames.

We demonstrate the practical feasibility of the attack against GEA-1 on standard hardware. Further, we discuss the real-world requirements and attack implications for today's mobile phone network. Eventually, we are dedicated to eliminating weak ciphers in current and future mobile phones -improving mobile network security.

Description of GEA-1 and GEA-2

In this section, we give a detailed description of the two algorithms GEA-1 and GEA-2, which we obtained from a source. Therefore we verify the correctness of the algorithms by a) using test vectors that are available on github [START_REF]MediaTek: Test Vector GEA1/2 -MediaTek-HelioX10-Baseband[END_REF] and b) verify the algorithm by checking the interoperability with commercial phones using the osmocom project [START_REF]osmocom: osmocom -Cellular Network Infrastructure[END_REF]. Both experiments confirm the correct functionality; thus, we can assume that the provided algorithms are accurate with a high degree of certainty.

For the encryption, the GEA algorithms take the following input parameters: the plaintext, which is the GPRS LLC (Logical Link Control) frame, the key (K), the direction bit (uplink/downlink), and the IV (Input) that consists of an increasing counter for each frame.

As we will see, GEA-2 is an extension of GEA-1-with slight but crucial exceptions. For this reason, we first describe GEA-1 first and explain the differences and extensions for GEA-2 in a second step. An overview of the keystream generation of GEA-1 and GEA-2 is shown in Figure 3.

GEA-1

GEA-1 is built from three linear feedback shift registers over F 2 , called A, B and C, together with a non-linear filter function, called f . The registers A, B, C have lengths 31, 32 and 33, respectively, and f is a Boolean function on seven variables of degree 4. The registers work in Galois mode. This means that if the bit that is shifted out of a register is 1, the bits in a specified set of positions in the register are flipped. The specification of f = f (x 0 , x 1 , . . . , x 6 ) is given in algebraic normal form as follows:

x 0 x 2 x 5 x 6 + x 0 x 3 x 5 x 6 + x 0 x 1 x 5 x 6 + x 1 x 2 x 5 x 6 + x 0 x 2 x 3 x 6 + x 1 x 3 x 4 x 6 + x 1 x 3 x 5 x 6 + x 0 x 2 x 4 + x 0 x 2 x 3 + x 0 x 1 x 3 + x 0 x 2 x 6 + x 0 x 1 x 4 + x 0 x 1 x 6 + x 1 x 2 x 6 + x 2 x 5 x 6 + x 0 x 3 x 5 + x 1 x 4 x 6 + x 1 x 2 x 5 + x 0 x 3 + x 0 x 5 + x 1 x 3 + x 1 x 5 + x 1 x 6 + x 0 x 2 + x 1 + x 2 x 3 + x 2 x 5 + x 2 x 6 + x 4 x 5 + x 5 x 6 + x 2 + x 3 + x 5 f f f f ai bi ci di zi D A B C
Fig. 3: Overview of the keystream generation of GEA-1 and GEA-2. The D register is only present in GEA-2.

Initialization. The cipher is initialized via a non-linear feedback shift register of length 64, denoted as S. This register is filled with 0-bits at the start of the initialization process. The input for initializing GEA-1 consists of a public 32-bit initialization vector IV , one public bit dir (indicating direction of communication), and a 64-bit secret key K. The initialization starts by clocking S 97 times, feeding in one input bit with every clock. The input bits are introduced in the sequence IV 0 , IV 1 , . . . , IV 31 , dir, K 0 , K 1 , . . . , K 63 . When all input bits have been loaded, the register is clocked another 128 times with 0-bits as input. The feedback function consists of f , xored with the bit that is shifted out and the next bit from the input sequence. See Figure 4 for particular tap positions. After S has been clocked 225 times, the content of the register is taken as a 64-bit string s = s 0 , . . . , s 63 . This string is taken as a seed for initializing A, B and C as follows. First, all three registers are initialized to the all-zero state. Then each register is clocked 64 times, with an s i -bit xored onto the bit that is shifted out before feedback. Register A inserts the bits from s in the natural order s 0 , s 1 , . . . , s 63 . The sequence s is cyclically shifted by 16 positions before being inserted to register B, so the bits are entered in the order s 16 , s 17 , . . . , s 63 , s 0 , . . . , s 15 . For register C the sequence s is cyclically shifted by 32 positions before insertion starts. Figure 5 depicts the process for register B. If any of the registers A, B or C end up in the all-zero state, the bit in position 0 of the register is forcibly set to 1 before keystream generation starts. s 16 , s 17 , . . . , s 63 , s 0 , s 1 , . . . , s 15 Fig. 5: Initialization of register B Keystream Generation. When all registers have been initialized, the actual keystream generation starts. This is done by taking the bits in seven specified positions in each register to be the input to f . The three outputs from the f -functions are xored together to produce one bit of the keystream. Figure 3 shows the particular feedback positions of each register, as well as showing which positions form which input to f . In Figure 3, the topmost arrow in the input to f represents x 0 , and the input at the bottom is x 6 . After calculating the keystream bit, all registers are clocked once each before the process repeats.

GEA-2

The cipher GEA-2 is a simple extension of GEA-1. A fourth register of length 29, called D, is added to the system together with an instance of f . During keystream generation, the output of f from the D register is added to the keystream together with the three others at each clock, as shown in Figure 3. The initialization process of GEA-2 follows the same mode as for GEA-1, but it is done in a longer register that is clocked more times.

Initializing GEA-2. As for GEA-1, the initialization of GEA-2 is done via a nonlinear feedback shift register, called W . The length of W is 97, and uses f as its feedback function. The input to GEA-2 are the same as for GEA-1; a 32-bit IV and a direction bit dir that are public, and a secret 64-bit key K.

Initialization starts with W being set to the all-zero state. Next, it is clocked 97 times, inserting one bit from the input sequence for each clock. The order for inserting IV, dir and K is the same as for GEA-1. After K 63 is inserted, W is clocked another 194 times, with 0 as input. This process, together with the particular tap positions for f , is shown in Figure 6. The content of W is now taken as a 97-bit string w = w 0 , . . . , w 96 , and inserted in A, B, C and D in much the same way as with GEA-1. The four registers starts from the all-zero state, and are filled with the bits of w in the same way as shown in Figure 5. The offsets of where in the sequence w each register starts is different than for GEA-1. Register D inserts the bits of w in the natural order w 0 , . . . , w 96 , whereas the registers A, B and C start with bits w 16 , w 33 and w 51 , respectively. Again, if any of the registers happens to end up in the all-zero state after initialization, the bit in position 0 is hard-coded to 1 before key generation start.

Deconstructing the Filter Function

The filter function f : F 7 2 → F 2 has a very particular Walsh (or Fourier) spectrum. Namely

f (α) = x∈F 7 2 (-1) f (x)+ α,x ∈ {0, ±2 7+1 2 } ,
for all α ∈ F 7 2 . Several ways to construct such a Boolean function are known (we refer to Claude Carlet's treatment [START_REF] Carlet | Boolean functions for cryptography and error-correcting codes[END_REF] for a detailed presentation of the required theory of Boolean functions). They appear as component functions of almost bent functions or can be constructed using bent functions in one dimension smaller. While we do not know how f was actually designed, it can certainly be decomposed into two bent functions

f i : F 6 2 → F 2 as f (x) = (1 + x 6 )f 0 (x 0 , . . . , x 5 ) + x 6 f 1 (x 0 , . . . , x 5 ) .
Furthermore, the functions f i are linearly equivalent to Maiorana-McFarland bent functions [START_REF] Mcfarland | A family of difference sets in non-cyclic groups[END_REF] (as actually all bent functions in 6 bits are classified in [START_REF] Rothaus | On "bent" functions[END_REF]). Indeed, we can decompose f 0 further into

f 0 (x 0 , . . . , x 5 ) = g 0 (x 0 , x 1 + x 2 , x 2 , x 3 , x 4 , x 5 )
where g 0 is a Maiorana-McFarland bent function given as

g 0 (x 0 , . . . , x 5 ) =   x 2 x 3 x 4   ,   x 0 + x 1 x 5 + x 5 x 0 x 1 + x 0 x 5 + x 0 + x 1 + 1 x 0 x 1 + x 5   + h 0 (x 0 , x 1 , x 5 ) ,
where

h 0 (x 0 , x 1 , x 5 ) = x 0 x 5 + x 1 x 5 + x 1 + x 5 .
In a similar fashion, f 1 can be written as

f 1 (x 0 , . . . , x 5 ) = g 1 (x 0 + x 2 + x 5 , x 1 , x 2 , x 3 , x 4 + x 5 , x 5 ) .
That is, f 1 is linearly equivalent to g 1 where g 1 is again a Maiorana-McFarland bent function. The function g 1 can be written as

g 1 (x 0 , . . . , x 5 ) =   x 0 x 3 x 4   ,   x 1 x 5 + x 2 x 5 + x 2 x 1 x 5 + x 1 + x 2 + 1 x 5 + 1   + h 1 (x 0 , x 1 , x 5 ) ,
where

h 1 (x 0 , x 1 , x 5 ) = x 1 x 2 + x 1 x 5 .
We like to note that those insights in the filter function do not play any role in our attacks and, for all we know, do not point at any weakness of the cipher. Rather, they indicate that the filter was generated following known and valid principles.

An Attack on GEA-1

First we recall some basic facts about LFSRs in Galois mode, as depicted in Figure 7. For further reading we refer to ([34, p. 378 ff.],[20, p. 227]).

. . .

∧ ∧ ∧ ∧ ∧ . . . l 0 l 1 l n-2 l n-1 a 0 a 1 a n-3 a n-2 a n-1
Fig. 7: An LFSR in Galois mode.

Given an LFSR L in Galois mode of degree n with entries in F 2 , clocking the inner state l = l 0 , . . . , l n-1 is equivalent to the matrix-vector multiplication

G L • l :=        a 0 1 0 . . . 0 a 1 0 1 . . . 0 . . . . . . . . . . . . . . . a n-2 0 0 . . . 1 a n-1 0 0 . . . 0        •        l 0 l 1 . . . l n-2 l n-1        =        a 0 l 0 + l 1 a 1 l 0 + l 2 . . . a n-2 l 0 + l n-1 a n-1 l 0        and the characteristic polynomial of G L is g(X) := X n + a 0 X n-1 + • • • + a n-2 X + a n-1 .
Throughout this work, we consider the case in which g is primitive. The characteristic polynomial g(X) is equal to the minimal polynomial of G L if and only if a n-1 = 1. Vice versa, given a primitive polynomial g(X)

:= X n + a 0 X n-1 + • • • + a n-2 X + a n-1 , then G L :=        a 0 1 0 . . . 0 a 1 0 1 . . . 0 . . . . . . . . . . . . . . . a n-2 0 0 . . . 1 a n-1 0 0 . . . 0       
is the companion matrix of an LFSR in Galois mode with minimal polynomial g. We call such a matrix the Galois matrix and the corresponding minimal polynomial the Galois polynomial in the sequel. Moreover, given an LFSR L in Galois mode with minimal (primitive) polynomial g, we denote the Galois matrix with G g . In the case of GEA-1 the Galois polynomials are

g A (X) = X 31 + X 30 + X 28 + X 27 + X 23 + X 22 + X 21 + X 19 + X 18 + X 15 + X 11 + X 10 + X 8 + X 7 + X 6 + X 4 + X 3 + X 2 + 1 , g B (X) = X 32 + X 31 + X 29 + X 25 + X 19 + X 18 + X 17 + X 16 + X 9 + X 8 + X 7 + X 3 + X 2 + X + 1 , g C (X) = X 33 + X 30 + X 27 + X 23 + X 21 + X 20 + X 19 + X 18 + X 17 + X 15 + X 14 + X 11 + X 10 + X 9 + X 4 + X 2 + 1 .
The initialization process of the registers A, B and C with the string s is obviously linear. Hence there exist three matrices

M A ∈ F 31×64 2 , M B ∈ F 32×64 2 and M C ∈ F 33×64 2 such that α = M A s , β = M B s , γ = M C s ,
where α, β and γ denote the states of the three LFSRs after the initialization phase. We exclude here the unlikely case that α, β or γ is still in the all-zero state after the shifted insertion of s.

We are now interested in the number of possible starting states of the registers after this initialization. For those considerations, we used the computer algebra system sagemath [START_REF]The Sage Developers: SageMath, the Sage Mathematics Software System[END_REF]. The corresponding code is attached in Appendix A. The first observation is that all the three matrices have full rank. This implies that the number of possible starting states after initialization is maximal when each LFSR is considered independently, i.e. there are 2 31 possible states for register A, 2 32 possible states for register B, and 2 33 possible states for register C, as should be expected. However, when considering pairs of registers, the picture changes drastically. In particular, the number of possible joint states after initialization of the registers A and C is much smaller than expected. For this it is convenient to consider the kernels of the linear mappings. Clearly, the corresponding linear mappings represented by M A , M B and M C have kernels of dimension of at least 33, 32 and 31, respectively. If we denote T AC := ker(M A ) ∩ ker(M C ) and U B := ker(M B ) then, curiously enough, we have

1. dim(T AC ) = 24 and dim(U B ) = 32 , 2. U B ∩ T AC = {0} .
From this it directly follows that F 64 2 can be decomposed into the direct sum U B ⊕ T AC ⊕ V , where V is of dimension 8. Thus, for the key-dependent and secret string s, there exists a unique representation s

= u + t + v with u ∈ U B , t ∈ T AC , v ∈ V and β = M B (u + t + v) = M B (t + v) α = M A (u + t + v) = M A (u + v) γ = M C (u + t + v) = M C (u + v) .
From this decomposition, s can be computed with a Divide-and-Conquer attack with a complexity5 of 2 37 GEA-1 evaluations to build (and sort) 2 8 tables with 2 24 entries of size 89 bits and a brute-force step of complexity 2 40 GEA-1 evaluations for each new session key K 0 , . . . , K 63 . The details will be given in Section 3.1.

In other words, the joint state of A and C can be described with only 40 bits and thus can take only 2 40 possible values. This is the key observation of the attack and the weakness that is highly unlikely to occur unintentionally.

Once s is determined, K 0 , . . . , K 63 can be recovered as follows. Let S i denote the state of register S after i clocks of initialization. So S 0 = (0, 0, . . . , 0) and S 225 = (s 0 , s 1 , . . . , s 63 ) where all the s j are known (see also Figure 4). The last 128 clocks of S all insert 0-bits from the string containing K, dir and IV , so it is straightforward to clock S 225 backwards 128 times and find the content of S 97 . Let S 97 = (a 0 , a 1 , . . . , a 63 ), where all the a i are known.

Starting from the other side, the first 33 clocks of S 0 only insert the known bits IV 0 , IV 1 , . . . , IV 31 , dir, so the content of S 33 is fully known. The next clock inserts K 0 +b 0 at position 63 of S 34 , where b 0 is a known bit. Further clocking do not change the content of this cell, but only shifts it further positions to the left, so after 63 clockings starting from S 34 we have S 97 = (K 0 + b 0 , . . .). Equating S 97 from the forward direction with S 97 from the backward direction gives us

K 0 = a 0 + b 0 .
With K 0 known, position 63 of S 35 can now be given as

K 1 + b 1
, where b 1 is known. Clocking S 35 forward 62 times gives S 97 = (K 0 + b 0 , K 1 + b 1 , . . .) and again equating with S 97 from the backwards side gives K 1 = a 1 + b 1 . Continuing this way recovers the whole session key K. Hence, the attack has to be conducted only once per GPRS session and is done in 2 40 operations once the table has been established.

A Simple Divide-and-Conquer Attack on GEA-1

A table Tab is built by exhaustive search over the 2 32 values

β t,v = M B (t + v), t ∈ T AC , v ∈ V ,
plugging β t,v into register B and clocking it times. The parameter will be determined later. The table is divided into 2 8 sub-tables Tab[v] indexed by v; the output bits b

(0) t,v , . . . , b ( -1) t,v
(after applying the filter f ), together with t, are stored in Tab [v]. We then sort each Tab [v] according to b

(0) t,v , . . . , b ( -1) t,v
interpreted as an -bit integer. The table has 2 32 entries of size + 24 bits, so it can be generated and sorted with a complexity of 32 • 2 32 = 2 37 operations if the size of is negligible (which it is, as we will see below).

Given bits of keystream z i , the sequence s is recovered as follows. First, an exhaustive search is conducted over the 2 40 values

α u,v = M A (u + v), γ u,v = M C (u + v), u ∈ U B , v ∈ V ,
plugging α u,v into A, γ u,v into C and clocking both registers times. We denote by a

(0) u,v , . . . , a ( -1) u,v , resp., c (0) u,v , . . . , c ( -1)
u,v , the output stream of register A, resp., C after applying the filter f . For each (u, v), the output stream

a (0) u,v ⊕ c (0) u,v ⊕ z 0 , . . . , a ( -1) u,v ⊕ c ( -1) u,v ⊕ z -1
is generated and it is checked whether there is a match in Tab [v]. In the positive case, this gives candidates for u, t and v and finally for s = u ⊕ t ⊕ v if and only if the entry is found in Tab [v]. The overall complexity of this step is 2 40 , assuming that generating bits of keystream, together with a search in the sorted table is below the complexity of one GEA-1 evaluation (for generating a keystream of size 128 bit).

The correct key will always be identified, but this procedure can also suggest some wrong keys, depending on the value of . There is a trade-off between the amount of known plaintext available, the size of table, and the number of remaining keys. A wrong partial key u⊕v yields a bitstream stored in Tab[v] with probability 1 2 for each entry, if we assume the widely accepted hypothesis that an bit output of a filtered LFSR behaves like uniformly distributed random bits as long as is below its period (which will be the case here). We have 2 24 entries in Tab[v], thus there are at most 2 24 possible correct entries per partial key. In other words, the probability that a wrong partial key does not cause a

hit in Tab[v] is 1 -1 2 2 24
and therefore the probability that none of the wrong partial keys cause a hit is

1 - 1 2 2 24 (2 40 -1) ≈ 1 - 1 2 2 64
.

If we want the probability for no false hit to be larger than or equal to 1 2 , we can choose = 65, for which we get 1 -1 2 2 64 ≈ 0.607. The corresponding size of the table Tab with this choice for is only 44.5 GiB and it can be built in time 2 37 .

If we only have n < 65 known plaintext bits, we obtain a set of roughly 2 64-n remaining keys; if n ≥ 24 we expect less than 2 40 candidate keys, and can try each of them without increasing significantly the complexity of the attack. The key candidates can be verified using redundancy in the frame (e.g. checksums), or known bits in a different frame (e.g. headers). We need 65 known bits of information in total, but they can be spread over several frames as long as one frame has 24 bit of known plaintext. In practice, there are many GPRS frames with predictable content, so that intercepting a ciphertext with some known plaintext bits is not an issue (see Section 5.1 for details). Thus the attack is fully practical.

Note that the attack presented is rather straightforward and can probably be optimized. Moreover, several trade-offs are possible. For instance, one can alternatively apply the attack by building a table corresponding to the 2 40 choices of α u,v , γ u,v and then performing an exhaustive search over 2 32 values for β t,v . This way, one would need 2 32 GEA-1 evaluations as the online time complexity, but much more memory for storing the table. For example, the memory needed to store 2 40 values of 65-bit length is 8.125 TiB.

On the Likelihood that dim(T AC ) = 24. We did an extensive computer search to answer the question if the situation in GEA-1 is unlikely to occur. To do so, over 10 6 samples, we randomly generated two primitive polynomials g 1 , g 2 of degrees d 1 , d 2 , built the corresponding Galois matrices G g1 , G g2 , computed the representation matrices M Gg 1 , M Gg 2 ,cs for the initialization and computed the dimension of the intersection T Gg 1 ,Gg 2 ,cs . Here, the parameter cs denotes the cyclic shift applied in the initialization process of the register. In Tables 1,2, and 3, the results for the parameters as in GEA-1 are given, i.e., for the parameters Recall that in GEA-1, the intersection is of dimension 24. Thus, in general, our attack is avoided almost automatically when choosing random primitive feedback polynomials and further research needs to be conducted to better understand the design of GEA-1. Experimental Verification. In this section we address our C++ implementation of the simple Divide-and-Conquer attack on GEA-1.

We first utilized sage to generate V and bases for T AC and U B . We then built a table Tab of 2 32 entries, similarly as described above. Notice that each sub-table Tab[v] is implemented as an array of 2 19 sorted vectors containing entries consisting of 64 bits for b t,v and 24 bits representing t. The remaining bit of b t,v is implicitly stored as an index in Tab [v]. Tab is stored on disk such that it can be loaded when the attack gets executed again.

Given 65 bits of keystream z i , the recovery of the initial state s is implemented as follows. For each combination of u ∈ U B and v ∈ V the output stream is generated using a bitsliced implementation of A and C. To check whether there is a match in Tab we search through the vector at Tab [v][idx] where idx represents the 19 most significant bits of the output stream. If there is a match we restore t from Tab and return s = u⊕t⊕v. To speed things up we parallelized both the generation of Tab and the recovery of s using OpenMP [START_REF] Dagum | Openmp: an industry standard api for shared-memory programming[END_REF].

To test our implementation we first picked random values for t, u, v. After this we determined suitable values for K, IV and dir by clocking the register S backwards. Then we used the GEA-1 implementation that we were provided with to generate 65 keystream bits. Finally we checked if our attack restores the correct initial state s = u ⊕ t ⊕ v.

We executed the attack on a cluster made up of four AMD EPYC 7742 64-Core Processors. Generating and storing Tab takes 30 minutes whereas loading it from disk only takes five minutes. Tab is 46 GiB in size and the recovery of s has a running time of 25 minutes averaged over six runs.

An Attack on GEA-2

GEA-2 does not suffer from the same problems as GEA-1 for initialization. However, it is still possible to mount an attack on GEA-2 that does not target initialization, but keystream generation. The idea is to combine a list merging algorithm and algebraic techniques.

Algebraic Cryptanalysis

The algebraic degree of the filtering function f is 4. The filtering function also has an algebraic immunity of 4. But, as the 4 registers are never mixed, the number of monomials present in the system of equations formed by the relations between the keystream and the initial state is very limited. More precisely, this number is upper bounded by 1 +

4 i=1 29 i + 31 i + 32 i + 33 i = 152682 .
This relatively small number would directly imply a powerful attack, just by using a linearisation technique, or, even more powerful, by applying the Berlekamp-Massey algorithm [START_REF] Berlekamp | Algebraic coding theory. McGraw-Hill series in systems science[END_REF][START_REF] Massey | Shift-register synthesis and BCH decoding[END_REF], as this value is naturally an upper bound to the linear complexity of the output (a direct consequence of Blahut's Theorem [START_REF] Blahut | Theory and practice of error control codes[END_REF]).

However, each session in GEA-2 (or GEA-1) is limited to 1600 bytes, that is 12800 bits. This data limitation frustrates direct algebraic cryptanalysis, as the linearization technique is impossible when we have less equations than monomials.

Guess-and-Determine

The Guess-and-Determine technique seems to have its origin already in the cryptanalysis of A5/1 cipher [START_REF] Golic | Cryptanalysis of alleged A5 stream cipher[END_REF][START_REF] Anderson | A5 (was hacking digital phones)[END_REF]. It can be a powerful technique, specially for analyzing stream ciphers. In the context of algebraic cryptanalysis, it has been shown in [START_REF] Duval | Cryptanalysis of the FLIP family of stream ciphers[END_REF] that Guess-and-Determine can really help to provide much simpler systems of equations. In a context of general multivariate system solving algorithms, this technique is known as the hybrid approach [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF].

For GEA-2, we mainly want to reduce the number of monomials present in our system below 12800. By guessing n d , n a , n b and n c bits in the registers D, A, B and C respectively, we find that the number of non-constant monomials in the equations is upper bounded by

4 i=1 29 -n d i + 31 -n a i + 32 -n b i + 33 -n c i .
To get a system of equations of size below 12800 one needs to guess at least 59 bits of the initial state. One choice is n d = 29 -16 = 13 bits in the first register, n a = 31 -16 = 15 bits in the second register, n b = 32 -17 = 15 bits in the third register and n c = 33 -17 = 16 bits in the fourth register.

This leads to an attack complexity of 2 59 times the cost of solving a linear system of size 12800, which is much more than the cost of the exhaustive search. We therefore need to combine guessing with other techniques.

Divide-and-Conquer Technique

The sum of the output of the four filtered registers frustrates the specific Divideand-Conquer cryptanalysis described by T. Siegenthaler in 1985: correlation attacks [START_REF] Siegenthaler | Decrypting a class of stream ciphers using ciphertext only[END_REF].

However, Divide-and-Conquer techniques can also be applied when we adapt it for the following problem. We are given two sets S 1 and S 2 , as well as two functions

f 1 : S 1 → F c 2 and f 2 : S 2 → F c 2 .
For a given t ∈ F c 2 the problem is to find all s 1 ∈ S 1 and s 2 ∈ S 2 such that f 1 (s 1 ) + f 2 (s 2 ) = t. This problem arises quite often in cryptography and started in [START_REF] Schroeppel | A T=O(2 n/2 ), S=O(2 n/4 ) algorithm for certain npcomplete problems[END_REF] with the cryptanalysis of the knapsack-based cryptosystem. Since then, advanced solving techniques have shown they can be a powerful tool for the cryptanalyst [START_REF] Bogdanov | A 3-subset meet-in-the-middle attack: Cryptanalysis of the lightweight block cipher KTANTAN[END_REF][START_REF] Dunkelman | Improved meet-in-the-middle attacks on reduced-round DES[END_REF][START_REF] Sasaki | Meet-in-the-middle preimage attacks on AES hashing modes and an application to Whirlpool[END_REF][START_REF] Lamberger | Rebound distinguishers: Results on the full whirlpool compression function[END_REF][START_REF] Khovratovich | Cryptanalysis of Luffa v2 components[END_REF].

One way to solve this problem is to use a hash table H. Typically, for all s 1 ∈ S 1 we compute f 1 (s 1 ) and add s 1 to H [f 1 (s 1 )]. Then for each s 2 ∈ S 2 we compute f 2 (s 2 ) and check the corresponding values for

s 1 in H [t + f 2 (s 2 )].
Using the right structure for H the complexity of exhausting all the solutions is

O(|S 1 | + |S 2 |) in time and O(|S 1 |) in memory.
Remark. This algorithm performs |S 2 | random accesses to H. If the table is too large to fit in RAM it may be faster to build the two lists, then to sort them and finally to sequentially go through them to find matches.

Description of the Attack

The techniques involved in our attack do not work in practice when used alone. However, they can be combined in an elegant way to recover the initial state with complexity significantly lower than 2 64 . Our attack works as follows.

1. Guess n a + n d bits in both registers A and D (note that the choice of values for n a and n d is not the same as in Section 4.2). The choice of registers A and D has been done with respect to their length, so as the choice of n a and n d that lead to the smallest number of guesses. 2. Using linearization technique, derive linear combinations of the keystream bits that are independent of the remaining variables in registers A and D. This corresponds to a set a linear masks m i , for 1 ≤ i ≤ c, such that for all i, m i • s A+D is constant, where s A+D denotes the xor-sum of the sequences generated by the registers A and D, and • is the scalar product. 3. Apply the Divide-and-Conquer technique described previously, with S 1 covering all initial states β in register B and S 2 covering all initial states γ in register C, with f 1 and f 2 being defined by the linear masks, and t i defined as m i • z ⊕ m i • s A+D , where z is the known keystream, and m i • s A+D is known:

f 1 : β → (m 1 • s B , . . . , m c • s B ) f 2 : γ → (m 1 • s C , . . . , m c • s C )
First, we build polynomials corresponding to the output of each filtered register, with the initial value of the register bits as variables. We use register C as an example since it is the largest one. Since the LFSR is linear, we can write the state as a matrix representing the linear expression of each bit in terms of the 33 variables; clocking the LFSR is just a matrix product with a total cost of at most 12800 × 33 3 = 2 28.8 . This could probably be improved further, but will be a negligible cost in the attack anyway.

Next, we notice that guessing n d = 9 bits from register D and n a = 11 bits from register A decreases the number of possible non-constant monomials in the 20+20 remaining variables from A and D to

4 i=1 20 i + 20 i = 12390
which is smaller than the amount of data available per session. Thus we can perform a Gaussian elimination on the system of equations to derive at least 12800 -12390 = 410 linear masks m i on the output of A and D, such that every non-constant monomial vanishes. On a 64-bit computer the cost of this step is around 12800 × 12390 × 12390/64 = 2 34.8 simple operations on 64-bit words.

In order to evaluate f 1 and f 2 efficiently, we write them as polynomials in the B and C variables, respectively. To do so we first choose c = 64 masks and we compute the corresponding polynomial expressions of outputs from B and C. This corresponds to multiplying a binary matrix of size 12800×(

4 i=1 32 i + 33
i ) by a binary matrix of size 64×12800. This requires 64×12800×88385/64 = 2 30.1 simple operations on 64-bit words. We also apply the masks to the keystream sequence with a negligible cost.

At the end of the previous step we have 64 equations of the form P i B = P i C where P i B and P i C are polynomials in variables from registers B and C respectively and we can apply the Meet-in-the-Middle technique to retrieve the possible values for B and C. First we evaluate (P 0 B , P 1 B , . . . , P 63 B ) for all the 2 32 possible initial states of register B and store the result in a hash table H. Then we evaluate (P 0 C , P 1 C , . . . , P 63 C ) for all the 2 33 possible starting states of C and get the corresponding values for B by looking into the hash table. Using the enumeration technique of [START_REF] Bouillaguet | Fast exhaustive search for polynomial systems in F 2[END_REF], we can evaluate the 64 degree-4 polynomials on all 2 n states for a cost of only 2 n × 64 × 4 bit operation. Therefore, the cost of this step is roughly (2 32 + 2 33 ) × 4 × 64/64 = 2 35.6 operations on 64-bit words plus 2 32 + 2 33 = 2 33.6 random accesses to the hash table.

Finally, for all the remaining values for registers B and C we solve the system of equations in variables from A and D. As it was already echelonized in the first step of the attack we only have to check whether it is consistent or not, requiring approximately 12390 bit-operations. Since there are only a few remaining key candidates, this step is negligible.

Overall the attack requires:

-2 20 × (2 34.8 + 2 30.1 + 2 35.6 ) = 2 56.3 operations on 64-bit words -2 20 × (2 33.6 ) = 2 53.6 memory accesses In terms of GEA-2 operations, we assume that one encryption requires at least 64 word operations 6 , and that one memory access is comparable to an encryption call. Therefore the complexity is equivalent to 2 53.7 GEA-2 encryptions. The memory complexity corresponds to 2 32 × 64 = 2 38 bits.

Improved Attack

We have developed two tricks to decrease the complexity of our attack against GEA-2. The first one is based on the observation that we perform the same computations several times and that this can be avoided by reorganizing them. The second improvement is highly inspired from classical time/data trade-offs where a sequence of n keystream bits can be seen as k (shifted) sequences of n -k keystream bits.

Gaussian Elimination Only Once. The first Gaussian elimination is performed 2 20 times, once for each guessed value of the 20 chosen bits of registers A and D. But since the polynomials are of degree 4, guessing a variable cannot create a monomial of degree 4. Thus, before starting to guess variables, it is possible to partially echelonize the system by removing all degree 4 monomials which do not contain a variable that will be guessed. This removes 20 4 + 20

4

= 9690 equations and requires 12800 × ( -2 36.9 + 2 20 × (2 28.4 + 2 30.1 + 2 35.6 ) = 2 55. 6 operations on 64-bit words -2 20 × (2 33.6 ) = 2 53.6 memory accesses Reducing Number of Guesses. We can improve the attack using the classical trick of targeting the internal state at several different clocks, instead of focusing only on the initial state. The novelty here is that we can find masks which simultaneously work for several shifted keystream sequences.

First, we use n d = 10 and n a = 11, so that the number of non-constant monomial from A and D is only

4 i=1 19 i + 20 i = 11230
. We target one of the 753 first internal states, therefore we extract shifted keystream sequences of length 12047 produced by each of those states. The initial state produces keystream z 0 • • • z 12046 , the state after one clock produces keystream z 1 • • • z 12047 , and so on. We define V as the vector space of masks m (of length 12047) such that m • z is independent of z for all the 753 sequences considered; V has dimension 12047 -753 + 1 = 11295.

Using the strategy of the previous attack, for each guess of the 21 bits in registers A and D, we can deduce a vector space of dimension 12047 -11230 = 817 of masks such that m i • s A+D is constant. We intersect this vector space with V to obtain a space of dimension 65 of masks such that both m i • s A+D and m i • z are constant, and we run the previous attack with 64 independent masks from this space.

The probability that the guess of the 21 bits is correct for at least one of the 753 first internal states is 1 -(1 -2 -21 ) 753 ≈ 2 -11.4 . Thus we have to repeat this step with 2 11.4 different guesses on the average, and the time complexity becomes:

-2 36.9 + 2 11.4 × (2 27.9 + 2 30.1 + 2 35.6 ) = 2 47 operations on 64-bit words -2 11.4 × (2 33.6 ) = 2 45 memory accesses This is equivalent to roughly 2 45.1 GEA-2 encryptions.

Recovering the Master Key

This attack recovers the internal states of the registers A, B, C and D, either at the beginning or after a few clocks. From this we can easily recover the sequence w, because the initialization and the update of the LFSRs are linear functions. As in the case of GEA-1, we can also recover the master key by clocking the W register forwards from the zero state, and backwards from the recovered state w. Therefore, we only have to perform the attack once per GPRS session; we can decrypt all the messages in a session if we have one known message of length 1600 byte.

Using Less Data

Our attack can be applied with less data than 12800 bits of keystream. In that case the time complexity is increased as shown in Figure 8. To reach a complexity below 2 64 (the complexity of an exhaustive search on the key), we need around 1468 consecutive keystream bits.

Experimental Verification

We now briefly describe our proof of concept implementation of the attack on GEA-2. The implementation consists of a sage and C++ part which is made accessible to sage using Cython.

In an initial step we built matrices that represent polynomials corresponding to the filtered output of B and C by evaluating B and C symbolically in sage.

Here we enumerated the 12 most significant bits and therefore we do not have one but 4096 matrices for each register. This allows straightforward parallelization of the Divide-and-Conquer step when using the enumeration technique of [START_REF] Bouillaguet | Fast exhaustive search for polynomial systems in F 2[END_REF]. The matrices are stored on disks such that they can be loaded when the attack gets executed again.

Given the keystream we first compute V as described above. Then we start guessing 21 bits in A and D. For each guess we compute 64 corresponding masks. These are then handed over to the C++ part which builds upon the M4RI [START_REF] Albrecht | The M4RI Library[END_REF] To test our implementation we picked random values for K, IV and dir and computed the keystream with the GEA-2 implementation we were provided with. We also determined the first 753 internal states such that we can directly check whether a guess of the 21 bits in A and D was correct or not.

We executed the attack on the same hardware as for the GEA-1 attack. It takes about one hour to perform the calculations on one guess and therefore we get roughly four months as the runtime of a full attack.

Discussion

In the following, we discuss the real-world attack feasibility, the attack severity and the attack implications.

Attack Requirements

To recover the full session key of a GEA-1 encrypted connection, the attacker must meet the following conditions: The attacker must i) sniff the encrypted radio traffic of the victim's phone and ii) know 65 bits of the keystream, preferably at the beginning of the keystream. As shown by Nohl and Melette [START_REF] Nohl | GPRS intercept: Wardriving your country[END_REF], sniffing the encrypted traffic can be conducted with the osmocom-bb project [START_REF]osmocom: osmocom -Cellular Network Infrastructure[END_REF] using ordinary hardware.

Meeting the requirement of knowing 65 bits of the keystream can be achieved by exploiting predictable SNDCP (Subnetwork Dependent Convergence Protocol) and IP header patterns. A GPRS data connection encapsulates each IP packet with the SNDCP, which is then encrypted by the LLC (Logical Link Control) protocol. In a small experiment, we study patterns that remain stable and predictable over multiple GPRS connections in the SNDCP and IP header. Header fields like the SNDCP NSAPI, the IP Version, TTL, ToS, and destination IP address fields remain stable over multiple connections. Consequently, guessing 65 plaintext bits and obtaining 65 keystream bits is plausible by an entirely passive attacker.

In contrast, the attack on GEA-2 requires the attacker to know the whole 1600 bytes of keystream to recover the session key with complexity 2 45.1 GEA-2 evaluations. Accordingly, the attacker must correctly predict 1600 bytes of plaintext. Depending on the attacker's capabilities, this can be within the area of possibility. If the attacker controls a server that the victim visits, he can access the bytes sent or receives, and consequently, the attack can predict 1600 bytes. The recovered key is then valid for the whole GRPS session, including other traffic of interest. Such an attack may require some social engineering, e. g., a phishing attack, to convince the victim to visit the website.

Attack Severity

In GPRS the operator chooses the encryption algorithm, i. e., GEA-1, GEA-2, GEA-3 (based on KASUMI with a 64-bit key), or GEA-4 (based on KASUMI with a 128-bit key). According to a study by Tomcsányi et al. [START_REF] Domonkos | Analysis of EG-PRS Ciphering Algorithms used Worldwide[END_REF], that analyzes the use of the ciphering algorithm in GRPS of 100 operators worldwide, most operators prioritize the use of GEA-3 (58) followed by the non-encrypted mode GEA-0 (38). Only a few operators rely on GEA-2 (4), while no operator uses GEA-1 (0). Consequently, the likelihood for an attack based on the GEA-1 and GEA-2 vulnerabilities is nowadays comparably small.

To draw a complete picture, we additionally analyze the support of both algorithms in mobile phones. Since 2013, ETSI prohibits implementing GEA-1 in mobile stations, while GEA-2 and the non-encrypted mode (GEA-0) are still mandatory to be implemented [START_REF]ETSI: Digital cellular telecommunications system ([END_REF]. We tested a range of current phones if they follow the specification regarding disabling the GEA-1 cipher. We use an osmocom GPRS setup which we extended with the support of GEA-1 and GEA-2 [START_REF]osmocom: osmocom -Cellular Network Infrastructure[END_REF]. Table 4 shows a selection of phones in which we cover a wide range of baseband manufacturers. Those manufacturers are responsible for implementing the standard accordingly. Surprisingly, all tested phones support the vulnerable ciphers GEA-1, thereby clearly disrespecting the specification.

Once the key is recovered, the attacker can decrypt all traffic for the complete GPRS session until the key gets invalid, which happens in the GPRS authentication and ciphering procedure triggered by the network. The start of this procedure depends on the operator's policy. Usually, the procedure starts on an expired timer, e. g., 1-24h, or the change of a location area, which is a regional group of base stations. would indeed reduce the amount of known keystream needed, it turns the attack into a chosen IV attack, which limits its practical interest.

Responsible Disclosure and Industry Implications

Following the guidelines of responsible disclosure, we have disclosed the vulnerability to the GSMA and ETSI Coordinated Vulnerability Disclosure programme [19] [START_REF]ETSI: ETSI -Coordinated Vulnerability Disclosure[END_REF]. We, thereby, followed two aims: In short term, we want to disable the support of GEA-1 from all mobile phones and thereby restore the specifications conformity. For mitigating the mid-risk of exploiting the GEA-2 vulnerabilities, we advocate for removing the support of GEA-2 from the specification.

The main objective of the GSMA CVD program was to disable the support of GEA-1. The GSMA informed the affected baseband vendors, phone manufacturers, including Google and Apple, through the CVD program. Further, the GSMA liaised with GCF (Global Certification Forum) [START_REF]GCF: GCF -Global Certification Forum[END_REF], the mobile industry's globally recognized certification scheme for mobile phones and wireless devices based on 3GPP standards. The GCF included two test cases as part of version 3.81.0 of the certification criteria, which became available for certification in January 2021. These are: Conformance test case 44.2.5.2.5 Ciphering mode / Non-support of GEA-1 from 3GPP TS 51.010-1 and field trial test case 5.6.5 GPRS functionality -Non-support of GEA-1 from GSMA TS.11. Those test cases now allow to verify that the support of GEA-1 is disabled by devices before entering the market.

In contrast, the submission to the ETSI CVD program followed the mid-term goal to remove the support of GEA-2 from the specification and consequently also from mobile devices. At the time of paper finalization, the ETSI has accepted our CVD submission and considers whether any standards related measures need to be taken. Specification changes usually require the consent of several parties and take accordingly longer. We will continue to fight for removing the support of GEA-2 from the specification.

Conclusion

We have shown that the first version of the GPRS Encryption Algorithm, GEA-1, only offers 40-bit (out of 64) security. We have further shown that it is very unlikely for a random instance to suffer from such weaknesses. Since GEA-1 was designed to be exportable within the export restrictions in European countries in the late 1990s, this might be an indication that a security level of 40 bits was a barrier for cryptographic algorithms to obtain the necessary authorizations. Ultimately, the weak design of GEA-1 brings security problems for today's communication, even if it is not being actively used by the operators.

The successor algorithm GEA-2 seems to be a stronger design, in which the weaknesses of GEA-1 are not present anymore. Still, the cipher does not offer full 64-bit security and we have shown an attack of complexity 2 45.1 GEA-2 evaluations. Although such an attack is more difficult to be applied in practice, we think that GEA-2 does not offer a high enough security level for todays standards. Therefore, we strongly recommend that only the much more secure GPRS Encryption Algorithms, starting from GEA-3, should be implemented.

Fig. 2 :

 2 Fig. 2: The distribution of the entropy loss within the joint initial 64-bit state of registers A and C after the linear initialization in GEA-1 for a random sample of 10 6 combinations of primitive LFSRs. The occurences of entropy losses up to 4 bits are omitted.

Fig. 4 :

 4 Fig. 4: Initialization of register S

Fig. 6 :

 6 Fig. 6: Initialization of register W

d 1 =

 1 31 and d 2 = 32, d 1 = 31 and d 2 = 33, d 1 = 32 and d 2 = 33 with the corresponding shifts. A Sage program that allows the reader to repeat those experiments is provided in Appendix B.

4 i=1 29 i

 429 + 31 i ) × 9690/64 = 2 36.9 operations on 64-bit words. Then for each guess the first Gaussian elimination is performed on a matrix with 12800-9690 = 3110 rows and 3 i=1 20 i + 20 i = 2700 columns. As a consequence, the time complexity of the attack becomes:

Fig. 8 :

 8 Fig.8: Time complexity of our attack against GEA-2 as a function of the number of consecutive keystream bits available.

Table 1 :

 1 Behavior of intersections for randomly generated LFSRs of lengths d 1 = 31, d 2 = 32 and cs = 16 (10 6 tries)

	Dimension of intersection < 5	5	6	7	8	9	10 11
	# of spaces	996,027 3,002 742 171 49	6	1	2

Table 2 :

 2 Behavior of intersections for randomly generated LFSRs of lengths d 1 = 31, d 2 = 33 and cs = 32 (10 6 tries)

	Dimension of intersection < 5	5	6	7	8	9	10 11
	# of spaces	998,027 1,490 366 86 26	5	0	0

Table 3 :

 3 Behavior of intersections for randomly generated LFSRs of lengths d 1 = 32, d 2 = 33 and cs 1 = 16, cs 2 = 32 (10 6 tries)

	Dimension of intersection < 5	5	6	7	8	9	10 11
	# of spaces	999,065 701 181 39 10	3	1	0

Available via https://www.legifrance.gouv.fr/jorf/id/JORFTEXT000000753702 and https://www.legifrance.gouv.fr/jorf/id/JORFTEXT000000753703, accessed Oct-06,

[START_REF] Berlekamp | Algebraic coding theory. McGraw-Hill series in systems science[END_REF] See minute 32:15 of the recorded talk.

The size of the registers are visible in the live state-recovery attack, see minute

48:25 of the recorded talk.[START_REF]Selected Areas in Cryptography -17th International Workshop, SAC 2010[END_REF] The authors acknowledged Mate Soos for ideas and also admitted that the live attack did not apply the SAT solver yet.

The complexity will be measured by the amount of operations that are roughly as complex as GEA-1 evaluations (for generating a keystream of size ≤ 128 bit).

In a brute-force search, the initialization requires at least 195 clocking of the W register per key.

Acknowledgment

This work was supported by the German Research Foundation (DFG) within the framework of the Excellence Strategy of the Federal Government and the States -EXC 2092 CaSa -39078197, and by French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE48-0017 (project SELECT). Patrick Derbez was supported by the French Agence Nationale de la Recherche through the CryptAudit project under Contract ANR-17-CE39-0003.

Most of all, we give thanks to Dieter Spaar and Harald Welte for their support and contact persons of the osmocom project.

Attack Implications

GEA-1 provides 40-bit security and is breakable by today's standard hardware. This fact causes severe implications for our mobile Internet connection during the early 2000s and now. During the early 2000s, Internet connections were barely secured by any transport layer security, such as TLS. Under the assumption that an operator used GEA-1 for the network, the entire traffic was accessible to a passive attacker. In contrast, nowadays connections are mostly secured by TLS. However, if the network encryption can be bypassed (as with GEA-1), metadata is still accessible, such as DNS requests, IP addresses, and hostnames when using the TLS SNI extension. Consequently, the use of GEA-1 has still far-reaching consequences on the user's privacy and should be avoided at all costs.

Even if the operator uses a stronger cipher like GEA-3, the support of GEA-1 by the phone allows an attacker to recover a previous session key. A requirement for this attack is that the operator also relies on GSM authentication. GSM authentication is not replay protected, and thus the attacker can replay the previous authentication request with a fake base station and instruct the phone to use the vulnerable cipher (Authentication and Ciphering Request). After a complete attack procedure, sending the ciphering request forces the phone to use a weak cipher (i.e. GEA-1) for the next data uplink packet. At that point, the attacker can guess the plaintext to recover parts of the keystream and thus also the previous session key. Consequently, the attacker can decrypt the previous session, which was encrypted with a stronger cipher, e. g., GEA-3. This shows that even when operators do not actively use GEA-1, the weak GEA-1 design affects the security of today's communication.

Time/Memory Trade-Off Attack against GEA-2. While the present attack against GEA-2 has a complexity of 2 45 GEA-2 evaluations and requires a large amount of known keystream, we could also think of a time/memory trade-off attack against GEA-2. However, in contrast to A5/1 where this could be applied [START_REF] Kalenderi | Breaking the GSM A5/1 cryptography algorithm with rainbow tables and high-end FPGAS[END_REF], the initial state of 125 bits prohibits any such attack aiming for the initial state. Building a time/memory trade-off, using e.g. rainbow-tables, (see [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF]) targeting directly the 64 bits secret key would only work for a fixed IV. While it

Appendix A Source Code to Compute the Kernels

Listing 1.1: gea1 kernels.sage def g e t I n i t M a t r i x ( p , keyLength , s h i f t ) :

P.<x> = PolynomialRing (GF( 2 ) ) l = p . d e g r e e ( )

#c o n s t r u c t t r a n s f o r m a t i o n m a t r i x A f o r LFSR i n G a l o i s mode

MA = g e t I n i t M a t r i x (pA , keyLength , s h i f t A ) MB = g e t I n i t M a t r i x (pB , keyLength , s h i f t B ) MC = g e t I n i t M a t r i x (pC , keyLength , s h i f t C )