The E0 Stream Cipher

The E0 Stream Cipher

Introduction

E0 is the encryption cipher of classic Bluetooth, the BR/EDR mode used for headsets, speakers, and many other accessories. It is a stream cipher. It produces a keystream that is XORed with the data of each packet, so encryption and decryption are the same operation.

The design is a classic one. Four linear feedback shift registers run side by side, and a small state machine called a summation combiner mixes their outputs and adds carries from one step to the next. The carries are what make the output nonlinear. Because the Bluetooth specification publishes full sample data, E0 is also a rare cipher that you can check clock by clock against an official trace.

Table of Contents

• History and Status
• The Four Registers
• The Summation Combiner
• Initialization
• The Session Key
• Byte Order
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History and Status

E0 is defined in the Bluetooth Core Specification, in the security part of the BR/EDR controller volume. It takes a 128-bit encryption key, the 48-bit Bluetooth address of the master device, and 26 bits of the master’s clock. A new keystream is set up for every packet.

Newer versions of Bluetooth can use AES in CCM mode for BR/EDR links instead, and the specification’s sample data includes AES-CCM examples as well. E0 remains in the specification for compatibility. It is classified as a broken stream cipher, and the attacks are covered in the Security Status section.

The Four Registers

E0 has four LFSRs. Each one shifts left by one bit per clock, and the new bit that enters is the XOR of a few taps.

Register	Length	Specification polynomial	Taps in this guide (newest bit is bit 0)	Output bit
LFSR1	25	t^25 + t^20 + t^12 + t^8 + 1	7, 11, 19, 24	23
LFSR2	31	t^31 + t^24 + t^16 + t^12 + 1	11, 15, 23, 30	23
LFSR3	33	t^33 + t^28 + t^24 + t^4 + 1	3, 23, 27, 32	31
LFSR4	39	t^39 + t^36 + t^28 + t^4 + 1	3, 27, 35, 38	31

All four polynomials are primitive, and each has only five terms. The total length of the registers is 128 bits. The taps in the table are the specification’s polynomials read in the other direction. For example, LFSR1 has exponents 20, 12, and 8 in the specification, and 25 - 20, 25 - 12, and 25 - 8 give 5, 13, and 17, which match the tap bits 24 - 5 = 19, 24 - 13 = 11, and 24 - 17 = 7. I derived the tap bits from the specification’s own sample data, and they agree with the polynomials on all four registers.

Each register contributes one bit to the combiner, taken from a fixed position. The registers are written as hex values in the sample data, with the newest bit as the lowest bit. The specification counts positions from 1 starting at the left of its figures, and it takes the output bits from positions 24, 24, 32, and 32. Position p is bit p - 1 in this guide, so those are bits 23, 23, 31, and 31, as in the table.

Interactive Visualizer

The visualizer above runs this exact algorithm. Enter a 128-bit session key, the address and clock bytes, and a message in hex. The log shows the four registers and the blend register after the main setup stages and after each byte of keystream. Click Decrypt on the output to get the message back.

The Summation Combiner

At each clock the four output bits x1 to x4 are added as ordinary integers, so the sum y can be 0 to 4. This is ordinary integer addition, not an XOR. The combiner also holds two 2-bit values, c(t) and c(t-1), called the blend registers. The keystream bit and the next blend value come from these equations:

z(t)    = x1 ^ x2 ^ x3 ^ x4 ^ c(t)[0]
s(t+1)  = floor((y + c(t)) / 2)
c(t+1)  = s(t+1) ^ T1[c(t)] ^ T2[c(t-1)]

Here c(t)[0] is the low bit of c(t). The sum y + c(t) can reach 7, so s(t+1) is a two-bit number from 0 to 3. The two maps T1 and T2 are linear bijections on two-bit values:

x	T1[x]	T2[x]
00	00	00
01	01	11
10	10	01
11	11	10

T1 leaves the value alone, and T2 is (x1, x0) -> (x0, x1 ^ x0). The integer addition in y is the nonlinear step. It carries into the blend registers, so the keystream is not a simple XOR of the four register outputs.

Initialization

Before each packet, E0 runs a setup that mixes the key, the address, and the clock into the registers. It takes 240 clocks, and it follows these steps:

