RE: RSA's RC5-64 Secret Key Challenge has been solved.
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 [EMAIL PROTECTED]
Re: RSA's RC5-64 Secret Key Challenge has been solved.
On Thu, Sep 26, 2002 at 02:45:12PM -0700, John Gilmore 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. Is A5/3 deployed yet? If not, a brute force attack is not needed, for A5/1 and A5/2 more efficient tools exist to cryptanalyse it. Even in real-time, although you might need to invest in some hard disk space before being able to eavesdrop and intercept. See the following paper for more information: A. Biryukov, A. Shamir and D. Wagner, Real Time Cryptanalysis of A5/1 on a PC As for A5/3, I'm not really sure what key length network operators are/will be using, 64-128 bits are allowed in the design requirements documentation. The specification should be available on the 3GPP website. A5/3 is based on Kasumi. Cheers, Ralf -- Ralf-P. Weinmann [EMAIL PROTECTED] PGP fingerprint: 2048/46C772078ACB58DEF6EBF8030CBF1724 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: RSA's RC5-64 Secret Key Challenge has been solved.
Ralf-P. Weinmann[SMTP:[EMAIL PROTECTED]] wrote: On Thu, Sep 26, 2002 at 02:45:12PM -0700, John Gilmore 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. Is A5/3 deployed yet? If not, a brute force attack is not needed, for A5/1 and A5/2 more efficient tools exist to cryptanalyse it. Even in real-time, although you might need to invest in some hard disk space before being able to eavesdrop and intercept. See the following paper for more information: A. Biryukov, A. Shamir and D. Wagner, Real Time Cryptanalysis of A5/1 on a PC As for A5/3, I'm not really sure what key length network operators are/will be using, 64-128 bits are allowed in the design requirements documentation. The specification should be available on the 3GPP website. A5/3 is based on Kasumi. Cheers, Ralf I spoke to David McNett ([EMAIL PROTECTED]) yesterday. He told me that they intend to fire up a the RC5-72 challenge, hoping to get lucky and find the key near the beginning. I think they're open to other suggestions, however. Factoring may or may not be reasonable. While RC5, DES, etc require minimal memory and storage, and can so run unobtrusively in the spare cycles of almost any machine, factoring, - even the seiving step - has large memory and storage requirements. The matrix reduction step at the end does not have any efficient distributed implementation I'm aware of. I think the lower RSA factoring challenges *may* be possible - RSA-576 is still standing, with a $10k prize. Other factoring challenges have up to $200k prizes. Challenges need to be carefully set up. It must be legal - hacking a deployed system in the face of the objections of the owner won't fly. It must be credible, in that there must be no reason to suspect collaboration between the challenger and the attacker. It must be realistic - it should model a real-world use closely enough to show that changes need to be made (the RSA secret key challenges where designed with IPSEC headers in mind - the single DES option was deprecated as soon as we showed that to be weak). This is an exciting time. With RC5-64 fallen, there are a lot of options for what to do next. The most interesting thing may not involve cryptanalysis. Peter Trei - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: RSA's RC5-64 Secret Key Challenge has been solved.
On Thu, 26 Sep 2002, Lucky Green wrote: 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. The GNU project has a SDR implementation, which claims to implement at least a plain FM receiver, and has GSM as a future direction: http://www.gnu.org/software/gnuradio/gnuradio.html Of course, as soon as someone implements a satellite PPV decoder on top of it the entire technology will probably be banned :( Pete -- Peter Clay | Campaign for _ _| .__ | Digital / / | | | Rights! \_ \_| | | http://uk.eurorights.org - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA's RC5-64 Secret Key Challenge has been solved.
At 01:16 PM 9/27/2002 +0200, Ralf-P. Weinmann wrote: Is A5/3 deployed yet? Kasumi (in the form of f8 (ciphering) and f9 (integrity) is beginning to be deployed in UMTS (WidebandCDMA) mobiles as we speak. But an exact specification of how to use Kasumi as A5/3 has only just been agreed; it will be 6-12 months (at least) before any significant amount of equipment, either fixed or mobile, will be produced and deployed, and it will be a couple more years after that before there will be significant probability that a call is encrypted using A5/3. As for A5/3, I'm not really sure what key length network operators are/will be using, 64-128 bits are allowed in the design requirements documentation. The specification should be available on the 3GPP website. A5/3 is based on Kasumi. A5/3 will be stuck at 64 bit keys for the forseeable future, due to compatibility issues in the protocol. f8 and f9, on the other hand, already use 128-bit keys. regards, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RSA's RC5-64 Secret Key Challenge has been solved.
First, the official PR release: --- Distributed Team Collaborates to Solve Secret-Key Challenge Contest designed to keep the cryptographic community updated on new achievements and help organizations maintain highest levels of security Bedford, MA, Thursday, September 26, 2002 - RSA Laboratories, the research center of RSA Security Inc. (Nasdaq: RSAS), the most trusted name in e-security(r), today announced that a coordinated team of computer programmers and enthusiasts, known as distributed.net, has solved the RC5-64 Secret-Key Challenge. The distributed.net team solved the challenge in approximately four years, using 331,252 volunteers and their machines. Distributed.net receives a cash prize of $10,000 for solving the challenge. Established in 1997, RSA Laboratories' Secret-Key Challenge is offered to quantify the strength of symmetric encryption algorithms such as DES and the RC5(r) algorithm with various key sizes. By sponsoring an actual contest, RSA Laboratories helps the industry confirm theoretical estimates, and through this constant evaluation, vendors are motivated to continue to improve their security solutions. The distributed.net consortium utilized the idle time of computers throughout the world to search through the list of all possible 64-bit keys for RSA Security's RC5 algorithm to find the one secret key selected at random by RSA Laboratories that decrypts a given message correctly. RSA Laboratories sponsors a series of cryptographic challenges that allow individuals or groups to attempt to solve various encryption puzzles for cash prizes. The RC5-64 Challenge is one of a series of contests held to determine the difficulty of finding a symmetric encryption key by exhaustive search (trial-and-error). Previous contests include the DES Challenge, the RC5-40 Challenge and the RC5-56 Challenge. We're very appreciative of all the volunteers who offered their time and computer's idle processing time to help solve this challenge, said David McNett, distributed.net co-founder and president. We have once again shown how collective computing power can be applied to security technology with ordinary PCs. We look forward to future RSA Laboratories-sponsored challenges that will assist in helping the cryptographic community gauge the strength of an algorithm or application against exhaustive key search. RSA Security congratulates the distributed.net team in solving the RC5-64 Secret-Key Challenge, said Burt Kaliski, chief scientist at RSA Laboratories. We appreciate the persistence of distributed.net and the many individuals involved in completing the search for this one key. Their work helps the industry confirm how much work is involved to search exhaustively for a key - and how a huge volume of computing time can be harnessed. The various challenges we sponsor are very useful for tracking the state of cryptographic achievements and helping ensure that organizations are maintaining the highest levels of security to protect their most critical data assets. About RSA Security Inc. RSA Security Inc., the most trusted name in e-security, helps organizations build trusted e-business processes through its RSA SecurID(r) two-factor authentication, RSA ClearTrust(r) Web access management, RSA BSAFE(r) encryption and RSA Keon(r) digital certificate management product families. With approximately one billion RSA BSAFE-enabled applications in use worldwide, more than 12 million RSA SecurID authentication users and almost 20 years of industry experience, RSA Security has the proven leadership and innovative technology to address the changing security needs of e-business and bring trust to the online economy. RSA Security can be reached at www.rsasecurity.com. RSA, RC5, BSAFE, ClearTrust, Keon, SecurID and The Most Trusted Name in e-Security are registered trademarks or trademarks of RSA Security Inc. in the United States and/or other countries. All other products and services mentioned are trademarks of their respective companies. - A personal note: In case people are wondering, the key turned out to be 63 DE 7D C1 54 F4 D0 39 and the encrypted message was The unknown message is: Some things are better left unread. I'm really happy with this - I wrote to Jim Bidzos proposing the contests way back in the fall of 1996, long before I came to work at RSA. At the time, I was aimed at killing DES, and creating pressure to ease the export limits on key size (they had just been raised from a ludicrous 40 up to 56. I didn't think this was good enough). I feel that I entirely suceeded. So I was in at the start of the contests, and at the end of this one (I was one of the two people at RSA who independently confirmed the decryption). I expect that this will be the last one attacked for a while - the next keylength is 72 bits, and at d.net's current rate, that would take them several centuries. Peter Trei
