A5/1

Last updated

A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It is one of several implementations of the A5 security protocol. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified.

Contents

History and usage

A5/1 is used in Europe and the United States. A5/2 was a deliberate weakening of the algorithm for certain export regions. [1] A5/1 was developed in 1987, when GSM was not yet considered for use outside Europe, and A5/2 was developed in 1989. Though both were initially kept secret, the general design was leaked in 1994 and the algorithms were entirely reverse engineered in 1999 by Marc Briceno from a GSM telephone. In 2000, around 130 million GSM customers relied on A5/1 to protect the confidentiality of their voice communications.[ citation needed ]

Security researcher Ross Anderson reported in 1994 that "there was a terrific row between the NATO signal intelligence agencies in the mid-1980s over whether GSM encryption should be strong or not. The Germans said it should be, as they shared a long border with the Warsaw Pact; but the other countries didn't feel this way, and the algorithm as now fielded is a French design." [2]

Description

The A5/1 stream cipher uses three LFSRs. A register is clocked if its clocking bit (orange) agrees with the clocking bit of one or both of the other two registers. A5-1 GSM cipher.svg
The A5/1 stream cipher uses three LFSRs. A register is clocked if its clocking bit (orange) agrees with the clocking bit of one or both of the other two registers.

A GSM transmission is organised as sequences of bursts. In a typical channel and in one direction, one burst is sent every 4.615 milliseconds and contains 114 bits available for information. A5/1 is used to produce for each burst a 114 bit sequence of keystream which is XORed with the 114 bits prior to modulation. A5/1 is initialised using a 64-bit key together with a publicly known 22-bit frame number. Older fielded GSM implementations using Comp128v1 for key generation, had 10 of the key bits fixed at zero, resulting in an effective key length of 54 bits. This weakness was rectified with the introduction of Comp128v3 which yields proper 64 bits keys. When operating in GPRS / EDGE mode, higher bandwidth radio modulation allows for larger 348 bits frames, and A5/3 is then used in a stream cipher mode to maintain confidentiality.

A5/1 is based around a combination of three linear-feedback shift registers (LFSRs) with irregular clocking. The three shift registers are specified as follows:

LFSR
number		Length in
bits		Feedback
polynomial		Clocking
bit		Tapped
bits
119813, 16, 17, 18
2221020, 21
323107, 20, 21, 22

These degrees were not chosen at random: since the degrees of the three registers are relatively prime, the period of this generator is the product of the periods of the three registers. Thus the period of A5/1 (before repetition) is 2^64 bits (2 to the power of 64).

The bits are indexed with the least significant bit (LSB) as 0.

The registers are clocked in a stop/go fashion using a majority rule. Each register has an associated clocking bit. At each cycle, the clocking bit of all three registers is examined and the majority bit is determined. A register is clocked if the clocking bit agrees with the majority bit. Hence at each step at least two or three registers are clocked, and each register steps with probability 3/4.

Initially, the registers are set to zero. Then for 64 cycles, the 64-bit secret key K is mixed in according to the following scheme: in cycle , the ith key bit is added to the least significant bit of each register using XOR —

Each register is then clocked.

Similarly, the 22-bits of the frame number are added in 22 cycles. Then the entire system is clocked using the normal majority clocking mechanism for 100 cycles, with the output discarded. After this is completed, the cipher is ready to produce two 114 bit sequences of output keystream, first 114 for downlink, last 114 for uplink.

Security

The message on the screen of a mobile phone with the warning about lack of ciphering CipheringNotProvided.jpg
The message on the screen of a mobile phone with the warning about lack of ciphering

A number of attacks on A5/1 have been published, and the American National Security Agency is able to routinely decrypt A5/1 messages according to released internal documents. [3]

Some attacks require an expensive preprocessing stage after which the cipher can be broken in minutes or seconds. Originally, the weaknesses were passive attacks using the known plaintext assumption. In 2003, more serious weaknesses were identified which can be exploited in the ciphertext-only scenario, or by an active attacker. In 2006 Elad Barkan, Eli Biham and Nathan Keller demonstrated attacks against A5/1, A5/3, or even GPRS that allow attackers to tap GSM mobile phone conversations and decrypt them either in real-time, or at any later time.

According to professor Jan Arild Audestad, at the standardization process which started in 1982, A5/1 was originally proposed to have a key length of 128 bits. At that time, 128 bits was projected to be secure for at least 15 years. It is now believed that 128 bits would in fact also still be secure until the advent of quantum computing. Audestad, Peter van der Arend, and Thomas Haug says that the British insisted on weaker encryption, with Haug saying he was told by the British delegate that this was to allow the British secret service to eavesdrop more easily. The British proposed a key length of 48 bits, while the West Germans wanted stronger encryption to protect against East German spying, so the compromise became a key length of 54 bits. [4]

