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...


Date: Sun, 5 Dec 1999 15:44:02 +0200 (IST)
From: Adi Shamir <[EMAIL PROTECTED]>
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


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 Discrepancies
between this description and the real algorithm may affect
the validity or performance of our attack.  

Best personal wishes,

Reply via email to