We study both distinguishing and key-recovery attacks against E0, the keystream generator used in Bluetooth by means of cor- relation. First, a powerful computation method of correlations is formu- lated by a recursive expression, which makes it easier to calculate corre- lations of the finite state machine output sequences up to 26 bits for E0 and allows us to verify the two known correlations to be the largest for the first time. Second, we apply the concept of convolution to the analy- sis of the distinguisher based on all correlations, and propose an efficient distinguisher due to the linear dependency of the largest correlations. Last, we propose a novel maximum likelihood decoding algorithm based on fast Walsh transform to recover the closest codeword for any linear code of dimension L and length n .I t requires timeO(n + L · 2 L )a nd memory min(n, 2 L ). This can speed up many attacks such as fast corre- lation attacks. We apply it to E0, and our best key-recovery attack works in 2 39 time given 2 39 consecutive bits after O(2 37 ) precomputation. This is the best known attack against E0 so far.
['Yi Lu', 'Serge Vaudenay']
Faster correlation attack on Bluetooth keystream generator E0