The A5/1 Stream Cipher

The A5/1 Stream Cipher

Introduction

A5/1 is the stream cipher that encrypted voice calls on GSM mobile networks. For many years it sat between a phone and the nearest cell tower, and it was meant to stop anyone from listening to the radio link. By the year 2000, about 130 million customers relied on it.

The cipher is small. It has three shift registers with a total of 64 bits, and a simple rule decides which of them move. That rule, called majority clocking, is the only clever part. It is also the part that made A5/1 a favorite for a whole generation of cryptanalysts.

Table of Contents

• History
• The Three Registers
• Majority Clocking
• Key and Frame Setup
• Generating Keystream
• Byte Order and Frame Numbers
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

A5/1 was developed in 1987, before GSM spread across Europe. A weaker sister cipher, A5/2, followed in the late 1980s for sale in other regions. The designs were kept secret, and the GSM community never subjected them to public review.

The secrecy did not last. The design leaked in 1994, and in 1999 Marc Briceno reverse-engineered the full algorithm from a GSM telephone. He published a clear reference implementation together with Ian Goldberg and David Wagner. That code is the source of the test vector used in this guide.

The same reference code makes a second claim. The authors wrote that every key generation algorithm they could find had been weakened from 64 bits to 54 bits, with the remaining ten bits set to zero. A short effective key makes every attack on A5/1 cheaper.

The Three Registers

A5/1 uses three linear feedback shift registers, called R1, R2, and R3. They have 19, 22, and 23 bits. Each one shifts left, and the new bit that enters at the bottom is the XOR of a few of its bits, called taps.

Register	Length	Feedback taps (bit numbers)	Clocking bit
R1	19	13, 16, 17, 18	8
R2	22	20, 21	10
R3	23	7, 20, 21, 22	10

Bit 0 is the lowest bit. The keystream bit is the XOR of the top bit of each register, which is bit 18 of R1, bit 21 of R2, and bit 22 of R3.

T = feedback tap, C = clocking bit, O = output bit (the top bit), N = new bit enters at bit 0

bit   22 21 20 19 18 17 16 15 14 13 12 11 10 9  8  7  6  5  4  3  2  1  0
R1                TO T  T  .  .  T  .  .  .  .  C  .  .  .  .  .  .  .  N
R2       TO T  .  .  .  .  .  .  .  .  .  C  .  .  .  .  .  .  .  .  .  N
R3    TO T  T  .  .  .  .  .  .  .  .  .  C  .  .  T  .  .  .  .  .  .  N

Each register shifts left, and the XOR of its tap bits becomes the new bit 0. A bit with two marks has both roles. In every register the output bit is also a feedback tap.

Interactive Visualizer

The visualizer above runs this exact algorithm. Enter a 64-bit key, a 22-bit frame number, and up to 15 bytes of data. Choose the downlink or the uplink burst. Each row shows the three registers after one byte of keystream, so you can see them change at uneven rates.

Majority Clocking

Most LFSR ciphers move every register on every tick, but A5/1 does not. Each register has one clocking bit, at bit 8 of R1 and bit 10 of R2 and R3. Before every step, the cipher looks at the three clocking bits and finds the majority value.

A register moves only if its own clocking bit equals the majority. With three bits there are always at least two that agree, so at least two registers move on every step. Sometimes all three do.

clocking bits   majority   registers that move
0 0 0           0          R1, R2, R3
0 0 1           0          R1, R2
0 1 0           0          R1, R3
1 0 0           0          R2, R3
...the same pattern holds for a majority of 1: the registers whose bit is 1 move

Over a long run, each register moves three quarters of the time. In 10,000 steps from the example below, R1, R2, and R3 moved 74.9%, 74.5%, 75.7% of the time, in that order. The irregular movement makes the keystream far harder to analyze than a plain combination of three LFSRs.

Key and Frame Setup

A5/1 encrypts one burst of radio data at a time. A burst carries 114 bits. To make every burst different, the cipher mixes in a 22-bit frame number along with the 64-bit session key. Setup has three phases:

