[4685] in cryptography@c2.net mail archive
Re: A5/1 cracking hardware estimate
daemon@ATHENA.MIT.EDU (Phil Karn)
Tue May 11 20:23:42 1999
Date: Tue, 11 May 1999 16:01:38 -0700 (PDT)
From: Phil Karn <karn@qualcomm.com>
To: daw@CS.Berkeley.EDU
Cc: cryptography@c2.net, karn@qualcomm.com
In-reply-to: <7ha4f5$dao$1@blowfish.isaac.cs.berkeley.edu>
(daw@cs.berkeley.edu)
I worked on cryptanalyzing A5-1 several years ago. I built a
tree-based search routine that could retire many keys in each test
cycle. The exact number per cycle varied enormously depending on how
far into the tree I was when I found a conflict with the keystream
that would let me prune the branch. In the early phases of the search
this could be as much as 1/8 of the entire 64-bit shift register
space, but most of the time it was "only" a few million keys.
My approach assumed an arbitrary 64 bits of initial shift register
state, and I couldn't readily see how to exploit the fact that the
initial key had less entropy because of the way the crank is turned
100 times before generating a keystream.
I haven't worked on this problem in a while, but it did seem to me
that this problem is even more amenable to custom hardware than DES.
I suppose I could dust off my code...
Phil