Known-plaintext attacks

The first attack on the A5/1 was proposed by Ross Anderson in 1994. Anderson's basic idea was to guess the complete content of the registers R1 and R2 and about half of the register R3. In this way the clocking of all three registers is determined and the second half of R3 can be computed. [2]

In 1997, Golic presented an attack based on solving sets of linear equations which has a time complexity of 240.16 (the units are in terms of number of solutions of a system of linear equations which are required).

In 2000, Alex Biryukov, Adi Shamir and David Wagner showed that A5/1 can be cryptanalysed in real time using a time-memory tradeoff attack, [5] based on earlier work by Jovan Golic. [6] One tradeoff allows an attacker to reconstruct the key in one second from two minutes of known plaintext or in several minutes from two seconds of known plain text, but he must first complete an expensive preprocessing stage which requires 248 steps to compute around 300 GB of data. Several tradeoffs between preprocessing, data requirements, attack time and memory complexity are possible.

The same year, Eli Biham and Orr Dunkelman also published an attack on A5/1 with a total work complexity of 239.91 A5/1 clockings given 220.8 bits of known plaintext. The attack requires 32 GB of data storage after a precomputation stage of 238. [7]

Ekdahl and Johansson published an attack on the initialisation procedure which breaks A5/1 in a few minutes using two to five minutes of conversation plaintext. [8] This attack does not require a preprocessing stage. In 2004, Maximov et al. improved this result to an attack requiring "less than one minute of computations, and a few seconds of known conversation". The attack was further improved by Elad Barkan and Eli Biham in 2005. [9]

Attacks on A5/1 as used in GSM

In 2003, Barkan et al. published several attacks on GSM encryption. [10] The first is an active attack. GSM phones can be convinced to use the much weaker A5/2 cipher briefly. A5/2 can be broken easily, and the phone uses the same key as for the stronger A5/1 algorithm. A second attack on A5/1 is outlined, a ciphertext-only time-memory tradeoff attack which requires a large amount of precomputation.

In 2006, Elad Barkan, Eli Biham, Nathan Keller published the full version of their 2003 paper, with attacks against A5/X сiphers. The authors claim: [11]

We present a very practical ciphertext-only cryptanalysis of GSM encrypted communication, and various active attacks on the GSM protocols. These attacks can even break into GSM networks that use "unbreakable" ciphers. We first describe a ciphertext-only attack on A5/2 that requires a few dozen milliseconds of encrypted off-the-air cellular conversation and finds the correct key in less than a second on a personal computer. We extend this attack to a (more complex) ciphertext-only attack on A5/1. We then describe new (active) attacks on the protocols of networks that use A5/1, A5/3, or even GPRS. These attacks exploit flaws in the GSM protocols, and they work whenever the mobile phone supports a weak cipher such as A5/2. We emphasize that these attacks are on the protocols, and are thus applicable whenever the cellular phone supports a weak cipher, for example, they are also applicable for attacking A5/3 networks using the cryptanalysis of A5/1. Unlike previous attacks on GSM that require unrealistic information, like long known plaintext periods, our attacks are very practical and do not require any knowledge of the content of the conversation. Furthermore, we describe how to fortify the attacks to withstand reception errors. As a result, our attacks allow attackers to tap conversations and decrypt them either in real-time, or at any later time.

In 2007 Universities of Bochum and Kiel started a research project to create a massively parallel FPGA-based cryptographic accelerator COPACOBANA. COPACOBANA was the first commercially available solution [12] using fast time-memory trade-off techniques that could be used to attack the popular A5/1 and A5/2 algorithms, used in GSM voice encryption, as well as the Data Encryption Standard (DES). It also enables brute force attacks against GSM eliminating the need of large precomputed lookup tables.

In 2008, the group The Hackers Choice launched a project to develop a practical attack on A5/1. The attack requires the construction of a large look-up table of approximately 3 terabytes. Together with the scanning capabilities developed as part of the sister project, the group expected to be able to record any GSM call or SMS encrypted with A5/1, and within about 3–5 minutes derive the encryption key and hence listen to the call and read the SMS in clear. But the tables weren't released. [13]

A similar effort, the A5/1 Cracking Project, was announced at the 2009 Black Hat security conference by cryptographers Karsten Nohl and Sascha Krißler. It created the look-up tables using Nvidia GPGPUs via a peer-to-peer distributed computing architecture. Starting in the middle of September 2009, the project ran the equivalent of 12 Nvidia GeForce GTX 260. According to the authors, the approach can be used on any cipher with key size up to 64-bits. [14]

