From: aba@dcs.exeter.ac.uk
Date: Thu, 17 Aug 95 08:11:06 PDT
To: cypherpunks@toad.com
Subject: Another SSL breakage...
Message-ID: <7849.9508171510@exe.dcs.exeter.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain


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