In this paper we propose two new algorithms for multi-pass fast correlation attacks on stream ciphers. The first algorithm aims at fast symbol-wise decoding in the circumstances that the noise is not very high and we have little resource for pre-computation. The second algorithm deals with the practical decoding problem in the high noise and limited keystream cases. The new algorithms are applicable to arbitrary form LFSR and compare favorably to the previously known algorithms in the scenarios under consideration. As applications, we demonstrate new key recovery attacks on one-level Bluetooth E0 and LILI-128, respectively. Given 2(37)-bit keystream and 2(28)-byte memory, our attack against one-level E0 needs 2(35.1) operations. Given 2(24)-bit keystream and 2(24.5)-byte memory, our attack on LILI-128 has time complexity 270.6 operations.
English Abstract:
In this paper we propose two new algorithms for multi-pass fast correlation attacks on stream ciphers. The first algorithm aims at fast symbol-wise decoding in the circumstances that the noise is not very high and we have little resource for pre-computation. The second algorithm deals with the practical decoding problem in the high noise and limited keystream cases. The new algorithms are applicable to arbitrary form LFSR and compare favorably to the previously known algorithms in the scenarios under consideration. As applications, we demonstrate new key recovery attacks on one-level Bluetooth E0 and LILI-128, respectively. Given 2(37)-bit keystream and 2(28)-byte memory, our attack against one-level E0 needs 2(35.1) operations. Given 2(24)-bit keystream and 2(24.5)-byte memory, our attack on LILI-128 has time complexity 270.6 operations.
