Skip to main content
SpringerLink
Log in
Book cover

Annual International Conference on the Theory and Applications of Cryptographic Techniques

EUROCRYPT 2021: Advances in Cryptology – EUROCRYPT 2021 pp 155–183Cite as

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

  • Conference paper
  • First Online:

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12697))

Abstract

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time \(2^{40}\) GEA-1 evaluations and using 44.5 GiB of memory.

The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design.

In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time \(2^{45.1}\) GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Notes

  1. 1.

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

  2. 2.

    See minute 32:15 of the recorded talk.

  3. 3.

    The size of the registers are visible in the live state-recovery attack, see minute 48:25 of the recorded talk.

  4. 4.

    The authors acknowledged Mate Soos for ideas and also admitted that the live attack did not apply the SAT solver yet.

  5. 5.

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

  6. 6.

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

References

  1. Anderson, R.J.: A5 (was hacking digital phones). Newsgroup Communication (1994). http://yarchive.net/phone/gsmcipher.html. Accessed 4 Mar 2021

  2. Berlekamp, E.R.: Algebraic Coding Theory. McGraw-Hill Series in Systems Science. McGraw-Hill (1968). http://www.worldcat.org/oclc/00256659

  3. Bettale, L., Faugère, J., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3(3), 177–197 (2009). https://doi.org/10.1515/JMC.2009.009

    Article  MathSciNet  MATH  Google Scholar 

  4. Biryukov, A., Gong, G., Stinson, D.R. (eds.): SAC 2010. LNCS, vol. 6544. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19574-7

    Book  MATH  Google Scholar 

  5. Blahut, R.E.: Theory and Practice of Error Control Codes. Addison-Wesley, Boston (1983)

    MATH  Google Scholar 

  6. Bogdanov, A., Rechberger, C.: A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN. In: Biryukov et al. [4], pp. 229–240. https://doi.org/10.1007/978-3-642-19574-7_16

  7. Bouillaguet, C., et al.: Fast exhaustive search for polynomial systems in \({\mathbb{F}_2}\). In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 203–218. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15031-9_14

    Chapter  Google Scholar 

  8. Brookson, C.: GPRS Security (2001). https://web.archive.org/web/20120914110208/www.brookson.com/gsm/gprs.pdf. (snapshot of 14 September 2012)

  9. Carlet, C., Crama, Y., Hammer, P.L.: Boolean functions for cryptography and error-correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press (2010). https://doi.org/10.1017/cbo9780511780448.011

  10. Dagum, L., Menon, R.: OpenMP: an industry standard API for shared-memory programming. IEEE Comput. Sci. Eng. 5(1), 46–55 (1998)

    Article  Google Scholar 

  11. Tomcsányi, D.P., Weyres, M., Simao, P.: Analysis of EGPRS Ciphering Algorithms used Worldwide. https://www.umlaut.com/en/analysis-of-egprs-ciphering-algorithms-used-worldwide. (to appear)

  12. Dunkelman, O., Sekar, G., Preneel, B.: Improved meet-in-the-middle attacks on reduced-round DES. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 86–100. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77026-8_8

    Chapter  MATH  Google Scholar 

  13. Duval, S., Lallemand, V., Rotella, Y.: Cryptanalysis of the FLIP family of stream ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 457–475. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_17

    Chapter  Google Scholar 

  14. ETSI: ETSI – Coordinated Vulnerability Disclosure. https://www.etsi.org/standards/coordinated-vulnerability-disclosure. Accessed 4 Mar 2021

  15. ETSI: Security algorithms group of experts (SAGE); report on the specification, evaluation and usage of the GSM GPRS encryption algorithm (GEA). Technical report (1998). https://www.etsi.org/deliver/etsi_tr/101300_101399/101375/01.01.01_60/tr_101375v010101p.pdf. Accessed 8 Oct 2020

  16. ETSI: Digital cellular telecommunications system (phase 2+) (GSM); security related network functions (3GPP TS 43.020 version 15.0.0 release 15). Technical Specification (2018). https://www.etsi.org/deliver/etsi_ts/143000_143099/143020/15.00.00_60/ts_143020v150000p.pdf. Accessed 8 Oct 2020

  17. GCF: GCF – Global Certification Forum. https://www.globalcertificationforum.org/. Accessed 4 Mar 2021

  18. Golić, J.D.: Cryptanalysis of alleged A5 stream cipher. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 239–255. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_17

    Chapter  Google Scholar 

  19. GSMA: GSMA – Coordinated Vulnerability Disclosure Programme. https://www.gsma.com/security/gsma-coordinated-vulnerability-disclosure-programme/. Accessed 4 Mar 2021

  20. Hoffman, K., Kunze, R.A.: Linear Algebra. PHI Learning (2004). http://www.worldcat.org/isbn/8120302702

  21. Kalenderi, M., Pnevmatikatos, D.N., Papaefstathiou, I., Manifavas, C.: Breaking the GSM A5/1 cryptography algorithm with rainbow tables and high-end FPGAS. In: Koch, D., Singh, S., Tørresen, J. (eds.) 22nd International Conference on Field Programmable Logic and Applications (FPL), Oslo, Norway, 29–31 August 2012, pp. 747–753. IEEE (2012). https://doi.org/10.1109/FPL.2012.6339146

  22. Khovratovich, D., Naya-Plasencia, M., Röck, A., Schläffer, M.: Cryptanalysis of Luffa v2 components. In: Biryukov et al. [4], pp. 388–409. https://doi.org/10.1007/978-3-642-19574-7_26

  23. Koops, B.J.: Crypto law survey (2013). http://www.cryptolaw.org. Accessed 8 Oct 2020

  24. Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: Rebound distinguishers: results on the full whirlpool compression function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_8

    Chapter  Google Scholar 

  25. Albrecht, M., Bard, G.: The M4RI Library. The M4RI Team (2021). http://m4ri.sagemath.org. Accessed 4 Mar 2021

  26. Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969). https://doi.org/10.1109/TIT.1969.1054260

    Article  MathSciNet  MATH  Google Scholar 

  27. McFarland, R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory Ser. A 15(1), 1–10 (1973). https://doi.org/10.1016/0097-3165(73)90031-9

    Article  MathSciNet  MATH  Google Scholar 

  28. MediaTek: Test Vector GEA1/2 – MediaTek-HelioX10-Baseband. https://github.com/Dude100/MediaTek-HelioX10-Baseband/blob/591772a0d659ef0f7bba1953d18f8fe7c18b11de/(FDD)MT6795.MOLY.LR9.W1423.MD.LWTG.MP.V24/driver/cipher/include/gcu_ut.h. Accessed 4 Mar 2021

  29. Nohl, K., Melette, L.: GPRS intercept: Wardriving your country. Chaos Communication Camp (2011). Slides http://events.ccc.de/camp/2011/Fahrplan/attachments/1868_110810.SRLabs-Camp-GRPS_Intercept.pdf. Accessed 8 Oct 2020. Recorded talk https://media.ccc.de/v/cccamp11-4504-gprs_intercept-en#t=1744. Accessed 8 Oct 2020

  30. Oechslin, P.: Making a faster cryptanalytic time-memory trade-off. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 617–630. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_36

    Chapter  Google Scholar 

  31. osmocom: osmocom – Cellular Network Infrastructure. https://osmocom.org/projects/cellular-infrastructure. Accessed 4 Mar 2021

  32. Rothaus, O.S.: On “bent” functions. J. Comb. Theory Ser. A 20(3), 300–305 (1976). https://doi.org/10.1016/0097-3165(76)90024-8

    Article  MATH  Google Scholar 

  33. Sasaki, Y.: Meet-in-the-middle preimage attacks on AES hashing modes and an application to Whirlpool. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 378–396. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_22

    Chapter  Google Scholar 

  34. Schneier, B.: Applied Cryptography - Protocols, Algorithms, and Source Code in C, 2nd edn. Wiley (1996). http://www.worldcat.org/oclc/32311687

  35. Schroeppel, R., Shamir, A.: A T=O(2\({}^{\text{ n/2 }}\)), S=O(2\({}^{\text{ n/4 }}\)) algorithm for certain np-complete problems. SIAM J. Comput. 10(3), 456–464 (1981). https://doi.org/10.1137/0210033

    Article  MathSciNet  MATH  Google Scholar 

  36. Siegenthaler, T.: Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Comput. 34(1), 81–85 (1985). https://doi.org/10.1109/TC.1985.1676518

    Article  Google Scholar 

  37. The Sage Developers: SageMath, the Sage Mathematics Software System (2020). https://www.sagemath.org

