Re: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm

[Peter Gutmann]

Declan McCullagh <[EMAIL PROTECTED]> writes:

>At 22:36 12/5/1999 -0500, Matt Blaze forwarded:
>>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

>Thanks, Matt, for forwarding. My article, with the no-interception-possible
>response from the GSM folks, is at:
>
> http://wired.lycos.com/news/politics/0,1283,32900,00.html

Quoting from the article:

>James Moran, the fraud and security director of the GSM Association in Dublin,
>says that "nowhere in the world has it been demonstrated --an ability to
>intercept a call on the GSM network. That's a fact To our knowledge
>there's no hardware capable of intercepting."

Given that there are a number of companies who sell GSM interception gear (and
who have been selling it for quite some time, several used to advertise it
quite openly on the web), this security director is, to take a line from the
Deep Crack book, "either lying, or incompetent, or both".  It's interesting to
note that all the vendors who advertised their stuff online have now restricted
access, presumably to maintain the myth that "there's no hardware capable of
intercepting" (aka security by Ostrich Algorithm :-).

Peter.

FW: Digital cell phone encryption broken, snooping possible

[ewollensky]

-Original Message-
From: Declan McCullagh [mailto:[EMAIL PROTECTED]] 
Sent: Monday, December 06, 1999 4:01 PM
To: [EMAIL PROTECTED]
Subject: FC: Digital cell phone encryption broken, snooping possible


***

http://wired.lycos.com/news/politics/0,1283,32900,00.html

 Cell Phone Crypto Penetrated 
 by Declan McCullagh ([EMAIL PROTECTED])

 10:55 a.m. 6.Dec.1999 PST 
 Israeli researchers have discovered
 design flaws that allow the descrambling
 of supposedly private conversations
 carried by hundreds of millions of wireless
 phones. 

 Alex Biryukov and Adi Shamir describe in a
 paper to be published this week how a PC
 with 128 MB RAM and large hard drives
 can penetrate the security of a phone
 call or data transmission in less than one
 second. 

 The flawed algorithm appears in digital
 GSM phones made by companies such as
 Motorola, Ericsson, and Siemens, and
 used by well over 100 million customers in
 Europe and the United States. Recent
 estimates say there are over 230 million
 users worldwide who account for 65
 percent of the digital wireless market. 

 [...]



--
POLITECH -- the moderated mailing list of politics and technology
To subscribe: send a message to [EMAIL PROTECTED] with this text:
subscribe politech
More information is at http://www.well.com/~declan/politech/
--

Re: Forthcoming Biryukov/Shamir result against A5/1 GSM privacy algorithm

[Declan McCullagh]

At 22:36 12/5/1999 -0500, Matt Blaze forwarded:
>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

Thanks, Matt, for forwarding. My article, with the no-interception-possible
response from the GSM folks, is at:

 http://wired.lycos.com/news/politics/0,1283,32900,00.html

-Declan

WPI Cryptoseminar, Monday Dec. 6 (fwd)

[R. A. Hettinga]

--- begin forwarded text


Date: Sun, 5 Dec 1999 21:12:39 -0500 (EST)
From: Christof Paar <[EMAIL PROTECTED]>
To: DCSB <[EMAIL PROTECTED]>, [EMAIL PROTECTED], [EMAIL PROTECTED]
cc: [EMAIL PROTECTED]
Subject: WPI Cryptoseminar, Monday Dec. 6 (fwd)
Sender: [EMAIL PROTECTED]
Reply-To: Christof Paar <[EMAIL PROTECTED]>

Please note that Dr. Stanley will be offering a new graduate course
EE579S, COMPUTER SECURITY, in the Spring 2000 semester. The class will
meet Tuesdays 6:00-8:50pm on the WPI campus. Please contact Dr. Stanley or
myself if you have further questions about the class.

- Christof Paar




 WPI Cryptography Seminar

  Using Cryptography to Combat Wireless Fraud - A Case Study

   Dr. Richard Stanley
