Faster Correlation Attack on Bluetooth Keystream Generator E0

We study both distinguishing and key-recovery attacksagainst E0, the keystream generator used in Bluetooth by means of correlation. First, a powerful computation method of correlations is formulated by a recursive expression, which makes it easier to calculate correlations 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 analysis 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. It requires time O(n+L· 2L) and memory min (n,2L). This can speed up many attacks such as fast correlation attacks. We apply it to E0, and our best key-recovery attack works in 239 time given 239 consecutive bits after O(237) precomputation. This is the best known attack against E0 so far.