1. Load the key. For each of the 64 key bits, clock all three registers once and then XOR the key bit into the lowest bit of each register. Key bits are taken from the first byte first, and from the lowest bit of each byte first. During this phase the majority rule is switched off.
2. Load the frame number. Do the same with the 22 bits of the frame number, lowest bit first.
3. Mix. Clock the registers 100 times with the majority rule switched on. The output is thrown away. This spreads the key and frame bits through all 64 bits of state.

Generating Keystream

After setup, every clock with the majority rule produces one keystream bit. The first 114 bits are used for the downlink, from the network to the phone. The next 114 bits are used for the uplink. Each burst is packed into 15 bytes. Bit 0 of the burst is the top bit of byte 0, bit 7 is its lowest bit, and so on. Bits 114 to 119, the last six bits of byte 14, are zero.

You encrypt a burst by XORing it with its keystream. Decryption is the same XOR. Since the cipher depends on the frame number, every frame in a call uses a different keystream under the same key.

Byte Order and Frame Numbers

Two details differ between implementations, and they trip up many people who compare test vectors. The first is the key byte order. The reference code reads the key as an array, with the first byte first. The libosmocore project loads the same key from the last byte to the first. A key written as 0123456789abcdef for libosmocore is efcdab8967452301 for this guide.

The second is the frame number. The cipher takes a 22-bit value called COUNT. GSM computes it from the TDMA frame number FN in three parts: T1 = FN div (26 * 51), T2 = FN mod 26, and T3 = FN mod 51. The COUNT is (T1 << 11) | (T3 << 5) | T2. For FN = 123456, the parts are T1 = 93, T2 = 8, and T3 = 36, which gives COUNT 0x02ec88. This guide and its visualizer take COUNT directly.

A Worked Example

This is the reference test vector. The key is 1223456789abcdef and the frame number is 0x000134.

Setup. All registers start at zero. After the 64 key bits, the registers are R1 = 4030d, R2 = 1fa05c, and R3 = 3668e1. After the 22 frame bits they are R1 = 064a2, R2 = 2bc0e5, and R3 = 72df8d. The 100 mixing clocks leave them at R1 = 1da4b, R2 = 2cb2f9, and R3 = 08be5f. The values are shown in hex and are already limited to the register widths of 19, 22, and 23 bits, so R1 takes five hex digits and R2 and R3 take six.

The first output clock. The clocking bits are 0, 0, 1, so the majority is 0. The registers that move are R1, R2. They become R1 = 3b497 and R2 = 1965f3, while R3 stays at 08be5f. The top bits are now 0, 0, 0, and their XOR is the first keystream bit, 0.

The first eight clocks. Here is how the registers move over the first eight keystream clocks. Reading the output bits from the top gives 01010011.

clock  clocking bits  majority  registers that move  output bit
1      0 0 1          0         R1, R2               0
2      0 1 1          1         R2, R3               1
3      0 0 1          0         R1, R2               0
4      1 1 1          1         R1, R2, R3           1
5      0 1 0          0         R1, R3               0
6      0 1 0          0         R1, R3               0
7      1 1 1          1         R1, R2, R3           1
8      0 1 0          0         R1, R3               1

The keystream. The first byte of the downlink burst is 01010011, which is 53. The two bursts are:

downlink: 534eaa582fe8151ab6e1855a728c00
uplink:   24fd35a35d5fb6526d32f906df1ac0

These match the values in the reference code. Both have the last six bits of the 15th byte set to zero.

Encryption. The message Hello, GSM! is 48656c6c6f2c2047534d21 in hex. XORed with the downlink burst it gives 1b2bc63440c4355de5aca4, and XORed with the uplink burst it gives 6c9859cf327396153e7fd8.

Python Implementation

This is a complete A5/1: the three registers, majority clocking, key and frame setup, bursts, and encryption. It also includes the function that turns a GSM frame number into COUNT.

# a5_1.py
#
# A5/1, the stream cipher that protected GSM voice calls.
# Three linear feedback shift registers of 19, 22 and 23 bits (64 bits in all)
# are clocked irregularly: each register moves only when its clocking bit
# agrees with the majority of the three clocking bits. A 64-bit session key
# and a 22-bit frame number go in, and every frame yields two 114-bit bursts
# of keystream, one for each direction.

