From owner-cypherpunks@toad.com Wed Aug 16 12:42:43 1995 Date: Wed, 16 Aug 95 10:42:43 +0200 From: Damien.Doligez@inria.fr (Damien Doligez) To: cypherpunks@toad.com Subject: SSL challenge -- broken ! Sender: owner-cypherpunks@toad.com Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- SSL challenge -- broken This is to announce the solution of the SSL challenge posted by Hal Finney on July 17, 1995 (message-ID: <3u6kmg$pm4@jobe.shell.portal.com>), also found at: The 40-bit secret part of the key is 7e f0 96 1f a6. I found it by a brute force search on a network of about 120 workstations and a few parallel computers at INRIA, Ecole Polytechnique, and ENS. The key was found after scanning a little more than half the key space in 8 days. The cleartext of the encrypted data is as follows: The SERVER-VERIFY message is: 9C B1 C7 83 D9 BB B7 75 01 6F 19 19 03 58 EC 05 MAC-DATA 05 MSG-SERVER-VERIFY AF 84 A7 79 F8 13 69 20 25 9B 53 A0 60 AE 75 51 CHALLENGE The CHALLENGE part is a copy of the challenge sent by the client in its first message. The answer is the CLIENT-FINISHED message: 22 BB 23 39 55 B0 7F B6 1A B0 35 85 F7 DB C1 E5 MAC-DATA 03 MSG-CLIENT-FINISHED BF EB 90 F8 2C 0C E1 EA 18 AC 11 4C 83 14 21 B6 CONNECTION-ID The next message is SERVER-FINISHED: D4 CD F3 4E 38 F1 2B 1E DC FD 72 C8 34 02 CD FF MAC-DATA 06 SERVER-FINISHED-BYTE 23 1C 05 40 60 72 49 6E 83 BA D1 28 CC 9B 5F 63 SESSION-ID-DATA Then comes the data message sent by the client. This is the juicy one. I have broken the contents into its fields (the body was just one long line) 72 23 B5 98 0D D0 07 1A DA F1 C7 A4 40 41 5A 10 MAC-DATA POST /order2.cgi HTTP/1.0 Referer: https://order.netscape.com/order2.cgi User-Agent: Mozilla/1.1N (Macintosh; I; PPC) Accept: */* Accept: image/gif Accept: image/x-xbitmap Accept: image/jpeg Content-type: application/x-www-form-urlencoded Content-length: 472 source-form=order2-cust.html& order_number=31770& prod_80-01020-00_Mac=1& carrier_code=UM& ship_first=Cosmic& ship_last=Kumquat& ship_org=SSL+Trusters+Inc.& ship_addr1=1234+Squeamish+Ossifrage+Road& ship_addr2=& ship_city=Anywhere& ship_state=NY& ship_zip=12345& ship_country=USA& ship_phone=& ship_fax=& ship_email=& bill_first=& bill_last=& bill_org=& bill_addr1=& bill_addr2=& bill_city=& bill_state=& bill_zip=& bill_country=USA& bill_phone=& bill_fax=& bill_email=& submit=+Submit+Customer+Data+ This order came from Mr Cosmic Kumquat, SSL Trusters Inc., 1234 Squeamish Ossifrage Road, Anywhere, NY 12345 (USA). Unfortunately, Mr Kumquat forgot to give his phone number, and the server's reply (in two packets) is: 09 12 AD FE A5 A9 BF D1 8C 8C E2 6A A3 48 B9 75 MAC-DATA HTTP/1.0 200 OK Server: Netscape-Commerce/1.1 Date: Wednesday, 12-Jul-95 05:40:30 GMT Content-type: text/html 1C CD C4 3D 80 F1 7B 94 11 AC E8 72 B1 99 BC FA MAC-DATA Error

Error

