RSA's RC5-64 Secret Key Challenge has been solved.

[Lucky Green]

John wrote:
> After getting that getting started, though, I suggest 
> beginning a brute-force attack on the GSM cellphone 
> encryption algorithm.  That's in use in hundreds of millions 
> of devices worldwide, protecting (or failing to protect) the 
> privacy of billions of phone calls a day.

According to the GSM Association's website there are currently 732
million GSM users world-wide. Still, I suspect that unlike RC5 and DES,
GSM's two "voice privacy" algorithms A5/1 and A5/2 might not be the best
candidates for brute force distributed key searches since the algorithms
were badly designed, are fundamentally broken, and thus are subject to
very efficient cryptanalytical attacks with work factors well below the
64-bit key space nominally utilized by GSM.

A5/2, the weaker of the two algorithms, can be broken in real-time on a
single, low-end, Pentium class computer.

A5/1, the stronger of the two algorithms, falls to a near real-time
attack on computing hardware far from bleeding edge, but the attack as
published requires a 2^48 preprocessing stage. That table could be
generated by a distributed effort.

http://cryptome.org/a51-bsw.htm

Unfortunately, the greatest challenge in publicly demonstrating the
insecurity of GSM and other civilian wireless communication protocols
lies not in breaking the compromised crypto, but in obtaining the
required RF and signal processing equipment. Full-featured equipment is
priced with governmental customers in mind and difficult to obtain.
Commercial-grade interception hardware usually lacks cryptanalytical
features.

Software defined radios would be well-suited to task, but those who
expended the effort of writing software-defined cellular telephony
modules so far understandably chose to sell the fruits of their labor to
paying customers rather than releasing the code as Open Source.

Until the required equipment becomes readily available to the public,
the interested parties likely will continue to make the same outrageous
claims they made in the past, such as that GSM is secure against
eavesdroppers irrespective of how weak the ciphers have been shown to be
since the GSM signal itself cannot be intercepted...

Lastly, while a publicly available A5/1 precomputation table would
likely be of interest to researchers, myself included, anybody
considering creating that table may wish to inquire with competent legal
counsel as to the legality of performing this research in the U.S.

--Lucky Green


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com