# register length, feedback taps, clocking bit, and output bit (the top bit)
R1_LEN, R1_TAPS, R1_CLOCK = 19, (13, 16, 17, 18), 8
R2_LEN, R2_TAPS, R2_CLOCK = 22, (20, 21), 10
R3_LEN, R3_TAPS, R3_CLOCK = 23, (7, 20, 21, 22), 10
BURST = 114


def parity(x):
    return bin(x).count("1") & 1


def shift(reg, length, taps):
    """Clock one register: shift left, feed the XOR of the tap bits into bit 0."""
    feedback = 0
    for t in taps:
        feedback ^= (reg >> t) & 1
    return ((reg << 1) | feedback) & ((1 << length) - 1)


class A51:
    def __init__(self):
        self.r1 = self.r2 = self.r3 = 0

    def clock_all(self):
        self.r1 = shift(self.r1, R1_LEN, R1_TAPS)
        self.r2 = shift(self.r2, R2_LEN, R2_TAPS)
        self.r3 = shift(self.r3, R3_LEN, R3_TAPS)

    def clock(self):
        """One irregular clock: only the registers that agree with the majority move."""
        b1 = (self.r1 >> R1_CLOCK) & 1
        b2 = (self.r2 >> R2_CLOCK) & 1
        b3 = (self.r3 >> R3_CLOCK) & 1
        majority = 1 if b1 + b2 + b3 >= 2 else 0
        if b1 == majority:
            self.r1 = shift(self.r1, R1_LEN, R1_TAPS)
        if b2 == majority:
            self.r2 = shift(self.r2, R2_LEN, R2_TAPS)
        if b3 == majority:
            self.r3 = shift(self.r3, R3_LEN, R3_TAPS)

    def bit(self):
        return ((self.r1 >> (R1_LEN - 1)) ^ (self.r2 >> (R2_LEN - 1)) ^ (self.r3 >> (R3_LEN - 1))) & 1

    def mix_in(self, bit):
        self.r1 ^= bit
        self.r2 ^= bit
        self.r3 ^= bit

    def snapshot(self):
        return self.r1, self.r2, self.r3


