Security of GSM: A5/1 cipher

Published on 28 Mar 2023

Photo by Annie Spratt on Unsplash

The Global System for Mobile Communications (GSM) is a standard that describes the protocols used in the 2G cellular mobile networks. GSM has a long history now, because its first implementation dates back to 1991. It seems interesting to me how complicated a technology like this can be if we carefully study all the physical (infrastructure and devices) and non-physical (algorithms) components.

In this article, I will talk about how I discovered the existence of A5/1, which is one of the encryption algorithms used in the GSM standard, and I will try to write some code to implement it.

Nothing too serious, just playing a bit with some theory and code.

The story

It all started from an interest I had in stream ciphers. In particular, I didn’t understand how they could ensure at least those three properties: confidentiality, high speed at least compared to block ciphers and low hardware complexity.

While researching, I bumped into Linear-Feedback Shift Registers (LFSR). I decided to read more about them on Wikipedia. At some point, I read that LFSRs are vulnerable to cryptoanalysis, and KPA attacks. This made me think that I was not on the right page, since I was looking for something secure and currently usable. I was about to leave the page.

Then, a word caught my attention. The word was GSM.

Important LFSR-based stream ciphers include A5/1 and A5/2, used in GSM cell phones.

I decided to spend a few moments more on LFSRs.

The A family

Without going into many details, the security of the GSM architecture lies in the usage of three different algorithms:

1) A3, for the authentication of the subscriber.

2) A5, for data encryption/decryption.

3) A8, for the generation of the session keys.

Speaking of the A5 algorithm, different versions exist: A5/0, A5/1 and A5/2. The first one doesn’t encrypt data and the last one is a weaker encryption scheme compared to A5/1, which is the standard.

When 3G came, a new algorithm was included in the A family with the name A5/3.

A few words about A5/1

A5/1 schema Schema by Jensen and Andersen at this link

I was surprised by how simple this encryption algorithm is. It is a stream algorithm that combines three LFSRs with irregular clocking. After a few steps to get the registers ready for the keystream generation, the actual output of the pseudorandom number generator can be XORed with the plaintext to produce the ciphertext.

A5 operates on 228-bit frames, divided into two sequences of 114 bits. The first sequence is used for downlink, and the second one is for uplink.

After a few searches on the web, I found a C implementation of the A5 algorithm made by Marc Briceno, Ian Goldberg, and David Wagner. The README of this version says “A pedagogical implementation of A5/1”.

Exactly what I needed.

After a few hours spent understanding the logic behind the code, I decided to do some changes and re-implement it. While reading the code I also found some suggestions left as comments, and I thought to address those suggestions.

I leave the link to my GitHub repository so you can have a look at the code. Feel free to get in touch with me using any of the contacts you can find at the bottom of this page.

Thank you!

Resources