A5/1 is the strong version of the encryption algorithm used by about 130 million GSM customers in Europe to protect the over-the-air privacy of their cellular voice and data communication. The best published attacks against it require between 2⁴⁰ and 2⁴⁵ steps. This level of security makes it vulnerable to hardware-based attacks by large organizations, but not to software-based attacks on multiple targets by hackers.

In this paper we describe new attacks on A5/1, which are based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets. After a 2⁴⁸ parallelizable data preparation stage (which has to be carried out only once), the actual attacks can be carried out in real time on a single PC.

The first attack requires the output of the A5/1 algorithm during the first two minutes of the conversation, and computes the key in about one second. The second attack requires the output of the A5/1 algorithm during about two seconds of the conversation, and computes the key in several minutes. The two attacks are related, but use different types of time-memory tradeoffs. The attacks were verified with actual implementations, except for the preprocessing stage which was extensively sampled rather than completely executed.

REMARK: We based our attack on the version of the algorithm which was derived by reverse engineering an actual GSM telephone and published at http://www.scard.org. We would like to thank the GSM organization for graciously confirming to us the correctness of this unofficial description. In addition, we would like to stress that this paper considers the narrow issue of the cryptographic strength of A5/1, and not the broader issue of the practical security of fielded GSM systems, about which we make no claims.

Authors and Affiliations

1. Computer Science department, The Weizmann Institute, 76100, Rehovot, Israel

   Alex Biryukov & Adi Shamir

2. Computer Science department, University of California, CA 94720, Berkeley, USA

   David Wagner

Editors and Affiliations

1. Karlsruhe University, Germany

   Gerhard Goos

2. Cornell University, NY, USA

   Juris Hartmanis

3. Utrecht University, The Netherlands

   Jan van Leeuwen

4. Counterpane Internet Security, Inc., 3031 Tisch Way, Suite 100PE, CA 95128, San Jose, USA

   Bruce Schneier

Reprints and permissions

© 2001 Springer-Verlag Berlin Heidelberg

Policies and ethics