GTE Labs

Monday, December 6
 4:30 pm,  AK 218
 (refreshments at 4:15 pm)


This talk will describe how the original technical specifications of
the AMPS cellular system were exploited to defraud cellular carriers
and avoid law enforcement.  We will see how these technical
shortcomings were mitigated using encryption technology, and how the
first attempts to do that failed.  The reasons for success and
failure will be discussed.  A review of the current state of wireless
fraud will be given.  A question and answer session will follow.



DIRECTIONS:

The WPI Cryptoseminar is being held in the Atwater Kent building on the
WPI campus. The Atwater Kent building is at the intersection of the
extension of West Street (labeled "Private Way") and Salisbury Street.
Directions to the campus can be found at
  http://www.wpi.edu/About/Visitors/directions.html


ATTENDANCE:

The seminar is open to everyone and free of charge. Simply send me a brief
email if you plan to attend.


TALKS IN THE FALL '99 SEMESTER:

10/4  Berk Sunar, SITI
  Comparison of Elliptic Curve Implementations

10/18 Jim Goodman, MIT
  Energy Scalable Reconfigurable Cryptographic
  Hardware for Portable Applications

10/28 Brendon Chetwynd, WPI/Raytheon
  Towards an Universal Block Cipher Module

11/15 Adam Elbirt, WPI
  A High-Speed FPGA Implementation of Serpent

12/6  Richard Stanley, GTE Labs
  Using Cryptography to Combat Wireless Fraud -- A Case Study


See
  http://www.ece.WPI.EDU/Research/crypt/seminar/index.html
for talk abstracts.


MAILING LIST:

If you want to be added to the mailing list and receive talk
announcements together with abstracts, please send me a short mail.
Likewise, if you want to be removed from the list, just send me a
short mail.

Regards,

Christof Paar


! WORKSHOP ON CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS (CHES 2000)!
!   WPI, August 17 & 18, 2000!
!  http://www.ece.wpi.edu/Research/crypt/ches!

***
 Christof Paar,  Assistant Professor
  Cryptography and Information Security (CRIS) Group
  ECE Dept., WPI, 100 Institute Rd., Worcester, MA 01609, USA
fon: (508) 831 5061email: [EMAIL PROTECTED]
fax: (508) 831 5491www:   http://ee.wpi.edu/People/faculty/cxp.html
***






For help on using this list (especially unsubscribing), send a message to
"[EMAIL PROTECTED]" with one line of text: "help".

--- end forwarded text


-
R. A. Hettinga 
The Internet Bearer Underwriting Corporation 
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

NSA sued for privacy violations

[Udhay Shankar N]

http://dailynews.yahoo.com/h/zd/19991205/tc/19991205067.html

Sunday December 05 04:30 PM EST
Privacy group sues NSA over spy net
Robert Lemos, ZDNet

Americans could learn more about the degree to which the secretive National 
Security Agency -- the government body charged with cracking codes and 
protecting critical information -- has been spying on U.S. citizens, if a 
suit filed on Friday by the Electronics Privacy Information Center garners 
results.

"The charter of the National Security Agency does not authorize domestic 
intelligence gathering," said Marc Rotenberg, director of EPIC, in a 
statement on Friday. "Yet we have reason to believe that the NSA is engaged 
in the indiscriminate acquisition and interception of domestic 
communications taking place all over the Internet."

The questions arose from reports to the European Union last year that the 
United Kingdom and Australia, among other countries, had cooperated with 
the United States to collect electronic communications across national 
borders. In the report, the spy network was dubbed "Echelon."

"We are concerned less with Echelon in particular and more with the NSA's 
eavesdropping practices in particular," said David Sobel, general counsel 
for EPIC.

'Interesting questions'

