Another attack on A5/1

Abstrakt:

A5/1 is a stream cipher used in the GSM standard. Several time-memory trade-off attacks against A5/1 have been proposed, most notably the attack by Biryukov, Shamir and Wagner, which can break A5/1 in seconds using huge precomputation time and memory. We present a completely different attack on A5/1, based on ideas from correlation attacks. Whereas time-memory trade-off attacks have a complexity which is exponential with the shift register length, the complexity of the proposed attack is almost independent of the shift register length. Our implementation of the suggested attack breaks A5/1 in a few minutes using 2-5 minutes of conversation.