[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
ANNOUNCE: bruteRC4, 40 bits all swept
Well we have demonstrated that 40 bit RC4 can be brute forced in
around a weeks compute time.
(We've also learned a list of thinks to fix for the next attempt as no
key was forthcoming :-|, details on why not and what is being fixed to
ensure this doesn't happen with a future RC4-40 or with the coming
40+88 SSL brute forceing are given below)
The problems are logistic, human error, etc, from a compute time point
of view it *really* was a full sweep of a 40 bit keyspace. And on
average you would expect to sweep in half this time.
The bulk of the work was done in under one weeks compute time, but
problems with people forgetting to acknowledge what they swept, meant
that 3 or 4 people swept the remaining key space over, which slowed
down this announce.
Here's the hall of fame, for bits/percentage swept per identifiable
contributer (this is tallied by acknowledgement, if you swept but did
not acknoweldge quickly enough or at all, that work won't show as the
last keyspace was re-swept to hurry things up. The first
acknowledgement to be recieved counts, the rest get ignored).
bits/40 percent contributer
----------------------------------------------------------------------
37.2 bits (14.063%) Jon Shekter <[email protected]>
36.4 bits (8.081%) Alvin Brattli <[email protected]>
36.1 bits (6.909%) anonymous
36.1 bits (6.836%) Dan Bailey <[email protected]>
36.1 bits (6.812%) Piete Brooks <[email protected]>
35.6 bits (4.688%) Loren Rittle <[email protected]>
35.6 bits (4.663%) Adam Back <[email protected]>
35.4 bits (4.102%) Eric Young <[email protected]>
35.4 bits (4.004%) Fred <[email protected]>
35.3 bits (3.809%) Martin Hamilton <[email protected]>
35.2 bits (3.711%) Kevin Wang <[email protected]>
35.0 bits (3.125%) Richard Martin <[email protected]>
34.7 bits (2.490%) Dan Oelke <[email protected]>
34.3 bits (1.978%) Branko Lankester
34.0 bits (1.611%) Simon McAuliffe <[email protected]>
34.0 bits (1.562%) Mike Gebis <[email protected]>
33.8 bits (1.392%) Pat Finerty <[email protected]>
33.8 bits (1.367%) <[email protected]>
33.5 bits (1.123%) Panu Rissanen <[email protected]>
33.4 bits (1.001%) Paul Bell <[email protected]>
33.3 bits (0.977%) Matt Thomlinson <[email protected]>
33.3 bits (0.952%) Will Kinney <[email protected]>
33.2 bits (0.903%) T J Hardin <[email protected]>
33.2 bits (0.879%) Patrick May <[email protected]>
32.8 bits (0.684%) Stephane Bortzmeyer <[email protected]>
32.7 bits (0.635%) anonner
32.5 bits (0.537%) Matt Pauker <[email protected]>
32.5 bits (0.537%) Ed Kern <[email protected]>
32.5 bits (0.537%) Andrew Kuchling <[email protected]>
32.5 bits (0.537%) <[email protected]>
32.4 bits (0.513%) <[email protected]>
32.3 bits (0.488%) Jon Baber <[email protected]>
32.2 bits (0.439%) Bryce Boland <[email protected]>
32.0 bits (0.391%) Thad Beier <[email protected]>
32.0 bits (0.391%) Per Stoltze <[email protected]>
32.0 bits (0.391%) Glenn Powers <[email protected]>
32.0 bits (0.391%) <[email protected]>
31.8 bits (0.342%) Mike Bailey <[email protected]>
31.7 bits (0.317%) Robert Hayden <[email protected]>
31.7 bits (0.317%) John Limpert <[email protected]>
31.6 bits (0.293%) Opus
31.6 bits (0.293%) Mark Rogaski <[email protected]>
31.6 bits (0.293%) <[email protected]>
31.5 bits (0.269%) Michael Bacon <[email protected]>
31.3 bits (0.244%) Jim Gillogly <[email protected]>
31.3 bits (0.244%) David Zuhn <[email protected]>
31.2 bits (0.220%) Russell Ross <[email protected]>
31.2 bits (0.220%) Don Kitchen <[email protected]>
31.0 bits (0.195%) Scott Renfro <[email protected]>
31.0 bits (0.195%) Planar <[email protected]>
30.8 bits (0.171%) Matt <[email protected]>
30.8 bits (0.171%) Joe Thomas <[email protected]>
30.8 bits (0.171%) Adrian Thomson <[email protected]>
30.6 bits (0.146%) Michael Axelrod <[email protected]>
30.6 bits (0.146%) Mark Eichin <[email protected]>
30.6 bits (0.146%) Jason Burrell <[email protected]>
30.3 bits (0.122%) Will Ware <[email protected]>
30.3 bits (0.122%) Kevin Maher <[email protected]>
30.3 bits (0.122%) Josh Sled <[email protected]>
30.3 bits (0.122%) Checkered Daemon <[email protected]>
30.3 bits (0.122%) Andrew Roos <[email protected]>
30.0 bits (0.098%) Jason Weisberger <[email protected]>
30.0 bits (0.098%) <[email protected]>
30.0 bits (0.098%) <[email protected]>
29.6 bits (0.073%) Mark Grant <[email protected]>
29.6 bits (0.073%) Lou Poppler <[email protected]>
29.6 bits (0.073%) Edwin de Graaf <[email protected]>
29.6 bits (0.073%) David Conrad <[email protected]>
29.6 bits (0.073%) Dan Tauber <[email protected]>
29.6 bits (0.073%) Alexandra Griffin <[email protected]>
29.6 bits (0.073%) <[email protected]>
29.6 bits (0.073%) <[email protected]>
29.0 bits (0.049%) Stuart <[email protected]>
29.0 bits (0.049%) Pekka Riiali <[email protected]>
29.0 bits (0.049%) Jeffrey Ollie <[email protected]>
29.0 bits (0.049%) James Hightower <[email protected]>
29.0 bits (0.049%) Hadmut Danisch <[email protected]>
29.0 bits (0.049%) Bob Snyder <[email protected]>
29.0 bits (0.049%) <[email protected]>
28.0 bits (0.024%) Sang Hahn <[email protected]>
28.0 bits (0.024%) Roy Silvernail <[email protected]>
28.0 bits (0.024%) Ollivier Robert <[email protected]>
28.0 bits (0.024%) Lucky Green <[email protected]>
28.0 bits (0.024%) L Futplex McCarthy <[email protected]>
28.0 bits (0.024%) Jeff Licquia <[email protected]>
28.0 bits (0.024%) J Francois <[email protected]>
28.0 bits (0.024%) Brian LaMacchia <[email protected]>
28.0 bits (0.024%) Andy Brown <[email protected]>
28.0 bits (0.024%) Adam Morrison <[email protected]>
28.0 bits (0.024%) <[email protected]>
----------------------------------------------------------------------
40.0 bits (100.000%) 89 cpunks + x * anonners in 1 weeks compute
Report is on the brute-rc4.html page also:
http://dcs.ex.ac.uk/~aba/brute-rc4.html
Problems.
---------
But, briefly these are the things which may be responsible for the
failure to find a key:
a) We weren't sure if we had a known plaintext / ciphertext pair
This due to lack of Microsoft Access specs, this was known from
the begining, but we thought we'd try it and see.
b) Eeek! There was a bug in bruterc4.c for some time which affected
Alphas, and possibly other BSD machines. This meant keyspace
wasn't being searched when the -v option was used.
c) Some people reported that their browser / uuencode software
combination meant that cutting and pasting of the uuencode plain
text and cipher text files was silently failing due to extra spaces
inserted by a flawed pasting operation.
d) Human error - it is possible that some keys were unswept - by
accident.
e) Malicious humans - we don't know, but think this was not a problem.
Solutions.
----------
Proposed solutions for future brute forcing efforts (such as the
upcoming SSL effort), for respective points above:
a) Need better spec of MA, or more experimentation / reverse
engineering.
For SSL this is not a problem as the SSL specs are openly available
and very detailed.
b) Write bug free software :-) Test more rigourously on multiple unixs
and architectures with a brief test run.
c) Use hex numbers in a config file. Ie don't use uuencode on web page.
d) We're going to have the programs (bruteRC4.c and bruteSSL.c) produce
a checksum on completion. Acknowledgements of swept keyspace must be
with checksum. Crude check to reduce chances of mistyped big hex nums.
Represent the key space as a 4 digit hex number like this: 1a23, in
terms of 24 bit keyspaces, and represent keyspace to sweep in terms
of numbers of those, lots of people had difficulty reasoning in log
base2 for bits.
e) Do nothing yet. If we get lots of compute and it proves to be a
problem perhaps implement some redundancy into the system.
Coming soon brute force attempt on Hal Finney's brute of 40+88bit SSL.
Watch this space, several cypherpunks are hard at work optimising
their bruteSSL.c code, and also writing farming software via a system
of servers connected via sockets. The WWW page doler will still be
available for those with out direct IP.
Hal Finney's SSL challenge is here:
http://www.portal.com/~hfinney/sslchal.html
More on SSL later, but we hoped to give the SSL one a wider announce
in sci.crypt, and see how *fast* we can brute 40 bit keyspace.
Hope to see your compute in the brute SSL effort when it is announced,
Adam
--
HAVE *YOU* EXPORTED A CRYPTO SYSTEM TODAY? --> http://dcs.ex.ac.uk/~aba/rsa/
--rsa--------------------------------8<-------------------------------------
#!/usr/local/bin/perl -s-- -export-a-crypto-system-sig -RSA-in-3-lines-PERL
($k,$n)=@ARGV;$m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%
Sa2/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||die"$0 [-d] k n\n")&~1)/2)
-------------------------------------8<-------------------------------------
TRY: echo squeamish ossifrage | rsa -e 3 7537d365 | rsa -d 4e243e33 7537d365