1. Shift in 208 input bits. The inputs are the 128 bits of K_session, the 48 bits of the address BD_ADDR, the 26 bits of the clock CL, and a six-bit constant, 111001. Each register gets its own share: 49 bits for LFSR1, 55 for LFSR2, 49 for LFSR3, and 55 for LFSR4. Within every byte the lowest bit goes in first.
2. Close the switches. During the first clocks, each register takes only the input bit and ignores its feedback. When the first input bit has travelled the whole register, its switch closes, and from then on the new bit is the feedback XOR the next input bit. Counting clocks from 1, the feedback is active from clock 26 on for LFSR1, from clock 32 on for LFSR2, from clock 34 on for LFSR3, and from clock 40 on for LFSR4.
3. Start the combiner. At clock 39 the blend registers are reset to zero. From clock 40 on, the combiner produces output bits. When the last input bit has gone in, the registers keep shifting with input 0.
4. Mix. Run until 200 output bits exist, which is clock 239.
5. Parallel load. At clock 240, the last 128 of those 200 bits are loaded into the four registers at once, and the blend registers keep their values. This is the first clock of real keystream. The 128 bits are grouped into the 16 octets Z[0] to Z[15], with the first bit generated as the lowest bit of Z[0]. LFSR1 gets Z[0], Z[4], Z[8], and the lowest bit of Z[12]. LFSR2 gets Z[1], Z[5], Z[9], and the upper seven bits of Z[12]. LFSR3 gets Z[2], Z[6], Z[10], Z[13], and the lowest bit of Z[15]. LFSR4 gets Z[3], Z[7], Z[11], Z[14], and the upper seven bits of Z[15]. In every case the first octet listed becomes the lowest byte of the register.

The specification gives the input arrangement in a figure. I recovered it from the sample data and checked it against all four sets. This table lists the bits in the order each register receives them, first bit first. Every byte of K_session and BD_ADDR goes in lowest bit first.

Register	Input bits, in order	Count
LFSR1	CL[24], bytes K[0], K[4], K[8], K[12], bits CL[8] to CL[15], byte BD_ADDR[2]	49
LFSR2	constants 1, 0, 0, bits CL[0] to CL[3], bytes K[1], K[5], K[9], K[13], bytes BD_ADDR[0], BD_ADDR[3]	55
LFSR3	CL[25], bytes K[2], K[6], K[10], K[14], bits CL[16] to CL[23], byte BD_ADDR[4]	49
LFSR4	constants 1, 1, 1, bits CL[4] to CL[7], bytes K[3], K[7], K[11], K[15], bytes BD_ADDR[1], BD_ADDR[5]	55

The six constant bits are the 111001 of the specification, split between LFSR2 and LFSR4. The code below builds the same lists in load_sequences.

The Session Key

The encryption key that E0 receives is not used directly. Its effective length can be anything from 1 to 16 bytes, and E0 reduces the key to that length with polynomial arithmetic over GF(2):

K_session(x) = g2(x) * ( K_enc(x) mod g1(x) )

For effective length L bytes, g1 has degree 8 * L, and g2 has degree at most 128 - 8 * L. Reducing modulo g1 throws away all but 8 * L bits of entropy. Multiplying by g2 encodes the result as a 128-bit block code, which spreads the possible starting states more evenly. For L = 16, g1 is just x^128, and K_session equals K_enc.

Take L = 1 as an example. The polynomial g1 is 0x11d, and g2 is 0xe275a0abd218d4cf928b9bbf6cb08f. For K_enc = a2b230a493f281bb61a85b82a9d4a30e, the remainder K_enc mod g1 is 0x9f, and K_session is 7aa16f3959836ba322049a7b87f1d8a5. A one-byte key leaves at most 256 possible session keys, no matter how long the original key was. For L = 16 the remainder and the session key are the key itself: 35ec8fc3d50ccd325f2fd907bde206de.

Byte Order

The specification numbers octets from the low end: octet i of a value holds bits 8i to 8i+7. K_session[0] is the lowest byte, and the lowest bit of each byte enters a register first. This guide follows the same rule, and it packs keystream bits into bytes the same way, so the first bit generated is the lowest bit of byte 0. The Bluetooth sample data lists values by octet, and the visualizer takes its inputs in that order. The address is BD_ADDR[0] to BD_ADDR[5], and the clock is the four bytes CL[0] to CL[3].

The specification’s clock CLK has one extra bit at the bottom, and CL is CLK[26:1]. In sample set 4 the clock CLK = 0x40034be corresponds to CL = 0x2001a5f, which is the bytes 5f1a0002.

A Worked Example

This is the fourth set of sample data from the Bluetooth specification. The session key is K_session = 2187f04aba9031d0780d4c53e0153a63, the address is 2c7f94560f1b, and the clock bytes are 5f1a0002.

Inputs. The registers receive 49, 55, 49, and 55 input bits. The first twelve bits of each are:

LFSR1: 010000100010
LFSR2: 100111111100
LFSR3: 100001111100
LFSR4: 111101001010

Setup. After clock 39 the four registers hold 147b3e1 6109b044 1e30c970c 7a520bcac6, after clock 139 they hold 09b37d4 4d2cfed2 03bed35bb 11b19bbe56, and after clock 239 they hold 1b3799e 31fea756 1d874e6a8 22dd6dd940. The blend registers that the parallel load keeps are c(239) = 11, c(238) = 00. All of these values appear in the specification’s table.

One combiner step. In the specification’s table, row 42 has the register output bits 0, 0, 0, 1, so y = 1. The blend registers are c(t) = 00 and c(t-1) = 01. The output bit is z = 0 ^ 0 ^ 0 ^ 1 ^ 0 = 1. For the next blend value, s = floor((1 + 0) / 2) = 0, and T2[01] = 11, so c(t+1) = 11. The table lists the same numbers.

Parallel load. The 200 output bits give these 16 octets in the last 128 bits, Z[0] to Z[15]: 3f b1 67 d2 2f a6 1f b9 e6 84 43 07 d8 1e e7 c3. They are loaded into the registers as 0e62f3f 6c84a6b1 11e431f67 61e707b9d2, which again matches the specification.

Keystream. The first 15 keystream bytes are:

94996fe0bf0774253339d8a1c0a529

The first eight keystream bits are 00101001, which pack into the byte 94. The first 20 key symbols in the specification’s table are 00101001100110011111. The message Bluetooth E0 demo is 426c7565746f6f74682045302064656d6f in hex, and it encrypts to:

d6f51a85cb681b515b199d91e0c14cf95a

Python Implementation

This is a complete E0: the four registers, the combiner, the setup with the parallel load, keystream generation, and the derivation of K_session from a key of any effective length. The two tables of polynomials were copied from the specification by a script.

# e0.py
#
# E0, the stream cipher of Bluetooth BR/EDR encryption.
# Four linear feedback shift registers of 25, 31, 33 and 39 bits feed a small
# state machine with 16 states, called the summation combiner. The combiner's
# output bit is the keystream. Setup mixes a session key, the master's
# Bluetooth address, and 26 bits of its clock into the registers, runs the
# cipher for 200 clocks, and reloads the registers with the last 128 bits.
#
# Bytes follow the Bluetooth specification: octet i of a value holds bits
# 8i to 8i+7, and the lowest bit of an octet goes in first. Keystream bits are
# packed the same way, so the first bit generated is the lowest bit of byte 0.

LENGTHS = (25, 31, 33, 39)
# feedback taps of each register, counted from the newest bit (bit 0); the
# oldest bit is bit L-1 and is always a tap
TAPS = ((7, 11, 19, 24), (11, 15, 23, 30), (3, 23, 27, 32), (3, 27, 35, 38))
# the bit of each register that feeds the combiner
OUT_BIT = (23, 23, 31, 31)
INPUT_BITS = (49, 55, 49, 55)

# Polynomials g1 and g2 for effective key lengths of 1 to 16 bytes
# (Bluetooth Core Specification, Vol 2 Part H, Table 4.4)
G1 = {1: 0x11d, 2: 0x1003f, 3: 0x10000db, 4: 0x1000000af, 5: 0x10000000039, 6: 0x1000000000291, 7: 0x100000000000095, 8: 0x1000000000000001b, 9: 0x1000000000000000609, 10: 0x100000000000000000215, 11: 0x1000000000000000000013b, 12: 0x10000000000000000000000dd, 13: 0x10000000000000000000000049d, 14: 0x1000000000000000000000000014f, 15: 0x10000000000000000000000000000e7, 16: 0x100000000000000000000000000000000}
G2 = {1: 0xe275a0abd218d4cf928b9bbf6cb08f, 2: 0x1e3f63d7659b37f18c258cff6efef, 3: 0x1bef66c6c3ab1030a5a1919808b, 4: 0x16ab89969de17467fd3736ad9, 5: 0x163063291da50ec55715247, 6: 0x2c9352aa6cc054468311, 7: 0xb3f7fffce279f3a073, 8: 0xa1ab815bc7ec8025, 9: 0x2c98011d8b04d, 10: 0x58e24f9a4bb, 11: 0xca76024d7, 12: 0x1c9c26b9, 13: 0x26d9e3, 14: 0x4377, 15: 0x89, 16: 0x1}


def poly_mod(a, m):
    """Remainder of a divided by m, as polynomials over GF(2)."""
    dm = m.bit_length()
    while a.bit_length() >= dm:
        a ^= m << (a.bit_length() - dm)
    return a


def poly_mul(a, b):
    result = 0
    while b:
        if b & 1:
            result ^= a
        a <<= 1
        b >>= 1
    return result


def session_key(k_enc, length):
    """K_session = g2(x) * (K_enc(x) mod g1(x)); k_enc is a 128-bit integer, length is 1 to 16."""
    if not 1 <= length <= 16:
        raise ValueError("the effective key length is 1 to 16 bytes")
    return poly_mul(G2[length], poly_mod(k_enc, G1[length])) & ((1 << 128) - 1)


def bits_lsb_first(value, count):
    return [(value >> b) & 1 for b in range(count)]


def load_sequences(k_session, bd_addr, clk):
    """The 208 input bits, in the order each register receives them (first bit first)."""
    k = list(k_session)
    a = list(bd_addr)
    cl = [(clk >> b) & 1 for b in range(26)]
    seq1 = [cl[24]] + sum((bits_lsb_first(k[j], 8) for j in (0, 4, 8, 12)), []) + cl[8:16] + bits_lsb_first(a[2], 8)
    seq2 = [1, 0, 0] + cl[0:4] + sum((bits_lsb_first(k[j], 8) for j in (1, 5, 9, 13)), []) + bits_lsb_first(a[0], 8) + bits_lsb_first(a[3], 8)
    seq3 = [cl[25]] + sum((bits_lsb_first(k[j], 8) for j in (2, 6, 10, 14)), []) + cl[16:24] + bits_lsb_first(a[4], 8)
    seq4 = [1, 1, 1] + cl[4:8] + sum((bits_lsb_first(k[j], 8) for j in (3, 7, 11, 15)), []) + bits_lsb_first(a[1], 8) + bits_lsb_first(a[5], 8)
    return [seq1, seq2, seq3, seq4]


def t2(c):
    """The map T2 of the specification: (x1, x0) goes to (x0, x1 xor x0). T1 is the identity."""
    return ((c & 1) << 1) | (((c >> 1) & 1) ^ (c & 1))


class E0:
    def __init__(self):
        self.lfsr = [0, 0, 0, 0]
        self.c = 0          # c(t), two bits
        self.c_prev = 0     # c(t-1)
        self.t = 0

    def shift_in(self, i, inp, closed):
        """Clock register i once. Before its switch closes only the input enters."""
        reg = self.lfsr[i]
        if closed:
            f = 0
            for b in TAPS[i]:
                f ^= (reg >> b) & 1
            new = f ^ inp
        else:
            new = inp
        self.lfsr[i] = ((reg << 1) | new) & ((1 << LENGTHS[i]) - 1)

    def combine(self):
        """Read the registers, return the output bit, and update the blend registers."""
        x = [(self.lfsr[i] >> OUT_BIT[i]) & 1 for i in range(4)]
        z = x[0] ^ x[1] ^ x[2] ^ x[3] ^ (self.c & 1)
        s = (sum(x) + self.c) >> 1
        new_c = s ^ self.c ^ t2(self.c_prev)
        self.c_prev, self.c = self.c, new_c
        return z


def initialize(k_session, bd_addr, clk):
    """Run the 239 clocks of setup. Return the generator, the 200 output bits, and the blend registers to keep."""
    if len(k_session) != 16 or len(bd_addr) != 6:
        raise ValueError("K_session is 16 bytes and the address is 6 bytes")
    if not 0 <= clk < (1 << 26):
        raise ValueError("the clock value has 26 bits")
    seqs = load_sequences(k_session, bd_addr, clk)
    e = E0()
    z_bits = []
    held = (0, 0)
    for t in range(1, 240):
        for i in range(4):
            inp = seqs[i][t - 1] if t - 1 < INPUT_BITS[i] else 0
            e.shift_in(i, inp, t > LENGTHS[i])
        if t == 39:
            # the blend registers are reset when the last switch closes; this step prepares c(40)
            e.c = e.c_prev = 0
            e.combine()
        elif t >= 40:
            held = (e.c, e.c_prev)   # the blend registers the parallel load keeps are the ones used at t = 239
            z_bits.append(e.combine())
    return e, z_bits, held


def parallel_load(e, z_bits, held):
    """At t = 240 the last 128 of the 200 output bits are loaded into the four registers."""
    # the 128 bits are Z[0] .. Z[15], bit 0 of Z[0] being the first bit generated. LFSR1 takes octets 0, 4, 8 and
    # the lowest bit of octet 12, LFSR2 takes 1, 5, 9 and the top 7 bits of 12, LFSR3 takes 2, 6, 10, 13 and the
    # lowest bit of 15, LFSR4 takes 3, 7, 11, 14 and the top 7 bits of 15. The first octet listed is the lowest byte.
    last = z_bits[-128:]
    zb = [sum(last[8 * j + b] << b for b in range(8)) for j in range(16)]
    e.lfsr[0] = zb[0] | (zb[4] << 8) | (zb[8] << 16) | ((zb[12] & 1) << 24)
    e.lfsr[1] = zb[1] | (zb[5] << 8) | (zb[9] << 16) | ((zb[12] >> 1) << 24)
    e.lfsr[2] = zb[2] | (zb[6] << 8) | (zb[10] << 16) | (zb[13] << 24) | ((zb[15] & 1) << 32)
    e.lfsr[3] = zb[3] | (zb[7] << 8) | (zb[11] << 16) | (zb[14] << 24) | ((zb[15] >> 1) << 32)
    e.c, e.c_prev = held
    return zb


def keystream_bits(k_session, bd_addr, clk, count):
    e, z_bits, held = initialize(k_session, bd_addr, clk)
    parallel_load(e, z_bits, held)
    bits = []
    for _ in range(count):
        bits.append(e.combine())
        for i in range(4):
            e.shift_in(i, 0, True)
    return bits


def keystream(k_session, bd_addr, clk, length):
    bits = keystream_bits(k_session, bd_addr, clk, 8 * length)
    return bytes(sum(bits[8 * j + b] << b for b in range(8)) for j in range(length))


def crypt(k_session, bd_addr, clk, data):
    return bytes(a ^ b for a, b in zip(data, keystream(k_session, bd_addr, clk, len(data))))


if __name__ == "__main__":
    k_session = bytes.fromhex("2187f04aba9031d0780d4c53e0153a63")
    bd_addr = bytes.fromhex("2c7f94560f1b")
    cl = bytes.fromhex("5f1a0002")
    clk = int.from_bytes(cl, "little")
    message = b"Bluetooth E0 demo"
    ciphertext = crypt(k_session, bd_addr, clk, message)
    print("K_session:  " + k_session.hex())
    print("BD_ADDR:    " + bd_addr.hex())
    print("CL[0..3]:   " + cl.hex())
    print("Keystream:  " + keystream(k_session, bd_addr, clk, 16).hex())
    print("Plaintext:  " + message.hex())
    print("Ciphertext: " + ciphertext.hex())
    print("Recovered:  " + crypt(k_session, bd_addr, clk, ciphertext).decode())

Running it produces this output:

