[6210] in cryptography@c2.net mail archive
Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm
daemon@ATHENA.MIT.EDU (Matt Blaze)
Sun Dec 5 22:55:58 1999
Message-Id: <199912060336.WAA19046@fbi.crypto.com>
To: cryptography@c2.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Sun, 05 Dec 1999 22:36:28 -0500
From: Matt Blaze <mab@research.att.com>
------- Forwarded Message
Date: Sun, 5 Dec 1999 15:31:21 +0200 (IST)
From: Adi Shamir <shamir@wisdom.weizmann.ac.il>
Message-Id: <199912051331.PAA19283@winter.wisdom.weizmann.ac.il>
To: mab@research.att.com
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
