ANNOUNCE: bruteRC4, 40 bits all swept

aba at dcs.exeter.ac.uk aba at dcs.exeter.ac.uk
Wed Jul 19 11:32:29 PDT 1995



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







More information about the cypherpunks-legacy mailing list