Download references

Acknowledgment

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

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

Author information

Authors and Affiliations

  1. Ruhr University Bochum, Bochum, Germany

    Christof Beierle, Gregor Leander, David Rupprecht & Lukas Stennes

  2. Univ Rennes, CNRS, IRISA, Rennes, France

    Patrick Derbez

  3. Inria, Paris, France

    Gaëtan Leurent

  4. Simula UiB, Bergen, Norway

    Håvard Raddum

  5. Laboratoire de Mathématiques de Versailles, Université Paris-Saclay, UVSQ, CNRS, Versailles, France

    Yann Rotella

Authors
  1. Christof Beierle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patrick Derbez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gregor Leander
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gaëtan Leurent
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Håvard Raddum
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yann Rotella
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. David Rupprecht
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Lukas Stennes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Christof Beierle , Patrick Derbez , Gregor Leander , Gaëtan Leurent , Håvard Raddum , Yann Rotella , David Rupprecht or Lukas Stennes .

Editor information

Editors and Affiliations

  1. Inria, Paris, France

    Anne Canteaut

  2. UCLouvain, Louvain-la-Neuve, Belgium

    François-Xavier Standaert

Appendices

Appendix A Source Code to Compute the Kernels

figure d

Appendix B Source Code to Compute the Dimensions

figure e

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Beierle, C. et al. (2021). Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2. In: Canteaut, A., Standaert, FX. (eds) Advances in Cryptology – EUROCRYPT 2021. EUROCRYPT 2021. Lecture Notes in Computer Science(), vol 12697. Springer, Cham. https://doi.org/10.1007/978-3-030-77886-6_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-77886-6_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-77885-9

  • Online ISBN: 978-3-030-77886-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation