Stream Cipher: E0

Hi! for this week we need to choose a stream cipher to investigate and also put an example, so, I chose E0 which is the algorithm that is used to protect the confidentiality of communication protocol in wireless Bluetooth, developed by Bluetooth Special Interest Group (SIG) [1] including 1500 companies.

The pseudo-random generator consists with four LFSRs (Linear feedback shift register) combined by a function having 4 bits of internal memory which is updated by a nonlinear function. Bluetooth work on the principle of a protocol for master-slave type.

Vulnerability: E0 is vulnerable with the fast correlation attack that can recover the encrypthon key in 2^38 operations if we know the first 24 bits.

If we need to implement a security using E0 must have the following parameters.

• Key length: 128 bits, the key is always extended to a word of 128 bits by adding bits redundancy even when the actual number of bits is less key.
• Initialization 64 bits vector, corresponding to the logical address of the master (48 bits) and the data of the clock (22 bits).

Under the bluetooth protocol, data is transmitted in the form of frames more than 2745 bits, so, each frame is encrypted by modulo 2 bit by bit with the first output bit of the pseudo-random generatos, initialized with a secret key which is the same during the session and an initial value which is modified at each frame change.

Description

E0 diagram[6]

E0 uses a combination of four LFSRs[5], and having a 4 bits in memory, this is used at two different levels, it is applied once furing initialization to generate an initial state of 128 bits from the secret key and the first vector and the same mechanism is then used to produce the keystream from this initial state[4].

The four registers LFSRs are binary with this lengths L1 = 25, L2= 31, L3=33, L4 = 39, total = 128 bits.

If we denote xⁱ_t the output at time t with i-th LFSR, then we need to calculate the 3-bit integer (0 to 4) corresponding to the sum of the outputs of the four LFSRs.

We need a combiner function F, that is a 4-bit finite state machine, if we have c_t =(q_t , p_t , q_t-1, p_t-1) it's the registers of F and l(t) = x¹_t+ x²_t+ x³_t+ x⁴_t is integer addition.

The output of the combiner function is pt, so, p_t = F(x_t, c_t)
The state change by the following instruction:

where

S_t+1is the binary representation of the right number, 1 most significant bit and 0 least significant bit.

The output of the algorithm is:

So, we can say that the E0 algorithm made for each packet transmissions generates a new encryption that combine the four registers (complex RAND, device address, master clock, secret key), which has a 25, 31, 33, 39 bits, 128 in total, the secret key is used as an input to E0 to produce a bit stream pt that is added with modulo 2 to be encrypted.

Example
So, this is my example, I use for made the calculation, python in console mode.

We need 4 variables, with determinate bits:
RAND = 1101101000001010110100111  (25 bits)
Device Address = 1101111001010011010001010100011  (31 bits)
Master Clock =  111000001001110111101000111001001 (33 bits)
Secret Key =110010111000000010100110010100110001101 (39 bits)

I just use random numbers generates with the function getrandbits in python, then, we need to do LFRS, so this is one iteration, we need to select the position base on the polynomials and made the sum.
P1(x) = 1 + 0 + 0 + 1 + 1
P1(x) = 11

P2(x) = 1 + 0 + 0 + 0 + 1
P2(x) = 10

P3(x) = 1 + 0 + 0 + 1 + 1
P3(x) = 11

P4(x) =  1 + 1 + 1 + 0 + 1
P4(x) = 100

Then, we need to have  l_t
lt = 11 + 10 + 11 + 100
_lt = 1100

Then we need to calcule  F(x_t, c_t) if we have c_t =(q_t , p_t , q_t-1, p_t-1) as memory of previous iterations, base in [1] we have 2 states 2-bit that:

Suppose that we have this combination and a t = 35 seg:
q_t = 00
p_t = 01
q_t-1 = 11
p_t-1= 10

S_t+1= floor(pi(100011)+2*(00)+01/2)
S_t+1 = 11110

p_t = F(x_t, c_t)
p_t = 11110

Then we can calculate Z:
Z = (l(t) % 2) + Pt
Z = (1100 % 2) + 11110
Z = 11110

So, Z contains one bit stream encrypted, this change in the time and in the state.

Vulnerability
The generator by combining registers used in the algorithm e0 is vulnerable to several attacks, I can mention for example linear attack, algebraic and fast algebraic attacks and fast correlation attacks. Most of these attacks requires the knowledge of a large number of successive bits of the key, which is not possible in the practical context of the Bluetooth protocol since the initial state of the generator is changed every number of bits.

By cons, sophisticated correlation attacks, presented by Yi Lu, Wili Meier [2], take into the session the re-synchronization occurs after encrypting each frame, and also there are one most effective[3] that allows to recover the encryption key from the knowledge of the first 24 bits of 2223.8 frames in 238 operations, as a result, the algorithm used in Bluetooth e0 is clearly offers insufficient security.

Biography.
[1] Bluetooth special interest group link
[2] Cryptanalysis of Bluetooth Keystream Generator Two-Level E0, Yi Lu, link
[3] A Practical Arrak on Bluetooth Encryption, Vili Meier, link
[4] Criptografía Moderana, cifra de flujo, P. Caballero link
[5] Communication Systems Security, Appendix B.L. Chen, link
[6] Algebraic Attacks and Stream Ciphers, Mikko Kiviharju, link