------- Forwarded Message
Date: Sun, 5 Dec 1999 15:31:21 +0200 (IST)
From: Adi Shamir <[EMAIL PROTECTED]>
Message-Id: <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
Subject: FYI
Dear Matt,
You may be interested in the following new 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.
I'll email you the paper in a few days, when its ready.
Best wishes,
Adi.
------- End of Forwarded Message
