[6211] in cryptography@c2.net mail archive
Re: cracking GSM A5/1
daemon@ATHENA.MIT.EDU (John Gilmore)
Sun Dec 5 23:27:41 1999
Message-Id: <199912060348.TAA22038@toad.com>
To: Lucky Green <shamrock@cypherpunks.to>
Cc: "Steven M. Bellovin" <smb@research.att.com>, cryptography@c2.net
In-reply-to: <NDBBIFGOKODBCKDGJDKLIELOCOAA.shamrock@cypherpunks.to>
Date: Sun, 05 Dec 1999 19:48:04 -0800
From: John Gilmore <gnu@toad.com>
Lucky Green said:
> Being rather familiar with GSM crypto, allow me to say this: most GSM voice
> traffic globally is encrypted using A5/2. We know how to break A5/2 in five
> clock cycles on an ASIC. ...
>
> A5/1 likely requires more clock cycles. How many clock cycles we don't know
> and won't know until the cryptographic community takes a serious look at
> A5/1. But I from what I know about A5/1, it won't be a showstopper by any
> standard.
Interesting timing on your message, Lucky...
John
Date: Sun, 5 Dec 1999 15:44:02 +0200 (IST)
From: Adi Shamir <shamir@wisdom.weizmann.ac.il>
Subject: FYI
Dear John,
I thought that you will be interested in the following result:
Real-Time Cryptanalysis of GSM's A5/1 on a PC
Alex Biryukov and Adi Shamir
Computer Science Department
The Weizmann Institute
Rehovot 76100, Israel
Abstract:
A5/1 is the strong version of the encryption algorithm used
by about 100 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^40 and 2^45 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 a new attack on A5/1, which is based
on subtle flaws in the tap structure of the registers, their
noninvertible clocking mechanism, and their frequent resets.
The attack can find the key in less than a second on a single
PC with 128 MB RAM and two 73 GB hard disks, by analysing the
output of the A5/1 algorithm in the first two minutes of the
conversation. The attack requires a one time parallelizable
data preparation stage whose complexity can be traded-off
between 2^37 and 2^48 steps. The attack was verified with
an actual implementation, except for the preprocessing stage
which was extensively sampled rather than completely executed.
Remark: The attack is based on the unofficial description
of the A5/1 algorithm at http://www.scard.org. Discrepancies
between this description and the real algorithm may affect
the validity or performance of our attack.
Best personal wishes,
Adi.
