Another SSL breakage...

-----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
<davby@ida.liu.se>:

> 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/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print
pack('H*',$_)while read(STDIN,$m,($w=2*$d-1+length($n)&~1)/2)
- -------------------------------8<-------------------------------
TRY: rsa -k=3 -n=7537d365 < msg | rsa -d -k=4e243e33 -n=7537d365

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQCVAwUBMDNbnSnIuJ1VakpnAQHe9AP8DJBhZ8LyRNx7PO1GY076Cap+xzdS0/ys
WE/tdm0GBfjqxvjtar85mmc1hZVPCn1m5Swsflk2ZpieLbwUzHz+g1ciW3IiZu1Y
8Qc2HJxWRrez3J5CeiMHgMJl6Bj6vF5XAWLW0v6NpujbOR9XuIjsKnH3jKvkhLF5
z0u7Oui0AX0=
=nkmn
-----END PGP SIGNATURE-----

On Thu, 17 Aug 1995 aba@dcs.exeter.ac.uk wrote:

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

I add my congratulations to everyone else's.  But, as the list rejoices 
that this means the "end of ITAR" or, more accurately put the "end of 
encryption programs as 'munitions'", I've got to play the devil's advocate.
Many of you, of course, see me as the Devil's Advocate.  

Anyway, certain arms of the government want to prevent strong crypto from 
being exported so that they can easily decode encrypted messages from 
abroad (at least those using US developed software).  Damien's impressive 
feat is that exportation of weak crypto indeed makes that possible.  Some 
posters have discussed the time and difficulty in decoding strong crypto 
... I think all agree that it would take significantly longer (or much 
more computer time) but is not impossible.

So ... has this proven that the banning of strong crypto is the correct 
way to go, and that, at least to some, credit card transactions using 
weak crypto will be acceptable to most (given the ease of getting CC#s 
other ways)?

Donning my asbestos suit,
And speaking only for myself ...

EBD

| So ... has this proven that the banning of strong crypto is the correct 
| way to go, and that, at least to some, credit card transactions using 
| weak crypto will be acceptable to most (given the ease of getting CC#s 
| other ways)?

	No.  Banning strong crypto will not help; those darn furriners
are using it anyway.  What it will mean is that the Information
Infrastructure of the future will bypass the United States, as without
strong cryptography, it is impossible to build a secure architechture.

	Should the United States wish to relagate itself to the status
of a third world nation becuase of terrorists, druge dealers, child
pornorgaphers and money launderers, that is indeed unfortunate.

Adam


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

where can the software be obtained I would like to run it on my dual pentium
under solaris 2.4 for benchmarking...

     thanx in advance
     kelly

> 
> 
> where can the software be obtained I would like to run it on my dual pentium
> under solaris 2.4 for benchmarking...

A copy is on all.net's W3/gopher server
FRC


-- 
-> See: Info-Sec Heaven at URL http://all.net
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236