def setup(key, frame):
    """Load a 64-bit key (8 bytes) and a 22-bit frame number, then mix for 100 clocks."""
    if len(key) != 8:
        raise ValueError("A5/1 keys are 8 bytes")
    if not 0 <= frame < (1 << 22):
        raise ValueError("A5/1 frame numbers have 22 bits")
    state = A51()
    # bit i of the key is bit (i mod 8) of byte (i div 8), so each byte goes in lowest bit first (as in the reference code)
    for i in range(64):
        state.clock_all()
        state.mix_in((key[i // 8] >> (i % 8)) & 1)
    for i in range(22):
        state.clock_all()
        state.mix_in((frame >> i) & 1)
    for _ in range(100):
        state.clock()
    return state


def burst(state):
    """Produce one 114-bit burst, packed into 15 bytes with the first bit as the top bit."""
    out = bytearray(15)
    for i in range(BURST):
        state.clock()
        out[i // 8] |= state.bit() << (7 - i % 8)
    return bytes(out)


def keystream(key, frame):
    """Return (downlink burst, uplink burst) for one frame, as the GSM specification lays them out."""
    state = setup(key, frame)
    return burst(state), burst(state)


def crypt(key, frame, data, uplink=False):
    """XOR up to 15 bytes of data with one burst. Decryption is the same operation."""
    if len(data) > 15:
        raise ValueError("a burst carries at most 114 bits, so at most 15 bytes here")
    stream = keystream(key, frame)[1 if uplink else 0]
    return bytes(a ^ b for a, b in zip(data, stream))


def gsm_count(frame_number):
    """The 22-bit COUNT that GSM derives from the TDMA frame number."""
    t1 = frame_number // (26 * 51)
    t2 = frame_number % 26
    t3 = frame_number % 51
    return (t1 << 11) | (t3 << 5) | t2


if __name__ == "__main__":
    key = bytes.fromhex("1223456789abcdef")
    frame = 0x134
    downlink, uplink = keystream(key, frame)
    message = b"Hello, GSM!"
    ciphertext = crypt(key, frame, message)
    print("Key:           " + key.hex())
    print("Frame number:  0x%06x" % frame)
    print("Downlink:      " + downlink.hex())
    print("Uplink:        " + uplink.hex())
    print("Plaintext:     " + message.hex())
    print("Ciphertext:    " + ciphertext.hex())
    print("Recovered:     " + crypt(key, frame, ciphertext).decode())

Running it produces this output:

Key:           1223456789abcdef
Frame number:  0x000134
Downlink:      534eaa582fe8151ab6e1855a728c00
Uplink:        24fd35a35d5fb6526d32f906df1ac0
Plaintext:     48656c6c6f2c2047534d21
Ciphertext:    1b2bc63440c4355de5aca4
Recovered:     Hello, GSM!

I checked this code against two independent sources before writing it up. It reproduces both bursts of the Briceno, Goldberg, and Wagner reference vector. It also reproduces the downlink and uplink bursts in the libosmocore regression test, which uses a different key and frame number and the byte order and COUNT conversion described above. As a further check, it agrees with a literal port of the reference C code on 300 random keys and frame numbers.

Limitations

This is a faithful teaching version of the cipher, not a production one:

• One burst only. The code produces one frame at a time and has no notion of a call.
• Not constant-time. The clocking decisions depend on secret bits, and Python integers are not constant-time either.
• Real phones differ in the details. Hardware and network code derive the key and COUNT in ways that vary between systems, as the byte order section above shows.
• A5/1 is weak. Treat this code as a study aid. Do not use it to protect anything.

Security Status

A5/1 is broken in practice. Ross Anderson described a guessing attack in 1994, and Jovan Golic published an attack in 1997 with about 2⁴⁰ steps. In 2000, Alex Biryukov, Adi Shamir, and David Wagner showed a time-memory tradeoff. It finds the key in about a second from two minutes of known keystream. The attack needs a large precomputation of about 2⁴⁸ steps and roughly 300 GB of storage. Biham and Dunkelman improved the numbers in the same year.

Later work made the attacks practical for outsiders. Ekdahl and Johansson attacked the initialization in minutes. Barkan, Biham, and Keller showed ciphertext-only attacks that need only a short stretch of encrypted conversation. In 2009, Karsten Nohl and Sascha Krißler built a large set of rainbow tables, about 1.7 TB, and distributed it over BitTorrent.

A5/3, which is based on the KASUMI block cipher, is the stronger replacement, and the libosmocore code also supports an A5/4 variant with a 128-bit key. A5/1 remains in use on some networks. Networks that still allow the weaker ciphers invite downgrade attacks.

FAQ

What is A5/1 used for?

It encrypts the radio link of GSM voice calls between a phone and the base station. It does not protect a call end to end. Once the traffic reaches the network, A5/1 no longer applies.

Why is A5/1 irregularly clocked?

Moving all three registers on every step would make the keystream a simple, regular combination of LFSR sequences, which is easy to analyze. Majority clocking adds nonlinearity at almost no cost in hardware.

Is A5/1 still secure?

It is no longer secure. Practical attacks have existed for years, including attacks that use precomputed tables. Modern networks use A5/3 or newer ciphers, and an eavesdropper can often force older networks to fall back to A5/1.

What is the difference between A5/1 and A5/2?

A5/2 is a deliberately weakened version that was meant for export. It adds a fourth register that controls the clocking, and it can be broken almost instantly. A5/1 is stronger but has still fallen to practical attacks.

Why does the frame number matter?

Reusing a keystream would let an attacker XOR two ciphertexts and cancel it. The frame number changes for every burst, so the keystream is different each time, even under one session key.

References

1. Briceno, M., Goldberg, I., and Wagner, D. “A pedagogical implementation of A5/1.” Reference source code, 1999. Available at: https://git.gnumonks.org/cgit/airprobe/plain/A5.1/C/A5.1.c

2. Osmocom. “libosmocore: A5 implementation and regression test.” Available at: https://cgit.osmocom.org/libosmocore/tree/src/gsm/a5.c

3. Biryukov, A., Shamir, A., and Wagner, D. “Real Time Cryptanalysis of A5/1 on a PC.” Fast Software Encryption (FSE) 2000.

4. Barkan, E., Biham, E., and Keller, N. “Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication.” CRYPTO 2003.

5. Wikipedia. “A5/1.” Available at: https://en.wikipedia.org/wiki/A5/1