Dave Emery wrote:
I certainly humbly defer to your expertise on the subject. I was
aware that A5/2 was very weak, though not aware that a 5 cycle result
had been found, and fully expect that (as indicated by the Shamir
announcement) that there probably is a similar very fast solution
to a5/1. And one supposes NSA has long ago derived these results in house
though some talented outsiders have yet to find a really cheap
A5/1 crack that would trivialize the required compute, meaning that
finding such is not totally trivial.
Your observation that you didn't know about the 5 clock cycle attack on A5/2
is noted. Our group really needs to sit down and write our long overdue GSM
crypto paper.
Other than better funding, the NSA has the advantage over us "outsiders" in
that the NSA or their European counterparts designed A5/1 and A5/2. They
didn't have to find a compromise. They had the luxury of being able to
engineer it in. Our 5 clock cycles attack against A5/2 only works because
several properties of the cipher come together just right. Chance? Many
doubt it. We can only wait and see if similar "fortunate coincidences" play
a role in the new attack against A5/1.
As you say, we shall simply have to wait and see what kind of
crack is most effective and how low the cracking cost goes. Shamir's
recent letter hints at cracking time and resources comparable with those
required to demodulate the call and follow the protocol - or less...
I am delighted that Biryukov and Shamir found a sub-second attack on A5/1.
Our group had an attack of just a tad under 2^40 based on Golic's paper, but
I just knew there had to be a much better attack. It didn't appear that we
would find that attack. I had tried to get others interested in
cryptanalyzing A5/1, but most cryptanalysts are busy working on the AES
candidates. For a while there, I thought that we might have to wait until
AES is chosen before A5/1 would receive some serious attention. I am glad
that it didn't take that long, since some 250 million GSM users worldwide
currently rely on the supposed voice privacy features of GSM. Other than
perhaps DES, GSM's COMP128, A5/1, and A5/2 are by far the most widely used
cryptographic algorithms in the world.
[On the GSM interception station project].
Have you actually written the code and tried it ? How well did
it work ? And in particular have you actually cracked real A5/1 even
with a 2^45 or so workfactor ?
The project is still underway. It is a complex project and I don't expect it
to be fully completed before 2Q2000. I am confident that the project will
succeed, but I'd rather not go into more detail at this time. Watch this
space. ;-)
--Lucky