K_session:  2187f04aba9031d0780d4c53e0153a63
BD_ADDR:    2c7f94560f1b
CL[0..3]:   5f1a0002
Keystream:  94996fe0bf0774253339d8a1c0a52994
Plaintext:  426c7565746f6f74682045302064656d6f
Ciphertext: d6f51a85cb681b515b199d91e0c14cf95a
Recovered:  Bluetooth E0 demo

I checked this code against the Bluetooth specification’s own data before writing it up. For all four sets of sample data, it matches every one of the 365 rows of the trace. That is the register contents, the four output bits, the output bit, and the three blend register columns, for 1,460 rows in all. It reproduces the 16 octets Z[0] to Z[15] that are loaded at clock 240, and the 125 key symbols that follow. The K_session derivation matches the sample data for all 16 effective key lengths. As a further check, it reproduces the recorded key symbol sequences of a third-party Python implementation for sample sets 1 and 4.

Limitations

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

• Setup per packet. Real Bluetooth repeats the 240-clock setup for every packet. This code sets up once per message.
• Two directions. The specification re-initializes with updated inputs before the reverse direction starts. This guide does not model that.
• Not constant-time. Python is not suitable for real encryption, and the code is slow compared to hardware.
• E0 is broken. Never use it for new designs.

Security Status

E0 has been attacked many times. Hermelin and Nyberg showed in 1999 that it could be broken in about 2⁶⁴ operations given about 2⁶⁴ known output bits. Lu and Vaudenay used a statistical attack in 2004 that needs the first 24 bits of about 2³⁵ frames and about 2⁴⁰ operations. In 2005, Lu, Meier, and Vaudenay published a conditional correlation attack that needs the first 24 bits of about 2²³·⁸ frames and about 2³⁸ computations. Wikipedia calls it the fastest known attack and the only practical known-plaintext attack.

A different weakness lies in the protocol. In the KNOB attack of 2019, Antonioli, Tippenhauer, and Rasmussen showed that an attacker who is not holding any secret can make two devices agree on an encryption key with only one byte of entropy. All versions of Bluetooth BR/EDR must support effective key lengths from 1 to 16 bytes, and the negotiation is not protected. A one-byte key is easy to brute force, which is the reduction step described above.

FAQ

What is E0 used for?

It encrypts the payload of packets in classic Bluetooth BR/EDR connections. It does not protect Bluetooth Low Energy, which uses AES-CCM.

Why does E0 use a summation combiner?

Four LFSRs on their own would give a keystream that is easy to model, because the registers are linear. The combiner adds integers with carries, and it keeps two blend registers between steps. That adds the nonlinearity the cipher needs.

Is E0 secure?

It is not secure. There are practical known-plaintext attacks, and the protocol around it allows key entropy to be pushed down to one byte. Use the AES-based encryption in newer Bluetooth versions.

What does the effective key length do?

It reduces the number of bits of entropy in the session key. Setting it to one byte leaves only 256 possible session keys. The polynomial g2 spreads those few bits over 128 bits.

How do I check an E0 implementation?

Use the sample data in the Bluetooth Core Specification, Volume 2 Part G. It lists the registers and the blend registers at every clock for four sets of inputs, and it gives the session keys for all 16 effective key lengths.

References

1. Bluetooth SIG. “Bluetooth Core Specification, Volume 2, Part H: Security Specification.” Available at: https://www.bluetooth.com/wp-content/uploads/Files/Specification/HTML/Core-54/out/en/br-edr-controller/security-specification.html

2. Bluetooth SIG. “Bluetooth Core Specification, Volume 2, Part G: Sample Data.” Available at: https://www.bluetooth.com/wp-content/uploads/Files/Specification/HTML/Core-61/out/en/br-edr-controller/sample-data.html

3. Lu, Y., Meier, W., and Vaudenay, S. “The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption.” CRYPTO 2005.

4. Antonioli, D., Tippenhauer, N. O., and Rasmussen, K. B. “The KNOB is Broken: Exploiting Low Entropy in the Encryption Key Negotiation Of Bluetooth BR/EDR.” USENIX Security Symposium 2019.

5. Wikipedia. “E0 (cipher).” Available at: https://en.wikipedia.org/wiki/E0_(cipher)