World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0000294149
Reproduction Date:

Title: A5/1  
Author: World Heritage Encyclopedia
Language: English
Subject: Stream cipher, A5/2, Grain (cipher), Mobile security, E0 (cipher)
Collection: 3Gpp Standards, Broken Stream Ciphers, Gsm Standard, Mobile Telecommunications Standards, Stream Ciphers
Publisher: World Heritage Encyclopedia


A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It is one of seven algorithms which were specified for GSM use.[1] 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.


  • History and usage 1
  • Description 2
  • Security 3
    • Known-plaintext attacks 3.1
    • Attacks on A5/1 as used in GSM 3.2
  • See also 4
  • Notes 5
  • References 6
  • External links 7

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.[2] 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; by 2011, it was 4 billion..

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."[3]


The A5/1 stream cipher uses three LFSRs. A register is clocked if its clocking bit (orange) agrees with one or both of the clocking bits 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 Comp128v2 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:

Length in
1 19 x^{19} + x^{18} + x^{17} + x^{14} + 1 8 13, 16, 17, 18
2 22 x^{22} + x^{21} + 1 10 20, 21
3 23 x^{23} + x^{22} + x^{21} + x^{8} + 1 10 7, 20, 21, 22

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 is mixed in according to the following scheme: in cycle 0\leq{i}<64, the ith key bit is added to the least significant bit of each register using XOR —

R[0] = R[0] \oplus K[i].

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.


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.[4]

Some attacks require an expensive preprocessing stage after which the cipher can be broken in minutes or seconds. Until recently, the weaknesses have been 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 estimated that 128 bits would in fact also still be secure as of 2014. 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 56 bits.[5]

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.[3]

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,[6] based on earlier work by Jovan Golic.[7] 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.[8]

Ekdahl and Johannson published an attack on the initialisation procedure which breaks A5/1 in a few minutes using two to five minutes of conversation plaintext.[9] 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.[10]

Attacks on A5/1 as used in GSM

In 2003, Barkan et al. published several attacks on GSM encryption.[11] 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 Ciphers. The authors claim:[12]

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[13] 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 precomputated 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.[14]

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.[15]

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 2TB completed table, and had been computed during three months using 40 distributed CUDA nodes, and then published over BitTorrent.[14][15][16][17] 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.[18]

Documents leaked by Edward Snowden in 2013 states that NSA "can process encrypted A5/1".[19]

See also


  1. ^ "Prohibiting A5/2 in mobile stations and other clarifications regarding A5 algorithm support". 
  2. ^ Quirke, Jeremy (2004-05-01). "Security in the GSM system" (PDF). AusMobile. Archived from the original (PDF) on 2004-07-12. 
  3. ^ a b  
  4. ^ NSA Able To Crack A5/1 Cellphone Crypto - Slashdot
  5. ^
  6. ^  
  7. ^ Golic, Jovan Dj. (1997). "Cryptanalysis of Alleged A5 Stream Cipher".  
  8. ^ Biham, Eli; Orr Dunkelman (2000). "Cryptanalysis of the A5/1 GSM Stream Cipher".  
  9. ^ Ekdahl, Patrik; Thomas Johansson (2003). ( "Another attack on A5/1" (PDF). IEEE Transactions on Information Theory 49 (1): 284–89.  
  10. ^ Barkan, Elad; Eli Biham (2005). "Conditional Estimators: An Effective Attack on A5/1". Selected Areas in Cryptography 2005: 1–19. 
  11. ^ Barkan, Elad;  
  12. ^ Barkan, Elad; Eli Biham; Nathan Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)" (PDF). 
  13. ^ Gueneysu, Tim; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp (2008). "Cryptanalysis with COPACOBANA" (PDF).  
  14. ^ a b Nohl, Karsten; Chris Paget (2009-12-27). GSM: SRSLY?. 26th Chaos Communication Congress (26C3):. Archived from the original on 6 January 2010. Retrieved 2009-12-30. 
  15. ^ a b Subverting the security base of GSM. Karsten Nohl and Sascha Krißler
  16. ^ O'Brien, Kevin (2009-12-28). "Cellphone Encryption Code Is Divulged". New York Times. Archived from the original on 1 January 2010. Retrieved 2009-12-29. 
  17. ^ McMillan, Robert. "Hackers Show It's Easy to Snoop on a GSM Call". IDG News Service. 
  18. ^ Frank A. Stevenson (2010-05-01). "Cracks beginning to show in A5/1". Archived from the original on 2012-03-06. 
  19. ^


  • Rose, Greg (2003-09-10). "A precis of the new attacks on GSM encryption" (PDF).  
  • Maximov, Alexander; Thomas Johansson; Steve Babbage (2004). "An Improved Correlation Attack on A5/1".  

External links

  • Briceno, Marc; Ian Goldberg; David Wagner (1999-10-23). "A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms" (PDF). 
  • "Huge GSM flaw allows hackers to listen in on voice calls". 2009-08-25. 
  • Horesh, Hadar (2003-09-03). "Technion team cracks GSM cellular phone encryption" (PDF).  
  • Barkan, Elad; Eli Biham; Nathan Keller (July 2006). "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07)". 
  • "Nathan Keller's Homepage". 
  • "Animated SVG showing A5/1 stream cypher". 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.