International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables

Bin Zhang
DOI: 10.1007/978-3-030-34618-8_15
Search ePrint
Search Google
Abstract: The GSM standard developed by ETSI for 2G networks adopts the A5/1 stream cipher to protect the over-the-air privacy in cell phone and has become the de-facto global standard in mobile communications, though the emerging of subsequent 3G/4G standards. There are many cryptanalytic results available so far and the most notable ones share the need of a heavy pre-computation with large rainbow tables or distributed cracking network. In this paper, we present a fast near collision attack on GSM encryption in 2G/3G networks, which is completely new and more threatening compared to the previous best results. We adapt the fast near collision attack proposed at Eurocrypt 2018 with the concrete irregular clocking manner in A5/1 to have a state recovery attack with a low complexity. It is shown that if the first 64 bits of one keystream frame are available, the secret key of A5/1 can be reliably found in $$2^{31.79}$$ cipher ticks, given around 1 MB memory and after the pre-computation of $$2^{20.26}$$ cipher ticks. Our current implementation clearly certified the validity of the suggested attack. Due to the fact that A5/3 and GPRS share the same key with A5/1, this can be converted into attacks against any GSM network eventually.
  title={Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  author={Bin Zhang},