On Friday, EPIC filed a suit in federal court to free up documents 
regarding the legal justification for any surveillance that NSA had 
performed regarding U.S. citizens. These same documents were requested 
earlier this year by the House Intelligence Subcommittee, but the NSA 
refused to provide them.

"There are a lot of interesting questions about the NSA's activity, and it 
raised a few eyebrows when they stonewalled the House subcommittee," said 
Sobel.

In early June, EPIC filed a Freedom of Information Act request with the 
NSA, asking for the same documents requested by the House subcommittee, and 
the NSA replied that it would provide the documents by Oct. 30.

The court filing comes after the NSA missed that deadline. The NSA has 30 
days to respond to the court filing.

--
  _
  http://www.unimobile.com/ http://pobox.com/~udhay
 Unimobile -  the world's first internet mobile
Now Live !

Re: Wassenaar Revises Crypto

[John Young]

Oops, you're right. Whatever changes were made on
December 3 this year apparently did not affect cryptography.
Sorry for antsy.

Ulf Möller wrote:

>Did they really change anything now? This looks like the December 1998 (!)
>list.
 

Net Brokers Push For Digital Signature Legislation (was Re: [ILN]INTERNET LAW NEWS - DECEMBER 6, 1999)

[R. A. Hettinga]

More from the "lie in x.509, go to jail front"...

Cheers,
RAH


At 7:39 AM -0500 on 12/6/99, Michael Geist wrote:


> NET BROKERS PUSH FOR DIGITAL SIGNATURE LEGISLATION
> Internet brokers are anxious to see proposed digital signature legislation
> become law, reports the Wall Street Journal.
> http://interactive.wsj.com/articles/SB944228530293080288.htm

-
R. A. Hettinga 
The Internet Bearer Underwriting Corporation 
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

Wassenaar Changes Crypto

[John Young]

On December 3 the Wassenaar members approved
changes to the cryptography provisions of the WA:

   http://cryptome.org/wass120399.htm

And enhanced enforcement:

   http://207.96.11.93/press/99/WassEnforce.html

RE: New Yorker article on NSA surveillance, crypto regs

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

--Lucky

Re: cracking GSM A5/1

[Vin McLellan]

  Talking about timely and untimely comments.  

Check out Newsweek's credulous, confused, and tech-ignorant report
about the (pre-oversight-hearing) moaning and and weeping at Fort Meade.
Consider, with Newsweek, the momentous challenge the NSA confronts in e-mail
and Internet phone calls  (both "almost impossible to intercept," sez
Newsweek); and the agony with which the NSA views the insidious spread of
dangerous European cellular-phone crypto (which I presume means GSM;-)  
ROFL!  If there were a hall of fame for incompetent and misleading
journalism about crypto, this is a contenda!  

Consider one timely one-liner:

>The NSA, for instance, wanted the CIA to do more “black-bag
> jobs” — illegal break-ins — to steal European technology for
>encrypting mobile phones. 

The embarrassment of the full text:




 Adi Shamir <[EMAIL PROTECTED]> wrote:



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

RE: cracking GSM A5/1

[Lucky Green]

> Real-Time Cryptanalysis of GSM's A5/1 on a PC
>
> Alex Biryukov and Adi Shamir

At last! Congratulations are in order. Way to go, Alex and Adi!

Between the COMP128 and A5/2 work of our group and Alex and Adi's break of
A5/1, my motivation for finishing that software radio-based GSM interception
station has just increased greatly. Not that I wasn't motivated to begin
with. :-)

Even counting the almost 200 GB of drive space that seem to be required by
this new attack, we still should come in well under the USD 10,000 target
figure. We tested the code the came out of my reverse engineering against
official test vectors, so I am confident that Alex and Adi's caveat that the
attack will only work if the A5/1 code is correct won't be an issue.

It will be interesting to see the actual attack. Our 15 milliseconds attack
against A5/2 only works because several properties of the cipher come
together just right. I wonder if the same holds true for the new attack
against A5/1...

We live in interesting times,
--Lucky