In December 2009, the A5/1 Cracking Project attack tables for A5/1 were announced by Chris Paget and Karsten Nohl. The tables use a combination of compression techniques, including rainbow tables and distinguished point chains. These tables constituted only parts of the 1.7 TB completed table and had been computed during three months using 40 distributed CUDA nodes and then published over BitTorrent. [13] [14] [15] [16] More recently the project has announced a switch to faster ATI Evergreen code, together with a change in the format of the tables and Frank A. Stevenson announced breaks of A5/1 using the ATI generated tables. [17]

Documents leaked by Edward Snowden in 2013 state that the NSA "can process encrypted A5/1". [18]

Using A5/1 as pseudorandom generator

Since the degrees of the three LFSRs are relatively prime, the period of this generator is the product of the periods of the three LFSRs, which represents 2^64 bits (2 to the power of 64).

One might think of using A5/1 as pseudo-random generator with a 64-bit initialization seed (key size), but it is not reliable. It loses its randomness after only 8 MB (which represents the period of the largest of the three registers).

See also

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Cryptanalysis</span> Study of analyzing information systems in order to discover their hidden aspects

Cryptanalysis refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

<span class="mw-page-title-main">Ciphertext</span> Encrypted information

In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. This process prevents the loss of sensitive information via hacking. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

<span class="mw-page-title-main">Eli Biham</span> Israeli cryptographer and cryptanalyst

Eli Biham is an Israeli cryptographer and cryptanalyst who is a professor at the Technion - Israel Institute of Technology Computer Science department. From 2008 to 2013, Biham was the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate school. Biham invented (publicly) differential cryptanalysis, for which he received his Ph.D., while working under Adi Shamir. It had been invented before by a team at IBM during their Data Encryption Standard work; the National Security Agency told IBM to keep the discovery secret.

In cryptography, a ciphertext-only attack (COA) or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts. While the attacker has no channel providing access to the plaintext prior to encryption, in all practical ciphertext-only attacks, the attacker still has some knowledge of the plaintext. For instance, the attacker might know the language in which the plaintext is written or the expected statistical distribution of characters in the plaintext. Standard protocol data and messages are commonly part of the plaintext in many deployed systems, and can usually be guessed or known efficiently as part of a ciphertext-only attack on these systems.

A5/2 is a stream cipher used to provide voice privacy in the GSM cellular telephone protocol. It was designed in 1992-1993 as a replacement for the relatively stronger A5/1, to allow the GSM standard to be exported to countries "with restrictions on the import of products with cryptographic security features".

KASUMI is a block cipher used in UMTS, GSM, and GPRS mobile communications systems. In UMTS, KASUMI is used in the confidentiality (f8) and integrity algorithms (f9) with names UEA1 and UIA1, respectively. In GSM, KASUMI is used in the A5/3 key stream generator and in GPRS in the GEA3 key stream generator.

<span class="mw-page-title-main">DES-X</span> Block cipher

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

In cryptography, the Cellular Message Encryption Algorithm (CMEA) is a block cipher which was used for securing mobile phones in the United States. CMEA is one of four cryptographic primitives specified in a Telecommunications Industry Association (TIA) standard, and is designed to encrypt the control channel, rather than the voice data. In 1997, a group of cryptographers published attacks on the cipher showing it had several weaknesses which give it a trivial effective strength of a 24-bit to 32-bit cipher. Some accusations were made that the NSA had pressured the original designers into crippling CMEA, but the NSA has denied any role in the design or selection of the algorithm. The ECMEA and SCEMA ciphers are derived from CMEA.

In cryptography, Madryga is a block cipher published in 1984 by W. E. Madryga. It was designed to be easy and efficient for implementation in software. Serious weaknesses have since been found in the algorithm, but it was one of the first encryption algorithms to make use of data-dependent rotations, later used in other ciphers, such as RC5 and RC6.

<span class="mw-page-title-main">Boomerang attack</span> Form of cryptanalysis

In cryptography, the boomerang attack is a method for the cryptanalysis of block ciphers based on differential cryptanalysis. The attack was published in 1999 by David Wagner, who used it to break the COCONUT98 cipher.

Introduced by Martin Hellman and Susan K. Langford in 1994, the differential-linear attack is a mix of both linear cryptanalysis and differential cryptanalysis.

In cryptography, COCONUT98 is a block cipher designed by Serge Vaudenay in 1998. It was one of the first concrete applications of Vaudenay's decorrelation theory, designed to be provably secure against differential cryptanalysis, linear cryptanalysis, and even certain types of undiscovered cryptanalytic attacks.

