Method and system for the cryptanalysis of GSM encryption

Technical field [0001] The invention relates to methods of cryptographic analysis, in particular cryptographic analysis with encrypted text of GSM encrypted communication, received from the ether.

[0002] The invention is planned to be published as a scientific article and presented at the Crypto 2003 conference, August 17-21, 2003, Santa Barbara, California, USA. [0003] Document WO 01/89253 A1 relates to the authentication of connections between user terminals and network access points in a cellular telecommunications system. This document presents the proposed authentication queries and responses to be exchanged between access points and terminals, which queries may contain information regarding the encryption algorithms supported by a given communication network. In addition, this document outlines the devices and methods for implementing the authenticated methods / procedures laid out.

Background of the invention [0004] This section details the need for the invention, the state of the art of cryptographic analysis methods and the encryption method currently used in GSM.

[0005] GSM is the most common method of cellular communication. It includes a means of data protection by encryption, which decryption may sometimes be desirable.

[0006] For example, law enforcement agencies such as the police may need to eavesdrop on cellular communications without being physically connected to the cellular infrastructure. This process often requires court permission and is sometimes referred to as legal wiretapping.

[0007] Customers have a sense of security when using a cell phone, which is sometimes unreasonable. Eavesdroppers can listen to a conversation, impersonate a call or make calls at the user's expense. Checking the level of system security by attempting to attack the system may be desirable. This way you can assess the actual level of network security. Such tests may be performed by the cellular network provider, local technical support units or customer protection agencies.

[0008] The above as well as other applications require efficient cryptographic analysis in real time, requiring short time and using a reasonable amount of digital memory, which in the prior art has not been achieved so far.

[0009] GSM is the most widespread cellular technology. Around December 2002, more than 787.5 million GSM customers in more than 191 countries accounted for around 71% of the entire digital wireless communications market. GSM includes security mechanisms. Network operators and their clients rely on these mechanisms for the privacy of their connections and the integrity of the cellular network. Security mechanisms protect the network by authenticating clients on the network, and provide clients with privacy by encrypting calls sent on the ether.

[0010] GSM uses encryption to secure transmitted signals. Currently, two basic methods are used, A5 / 1 and A5 / 2, the first being used mainly in the Middle East and the second widely used in the rest of the world. A5 / 1 is harder to decrypt without knowing the key used.

[0011] Therefore, in order to listen to GSM transmission, it is necessary to decrypt the message. Frequency hopping in GSM additionally makes it difficult to solve this problem.

[0012] There are three main types of cryptographic algorithms used in GSM: A5 is a stream cipher used for encryption, A3 is an authentication algorithm, and

A8 is a key reconciliation algorithm. The construction of A3 and A8 is not specified in the GSM specifications, only the external interface of these algorithms is specified. The operators can choose the exact structure of the algorithm independently. However, many operators use the example called COMP128, presented in the GSM Memorandum of Understanding (MoU).

[0013] In the prior art, cryptographic analysis methods place unrealistic requirements, such as a few minutes of conversation known to bits, see reference list below.

[0014] Briceno, Goldberg and Wagner performed a cryptographic analysis of the found COMP128, which enabled the shared key (master) of the cell phone and the network to be determined, thus enabling cloning. The A5 algorithm description is part of the GSM specification but has never been made public. There are two currently used A5 versions: A5 / 1 and A5 / 2. A5 / 1 is a "strong" version limited in terms of export. A5 / 2 is a version without export restrictions, however it is considered a "weak" version.

[0015] The source code for the exact structure, both A5 / 1 and A5 / 2, was reconstructed by Briceno based on a real GSM telephone in 1999 and checked using known test vectors. A5 / 3 is an additional new version that is standardized but not yet used in GSM networks. It has been selected recently and is based on the KASUMI block cipher.

[0016] The GPRS packet data transmission system (General Packet Radio Service) is a new service for the GSM network, which offers internet content and packet data transmission services with constant access and higher bandwidth, enables services such as browsing the Internet in color, sending email on the move, powerful visual connectivity, multimedia messaging and location-based services. GPRS uses its own cipher, however, the key to the GPRS cipher is generated by the same A3A8 algorithm on the subscriber's SIM card, using the same Ki as used to create the encryption keys for A5 / 1, A5 / 2 and A5 / 3. We will use this fact to attack him later. A5 / 1 cryptographic analysis was performed initially by Golica, later by: Biryukov, Shamir and Wagner, Biham and Dunkelman, and more recently by Ekdahl and Johansson.

[0017] After restoring the source code A5 / 2, it was immediately subjected to cryptographic analysis by Goldberg, Wagner and Green. Their attack is a known plaintext attack that requires a difference in the plaintext of two GSM frames, exactly 2 away¹¹ frames (about 6 seconds). The average time complexity of this attack is approximately 2 ^ products of the scalar 114-bit vectors.

[0018] Apparently, this attack cannot be used (or is unreliable) in about half of the cases because it requires that in the first frame the 11th bit R4 be zero after initialization of the cipher. Later work by Petrovic and Fuster-Sabater suggests treating the initial internal state of the cipher as variables, writing each output bit of the A5 / 2 algorithm as the quadratic function of these variables and linearizing the square members. They showed that the A5 / 2 output can be predicted with extremely high probability after several hundred known output bits. However, this attack does not reveal the session key A5 / 2 (Kc).

[0019] It is therefore impossible to use this attack as a component of more advanced attacks, such as those we will introduce later. The time complexity of this last result is proportional to 2ⁿ Gauss elimination size matrix (estimated) about 400 x 719.

[0020] Goldberg, Wagner and Green reported the first attack on A5 / 2. The time complexity of this attack is very small. However, it requires XOR knowledge of plaintexts in two frames separated by 2ⁿ frames. Their attack shows that the cipher is quite weak, although it could be difficult to put it into practice. The problem is knowing the exact XOR of plaintexts in two frames 6 seconds apart. [0021] Another aspect is the time from the beginning of the attack to its completion. Their attack lasts at least 6 seconds, because it takes 6 seconds to fully receive data. The new method disclosed in this application significantly increases the attack speed.

[0022] The attack in the public plaintext of Petrovic and Fuster-Sabater has similar data requirements as our attack, however, it does not obtain the session key (Kc), and therefore may not be suitable for active attacks, which we will describe later.

[0023] The state of the art can be viewed through the following publications:

1. Pedagogical implementation (in programming language C) A5 / 1 and A5 / 2:

Marc Briceno, Ian Goldberg, David Wagner, A pedagogical implementation of the GSM A5 / 1 and A5 / 2 "voice privacy" encryption algorithms, <a href="http://cryptome.org/gsm-a512.htm">http://cryptome.org/gsm-a512.htm</a> (Originally on <a href="http://www.scard.org">www.scard.org</a>), 1999.

2. Description and cryptographic analysis COMP128, used by many GSM operators as A3A8:

Marc Briceno, Ian Goldberg, David Wagner, An implementation of the GSM A3A8 algorithm, <a href="http://www.iol.ie/kooltek/a3a8.txt">http://www.iol.ie/kooltek/a3a8.txt</a>, 1998.

Marc Briceno, Ian Goldberg, David Wagner, GSM Cloning, <a href="http://www.isaac.cs.berkeley.edu/isaac/gsm-faq.html">http://www.isaac.cs.berkeley.edu/isaac/gsm-faq.html</a>, 1998.

3. A5 / 1 cryptographic analysis with known plaintext:

Eli Biham, Orr Dunkelman, Cryptanalysis of the A5 / 1 GSM Stream Cipher, Progress in Cryptology, proceedings of Indocrypt'00, Lecture Notes in Computer Science 1977, Springer-Verlag, pp. 43-51, 2000.

