RE: New Yorker article on NSA surveillance, crypto regs

1999-12-06 Thread Lucky Green

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


RE: New Yorker article on NSA surveillance, crypto regs

1999-12-05 Thread Lucky Green

Dave Emery wrote:
   And much of the worlds wireless phone plant is GSM, which is
 almost always encrypted, which must add significantly to NSAs burden
 intercepting it, even if they can break keys very quickly...

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. For an agency that operates interception satellites
costing USD 1.5 billion each featuring antennas over twice the size of a
football field, adding 5 lousy clock cycles for the cryptanalysis to the
many clock cycles required to demodulate a GSM call can not be considered to
be significant. Immaterial would be a better term.

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

I know how to build a GSM interception station using off-the-shelf hardware
and a PII running Linux for a total cost of well below USD 10k. Give me a
couple of billions of dollars, peanuts for the NSA, and I hereby guarantee
you that I can take that system down to a single chip and some RF hardware.


  "Among the many misdeeds of British rule in India, history will look
   upon the Act depriving a whole nation of arms as the blackest."
  - Mohandas K. Gandhi, An Autobiography, pg 446

Re: New Yorker article on NSA surveillance, crypto regs

1999-12-03 Thread Steven M. Bellovin

In message [EMAIL PROTECTED], Declan McCullagh wri

 While much of it resonates as true, the timing -- just before crucial
 oversight hearings and concerns about illegal NSA spying -- might be a
 little coincidental:,1283,32770,00.html
 Last week's CNN article and televised report raised near-identical concerns
 about newfound NSA eavesdropping ineffectiveness:

These two articles state that "The worldwide move to digital, rather than
analog, phones and other equipment is making eavesdropping more difficult.
So are fax machines".  Can someone tell me why "digital" is harder for NSA?
Fax should be easier than voice, since there is in-band caller information.
(In the U.S., that information is legally required to be accurate.  I wonder
if they've ever seen pages from "Cali Cartel, Inc.")