In cryptography, the Davies attack is a dedicated statistical cryptanalysis method for attacking the Data Encryption Standard (DES). The attack was originally created in 1987 by Donald Davies. In 1994, Eli Biham and Alex Biryukov made significant improvements to the technique. It is a known-plaintext attack based on the non-uniform distribution of the outputs of pairs of adjacent S-boxes. It works by collecting many known plaintext/ciphertext pairs and calculating the empirical distribution of certain characteristics. Bits of the key can be deduced given sufficiently many known plaintexts, leaving the remaining bits to be found through brute force. There are tradeoffs between the number of required plaintexts, the number of key bits found, and the probability of success; the attack can find 24 bits of the key with 252 known plaintexts and 53% success rate.

The following outline is provided as an overview of and topical guide to cryptography:

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

References

  1. ↑ Quirke, Jeremy (1 May 2004). "Security in the GSM system" (PDF). AusMobile. Archived from the original (PDF) on 12 July 2004. Retrieved 8 September 2008.
  2. 1 2 Ross Anderson (17 June 1994). "A5 (Was: HACKING DIGITAL PHONES)". Newsgroup:  uk.telecom. Usenet:   2ts9a0$95r@lyra.csx.cam.ac.uk.
  3. ↑ NSA Able To Crack A5/1 Cellphone Crypto - Slashdot
  4. ↑ "Sources: We were pressured to weaken the mobile security in the 80's". 9 January 2014.
  5. ↑ Biryukov, Alex; Adi Shamir; David Wagner. "Real Time Cryptanalysis of A5/1 on a PC". Fast Software Encryption—FSE 2000: 1–18.
  6. ↑ Golic, Jovan Dj. (1997). "Cryptanalysis of Alleged A5 Stream Cipher" (PDF). Eurocrypt 1997: 239–55. Archived from the original (PDF) on 15 July 2010. Retrieved 13 January 2016.
  7. ↑ Biham, Eli; Orr Dunkelman (2000). "Cryptanalysis of the A5/1 GSM Stream Cipher". Progress in Cryptology —INDOCRYPT 2000. Lecture Notes in Computer Science. Vol. 1977. pp. 43–51. doi:10.1007/3-540-44495-5_5. ISBN   978-3-540-41452-0.
  8. ↑ Ekdahl, Patrik; Thomas Johansson (2003). "Another attack on A5/1" (PDF). IEEE Transactions on Information Theory. 49 (1): 284–89. doi:10.1109/TIT.2002.806129. Archived from the original (PDF) on 25 May 2005.
  9. ↑ Barkan, Elad; Eli Biham (2005). "Conditional Estimators: An Effective Attack on A5/1". Selected Areas in Cryptography 2005: 1–19.
  10. ↑ Barkan, Elad; Eli Biham; Nathan Keller (2003). "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication". Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Vol. 2729. pp. 600–16. doi: 10.1007/978-3-540-45146-4_35 . ISBN   978-3-540-40674-7.
  11. ↑ Barkan, Elad; Eli Biham; Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)" (PDF). Archived from the original (PDF) on 25 January 2020. Retrieved 15 September 2019.
  12. ↑ Gueneysu, Tim; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp (2008). "Cryptanalysis with COPACOBANA" (PDF). IEEE Transactions on Computers . 57 (11): 1498–1513. doi:10.1109/TC.2008.80. S2CID   8754598.
  13. 1 2 Nohl, Karsten; Chris Paget (27 December 2009). GSM: SRSLY?. 26th Chaos Communication Congress (26C3). Archived from the original on 6 January 2010. Retrieved 30 December 2009.
  14. 1 2 "Archived copy" (PDF). Archived from the original (PDF) on 26 July 2011. Retrieved 29 December 2009.{{cite web}}: CS1 maint: archived copy as title (link) Subverting the security base of GSM. Karsten Nohl and Sascha Krißler
  15. ↑ O'Brien, Kevin (28 December 2009). "Cellphone Encryption Code Is Divulged". New York Times. Archived from the original on 29 April 2011. Retrieved 29 December 2009.
  16. ↑ McMillan, Robert. "Hackers Show It's Easy to Snoop on a GSM Call". IDG News Service. Archived from the original on 20 January 2012. Retrieved 29 December 2009.
  17. ↑ Frank A. Stevenson (1 May 2010). "Cracks beginning to show in A5/1". Archived from the original on 6 March 2012.
  18. ↑ Timberg, Craig; Soltani, Ashkan (13 December 2013). "By cracking cellphone code, NSA has ability to decode private conversations". The Washington Post . Retrieved 28 September 2016.

Notes

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.