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 <jshekter@alias.com> 36.4 bits (8.081%) Alvin Brattli <alvin@phys.uit.no> 36.1 bits (6.909%) anonymous 36.1 bits (6.836%) Dan Bailey <merzbow@ibm.net> 36.1 bits (6.812%) Piete Brooks <Piete.Brooks@cl.cam.ac.uk> 35.6 bits (4.688%) Loren Rittle <rittle@comm.mot.com> 35.6 bits (4.663%) Adam Back <aba@dcs.ex.ac.uk> 35.4 bits (4.102%) Eric Young <eay@mincom.oz.au> 35.4 bits (4.004%) Fred <admin@dcwill.com> 35.3 bits (3.809%) Martin Hamilton <martin@mrrl.lut.ac.uk> 35.2 bits (3.711%) Kevin Wang <kwang@blackbox.punk.net> 35.0 bits (3.125%) Richard Martin <rmartin@alias.com> 34.7 bits (2.490%) Dan Oelke <droelke@aud.alcatel.com> 34.3 bits (1.978%) Branko Lankester 34.0 bits (1.611%) Simon McAuliffe <sai@comp.vuw.ac.nz> 34.0 bits (1.562%) Mike Gebis <m-gebis@uiuc.edu> 33.8 bits (1.392%) Pat Finerty <zinc@zifi.genetics.utah.edu> 33.8 bits (1.367%) <hodgeman@csd.uwm.edu> 33.5 bits (1.123%) Panu Rissanen <Panu.Rissanen@lut.fi> 33.4 bits (1.001%) Paul Bell <pjb@23kgroup.com> 33.3 bits (0.977%) Matt Thomlinson <phantom@u.washington.edu> 33.3 bits (0.952%) Will Kinney <kinney@colorado.edu> 33.2 bits (0.903%) T J Hardin <hardin@cyberspace.com> 33.2 bits (0.879%) Patrick May <pjm@ionia.engr.sgi.com> 32.8 bits (0.684%) Stephane Bortzmeyer <bortzmeyer@cnam.fr> 32.7 bits (0.635%) anonner 32.5 bits (0.537%) Matt Pauker <mpauker@peganet.com> 32.5 bits (0.537%) Ed Kern <ejk@digex.net> 32.5 bits (0.537%) Andrew Kuchling <andrewk@cst.ca> 32.5 bits (0.537%) <rmtodd@mailhost.ecn.uoknor.edu> 32.4 bits (0.513%) <somogyi@digmedia.com> 32.3 bits (0.488%) Jon Baber <jbaber@mi.leeds.ac.uk> 32.2 bits (0.439%) Bryce Boland <bryce@cybernet.co.nz> 32.0 bits (0.391%) Thad Beier <thad@thresher.uucp.netcom.com> 32.0 bits (0.391%) Per Stoltze <stoltze@fysik.dtu.dk> 32.0 bits (0.391%) Glenn Powers <gpowers@bradley.edu> 32.0 bits (0.391%) <janzen@idacom.hp.com> 31.8 bits (0.342%) Mike Bailey <bailey@computek.net> 31.7 bits (0.317%) Robert Hayden <hayden@krypton.mankato.msus.edu> 31.7 bits (0.317%) John Limpert <johnl@radix.net> 31.6 bits (0.293%) Opus 31.6 bits (0.293%) Mark Rogaski <rogaski@phobos.lib.iup.edu> 31.6 bits (0.293%) <josh@silicon.net> 31.5 bits (0.269%) Michael Bacon <mbacon@dfw.net> 31.3 bits (0.244%) Jim Gillogly <jim@acm.org> 31.3 bits (0.244%) David Zuhn <zoo@armadillo.com> 31.2 bits (0.220%) Russell Ross <rross@sci.dixie.edu> 31.2 bits (0.220%) Don Kitchen <don@cs.byu.edu> 31.0 bits (0.195%) Scott Renfro <csylvix!srenfro@cuok.cameron.edu> 31.0 bits (0.195%) Planar <Damien.Doligez@inria.fr> 30.8 bits (0.171%) Matt <panzer@dhp.com> 30.8 bits (0.171%) Joe Thomas <jthomas@access.digex.net> 30.8 bits (0.171%) Adrian Thomson <a.thomson@nexor.co.uk> 30.6 bits (0.146%) Michael Axelrod <mja@cacs.usl.edu> 30.6 bits (0.146%) Mark Eichin <mark@kitten.gen.ma.us> 30.6 bits (0.146%) Jason Burrell <jburrell@crl.com> 30.3 bits (0.122%) Will Ware <wware@world.std.com> 30.3 bits (0.122%) Kevin Maher <kmaher@ucsd.edu> 30.3 bits (0.122%) Josh Sled <jsled@cello.gina.calstate.edu> 30.3 bits (0.122%) Checkered Daemon <cdaemon@goblin.punk.net> 30.3 bits (0.122%) Andrew Roos <andrewr@realtime.co.za> 30.0 bits (0.098%) Jason Weisberger <jweis@primenet.com> 30.0 bits (0.098%) <pdlamb@iquest.com> 30.0 bits (0.098%) <matt@comp.vuw.ac.nz> 29.6 bits (0.073%) Mark Grant <mark@unicorn.com> 29.6 bits (0.073%) Lou Poppler <lwp@mail.msen.com> 29.6 bits (0.073%) Edwin de Graaf <graaf@iaehv.nl> 29.6 bits (0.073%) David Conrad <conrad@detroit.freenet.org> 29.6 bits (0.073%) Dan Tauber <dat@netcom.com> 29.6 bits (0.073%) Alexandra Griffin <acg@kzin.cen.ufl.edu> 29.6 bits (0.073%) <pkronenw@erc.cat.syr.edu> 29.6 bits (0.073%) <ghazelwo@cs.oberlin.edu> 29.0 bits (0.049%) Stuart <stu@nemesis.wimsey.com> 29.0 bits (0.049%) Pekka Riiali <Pekka.Riiali@lut.fi> 29.0 bits (0.049%) Jeffrey Ollie <jeffo@noc.netins.net> 29.0 bits (0.049%) James Hightower <jamesh@netcom.com> 29.0 bits (0.049%) Hadmut Danisch <danisch@ira.uka.de> 29.0 bits (0.049%) Bob Snyder <rsnyder@janet.advsys.com> 29.0 bits (0.049%) <stevet@smeg.net4.io.org> 28.0 bits (0.024%) Sang Hahn <sghahn@math1.kaist.ac.kr> 28.0 bits (0.024%) Roy Silvernail <roy@cybrspc.mn.org> 28.0 bits (0.024%) Ollivier Robert <roberto@keltia.freenix.fr> 28.0 bits (0.024%) Lucky Green <shamrock@netcom.com> 28.0 bits (0.024%) L Futplex McCarthy <futplex@pseudonym.com> 28.0 bits (0.024%) Jeff Licquia <jalicqui@prairienet.org> 28.0 bits (0.024%) J Francois <frenchie@magus.dgsys.com> 28.0 bits (0.024%) Brian LaMacchia <bal@mit.edu> 28.0 bits (0.024%) Andy Brown <a.brown@nexor.co.uk> 28.0 bits (0.024%) Adam Morrison <adam@math.tau.ac.il> 28.0 bits (0.024%) <mikew@nersc.gov> ---------------------------------------------------------------------- 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