An implementation of the E0 stream cipher, the encryption algorithm used in the Bluetooth protocol, written in Magma. This project was developed as part of a cryptography course in the MSc Mathematics program and implements the full keystream generation mechanism of E0, including its four LFSRs and non-linear combining machine.
E0 is a stream cipher — rather than encrypting data in fixed-size blocks, it generates a pseudorandom keystream that is XORed with the plaintext bit by bit. It was designed for the Bluetooth standard and is used to encrypt communication between Bluetooth devices.
The cipher combines four Linear Feedback Shift Registers (LFSRs) of different lengths with a non-linear finite state machine that introduces the unpredictability necessary for cryptographic security.
LFSR₁ (25 bits) ──┐
LFSR₂ (31 bits) ──┤
├──► Non-Linear FSM (4 bits) ──► keystream bit kₜ
LFSR₃ (33 bits) ──┤
LFSR₄ (39 bits) ──┘
Total internal state: 25 + 31 + 33 + 39 + 4 = 132 bits
Each LFSR generates a linear recurring sequence over GF(2). The feedback taps are chosen to maximize the period of the output sequence:
| Register | Length | Feedback taps (from MSB) |
|---|---|---|
| LFSR₁ | 25 bits | 0, 8, 12, 20 |
| LFSR₂ | 31 bits | 0, 12, 16, 24 |
| LFSR₃ | 33 bits | 0, 4, 24, 28 |
| LFSR₄ | 39 bits | 0, 4, 28, 36 |
The four LFSR output bits are combined through a non-linear finite state machine with a 4-bit internal state (c₀, c₁, c₂, c₃). At each clock cycle, the machine:
- Computes a sum
z = s₁ + s₂ + s₃ + s₄ + 2·c₁ + c₀over the integers - Extracts the carry bits
z₁(bit 1) andz₀(bit 0) ofz - Updates its internal state:
c₃ ← c₁c₂ ← c₀c₁ ← z₁ + c₄ + c₁c₀ ← z₀ + c₄ + c₃ + c₂
- Outputs keystream bit:
kₜ = s₁ + s₂ + s₃ + s₄ + c₀(mod 2)
This non-linear component is what makes E0 more than a simple combination of LFSRs.
The initial state is provided as a 132-bit hexadecimal string (33 hex characters): the first 128 bits initialize the four LFSRs, the last 4 bits initialize the non-linear machine.
load "magma/e0.mag";
// 132-bit initial state as hex string (33 characters)
S := "0F1E2D3C4B5A69788796A5B4C3D2E1F0A";
// Generate 16 keystream bits
Ks := E0_Keystream(S, 16);
print Ks;
An LFSR of length n over GF(2) generates a sequence defined by a linear recurrence:
sₜ = c₁·sₜ₋₁ + c₂·sₜ₋₂ + ... + cₙ·sₜ₋ₙ (mod 2)
where c₁, ..., cₙ ∈ GF(2) are the feedback coefficients (taps). When the feedback polynomial is primitive over GF(2), the LFSR achieves its maximum period of 2ⁿ - 1. The tap positions in E0 are chosen precisely for this property.
LFSRs alone are cryptographically weak: given 2n consecutive output bits of an LFSR of length n, the entire sequence can be reconstructed using the Berlekamp-Massey algorithm. The non-linear FSM in E0 is designed to prevent this attack by making the keystream non-linear with respect to the initial state.
E0 is considered cryptographically weak by modern standards and has been deprecated for new Bluetooth implementations. Known attacks include:
- Correlation attacks — the non-linear FSM does not fully decorrelate the keystream from the individual LFSR outputs
- Algebraic attacks — the relatively simple non-linear component can be exploited using systems of polynomial equations over GF(2)
- Fluhrer attack (2004) — recovers the 132-bit initial state from approximately 2²³·⁸ keystream bits with practical complexity
Despite its weaknesses, E0 is an excellent case study for understanding:
- Why combining linear components non-linearly is not always sufficient
- The design principles that led to stronger stream ciphers like Trivium and Grain
- How real-world cryptographic standards can be compromised over time
The file magma/test.txt verifies the implementation against three known-good keystreams:
| Initial State (hex) | Length | First 10 output bits |
|---|---|---|
25AC1EA08E1EC131E0A1780F7A2A42BBD |
10 | 0100011001 |
E22F92FFF8C245C49D10359A02F1E555B |
10 | 1000110011 |
A253E3DC99C6E648171901CCEDE88BC5F |
100 | 0010111111110101101101000101001110011001100101101010011011010101011011110010101110110101010111001011110101... |
Run the tests with:
load "magma/e0.mag";
load "magma/test.txt";
// Expected output:
// correct!
// correct!
// correct!
e0-stream-cipher/
├── README.md
└── magma/
└── e0.mag # Full E0 keystream generator
- Magma Computational Algebra System (v2.20 or later recommended)
- A free online Magma calculator is available at magma.maths.usyd.edu.au/calc
- toy-block-cipher — SPN block cipher implementation (AES-like structure)