The shipping address you supplied is not complete. The street address, city, state, zip code, country and phone number are mandatory fields. Please go back and specify the full shipping address. Thank you. This result was found with a quick-and-dirty distributed search program, which I wrote when I realized that the cypherpunks were going to be a few weeks late with their collective effort. When the program was running, it took little more than one week to find the key (it would have taken about 15 days to sweep the entire key space). I ran it on almost all the machines I have access to, summarized in the following table: type speed (keys/s) number notes - -------------------------------------------------------- DEC (alpha) 18000-33000 34 DEC (MIPS) 2500-7500 11 SPARC 2000-13000 57 HP (HPPA/snake) 15000 3 Sony (R3000) 1100-4000 3 Sun 3 600 2 Sequent B8000 100 x 10 1 (1) Multimax (NS532) 600 x 14 1 (1) KSR 3200 x 64 1 (1) (2) Notes: 1. These are multiprocessor machines 2. The KSR spent only about 2 days on this computation. The total average searching speed was about 850000 keys/s, with a maximum of 1350000 keys/s (1150000 without the KSR). Conclusions: * Many people have access to the amount of computing power that I used. The exportable SSL protocol is supposed to be weak enough to be easily broken by governments, yet strong enough to resist the attempts of amateurs. It fails on the second count. Don't trust your credit card number to this protocol. * Cypherpunks write code, all right, but they shouldn't forget to run it. I want to thank the people at INRIA, Ecole Polytechnique, and Ecole Normale Superieure for giving their CPU time. (Most of them are on vacation anyway...) You can find a copy of this text at -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCSAwUBMDG4dVNZwSQVabihAQGeFAPnUZil4WlauoMke9HaULDNOVf1hLXS0i9U VJWZsPHcihDbn6nBN9T6f3sW/S08N5YJFSCmuZzqO59c0nOAKILb6a3TsXjFEcu8 W8UfwFsZa6gx7iuYqandhoHBEkkc5NSwMe1f+lPiV2MdclzQ4/VtZ7Oa1VB+RftD Am4+w/Y= =Fju1 -----END PGP SIGNATURE----- **** This is a timestamp of the above message: -----BEGIN PGP MESSAGE----- Version: 2.6.2 iQBVAwUAMDGsOeWrvYiumrHZAQF0QwIAnDWdVVTiVmUTY5lp08yPeLRoFetczb+U E0WVgTUJ4a16tinOPaJl/6jOpPUUPWMjkDaD2N1xw8lGqm0UgZJiGIkAkgMFATAx uKJTWcEkFWm4oQEBAQ8D5ixvYrpEAQYfeNXmbB46BTTnBwBPS/JjfVFEEnC0Zsoj cyh/WELUsZf785b23vEq9JFvZB+bq1UsJTpttl335TrW344ZYof3kl6fdEF2Jf5q LxQjkuP9s/OQX5iJZpHz4LUxbb+/hOwSdZ2O3LV7ETiHs9AK1+bnKfOGDyei =qO7V -----END PGP MESSAGE----- From owner-cypherpunks@toad.com Thu Aug 17 04:07:45 1995 From: John Young Date: Thu, 17 Aug 1995 08:07:45 -0400 To: cypherpunks@toad.com Subject: WSJ on SSL Crack Sender: owner-cypherpunks@toad.com Precedence: bulk The Wall Street Journal, August 17, 1995, p. B3. French Hacker Cracks Netscape Code, Shrugging Off U.S. Encryption Scheme By Jared Sandberg A computer hacker in France has breached the encryption scheme of new Netscape software for navigating the Internet, the global computer network. The breach underscores flaws in U.S. rules restricting the export of more-sophisticated security measures. The hacker, a French student at the Ecole Polytechnique, cracked the weaker encryption scheme that U.S. government policy forces Netscape Communications Corp. to use in a foreign version of its Navigator software. Yesterday, he posted the results of his efforts on the Internet's Cypherpunks discussion group. The student took up a challenge issued on July 14 in the Cypherpunks group, which is frequented by cryptography experts and hackers and mathematicians. He used 120 powerful computer workstations and two supercomputers to crack a piece of information encrypted in Netscape's "browser" software. The security is aimed at scrambling sensitive financial data to keep credit-card numbers, sales transactions and other material safe from breakms. The highly sophisticated computers took eight days to break the code -- far more power and time than the typical illegal hacker would be able to muster for criminal pursuits. But the chore nonetheless highlights the vulnerabilities that could make customers shy away from conducting commerce on the Internet, particularly international users who can't get hold of the tougher security measures allowed within the U.S. The French hacker was able to crack the so-called 40-bit encryption scheme in Netscape's overseas version of its software. In the U.S., Netscape employs a far more powerful design -- 128 bits, a number that refers to length of the encoding "key," which is used to scramble data. U.S. rules limit Netscape to exporting only 40-bit encryption overseas. Yet the 128-bit version takes exponentially more power to crack: Compared with violating the 40-bit scheme, the 128-bit key would take 10-to-the-26th-power more time to breach, experts say. That's a 1 followed by 26 zeroes, a factor of time that makes it all but impossible for hackers to break in. Netscape wasn't surprised at the findings. The company said it has always known and stated that 40-bit security could be breached by "brute force," the use of massive computing power to descramble the information. "This is a good indication of why the government should allow us to ship more secure software," said Mike Homer, Netscape's vice president of marketing. "The laws are archaic." Clinton administration officials have viewed strong encryption as a weapon for foreign terrorists, who could exchange communications without fear of eavesdropping by law enforcement officials. That policy, however, has raised the hackles of industry executives, who say that without strong encryption abroad, the growth of electronic commerce could be significantly stunted. Last week, a group of software executives told the White House that restrictive export regulations might blunt American competitiveness in foreign markets. "Netscape security is fine," said Dietrich Cappe, a senior partner at Red Planet LLC, an Internet consulting company. "As long as the government's export restriction exists, commerce is going to be severely hampered." Netscape licenses the encryption algorithm from RSA Data Security Inc., one of the most prominent software security firms that licenses its software to most major software companies. "We've warned the government that the level of security they allow our customers to export is too weak," said James Bidzos, president of RSA. "Maybe they'll listen now." Netscape's Mr. Homer noted, however, that the amount of effort and computing power, which could cost as much as $10,000 in addition to the cost of the machines, don't make even breaches of 40-bit security practical from a thief's perspective. "You'd be better off working in a shoe store, stealing credit card numbers for a week." Mr. Homer said. [End] From owner-cypherpunks@toad.com Thu Aug 17 17:10:00 1995 From: aba@atlas.ex.ac.uk Date: Thu, 17 Aug 95 16:10:00 +0100 To: cypherpunks@toad.com Cc: davby@ida.liu.se, Damien.Doligez@inria.fr, hfinney@shell.portal.com, asb@nexor.co.uk, aba@atlas.ex.ac.uk Subject: Another SSL breakage... Sender: owner-cypherpunks@toad.com Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- All hell seems to have broken loose whilst I was lazing on the beach yesterday. SSL breakings, big name newspaper newsreports (of varying degrees of accuracy), and much ITAR bashing (yay!) or perhaps that should be nooooh! 'cos I might be doing myself out of work as a UK crypto hacker (as John Hemming said in the article Robert Hettinga forwarded) if we loose the fun advantage of being in the free world, and not having to follow the ITAR nonsense. Anyway, congratulations Damien! As Hal said, another group was working on the SSL challenge (albiet just for software testing purposes). Here's the story.... on Tue, 15 Aug 1995 10:43:15 +0200 I recieved this from David Byers : > Eureka! > > Encrypted Master Key: 7ef0961fa6 > > [...] So who was first? David hit it Tue 10:43 GMT+2. Doesn't matter, the more the merrier, and the better to demonstrate the silly ITAR export restrictions. This was a trial run at breaking it which two people had done just to check if their respective software was working correctly. It appears that it was :-). This testing was some of the reason for the slowness in getting the group effort started, we were very keen to ensure it really would work, and that the software was working perfectly. Disappointment with the RC4 bruting demonstrated the importance of checking first. On with the story, Davids eureka arrived Tuesday, I tinkered with it some, but was interpreting it wrongly and left it for that day, then I was away yesterday (at the beach with wife and kids, nice weather over here), and figured out how to apply the key this morning (with a bit of prompting from Hal as to what I was doing wrong), just after reading Damien's announce on cpunks, where he independently bruted it on a farm of workstations. Here's the output, with the "Mr Cosmic Kumquat" from "SSL Trusters Inc": > PPOST /order2.cgi HTTP/1.0Referer: https://order.netscape.com/order2.cgi > User-Agent: Mozilla/1.1N (Macintosh; I; PPC) > Accept: */* > Accept: image/gif > Accept: image/x-xbitmap > Accept: image/jpeg > Content-type: application/x-www-form-urlencoded > Content-length: 472 > > source-form=order2-cust.html&order_number=31770&prod_80-01020-00_Mac=1&carrier_code=UM&ship_first=Cosmic&ship_last=Kumquat&ship_org=SSL+Trusters+Inc.&ship_addr1=1234+Squeamish+Ossifrage+Road&ship_addr2=&ship_city=Anywhere&ship_state=NY&ship_zip=12345&ship_country=USA&ship_phone=&ship_fax=&ship_email=&bill_first=&bill_last=&bill_org=&bill_addr1=&bill_addr2=&bill_city=&bill_state=&bill_zip=&bill_country=USA&bill_phone=&bill_fax=&bill_email=&submit=+Submit+Customer+Data+ (I won't bother formating it more cleanly as Damien has already done the honors). I think a group effort ought to be done now that we are confident of the software, just to see how darn fast we (cypherpunks as a group) can knock off SSL keys. (This one was done by 2 people for testing purposes, and independently by Damien (who we didn't know was working on it)). I'd really like to work up to a really meanly few hours breakage, as it looks that much more impresive. The next media release ought to be of a steady offer, of the form, cpunks break keys in x hours, where x is a very small number. And not just break one key, but will break lots of keys, as required, until something is done about it (ITAR) :-) Eric Young is currently away on holiday, but I have his machine stats from earlier email, where he explained the hardware he was testing on. Eric swept 8000 - FFFF, and David 0000 - 7ef0 (where he hit the key) Machine stats for this bruting: 1 x 16k processor MasPar MP-1 - 1.5M keys/sec 4 CPUs of R4400 200mhz - 24000 keys/sec 4 CPUs of sparc 60mhz - 17500 keys/sec 2 CPUs of sparc 50mhz - 14800 keys/sec 1 CPU of Pentium 75mhz - 10200 keys/sec 1 CPU of Alpha - 10000 keys/sec 2 CPUs of 88100 - 8000 keys/sec 1 CPU of 88000 - 3500 keys/sec 1 CPU of R3000 36mhz - 3800 keys/sec 49 CPUs of 486DX 50mhz - 3780 per src The workstations total: - 424,320 keys/sec, and the Maspar 1.5M keys/sec on it's own. The 0000 - 8000 sweep was finished Aug 11 (he might have finished a day or two earlier, that's when he replied to my question as to how he was getting on. He left for his holiday after that email. The MasPar sweepings were going fast, swept 0000 - 795d (this was sometime before the 11th Aug) but someone else wanted the machine, so a pause ... and then (presumably Tues morning) 795d - 7ef0 and bang he hit it. We were getting worried about the possibility of software failure by then as we'd already swept 8000 - FFFF and 0000 - 795D accounting for 97.4% of the key space. It was hiding away in the last bit of unswept keyspace. Luck of the draw... A few quick calculations: The maspar alone could do the entire keyspace in 8 1/2 days, or an expected average time of ~100 hours. I believe I'm right that there would be lots of organisations which would sell you idle maspar hours for a lot less than $100 / hr. Heck you could do it with PC's, if they (WSJ article) think it's worth $10k all I can say is "give me the $10k", and I'll do it and make a handsome profit. The workstation farm, at 424k keys/sec could do the job in 30 days, or 15 days average. The workstation farm was only used to sweep half the key space, and was used overnight (12 hours) and weekends (61 hours) only as people were using the machines during the day. Could it have been done with out anyone knowing? Hell, yes - it was in fact, no announce was made as it was just testing etc. Adam - -- HAVE *YOU* EXPORTED RSA TODAY? --> http://dcs.ex.ac.uk/~aba/rsa/ - --rsa--------------------------8<------------------------------- #!/bin/perl -s-- -export-a-crypto-system-sig -RSA-3-lines-PERL $m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%Sa 2/d0From: aba@atlas.ex.ac.uk >on Tue, 15 Aug 1995 10:43:15 +0200 I recieved this from David Byers >: > >> Eureka! >> >> Encrypted Master Key: 7ef0961fa6 Then David beat me by about two hours. My program found the result at 12:23 +0200 on the same day. I was not at work (aug 15 is a holiday in France), so I saw it a few hours later, and I wrote my announcement yesterday. I will happily redirect all the journalists to David... -- Damien From owner-cypherpunks@toad.com Thu Aug 17 15:41:18 1995 From: aba@atlas.ex.ac.uk Date: Thu, 17 Aug 95 14:41:18 +0100 To: perry@piermont.com ("Perry E. Metzger") Cc: cypherpunks@toad.com, aba@atlas.ex.ac.uk In-Reply-To: perry@piermont.com's message of 17 Aug 1995 08:34:06 -0400 Subject: Re: SSL challenge -- broken ! Sender: owner-cypherpunks@toad.com Precedence: bulk > It has occured to me that, because the RC4 key crackers spend most > of their time in key setup, you can crack N SSL sessions that you > captured in not substantially more time than it took to crack > 1. This is analagous to the way brute force Unix password file > hacking operates. This occurred to me a whila ago too, and I thought it a very cool idea, as it would mean you could do loads of keys at once with little additional compute time. Then I changed my mind, there's a reason this doesn't work with 40 + 88 SSL, I think. It works well enough for straight RC4, as you just compare lots of keys at once, the RC4 output which will be XORed just gets compared against lots of sample plain text / cipher texts simulataneously. The actual key used is the 40 bit key you're bruting, plus what is effectively an 88 bit salt (in unix password nomenclature, only unix password salts are typically 12 bits). The actual 128 bit RC4 key is generated by taking the MD5 of the known and unknown key bits, plus a couple of other things. As the 88 known bits are randomly generated you can't combine work. If I have misunderstood something, or there is a way to work around this, please explain, because being able to do this would be a huge boon to the key breaker. It would allow you to break keys at a ferocious rate if you had lots of keys to break. Adam From owner-cypherpunks@toad.com Thu Aug 17 18:35:06 1995 Date: Thu, 17 Aug 1995 16:35:06 +0200 Subject: UK Independent on SSL crack To: cypherpunks@toad.com From: anon-remailer@utopia.hacktic.nl (Anonymous) Organization: Hack-Tic International, Inc. Comments: Hack-Tic may or may not approve of the content of this posting Comments: Please report misuse of this automated remailing service to Sender: owner-cypherpunks@toad.com Precedence: bulk from the "ukpipeline" :-) >>>>>>>>>>>>>>>>>>>> UK Indpendent newspaper, 17/8/1995 Internet's 30bn Pound Secret Revealed Charles Arthur Technology Correspondent A French student has cracked the most commonly used encryption system used to pass financial transactions over the Internet, threatening a business forecast to be worth billions of pounds worldwide. Damien Doligez, 27, a PhD student at the Inria research centre near Paris, broke a software "key" used by the Netscape browsing program, which lets users navigate the World Wide Web. With Netscape, Internet users can visit shopping "sites" on the Web and order goods by sending their credit card and address over the network to the site. To prevent anyone picking up those confidential details as they pass through the network, they are encrypted first using a software "key". This is the system used for example by Barclays Bank's "BarclaySquare" project, launched in May, which offers access to eight major retailers. Market research companies forecast that money transmission over the Internet will be worth more than 30bn pounds by 2005. At the launch of BarclaySquare, Roger Alexander, managing director of the unit said: "The encryption method has been rigorously tested by us". But Mr. Doligez has compromised that security by decoding a test example of an encrypted transaction, posted on a number of Internet discussion groups in July. The transaction was scrambled using a digital key 40 bits long, which offers about 1,000 billion ( a million million) possible combinations. Mr Doligez harnessed spare time on 120 workstations and parallel computers. The computers turned up the answer after eight days. "I wouldn't trust my credit card number to Netscape," Mr Doligez told the Independent from Paris yesterday. Netscape Communications, whose flotation on the New York Stock Exchange raised more than $1bn, said "We have always said this would be theoretically possible." [end]