ANNOUNCE: 2nd SSL challenge - we need your compute!
Adam Back
This is a request for idle compute time for the brute force of Hal's
second SSL challenge.
You will likely have read about the brute force crack of a netscape
SSL session by Damien Doligez <Damien....@inria.fr>, which was
widely covered in the media, and much discussed in this (and other)
newsgroups.
Damien has information on his breaking of the 1st challenge at:
http://pauillac.inria.fr/~doligez/ssl/
Hal Finney <hfi...@shell.portal.com> has now issued a 2nd challenge,
the aim with this challenge is to demonstrate in how short a time an
export SSL key can be broken. ie not how soon, but how *quickly* from
start to finish (note the distinction), so for this reason we are
constructing a virtual start line, and the virtual start gun will fire
at:
Thu Aug 24 at 18:00 GMT
If you are interested to join in, please obtain the sources / binaries
for your system in preparation for the start. (Even if you are after
the start, join in as it will take a while).
Piete Brooks <p...@cl.cam.ac.uk> wrote and is hosting the socket server,
and WWW pages, see this URL for the socket client and brute forcing
software, and WWW forms interface key doler:
http://www.brute.cl.cam.ac.uk/brute/
ftp archive (software available by both WWW and ftp):
ftp://ftp.brute.cl.cam.ac.uk/pub/brute/
Prize fund - donate c$ for the prize
======================================================================
I have set up a prize fund in c$ (digicash ecash) to add a bit of fun
to the proceedings, and stimulate interest in DigiCash (the best ecash
on the planet IMO).
The prize fund at time of writing is c$ 292.30, and the winner will be
the person who hits the key. The person who gets the prize will be
encouraged to participate in the ecash market to cash the money in, to
increase cash flow (there is currently a shortage of c$ sellers), and
to avoid taking the cash out of circluation.
Give your c$ donations for the prize fund here:
http://dcs.ex.ac.uk/~aba/sslprize.html
(or via email: shop-id: SSL-prize-fund, account-id: a...@dcs.ex.ac.uk)
The (unofficial) digicash exchange:
http://www.c2.org/~mark/ecash/ecash.html
Sign up for the Digicash trial (get c$ 100 free on opening account):
http://www.digicash.com/ecash/
A couple of things to note, the ecash exchange is not affiliated with
digicash, it is an experiment setup by digicash enthousiasts to allow
a floating exchange mechanism for buying and selling c$. The other
thing to note is that exchange rate is currently (from the exchange
above) about 100 c$ = 5 US $.
Compiling for some platforms required
======================================================================
We are currently lacking a DOS only version of the BRUTESSL.EXE, this
is complicated by the fact that Andrew Roos <And...@vironix.co.za>
has 32 bit 80x86 assembly speedups as well as a generic C version in
his brutessl application which makes it tricky to get a 32 bit
application. (Oh for standard flat 32 bit UNIX). Apparently it is
possible using the Pharlap DOS extender software, so if anyone is able
to help with this, please contact Piete or myself (Adam).
Any platforms you would like to see pre-compiled binaries for, send
them along, the source code is available from the ftp, and http
addresses above. A MAC binary would be nice also.
More technical things... skip unless you're interested
======================================================================
The socket server which will be doling out the keys is running on:
but you shouldn't need to know that unless you like to know what's
going on the client software is wired to use this by default.
There is an draft RFC like specification for the SMTP like protocol
which the client and server use to talk to each other (SKSP = Simple
Key Searching Protocol):
http://www.brute.cl.cam.ac.uk/ftp/pub/brute/protocol.txt
Who's doing what (who to complain to about things not working :-)
======================================================================
Hal Finney Issued challenge 1 and 2
Piete Brooks hosting www, and socket server, author of unix socket code
Andrew Roos wrote brutessl app
Andy Brown wrote windows NT client & protocol spec with Piete
Adam Back general software questions, prize fund ecash shop
Damien Doligez Broke 1st challenge
Eric Young \ independently broke 1st challenge also
David Byers /
Mark Grant WWW Ecash exchange
email / www for those poeple:
Hal Finney <hfi...@shell.portal.com> http://www.portal.com/~hfinney/
Andy Brown <a.b...@nexor.co.uk>
Piete Brooks <p...@cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/pb/
Adam Back <a...@dcs.ex.ac.uk> http://dcs.ex.ac.uk/~aba/
Andrew Roos <And...@vironix.co.za>
Damien Doligez <Damien....@inria.fr> http://pauillac.inria.fr/~doligez/
Eric Young <e...@mincom.oz.au>
David Byers <da...@ida.liu.se>
Mark Grant <Mark....@insignia.co.uk> http://www.c2.org/~mark/
(also lots of other people have offered compute time, and / or
contributed technical advice / bug reports etc)
Adam Back <a...@dcs.ex.ac.uk>
Piete Brooks <p...@cl.cam.ac.uk>
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i
iQCVAwUBMDs1PynIuJ1VakpnAQFRYAP/bftPKcqY2r8rP1cXQhVxIpLcCOWWTTRe
RC9vAdjW0w3wvvXF2adNWEtM46lSPsT15Xjzk4hoq6hX+BZtPqtUTAZMnbPPc1nR
lvwloBUnHOEdRW1CrbX7iH29iJ6ItjieWtXvSV9pOXNQVR0CHCDeqkEZK26XnzaH
yC4yW+pjfr0=
=Sk/B
-----END PGP SIGNATURE-----
Piete Brooks
has lead me to believe that this is where people might look for more info ...
For details see http://www.brute.cl.cam.ac.uk/brute/ but in brief it took
114456 seconds (31h 47m 36s) to crack Hal's second challenge with buggy
software meaning that a lot of the time was wasted by clients trying to get
segments to scan.
Many thanks to the 203 of you who participated, and apologies for all the
hassles I caused.
Jeremy Bradley
Well done to everyone - especially Peite for doing all the clever key-doling
server stuff. If we try this again we may well get this significantly under 24 hrs -
if we get ~500 people onto it maybe < 12hrs!!
Though I'm not sure if the server could stand >500 people :-)
How about trying to distribute the key-doling activity as well as the key-space-search?
--Jeremy Bradley
Adam Back
Jeremy Bradley <bra...@cs.bris.ac.uk> wrote:
> Well done to everyone - especially Peite for doing all the clever
> key-doling server stuff. If we try this again we may well get this
> significantly under 24 hrs -
>
> if we get ~500 people onto it maybe < 12hrs!!
>
> Though I'm not sure if the server could stand >500 people :-)
I think it would have been a lot shorter than 32 hrs even with current
compute. There were problems with the early versions of the
key-doling client which caused server overload. This meant that
machines ran idle because they couldn't get through to the server to
get more work. Also lots of ACKs of work done were not reported due
to time-out.
For instance the 8 indies I had running were often idle, perhaps as
much as 2/3 to 3/4 of the time.
It's very difficult to tell for sure what the aggregate effect was
because no one knows how all of the machines were, but if they were
all in a similar state to mine (and I don't see any reason for them
not to be), it could have happened in 8 - 10 hrs with the compute we
had already, possibly less.
> How about trying to distribute the key-doling activity as well as
> the key-space-search?
Piete is working on it...
Watch out for a 3rd challenge.
See
http://www.brute.cl.cam.ac.uk/brute/
for information, the decoded SSL message for Hal's 2nd challenge,
credits (space searched broken down by compute donor), etc.
Expect an announce of the 3rd challenge closer to the time.
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
Jeremy Bradley
>Jeremy Bradley <bra...@cs.bris.ac.uk> writes:
>
>>How about trying to distribute the key-doling activity as well as the
>>key-space-search?
>
>but zero communicaton required on the part of the entities doing the tests.
Probably because - in theory - it could go on for an indefinite length of time.
If you manage the key-space allocation properly then at least you know that
will come to a point when the whole key-space should have been searched.
Having said that I think many people were running a random search as well as
the exhaustive one - I was - I think the random search appeals to the
"it could be you" side of people :-)
--Jeremy Bradley.
Will Ware
: m...@io.org (Matthew Francey) wrote:
: >why not just have everyone test random keys? moderately longer (37%?),
: >but zero communicaton required on the part of the entities doing the tests.
: the exhaustive one - I was - I think the random search appeals to the
: "it could be you" side of people :-)
This smells like a good Prisoner's Dilemma problem. I have a certain
number of MIPs at my disposal, and I promise to dedicate some portion
of them to the official exhaustive key search, but I'm tempted to
reserve some of them for the lottery approach, and to do that with
political grace, I may be tempted to fib about how many MIPs I have.
There's probably some interesting game theoretical analysis of this.
--
-------------------------------------------------------------
Will Ware <ww...@world.std.com> web <http://world.std.com/~wware/>
PGP fingerprint 45A8 722C D149 10CC F0CF 48FB 93BF 7289
dsie...@icaen.uiowa.edu
>Jeremy Bradley <bra...@cs.bris.ac.uk> writes:
>>How about trying to distribute the key-doling activity as well as the
>>key-space-search?
>why not just have everyone test random keys? moderately longer (37%?),
>but zero communicaton required on the part of the entities doing the tests.
This seems to be by far the best way of doing things. Not as elegant or
impressive, but probably the way you'd implement it if you were a "bad guy"
stealing large resources from others. I assume that's sort of what we're
testing here -- how unsafe are we from a cracker who's got several networks
of hundreds of machines at his disposal? He'd want to limit the communication
between his machines as much as possible, having them all hitting a server
risks his exposure more than having one send a single message (perhaps as an
anonymous ftp upload to a few writable directories at random FTP sites?) he's
essentially invisible.
--
Doug Siebert || "Usenet is essentially Letters to the Editor
University of Iowa || without the editor. Editors don't appreciate
dsie...@icaen.uiowa.edu || this, for some reason." -- Larry Wall
Matthew Francey
>How about trying to distribute the key-doling activity as well as the
>key-space-search?
why not just have everyone test random keys? moderately longer (37%?),
but zero communicaton required on the part of the entities doing the tests.
--
Matthew Francey | m...@io.org | VE3RQX | GPS(NAD27) N43o34.203' W79o34.572' +93m
Vincent Archer
>Having said that I think many people were running a random search as well as
>the exhaustive one - I was - I think the random search appeals to the
>"it could be you" side of people :-)
Just have the key allocation server hands out keyspaces at random.
--
Vincent ARCHER -=-=- Herve Schauer Consultants -=-=- arc...@hsc.fr.net
Michael Shields
> >why not just have everyone test random keys? moderately longer (37%?),
> >but zero communicaton required on the part of the entities doing the tests.
>
> If you manage the key-space allocation properly then at least you know that
> will come to a point when the whole key-space should have been searched.
Assuming you trust everyone to search the keyspace they request, yes.
In an environment of untrusted participants, random searching may actually
be optimal.
--
Shields.
Will Ware
: Jeremy Bradley <bra...@cs.bris.ac.uk> wrote:
: > If you manage the key-space allocation properly then at least you know that
: > will come to a point when the whole key-space should have been searched.
: Assuming you trust everyone to search the keyspace they request, yes.
: In an environment of untrusted participants, random searching may actually
: be optimal.
"Trust" here could include not simply cases where searchers might be
malicious, but also where they might make a mistake, such that the
area they think they're searching fails to be searched.
Even with the allowance for trust on that level, I think you still need
to trust people when they tell you how quickly they can search keyspace.
If people consistently overclaim their search speeds, your estimate is
in danger.
Bill
Michael Shields <shi...@tembel.org> wrote:
>In article <DE300...@uns.bris.ac.uk>,
>Jeremy Bradley <bra...@cs.bris.ac.uk> wrote:
>> m...@io.org (Matthew Francey) wrote:
>[...]
>> >why not just have everyone test random keys? moderately longer (37%?),
>> >but zero communicaton required on the part of the entities doing the tests.
>>
>> Probably because - in theory - it could go on for an indefinite length of time.
>> will come to a point when the whole key-space should have been searched.
>
>Assuming you trust everyone to search the keyspace they request, yes.
>In an environment of untrusted participants, random searching may actually
>be optimal.
>Shields.
Agreed. An excellent way to sabotage cooperative-cracking efforts that
attempt to demonstrate the security or insecurity of an algorithm would be
to volunteer, and then not search the assigned keyspace. The more such
"hostile volunteers", the more likely that the correct key will be in a
keyspace assigned to someone opposing the project, who will either not do
the search, or not report success.
- Bill (ha...@midway.uchicago.edu)
Jeremy Bradley
>Agreed. An excellent way to sabotage cooperative-cracking efforts that
>attempt to demonstrate the security or insecurity of an algorithm would be
>to volunteer, and then not search the assigned keyspace. The more such
>"hostile volunteers", the more likely that the correct key will be in a
>keyspace assigned to someone opposing the project, who will either not do
>the search, or not report success.
Very true - indeed if you look at the "hall-of-fame" listings for the 2nd
SSL challenge - one of the striking things is the amount of requested
space that hasn't been returned.
Now of course the people concerned might have just not finished the processing...
..but in some cases individuals have requested thousands of 24-bit chunks which
would take many days on desktop systems.
However, there is a safeguard against this kind of attack and that is the
forced reallocation of key-space if requested chunks take over-long to process.
I believe this system was in progress for the 2nd SSL challenge and from what
I remember seeing, some keyspace was even checked twice.
--Jeremy Bradley.
Stuart Lynne
Jeremy Bradley <bra...@cs.bris.ac.uk> wrote:
>ha...@kimbark.uchicago.edu (Bill) wrote:
>
>>the search, or not report success.
>
>Very true - indeed if you look at the "hall-of-fame" listings for the 2nd
>SSL challenge - one of the striking things is the amount of requested
>space that hasn't been returned.
>
>Now of course the people concerned might have just not finished the processing...
>..but in some cases individuals have requested thousands of 24-bit chunks which
>would take many days on desktop systems.
>
>However, there is a safeguard against this kind of attack and that is the
>forced reallocation of key-space if requested chunks take over-long to process.
>I believe this system was in progress for the 2nd SSL challenge and from what
>I remember seeing, some keyspace was even checked twice.
My machine was one that did this. One file was mis-configured so that the
daemon quite happily kept asking for key space to search, failed while
calling the program to do the search and just started happily over and
over.. until I got home and saw what it was doing.
In theory the key server is (was) supposed to simply cycle back through the
key space repeatedly re-issuing un-acked areas when there was nothing else
to check. So other than perhaps denial of service if the key server is just
too busy to respond to legitimate requests, having hostile key requesters
shouldn't slow things down at all. The key server will always be willing to
provide a legitimate request with an non-acked space to search even if it
already has sent it to someone else.
--
Stuart Lynne <s...@wimsey.com> 604-933-1000 <http://www.wimsey.com>
PGP Fingerprint: 28 E2 A0 15 99 62 9A 00 88 EC A3 EE 2D 1C 15 68
Gregg Man
keyspace but never (obviously) reporting a success if encountered. There
would never be a way to ensure that a solution had NOT been found, without
multiple random checks of the entire space. Seems this could -seriously-
slow things down!
Stuart Lynne
Once the entire key space has been handed out and acked (or just recently
handed out) you just start over. You also ensure that you don't hand the
same requestors the same key space on subsequent passes.
Adam Back
> Gregg Man <greg...@aol.com> wrote:
> }What about (a) hostile searcher(s) erroneously ack-ing searches of the
> }keyspace but never (obviously) reporting a success if encountered. There
> }would never be a way to ensure that a solution had NOT been found, without
> }multiple random checks of the entire space. Seems this could -seriously-
> }slow things down!
>
> Once the entire key space has been handed out and acked (or just recently
> handed out) you just start over. You also ensure that you don't hand the
> same requestors the same key space on subsequent passes.
At the moment the way it works is that when the keyspace rolls over,
stuff which hasn't been acked yet is just reallocated, first person to
ack gets the credit.
The acks are easy enough to forge, so the checksum contained with an
ack was designed to prevent human error (especially for those using
the www interface) rather than stop malicious users. It would stop a
casual malicious user, but the determined one could easily read the
source to see what is required for the checksum.
This idea by Don Kitchen, which he posted on the cypherpunks list,
sounds like a way to hinder the malicious user to the point that being
malicious costs almost as much as doing the work for real:
Don Kitchen <d...@cs.byu.edu> wrote on cypherpunks:
> When doling out a segment of 16M keys, attach results of two randomly
> chosen garbage decryptions. The bruter has to report back which two keys
> they are. The overhead would add up, but I don't think it would be
> significant. [...]
>
> Anyway, the idea is that if you have to prove that you swept a big
> enough chunk to find the two keys, you've proven that you've swept
> a great portion of the keyspace. Of course, this does nothing to
> prevent _withholding_ a result. But it does prove that most of the
> keyspace has been swept; and most likely the search continued even after
> the two keys are found.
Now this sounds like a good solution to me, as it makes the malicious
user actually work for his faked acks, to the extent that he really
must do all the searching he's said he's done or at least a large
fraction of them (depends how many challenges you issue, but it should
get to quite high with say 10 challenges, and wouldn't cost much
compute, probably a couple of % extra max).
If that isn't enough (ie if someone with malicious intent *and* more
compute than every body else, like say the NSA, starts playing they
can draw out lots of keyspace, but even they would only stand a
certain chance of succeeding in `stealing' sections of keyspace and
acking it wrongly. I mean depending on what % of keyspace the
malicious attacker gets, there is some chance that they don't happen
to get the section with the key in, and someone else gets it and does
report it.
The random approach, just pick random starting points would be the
real fail safe method, but is less efficient. I reckon Don's approach
should be good against all but an attacker who has more compute than a
significant proportion of everyone else put together.
Problem is now that netscape has been dusted so badly due to poor
random number generator seeding, it kind of takes the fun out of brute
forcing 40 bit keys for silliness of ITAR demonstration purposes.
Perhaps after they have released the new netscape2.0 code with the
fixed ran no generator, when the brute force will again (we hope!) be
the quickest method to break.
Adam
--
Munitions T-shirt home page: http://www.obscura.com/~shirt/