RE: cracking GSM A5/1

[Lucky Green]

 Real-Time Cryptanalysis of GSM's A5/1 on a PC

 Alex Biryukov and Adi Shamir

At last! Congratulations are in order. Way to go, Alex and Adi!

Between the COMP128 and A5/2 work of our group and Alex and Adi's break of
A5/1, my motivation for finishing that software radio-based GSM interception
station has just increased greatly. Not that I wasn't motivated to begin
with. :-)

Even counting the almost 200 GB of drive space that seem to be required by
this new attack, we still should come in well under the USD 10,000 target
figure. We tested the code the came out of my reverse engineering against
official test vectors, so I am confident that Alex and Adi's caveat that the
attack will only work if the A5/1 code is correct won't be an issue.

It will be interesting to see the actual attack. Our 15 milliseconds attack
against A5/2 only works because several properties of the cipher come
together just right. I wonder if the same holds true for the new attack
against A5/1...

We live in interesting times,
--Lucky

Re: cracking GSM A5/1

[Vin McLellan]

  Talking about timely and untimely comments.  

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;-)  
ROFL!  If there were a hall of fame for incompetent and misleading
journalism about crypto, this is a contenda!  

Consider one timely one-liner:

The NSA, for instance, wanted the CIA to do more “black-bag
 jobs” — illegal break-ins — to steal European technology for
encrypting mobile phones. 

The embarrassment of the full text:
http://www.msnbc.com/news/342480.asp#BODY



 Adi Shamir [EMAIL PROTECTED] 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: 

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.  

snip