[6213] in cryptography@c2.net mail archive
Re: cracking GSM A5/1
daemon@ATHENA.MIT.EDU (Vin McLellan)
Mon Dec 6 09:16:44 1999
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
To: John Gilmore <gnu@toad.com>, Lucky Green <shamrock@cypherpunks.to>
From: Vin McLellan <vin@shore.net>
Cc: cryptography@c2.net
Message-Id: <E11us3s-00034k-00@nautilus.shore.net>
Date: Mon, 6 Dec 1999 01:55:52 -0500
Talking about timely and untimely comments..... =20
Check out Newsweek's credulous, confused, and tech-ignorant report
about the (pre-oversight-hearing) moaning and and weeping at Fort Meade.
Consider, with Newsweek, the momentous challenge the NSA confronts in e-mail
and Internet phone calls (both "almost impossible to intercept," sez
Newsweek); and the agony with which the NSA views the insidious spread of
dangerous European cellular-phone crypto (which I presume means GSM;-) =20
ROFL! If there were a hall of fame for incompetent and misleading
journalism about crypto, this is a contenda! =20
Consider one timely one-liner:
>The NSA, for instance, wanted the CIA to do more =93black-bag
> jobs=94 =97 illegal break-ins =97 to steal European technology for
>encrypting mobile phones.=20
The embarrassment of the full text:
<http://www.msnbc.com/news/342480.asp#BODY>
--------------------
Adi Shamir <shamir@wisdom.weizmann.ac.il> wrote:
<snip>
>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:=20
>
>A5/1 is the strong version of the encryption algorithm used=20
>by about 100 million GSM customers in Europe to protect the=20
>over-the-air privacy of their cellular voice and data
>communication. The best published attacks against it require=20
>between 2^40 and 2^45 steps. This level of security makes it=20
>vulnerable to hardware-based attacks by large organizations,=20
>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=20
>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=20
>PC with 128 MB RAM and two 73 GB hard disks, by analysing the=20
>output of the A5/1 algorithm in the first two minutes of the=20
>conversation. The attack requires a one time parallelizable=20
>data preparation stage whose complexity can be traded-off=20
>between 2^37 and 2^48 steps. The attack was verified with=20
>an actual implementation, except for the preprocessing stage=20
>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. =20
>
<snip>