Alex Biryukov, Adi Shamir, Cryptanalytic Time / memory / Data Tradeoffs for Stream Ciphers, Advances in Cryptology, proceedings of Asiacrypt'00, Lecture Notes in Computer Science 1976, Springer-Verlag, pp. 1-13, 2000.

Alex Biryukov, Adi Shamir, David Wagner, Real Time Cryptanalysis of A5 / 1 on a PC, Advances in Cryptology, proceedings of Fast Software Encryption'00, Lecture Notes in Computer Science 1978, Springer-Verlag, pp. 1-18, 2001.

Patrik Ekdahl, Thomas Johansson, Another Attack on A5 / 1, to be published in IEEE Transactions on Information Theory, <a href="http://www.it.lth.se/patrik/publications.html">http://www.it.lth.se/patrik/publications.html</a>, 2002.

Jovan Golic, Cryptanalysis of Alleged A5 Stream Cipher, Advances in Cryptology, proceedings of Eurocrypt'97, LNCS 1233, pp. 239-255, Springer Verlag, 1997.

4. Information related to A5 / 2:

Ian Goldberg, David Wagner, Lucky Green, The (Real-Time) Cryptanalysis of A5 / 2, presented at the Rump Session of Crypto'99, 1999.

Security Algorithms Group of Experts (SAGE), Report on the specification and evaluation of the GSM cipher algorithm A5 / 2, <a href="http://cryptome.org/espy/ETR278e01p.pdf">http://cryptome.org/espy/ETR278e01p.pdf</a>, 1996.

Slobodan Petrovic, Amparo Fuster-Sabater, Cryptanalysis of the A5 / 2 Algorithm, Cryptology ePrint Archive, Report 2000/052, Available online on <a href="http://eprint.iacr.org">http://eprint.iacr.org</a>, 2000.

Description of the background of A5 / 2 protection and GSM [0024] In this section we describe the internal structure of A5 / 2 and how to use it, see Fig. 4. A5 / 2 consists of 4 LFSRs with a maximum length: R1, R2, R3 and R4. These registers are 19 bits, 22 bits, 23 bits and 17 bits, respectively. Each register has finite impulse response filters and a feedback function. Their indecomposable polynomials are, respectively: x¹⁹© × '× ©²&lt;© x @ l, x²²&lt;© x © 1, x²³© x¹⁵x²&lt;© x © 1 ix¹⁷x⁵©1.

[0025] It should be noted that we give the bits in the registers in reverse order, i.e. in our numbering scheme, X corresponds to a filter with a finite impulse response in the index len-i-1, where len is the absolute length of the register. For example, when R4 is treated, XOR R4 [17-0-1 = 16] and R4 [17-5-1 = 11] are calculated. Then the register moves one place to the right and the XOR value is placed in R4 [0].

[0026] At each step A5 / 2, registers R1, R2 and R3 are clocked according to the clocking mechanism, which will be described later. Then register R4. After clocking, one output bit is ready at output A5 / 2. The output bit is a non-linear function of the internal state R1, R2 and R3.

[0027] After initialization, 99 output bits are discarded, and the next 228 output bits are used as the output key stream. Some references state that A5 / 2 rejects 100 output bits and that the output is used with a one-bit delay. This corresponds to the statement that 99 output bits are discarded and that the output is used without delay. We denote K_c[i] as the i-th bit of the 64-bit session key K_c, Rj [i] as the first bit of the register jif [i] as the first bit of the 22-bit publicly known frame number.

[0028] The generation of the key stream is as follows:

1. Initialization with Kc and frame number.

2. Forcing of value 1 for bits R1 [15], R2 [16], R3 [18], R4 [10].

3. Operation A5 / 2 for 99 clock cycles and ignoring output data.

4. Operation A5 / 2 for 228 clock cycles and using output data as the key stream.

[0029] The first output bit is defined as the output bit after the first clock cycle has been performed.

[0030] Initialization takes place as follows:

• Setting all LFSR values ​​to 0 (R1 = R2 = R3 = R4 = 0).

• For i: = 0 to 63 execution

1. Timing of all 4 LFSRs.

2. R1 [0] - R1 [0] © Kc [i]

3. R2 [0] - R2 [0] © K_c[and]

4. R ^ 3 [0] - R3 [0] © Kc [i]

5. R4 [0] - R4 [0] © Kc [i] • For i: = 0 to21 to

1. Timing of all 4 LFSR ..

2. R1 [0] —R1 [0] © / [i]

3. R2 [0] - R2 [0] © f [i]

4. R ^ 3 [0] - R3 [0] © f [i]

5. R4 [0] - R4 [0] © f [i] [0031] Fig. 4 shows the internal structure of the A5 / 2 algorithm.

[0032] The clocking mechanism works as follows: register R4 controls the clocking of registers R1, R2 and R3. When the clocking R1, R2 and R3 is to be performed, the bits R4 [3], R4 [7] and R4 [10] are the input data of the clocking unit. The clock unit performs most functions on bits. R1 is clocked if and only if R4 [10] agrees with the majority. R2 is clocked if and only if R4 [3] agrees with the majority. R3 is clocked if and only if R4 [7] agrees with the majority. After these clockings, R4 is clocked.

[0033] After timing, the exit bit is ready. The output bit is calculated as follows:

output = R1 [18] © May (R1 [12], R ^ 1 [14] © 1, R1 [15])] R2 [21] © May (R2 [9], R2 [13], R2 [16] @ 1) @ R3 [22) maa ((R3 [33] @ 1, R3 [16], R3 [18]), where May (·, ·,) is the majority function, i.e. there are 3 bits in each register, most of which are subjected to a negative alternative to create an output (when one bit of each three is inverted), in addition to the last bit of each register. Note that in terms of input the majority function is quadratic: May (a, b, c) = ab @ @ bc ca.

[0034] A5 / 2 is built on a somewhat similar skeleton A5 / 1. The feedback functions R1, R2 and R3 are the same as the feedback functions A5 / 1. The A5 / 2 initialization process is also somewhat similar to the A5 / 1 initialization. The difference is that A5 / 2 also initializes R4 and that after initialization one bit in each register has a forced value of 1. Then A5 / 2 rejects 99 output bits, while A5 / 1 rejects 100 output bits. The clock mechanism is the same, but the input bits of the clock mechanism in the case of A5 / 2 are from R4, while in A5 / 1 they are from R1, R2 and R3. Designers intended to use similar building blocks to save on hardware components in the phone.

[0035] This algorithm outputs 228 bits of the key stream. The first block of 114 bits is used as the key stream to encrypt the link from the network to the client, and the second block of 114 bits is used to encrypt the link from the client to the network. Encryption is done as a simple XOR message with a key stream.

[0036] Although A5 is a stream cipher, it is used to encode 114-bit "blocks". Each such block is the GSM pulse content, which is a GSM ether-interface data unit. It should be noted that each frame is made up of 8 consecutive pulses, serving 8 clients in parallel. Each client is assigned an impulse index. All impulses in this index are for this client. The frames are numbered consecutively and each frame is assigned a public 22-bit frame number. This frame number is used for A5 initialization. If we always focus on one customer, we use the terms "impulse" and "frame" interchangeably.

[0037] One may wonder why GSM uses a stream cipher instead of a 114-bit block cipher. A possible explanation is that GSM performs error correction and then encryption. Suppose one bit in a block was inverted due to an error. Decryption of this block with a block cipher would lead to a block that would appear randomly and whose error correction codes would have no chance to be repaired. However, when using a stream cipher, one inverted bit results in exactly one inverted bit after decryption.

GSM security background [0038] The following is a more detailed description of the use and specification of the A3 and A8 algorithms.

[0039] A3 provides telephone authentication in the network, and A8 is used to negotiate the session key. The security of these algorithms is based on the user-specific secret key Ki, which is shared by the telephone and the network. GSM specifications do not specify the length Ki, so it depends on the operator's decision, but usually it is a 128 bit key. Client authentication in the network is done using the A3 authentication algorithm as follows: the network asks the client using a randomly selected 128-bit RAND value. The client calculates the 32-bit response SRES = A3 (Ki, RAND) and sends the SRES to the network, which can then check its correctness.

[0040] Session key K_c is obtained by the algorithm A8 as follows: Kc = A8 (Ki, RAND). Note that A8 and A3 are always invoked together and with the same parameters. In most applications, they form one algorithm with two output values, SRES and K_c. That is why they are usually referred to as A3A8. [0041] The above description of the state of the art encryption in GSM is based on the detailed description of the invention below.

[0042] The term cryptographic analysis is used according to the invention to describe a process enabling communication encryption / decryption without prior knowledge of the session key used. In some cases, cryptographic analysis may obtain the session key used. In other cases, the session key is not obtained, but it may still be possible to decrypt or encrypt the message in the same way as if the appropriate encryption using the session key was used. Sometimes, according to the invention, the term decryption is also used in the sense of cryptographic analysis.

[0043] Known plaintext means that the attacker has access to encrypted messages as well as to messages that have been encrypted.

[0044] Only encrypted text means that the attacker only has access to encrypted messages and has no access to the messages before they were encrypted.

[0045] According to the invention, the term telephone should be understood in a broad sense as a cellular device using a GSM network.

Summary of the Invention [0046] According to the invention, there is provided a method and system for performing effective cryptographic analysis of GSM encrypted communication. This method uses cryptographic analysis of only encrypted text. The system does not have to be wired to the cellular infrastructure, it can receive messages sent through the ether.

[0047] New methods for attacking encryption and GSM security protocols are disclosed. These methods are used much easier and are much faster.

[0048] In general, in the case of A5 / 2 GSM, the mobile attacker receives encrypted messages, performs effective cryptographic analysis, and allows listening to GSM messages and / or viewing related information. This process performed on a personal computer may take less than one second.

[0049] In principle, a similar method can be used for GSM A5 / 1, however, in this case, encryption is more complex and message encryption may require about 5 minutes. Due to the need to track frequency hopping in GSM, a complex system may be required that is difficult to implement.

[0050] According to another embodiment of the invention, in the case of A5 / 1 GSM, the attacker system creates a small cell around itself that contains the target GSM telephone. The system imitates the cellular network for the target telephone and the target telephone for the GSM infrastructure. This requires transmission capabilities from the attacker system, but decryption is then much simplified and much faster.

[0051] In addition, new improvements are presented in GSM networks. These include improvements to cryptographic algorithms and protocols. For example, GSM operators can introduce such improvements.

[0052] Even GSM networks using the new A5 / 3 succumb to our attack because A5 / 3 is built into GSM. The disclosure includes changes to the way A5 / 3 is embedded to protect networks against such attacks.

[0053] A higher level of security can be achieved and maintained by performing such tests or attacks on a cellular network. Existing and future vulnerabilities can be detected and corrective action taken. In this way, you can improve the construction of the GSM network itself to increase its level of security.

[0054] The invention may not be limited to the GSM cellular network - a similar version A5 / 3 is also used, for example, in third generation cellular networks.

[0055] Further objects, advantages and other features of the invention will become apparent to those skilled in the art upon reviewing the disclosure that follows.

Brief description of the drawings [0056]

Fig. 1 shows a GSM cell with base station, subscriber and attacker system.

Fig. 2 shows a detailed block diagram of the attacker system.

Fig. 3.shows a block diagram of another embodiment of the attacker system in detail.

Fig. 4.shows the internal structure A5 / 2 in detail (prior art).

Fig. 5. shows in detail the attack method only in encrypted text.

Fig. 6 shows in detail the method of attack by known plaintext on A5 / 2.

Detailed description of the invention [0057] A preferred embodiment of the invention will now be described based on an example and with reference to the accompanying drawings.

[0058] Fig. 1 shows a GSM cell 11 with base station 12, subscriber 13 and attacker system 14. Wireless links 21, 22, 23 exist between these units.

[0059] Fig. 2 shows a detailed block diagram of the attacker system. This system can be used to apply the methods described in detail in this disclosure. The attacking system includes a first transceiver 31 with an antenna 32 that communicates with the target subscriber device and a second transceiver 33 with an antenna 34 that communicates with the base station. The system also includes a computer / controller 36, which controls the operation of the system, is controlled by the operator and displays the results of decryption. The computer 36 also allows the operator to listen to the target phone's communication.

[0060] Fig. 3 shows in detail a block diagram of another embodiment of the attacker system. It includes the first transceiver 31, which is in a different location from the transceiver 33 - the first is near the target subscriber, and the second is near the base station.

[0061] The system further includes an interface 38 for locating the first transceiver 31 at a remote location.

[0062] Alternatively, the system may use directional antennas directed to the subscriber or base station, respectively.

[0063] Although the examples presented here relate mostly to GSM A5 / 2, A5 / 1, A5 / 3 and GPRS, they can also be adapted to other networks using the invention.

[0064] The examples in this disclosure describe in detail the cryptographic analysis of GSM encrypted communication using only encrypted text. The attacks operate on GSM networks that use, for example, A5 / 1 or A5 / 2, and even the newly selected A5 / 3.

[0065] The attack on A5 / 2 requires about 40 milliseconds of encrypted cell conversation, received from the ether, and finds the correct key in less than one second of operation on the personal computer. It has been shown how we can easily adapt our attack against A5 / 2 to actively attack networks using A5 / 1 or A5 / 3. Earlier attacks on GSM required unrealistic information, such as long periods of known plaintext. Our attacks are the first practical attacks on GSM networks and do not require any knowledge of the content of the conversation.

[0066] These attacks allow attackers to download any conversation and decrypt it either in real time or at any time later. We also show you how to carry out active attacks, such as interception, data change and connection theft. Even after using such attacks, they cannot be identified by a network operator using prior art methods and systems.

[0067] A5 / 3 is also used in third generation cellular networks, so the invention is not limited to GSM and can also be used for other cellular systems.

[0068] The disclosure provides a method of carrying out an attack only with encrypted text on A5 / 2. In our tests, our attack found the key in less than one second of operation on a personal computer. It has been shown that the attack on A5 / 2 we propose can be adapted to carry out an active attack even on GSM networks that use A5 / 1 and A5 / 3, thus conducting a real-time active attack on a GSM network without any previously required knowledge .

Method of attack only with encrypted text [0069] The new method of full attack includes, see for example Fig. 5:

1. Effective attack with known plaintext on A5 / 2, obtaining the session key. This first attack is algebraic. Uses the low algebraic order of the A5 / 2 output function. The output information A5 / 2 is presented as a quadratic function of many variables in the initial state of registers. Next, we construct an over-defined system of quadratic equations that expresses the process of generating the key stream, and solve these equations.

2. Enhancement of the attack with known plaintext to attack only with encrypted text on A5 / 2. We observe that GSM uses error correction codes before encryption. We show you how to convert this attack to an encrypted text attack on A5 / 2 using this observation.

3. Adaptation of the attack on A5 / 2 for active attack on GSM networks using A5 / 1 and A5 / 3, as well as on GPRS. The inventor discovered that due to the design of the GSM security module interface, the key used in A5 / 2 is the same key as used in A5 / 1 and A5 / 3. And the same mechanism that sets the key in the A5 cipher, i.e. A3A8, is used to designate the key for GPRS. It shows how to carry out an active attack on any GSM network.

End of the way.

Note: See the description of the background of the A5 / 2 and GSM security in the "Background" section of this disclosure.

Methods of attack with known plaintext on A5 / 2 [0070] In this section we present a new attack with known plaintext (attack with known key stream) on A5 / 2. With the key stream divided into frames and the appropriate frame numbers, the attack obtains a session key.

[0071] Compared to prior art attacks, the new attack method may give the impression that it requires more information, but works within just a few milliseconds of data. We then improve our attack to attack only with encrypted text, which only requires about 40 milliseconds of encrypted, unknown data. That is why putting our attack into practice is very easy. We simulated our attack with known plaintext on a personal computer and checked the results. This simulation obtains the key in less than one second. [0072] The computation time and memory complexity of this attack are similar to those of Goldberg, Wagner and Green.

[0073] Thus, the method comprises the following steps, see Fig. 6:

1. Knowing the initial internal state of registers R1, R2, R3 and R4 and the number of the initial frame, you can get the session key using simple algebraic operations. This is mainly due to the fact that the initialization process is linear in terms of session key and starting frame number. Therefore, during the attack, we focus on revealing the initial internal state of the registers.

2. Let kk Ik ···· represent the output of the A5 / 2 algorithm divided into the kr framework. It should be noted that each kj is the key stream output for the entire frame, i.e. each kj is 114 bits long. Let f, f + 1, f + 2, ... denote the frame numbers associated with these frames, where f is the number of the initial frame. We mark the i-th bit of the key stream in the j frame as kj [i]. The initial internal state of the Ri register in box j is designated Rij. This is an internal state after initialization, but before 99 measures. It should be noted that this notation is somewhat inaccurate because the output data is actually 228 bits when the first part is used to encrypt the network-telephone link and the second 114-bit part is the telephone-network links.

3. Suppose the initial state R40 of the R4 register in the first frame is known. An important observation is that R4 controls the timings of the other registers and if R4 is known, the exact number of timings for each register from its initial state is also known. Each register has linear feedback, so by having the number of clockings of a given register, you can express each bit of its internal state as a linear combination of the bits of the original internal state.

4. The output of the A5 / 2 algorithm is the XOR of the last bits of registers R1, R2 and R3 and the three majority functions of bits R1, R2 and R3 (details in figure 4). Thus, the resulting function is quadratic when the variables are bits in the initial state of these registers. We use this low algebraic order of data output. In the following paragraphs, the goal is to express each bit of the entire cipher output (consisting of several frames) as the quadratic function of many variables in the initial state. Then we construct an over-defined system of quadratic equations that express the key stream generation process and solve it.

5. For a given frame number f, there is an algebraic description of each output bit. In this algebraic description, we linearize to square expressions. We observe that each majority function works on bits of a single register. That is why we have quadratic expressions consisting of variables only from the same register. Considering that the value of one bit in each register is set to 1: R1 contributes 18 linear variables plus all their products (17-18) / 2 = 153. In the same way, R2 brings 22+ (22-21) / 2 = 22 + 231 variables, and R3 brings 22+ (22-21) / 2 = 22 + 231 variables. So far, after linearization, there are 18 + 153 + 21 + 210 + 22 + 231 = 655 variables. You also need a variable that will have a fixed value of 1. In total, we get a set of 656 variables. The set of these 656 variables is V0. Of these variables, 18 + 21 + 22 = 61 variables directly describe the full initial state R1, R2 and R3.

6. Each output bit we have adds one equation in the variables with V0. One frame consists of 114 bits. That is why we get 114 equations from each frame. The solution of the system of equations reveals the value of variables in V0, among them linear variables, which I directly describe the initial internal state of R1, R2 and R3. However, there are not enough equations at this stage to successfully solve the system. The main observation is that, knowing the variables in V0 defined in frame f, you can describe the bits of any other frame using the variable expressions in the set V0. When moving to the next frame, the frame number is incremented by 1 and the internal state is reinitialized. We assume that the value of the R40 register is known. Due to the method of initialization, in which the frame number is subjected to an alternative that was beaten after a register bit (see description A5 / 2), we know the value of R41. The values ​​of R10, R20 and R30 are not known, so we also do not know the values ​​of registers R1x, R21 and R3_b but we know the XOR-difference between R10, R20, R30 and Rh, R21, R31, respectively.

7. We define a set of variables that describe their state and linearize these variables as Vt, in the same way as we did at the first frame, creating a set of V0. Due to the initialization method for each registry and we know the difference between Rii and Rio. Knowing this difference, we can describe the variables in the set Vi by the linear expression of the variables in the set Vo. This is - including square expressions! To show this, let's assume that arbi is a square expression in Vi, naturally ao-bo is a square expression in V0 and the difference between d_and and db is known so that: ax = a0® da ib₁= bo®db

8. That is why arb₁= (Ao®d_and) - (bo®db) = ao-bo®ao'db®bo-d_and®dadb If db and da are known, the equation is linear in the variables in V0. This allows the use of output bits in the second frame to obtain additional linear equations in variables with V0. The same applies to any other frame.

It is clear that after obtaining 656 linearly independent equations, the system can easily be solved by using Gauss elimination. However, collecting 656 linearly independent equations is very difficult in practice. This is the result of frequent re-initialization and low-order majority function. The solution of all variables is not necessary, i.e. it is enough to solve the linear variables of the system, because the other variables are defined as their products. We tested experimentally and found that after receiving in turn about 450 equations, the original linear variables in Vo can be solved using Gaussian elimination.

End of the way.

[0074] This attack can be summarized as follows: all possible values ​​of R40 are tested and for each such value solved a linearized system of equations that describes the output. The solution of the equations gives the internal state R1, R2 and R3. Along with R4, the full internal state is known, which provides suggestions for the key ..

[0075] The time complexity of the attack is as follows: there are 2¹⁶ possible conjectures as to the value of R40. This number should be multiplied by the time it takes to solve the binary linear system of 656 variables for a given supposition, i.e. about 656³~2⁸ XOR operations, i.e. about 2⁴⁴ total XOR operations.

[0076] Result: we successfully used this algorithm, which lasts about 40 minutes on our 800MHz PIII personal computer with Linux. Memory requirements are negligible: storing a linearized system in memory requires 656² bits ~ 54kB. When using this algorithm on a personal computer, we used the fact that the PC device can perform XOR 32 bits with 32 other bits in one operation.

Optimization of the method of attack with known plaintext A5 / 2 [0077] Possible optimization consists in filtering out incorrect R40 values ​​and solving the system of equations only for the correct R40 value. Filtering is based on the perception that the system of equations for each R40 suggestion has linearly dependent rows. This filtering saves a considerable amount of time by reducing the number of relatively expensive processes for solving systems of equations.

1. There is a different system of equations for each different R40 value. Our filtering stage technique requires a pre-computation stage in which 2 ^ possible systems are solved in advance. Knowing the matrix S, which describes the system, and for any output k, ie S-Vo = k, we calculate the "solving matrix" of the Tukładu.

2. The matrix T is calculated by taking a unit matrix with the same number of rows as the matrix S, and subjecting it to the same series of operations as the operations performed during the Gaussian S elimination. Multiplying by T on the left side of S results in applying the Gaussian elimination to S:

<img file="PL1623529T3_D0001.tif" />

where V_s is the matrix whose rows are linearly independent and the rows below the matrix V_s are all zero lines. Zero rows are the result of a system of equations containing linearly dependent rows. We are interested in using linearly dependent S lines.

3. We do it using the linearly dependent output bilv A5 / 2:

<img file="PL1623529T3_D0002.tif" />

4. We want to check the assumption of the R40 value, i.e. filter out the wrong assumptions of R40. You can use those T lines that, when multiplied by the output of k, give the value zero. With the correct guess, all these lines give a value of zero after the above multiplication. With an incorrect guess, each line multiplied by k can be zero with a probability of about 50%. Therefore, for each incorrect assumption R40, you need to calculate an average of about two rows (scalar products). During the initial calculation, we save for each possible value of R4o only about 16 T lines, which after multiplying by k become the value 0. When conducting an attack, incorrect assumptions of R40 are filtered by multiplying the saved rows by k.

5. When the results of all multiplications of the putative R40 are zero, we get a candidate system of equations that is actually a candidate for the value of R40. Knowing the suggestion for R40, we solve this suggested system of equations and calculate the initial internal state of R1, R2 and R3. Given the putative R40, it is easy to determine K_c. The filtering stage is designed in such a way that the correct guess of R40 survives it. It should be noted that the number of R40 values ​​that survive the filtering step is about one, i.e. the correct R40 value.

End of the way.

278 [0078] Result: the memory complexity is about 2 bytes (less than 250 MB) needed to store the above line vectors.

[0079] The above result applies when known plaintext from a wireless link originating from the network is towards a mobile phone. When using known plaintext from a cell phone link towards the network, achieving a state where there are linearly dependent lines requires several more equations. This is because a second 114-bit block with 228 bits of A5 / 2 output is used on the phone-to-network connection. These bits are less affected by frequent re-initializations, and are therefore slightly less linearly dependent.

[0080] It should be noted that the use of this optimization requires some compromise.

[0081] If four frames of known plaintext are required, the XOR between frame number f and each of f + 1, f + 2 and f + 3 must be known in advance before the exact value of f is known. This XOR difference is necessary to express bit stream key frames as linear expressions throughout the set V0 and to calculate the system of equations. In other words, the system of equations depends not only on the R40 but also on the XOR difference.

[0082] The problem here is the addition operation, for example f + 1 can give a transfer that would propagate through f, thus preventing the calculation of the XOR-difference in advance. To facilitate calculations, we require that f have the specific bit set to 0. This requirement prevents propagation of the transfer beyond the specific bit. We take into account that we need to calculate the XOR difference for up to the sum of the number 3 and the frame number f, so we need the value of the third bit of the least significant f to be zero, and we must also require that the last two bits of f have a constant value, since any the combination of these bits leads to a different XOR-difference when added.

[0083] These requirements are sufficient to enable the above differences to be calculated in advance. To enable any fixed value of the two lower bitsf, the pre-calculation is performed for each such possible value. There are four possible values. This multiplies the complexity of memory, as well as the time complexity of the initial calculation, by a factor of four. The above complexity of memory already takes this factor into account. In the event that the two lower bits are zero, we can remove the requirement that the third bit be 0, because in this case adding a maximum of three cannot cause a move beyond the first two bits.

[0084] So of the eight possible values ​​for the bottom three bits f we allow five. We emphasize that this limitation of possible values ​​of f has no serious practical consequences, as it is required to wait at a maximum of 3 frames per frame number that would meet the requirements. An immediate attack using only the encrypted text we are describing involves this attack and must work in 4 frame blocks. It should be noted that in this case, if the first frame number of the four consecutive frames does not meet the requirements. If this happens, it is ensured that the first frame number in the next block of 4 frames will meet the requirements.

[0085] We analyze the time complexity of this optimized attack as follows: knowing the value of the frame number f, for each incorrect guess R40 we must try the average of two scalar products. After obtaining the correct R40 value, the time needed to solve the system of equations for the correct value is about 2, which is negligible. Thus, the average time complexity of this optimized attack is approximately 2¹⁶ scalar products.

[0086] We analyze the time complexity of the initial calculation as follows: at the stage of the initial calculation, we calculate the system of equations S and its matrix T for each value of R40 out of 216 possible values ​​and for each allowed XOR-difference f. For each such system we keep only about 16 lines T, which get a value of 0 after multiplying by k. To calculate T, we perform a Gauss elimination on S. The time complexity for Gauss elimination is about 2 XOR. After multiplying the above numbers, we get 2⁴⁴ We repeat this process for each of the four required XOR-differences f, so we multiply this number by four. Thus, the time complexity of the initial calculation in^snose^and 2^{46 XOR}.

[0087] We performed this optimized attack on our personal computer and obtained K_c lasts less than one second. One-time pre-calculation takes about 160 minutes.

The method of immediate attack only with encrypted text on A5 / 2 [0088] In this section we present the attack on A5 / 2. An important factor that allows us to transform the attack from the section "Attack with known plaintext on A5 / 2" into an attack only with encrypted text against A5 / 2 is that in GSM error correction codes are used before encryption. Thus, the encryption plaintext has highly structured redundancy.

[0089] There are several types of error correction methods used in GSM and different error correction schemes are used for individual data channels. For simplicity, we focus on control channels, and in particular on the Slow Associated Control Channel (SACCH) error correction codes. Note that this error correction code is the only code used to start a conversation. Therefore, just focus on this code. Using this error correction code, we only attack with encrypted text that obtains the key. However, the new attack method can also be applied to other error correction codes.

[0090] In SACCH, the message to be encoded using error correction codes has a fixed length of 184 bits. The result is 456 bits long. This 456-bit message is interleaved into 4 pulses. The coding operation and interleaving operation can be modeled together as one 456 x 184 matrix over GF (2), which we denote G. The message to be encoded is treated as an 184-bit binary vector, P. The result of the coding-interleaving operation is: M = GP. The resulting vector M is divided into 4 pulses. In the encryption process, each pulse is subjected to an alternative excluding the 5/2 output for the corresponding pulse.

[0091] If the matrix G is a binary matrix 456 x 184, there are 456-184 = 272 equations that describe the nucleus of the inverse transformation. In other words, with the known M = GP vector there are 272 linearly independent equations on its elements. Let K be a matrix describing these linear equations, i.e. KgM = 0 for any such M.

[0092] We denote the output string of A5 / 2 bits for the time of 4 frames by k = k ^ j ^ kj + and ^ kj + 2 ^ kj + 3, where || means the join operator. The encrypted text C is calculated by C = M ΦΚ. We use the same 272 equations for C, namely:

KG (M @ k) = KG-M®KGk = 0®KGk = Kg k.

[0093] If the encrypted text C is known, we get essentially linear equations over the elements k [0094] It should be noted that the equations we get are independent of P - they only depend on k. Each bit in k is replaced by its description in the form of expressions linear over V0 (see our description of an immediate attack with known plaintext) and in this way we get equations on variables from V0. Each 456-bit coding block provides 272 equations. Other details of the attack and its time complexity are similar to the optimized case from the previous section, where we substitute KU for k.

[0095] While in a known plaintext attack, four data frames are sufficient to carry out an attack, in an encrypted text attack we only need eight frames, because we only get about half of the information from each encrypted frame compared to a known plaintext attack. When analyzing the time complexity and memory complexity of this attack, only encrypted text takes into account that we limit the four lower bits of the frame number f. We only allow 9 out of 16 possible values ​​for these four bits. This limitation doubles the complexity of memory compared to the optimized attack of known plaintext, and also doubles the complexity of pre-calculation.

[0096] End of method.

[0097] We summarize the complexity of the attack only with encrypted text as follows: the average time complexity of the attack with only encrypted text is approximately 2¹⁶ scalar products. The complexity of memory is about 2²⁸⁸ bytes (less than 500 MB), the time complexity of the pre-calculation is about 2 XOR. Our execution on a personal computer is obtained by K._c in less than one second, and it takes about 320 minutes to complete a one-time pre-calculation. [0098] Using our methods, we have also been able to improve the attack of Goldberg, Wagner and Green as well as the attack of Petrovic and Finster-Sabater to attack only encrypted text. Upon knowledge of the present disclosure, the improvement mentioned above should be apparent to those skilled in the art.

Method of direct attack against A5 / 1 [0099] The following is an example of such a direct attack:

[0100] For a given block of several encrypted frames, we use the methods of the previous sections to calculate the KgIo Bits we receive are only A5 frames dependent on a few frames. We call these output bits coded stream. Suppose we know that the frame number of the first of these frames is divided by four without a remainder. The whole process can be considered a function from the internal state A5 / 1, to the coded stream.

Let's denote this function by f () when only 64 bits of output are passed confidentially, so f () maps 64 bits to 64 bits.

[0101] Thus, f () is a function that takes the internal state A5 / 1 after initialization and produces the coded stream. By inverting f (), we reveal the internal state and break the cipher. Note that we must make an assumption about the frame number, otherwise f () will depend on the frame number. We can use one of the time-memory-data compromises known in the art, for example those described by Biryukov and Shamir in the article "Cryptanalytic Time / Memory / Data Tradeoffs for Stream Ciphers", Advances in Cryptology, materials from the Asiacrvpt'00 conference, Lecture Notes in Computer Science 1976, Springer-Verlag, pp. 1-13, 2000.

[0102] We use their notation for a compromise, i.e. N means the space of internal states, T means the number of estimates f (), D means the number of available data points, M means the number of memory lines. In this case, N = 2⁶⁴ and each memory line is 16 bytes long. For example, on the compromise curve N = D IM T, T&gt; D and N = 264, one point is D = 2⁸, which means about 8 seconds of ether data, M = 2³⁹, which is about 8.8 terabytes (which can be saved on 44 hard drives with a capacity of 200 GB). If we use similar encoding for the previous sections, it means that we need to multiply the data by 4 to compensate for the different numbers of frames. So you need 176 hard drives, 200 GB each.

[0103] The time it takes for an actual attack to be T = 234 estimates f (). Assuming that f () can be calculated 2²⁰ times per second on one personal computer, the calculation requires 2^H seconds. In a network of 1000 computers, it takes about 16 seconds. It will cause about 2¹⁷ random access to the disk, and if each disk can be randomly accessed about 200 times per second, the access time is about 655 seconds. However, there are 176 hard drives, so the total access time is 3.76 seconds, which occurs in the background during other calculations.

[0104] The pre-calculation takes N / A, which corresponds to 2⁵6 f () estimates that last 236 seconds on one personal computer. We have to calculate it four times. In total, in a network of 10,000 computers, this task should be completed in about 10 months. For distributed operation, this network requires a bandwidth of about 1.35 MB / s. This calculation is feasible via the Internet, for example.

[0105] It should be noted that the increase in the amount of data available drastically reduces the remaining requirements. If we have 5 minutes of such data, i.e. 37.5 times more data than from 8 seconds, then D = 2ⁿ, you only need to use a total of about 44 hard disks with 200 MB each, i.e. about M = 2 and the time would be T = 2, which would take about 5 minutes to calculate on one PC. This means that the attack is carried out in real time, but only one frame out of several thousand is the frame that allows the attack to succeed. When a given frame is encountered, the attack will almost immediately determine whether this frame is indeed "the right one" or not.

[0106] The attack requires 214 random disk accesses, which take about 81 seconds, but are performed on 44 hard disks in parallel, which takes about 1.86 seconds in total, which are taken in the background of the calculation. The preliminary calculation is reduced to N / A = 2^Mf () estimates, which take about 231 seconds, or about 3 months on a network of 1,000 personal computers.

[0107] When 1 hour of such data is allowed, only about 270 GB of memory is needed, which can be stored on one or two hard drives. The actual attack time is about one hour on one personal computer, which means that it is actually real time, access time to the hard disk is about 5 minutes, which is negligible. The initial calculation can be completed in a network of 40 PCs in about 10 months.

[0108] Even if A5 / 2 is no longer used in GSM networks, but remains A5 / 1, this direct attack on A5 / 1 can be used to allow an attack on GPRS, using their key being generated using the same mechanism (i.e. A3A8) and therefore at the same input (i.e. RAND and Ki) the output that is the key is the same. This is an example that can occur in other ciphers, if only two ciphers share the same key handshaking and an active attack can be more easily carried out on one of these ciphers.

[0109] Briceno found that many GSM networks only use 54 bits out of 64 key bits, setting the value of 10 key bits to 0. The prior art methods did not use this fact during cryptographic analysis. We observe that when the bits have a fixed value, a direct attack on A5 / 1 can be seriously improved. When N decreases with 2⁶⁴ up to 2⁵⁴, only 54 bits of zf () need to be included. Therefore, each memory line is now only 54 times 2 bits long = 13.5 bytes, let's assume 14 bytes.

[0110] Consider the compromise curve, N = D IM T, T&gt; D and N = 2, example shown above, where D = 2, which corresponds to about 8 seconds of ether data, but now M = 2, which is about 500 GB, you can save on three hard drives of 200 GB. T = 2²6, which only takes about one minute of calculations ON ONE PC! This calculation can be done in parallel on several computers, achieving a direct attack on A5 / 1 in real time. The one-time preliminary calculation lasts N / A = 246, which is a total of about 3100 computer days and can be calculated in a network of 10 PCs in about 10 months. [0111] Attack adaptation for networks requiring A5 / 1 or A5 / 3 but agreeing to less.

[0112] Some networks may prefer that a cell phone works with A5 / 1, but if not possible, works with A5 / 2. When a cell phone tries to access the network, it informs the network of its capabilities, including which encryption algorithm it can use. A simple middle-class attack would involve changing the information the network receives so that it recognizes that the phone can work in either A5 / 2 or A5 / 0. If the network agrees to A5 / 2 encryption, then the encryption keys can be found using the method described above. A similar average class attack can be made when the network prefers A5 / 3 but agrees to less (either A5 / 1 or A5 / 2).

The method of adaptation of attacks to any GSM network [0113] The attack presented in the section "The method of immediate attack only with encrypted text on A5 / 2" assumes that the encryption algorithm is A5 / 2. With this attack, it's easy to get K_c in real time from several tens of milliseconds of encrypted text.

[0114] We ask the question what happens when the encryption algorithm is not A5 / 2, but A5 / 1 or newly selected A5 / 3, or even GPRS. The surprising answer is that you can then apply almost the same attack. The success of a new attack only requires that the mobile phone support A5 / 2, but this is in fact a mandatory GSM requirement for roaming to networks using A5 / 2.

[0115] The following attack obtains an encryption key that uses the network when A5 / 1 or A5 / 3 is used. The key is discovered in a man in the middle attack on the target client. The attacker plays two roles in this attack. Imitates the client's network and imitates the client's network. It should be noted that this type of attack is relatively easy to perform in a cellular environment.

[0116] When initiating a conversation, the network may send an authentication request to the attacker, which the attacker sends to the victim. The victim of the attack calculates the SRES and gives it to the attacker who sends it back to the network. The attacker was "authenticated" on the network. The network then asks the client to start encryption with A5 / 1.

[0117] In our attack - if the attacker imitates the client - the network will actually ask the attacker to start encrypting with A5 / 1. The attacker has no keys yet, so he is unable to start encryption. The attacker needs a key before being asked to use it. To achieve this, the attacker asks the victim to encrypt using A5 / 2 as soon as the victim sends SRES and before the attacker provides network authentication information.

[0118] This request looks legitimate to the victim because the victim of the attack sees the attacker as a network. The attacker then uses cryptographic analysis to obtain the A5 / 2 encryption key used by the victim. Only then does the attacker send authentication information to the network. The key depends only on RAND, which means that the key obtained by attacking A5 / 2 is the same key as the one to be used when using A5 / 1 or even 64-bit A5 / 3! The attacker can now encrypt / decrypt using A5 / 1 or A5 / 3 using this key.

[0119] It could be suspected that the network could identify this attack by detecting a slight delay in the time needed to perform the authentication procedure. However, the GSM standard gives the phone 12 seconds to complete the authentication calculations and send a response. The delay caused by this attack is less than one second. In addition, the transmission of GSM signal messages between the network and the phone can usually take some time, due to the Layer 2 protocol delay. In summary - the delay occurs but is negligible. [0120] Many networks rarely initiate the authentication procedure and use the key created during previous authentication, stored on the client's SIM card. This key is numbered by the network with a number between zero and six. The attacker can uncover these saved keys by imitating the network to the victim's phone. Then the attacker initiates a radio connection with the victim and asks the victim's phone to start encryption using the A5 / 2 algorithm and the key with the appropriate number. Then the attacker applies the attack and obtains the key, then ends the radio connection. The cell owner and network will not notice any signs of attack.

[0121] One wonders if the network operator can discover an attack if the attack transmits and an interface can be called. While this is essentially true, both of these attacks require less transmission than might be expected at first glance. At first, the attacker may seem to be transmitting throughout the conversation. However, after the first second of connection, the attacker already has the encryption key and does not really need to continue the active man in the middle attack.

[0122] An attacker may want to terminate activity, allow the network and the victim to continue the connection, and retrieve the encrypted conversation using the key he discovered. The first step in doing this is to change the cipher used by the victim to match the network's requirements. The attacker should ask the victim of the attack to change the combination to no combination, and then change to the combination used by the network, i.e. A5 / 1. An attacker could cause the network to order the call to be transferred to a different frequency. At the same time, the attacker requests the victim's phone to make a transfer to the same frequency.

[0123] It should be noted that, in fact, GSM is not transmitting on one frequency. Instead, GSM uses a frequency hopping scheme. For simplicity, we refer to a specific hopping sequence as a single frequency. This has no consequences for the attacks we present. In most GSM calls, handover is initiated by the network shortly after the start of the call. If this is the case anyway, it saves the attacker the need to "cause" the network to order a handover. In this way, the attacker can interrupt his transmission, retaining the ability to eavesdrop on the conversation. In the second scenario, the attacker attacks at the selected time and the entire attack can be carried out within a few seconds at most. If the acquired keys are used later, the attacker will not have to make any transmissions.

[0124] The scenarios described below show an attack in which an attacker can download any conversation by transmitting only for a short period at a later, selected time, maybe after the connection.

[0125] Attack adaptation is based on the fact that the same key is sent to A5 / 2 and A5 / 1, and even to 64-bit A5 / 3 (in the scenario where A5 / 3 is used in GSM, according to standards GSM). Thus, the discovery of the key for A5 / 2 reveals the key to A5 / 1 and 64bit A5 / 3.

[0126] This attack also applies to GPRS for similar reasons. When the network asks the phone for a new GPRS key using a random 128-bit RAND value, the attacker can use the "man-in-the-middle" method and initiate a radio connection with the victim of the attack, initiate an authentication request using the same RAND value, and then ask her for encryption using A5 / 2. Then he can find the key by using only the encrypted text we present. The key obtained will be the same as the GPRS key, which results from the fact that both are created using the same A3A8 algorithm and the same Ki, so when the same RAND is specified, the same session key is created.

[0127] An attacker may opt out of the "man-in-the-middle" attack and register GPRS communication, and then decrypt it using a similar attack in which he asks the victim to authenticate using the same RAND that was used in the session, and then asking the victim to encrypt with A5 / 2 and get the key. Even if GPRS changes the key several times using the new RAND, when the attacker recorded the communication and RAND can each time repeat this process later in the attack on the victim, find the key and decrypt communication. These attacks can be used in a similar way to impersonate. It should be noted that although you can use A5 / 3 with 64-128-bit keys, the GSM standard allows you to use only 64-bit A5 / 3. Unfortunate consequences scenarios for GSM [0128] The presented attacks can be used to emulate real attacks in several scenarios. This section contains four examples. These attacks work for various possible encryption algorithms, for example: A5 / 1, A5 / 2 or A5 / 3, and even GPRS.

Eavesdropping attack connection [0129] A simple scenario that can be predicted is eavesdropping on conversations. An attacker can decrypt and eavesdrop on encrypted communications using GSM as soon as it obtains an encryption key. With the help of eavesdropping, both voice calls and data can be eavesdropped.

[0130] Another possible eavesdropping attack is that the attacker records the encrypted conversation. The attacker must ensure that he knows the RAND value that generated the key being used. At a later time, convenient for the attacker, the attacker imitates the network for the victim of the attack. The attacker then initiates a radio session, asks the victim to authenticate using the above RAND, and obtains the session key that was used in the recorded conversation. When the attacker has the key, he can easily decrypt the conversation and can listen to its content.

[0131] It should be noted that an attacker can record multiple conversations and obtain all keys with subsequent attacks. The attack has the advantage that the transmission occurs only at a time convenient for the attacker. This can happen even years after the conversation is recorded or when the victim is in another country, or in a place convenient for the attacker.

[0132] Another attack is to find the key before the conversation, by obtaining a stored key, as described earlier. Finding the key before the call is effective if the network does not ask the subscriber to perform authentication using a different RAND at the beginning of the call.

Attacking Attack [0133] Although the GSM network can perform authentication when the connection starts, encryption is a means of preventing GSM from spoofing in the later stages of the conversation. This is based on the assumption that the scammer would not have Kc and thus would not be able to have an encrypted conversation. It has been shown how to obtain the encryption keys. Once the attacker obtains encryption keys, he can cut off the victim of the attack from the connection and pretend to be the victim of the other party. Therefore, impersonating a conversation after authentication is possible.

[0134] Some people may argue that it would be difficult to put this attack into practice because of the difficulty in transmitting the required data over the ether. It is emphasized that spoofing is a relatively easy attack in a cellular environment. GSM transmission occurs on a radio frequency, which makes these types of attacks very easy to carry out and difficult to detect. For example, an attacker could ensure that his signal reaches the cell's antenna with much more power than the signal of the victim of the attack. The attacker can also cause interference, ensuring that the noise signal reaches the victim's antenna with high power.

[0135] Impersonation can occur during early connection setup, even before the attack victim's phone rings. The operator could hardly suspect an attack was taking place. The only symptom of the attack is a moment of slightly increased electromagnetic interface.

[0136] Another way of impersonating incoming calls is to perform some type of "man in the middle" attack, except that the attacker receives the call instead of passing it on to the victim of the attack.

Attack with data message change (SMS) [0137] After eavesdropping on the connection link, the attacker decides on the content. The attacker can listen to the message sent by the victim of the attack and send his own version. The attacker can stop the message or send his own SMS. This violates the integrity of GSM traffic.

Connection Theft Attack [0138] GSM was thought to be protected against connection theft due to A3A8 authentication procedures.

[0139] However, due to said weaknesses, the attacker can make outgoing calls at the expense of the victim of the attack. When the network asks for authentication, a man in the middle attack, similar to one described in the "How to adapt attacks to any GSM network" section, would succeed. The attacker initiates a parallel outgoing call to the cellular network and a radio session to the victim. When the network asks the attacker for authentication, the attacker asks the victim for authentication and forwards the received authentication to the network.

[0140] An attacker may also obtain Kc as described in this disclosure. Then the attacker can terminate the victim's radio session and continue the outgoing call as usual. This attack is virtually undetectable by the network because it gives the impression of normal access. The victim's phone will not ring and the victim will not receive any indication that he is being attacked. At least until you receive your monthly bill.

[0141] Various other embodiments of attack methods will occur to those skilled in the art upon reading the present disclosure. The methods described above can be developed further.

1. A method of cryptographic analysis, including

A. Requesting the phone to encrypt using A5 / 2.

B. Using the results to decrypt encrypted communications using A5 / 2, A5 / 1 A5 / 3 or GPRS.

Thus, the attacker influences the decision regarding the encryption method used, in this case in a way that enables subsequent decryption.

2. The method of attack is the average value of the cryptographic analysis class, including:

A. Causing the attacker that the network recognizes that the phone is unable to encrypt with A5 / 1, but only with A5 / 2.

B. Allow the attacker to use the attack and decrypt communications.

3. A method of cryptographic analysis, including:

A. Performing direct cryptographic analysis A5 / 1 only in encrypted text.

B. Using the result of step (A) to enable decryption and / or encryption of subsequent communication that is compatible with encryption using the session key and / or decryption using the session key.

In the above cryptographic analysis method, it can be considered that some of the session key bits have a known constant value. Cryptographic analysis can also find the session key.

4. A method of cryptographic analysis, including:

A. Performing direct cryptographic analysis A5 / 2 only in encrypted text.

B. Using the result of step (A) to enable decryption and / or encryption of subsequent communication that is compatible with encryption using the session key and / or decryption using the session key.

In the above cryptographic analysis method, it can be considered that some of the session key bits have a known constant value.

In addition, cryptographic analysis can also find the session key.

5. A method of securing GSM connectivity, including repeated GSM authentication during an ongoing session.

[0142] In the above method of securing GSM communications, the encryption key may also be changed as a result of using the GSM authentication procedure.

[0143] In addition, an attacker may transmit radio frequency transmissions.

[0144] The above methods of active GSM cryptographic analysis may also include:

A. The transmission of the attacker makes the network decide that the average value of the phone class is such that the phone is not able to encrypt using A5 / 1, but only using A5 / 2.

B. This causes the network to request encryption only with A5 / 2, allowing the attacker to use the attack and decrypt communications.

[0145] The above methods of active GSM cryptographic analysis may also include:

A. The transmission of the attacker makes the network decide that the average value of the phone class is such that the phone is not able to encrypt with A5 / 3, but only with A5 / 2 or A5 / 1.

B. This causes the network to request encryption only with A5 / 1, allowing the attacker to use the attack and decrypt communications.

[0146] The above methods of active GSM cryptographic analysis may also include:

A. The attacker's transmission makes the phone decide that the transmission comes from the network and requests the phone to encrypt using A5 / 2.

B. The phone responds with data encrypted with A5 / 2.

C. Using a session key from cryptographic analysis to decrypt and / or encrypt communications over the wireless link between the attacker and the phone, and / or decrypt and / or encrypt communications over the wireless link between the attacker and a network that is encrypted using A5 / 2, A5 / 1, A5 / 3 or GPRS, and / or decrypting and / or encrypting communications via a wireless link between the telephone and a network that is encrypted using A5 / 2, A5 / 1, A5 / 3 or GPRS.

[0147] The above methods of active GSM cryptographic analysis may also include:

A. The attacker's transmission makes the phone decide that the transmission originates from the network and requests the phone to encrypt using A5 / 1.

B. The phone responds with data encrypted with A5 / 1.

C. Using a session key from cryptographic analysis to decrypt and / or encrypt communications over the wireless link between the attacker and the phone, and / or decrypt and / or encrypt communications over the wireless link between the attacker and a network that is encrypted using A5 / 2, A5 / 1, A5 / 3 or GPRS, and / or decrypting and / or encrypting communications via a wireless link between the telephone and a network that is encrypted using A5 / 2, A5 / 1, A5 / 3 or GPRS.

[0148] In the above cryptographic analysis method, cryptographic analysis only in encrypted text may include:

A. Performing an effective attack with known plaintext on A5 / 1, which attack obtains the session key.

B. Improving the attack with known plaintext to attack only with encrypted text on A5 / 1.

Improvements in the method and system of the GSM network [0149] Various improvements in cellular systems will come to the mind of those skilled in the art after becoming familiar with the new attack methods described in detail in this disclosure. [0150] Examples relating to GSM include:

1. GSM operators should change the currently used cryptographic algorithms and protocols to protect the privacy of their customers.

2. Even GSM networks using the new A5 / 3 succumb to the attack presented here due to the current way of integrating A5 / 3 with GSM. Accordingly, it is suggested that changes be made to the way A5 / 3 integrates to protect networks against such attacks. A possible correction is to remove the relationship between the keys used in A5 / 1 and A5 / 2 and the keys used in A5 / 3. This change should also be made in GPRS. It is usually advantageous to create unrelated keys for different encryption so that the weakness of one does not affect the other.

3. Even if GSM uses longer keys for A5 / 3, the trivial way GSM does this is to use the same first key bits for A5 / 1 and A5 / 2, and to add a number of additional key bits. This will make our attack easily discover 64 bits of the key used in A5 / 3, seriously reducing the effectiveness of security.

4. The attack shown only in encrypted text is possible due to the fact that error correction codes are currently used before encryption. In the case of GSM, positive structured redundancy before performing encryption drastically reduces system security. A method and structure are proposed to remedy this defect.

5. A modification of the GSM standard, enabling the use of more than 64-bit A5 / 3, would provide better security and reduce the effectiveness of the attack.

6. Performing authentication more often, even during an ongoing session, can be a good security measure. It would prove that there is still a "real" subscriber at the other end of the channel. In addition, GSM authentication changes the key, which would force the eavesdropper to perform the attack from the beginning. Even if the key were not changed during the conversation, it would ensure that no one is impersonating.

7. Stop using A5 / 2, especially on telephones. Stopping the use of A5 / 2 would leave a direct attack on A5 / 1, which is more expensive and difficult to perform. An attack against A5 / 1 can still be adapted against GPRS (just like the attack on A5 / 2), but the cost would be much higher. The disadvantage of this change is that it would force infrastructure improvements in networks that use A5 / 2. Another option is to create a series of phones that do not support A5 / 2. They would not encrypt while roaming to the A5 / 2 network (but, as we show, A5 / 2 is not secure anyway), but would increase the level of protection in networks using A5 / 1 or A5 / 3, because the attack on A5 / 2 would not work . For this reason, you would have to use a direct attack on A5 / 1, which is much more expensive and difficult to perform.

8. The use of more available bits for encryption, i.e. the use of all 64 available key bits. In the future, when more bits are available, more bits can be used.

[0151] It should be noted that the above is just one example of the device and method within the scope of the invention, and after reading the disclosure provided herein, various modifications will occur to those skilled in the art.