A Real-World Attack Breaking A5/1 within Hours
Timo Gendrullis, Martin Novotny, Andy Rupp
Workshop on Cryptographic Hardware and Embedded Systems -- CHES 2008. Washington DC, USA, August 10-13, 2008.
In this paper we present a real-world hardware-assisted attack on the well-known A5/1 stream cipher which is (still) used to secure GSM communication in most countries all over the world. During the last ten years A5/1 has been intensively analyzed [1,2,3,4,5,6,7]. However, most of the proposed attacks are just of theoretical interest since they lack from practicability — due to strong preconditions, high computational demands and/or huge storage requirements — or have never been fully implemented. In contrast to these attacks, our attack which is based on the work by Keller and Seitz  is running on an existing special-purpose hardware device, called COPACOBANA . With the knowledge of only 64 bits of keystream the machine is able to reveal the corresponding internal 64-bit state of the cipher in about 6 hours on average. We provide a detailed description of our attack architecture as well as implementation results.[pdf]