From owner-cypherpunks@toad.com Fri Mar 17 00:41:48 1995 Date: Thu, 16 Mar 1995 08:35:19 -0500 From: der Mouse To: cypherpunks@toad.com Subject: Re: Lotus Notes Encryption Strategies Sender: owner-cypherpunks@toad.com Precedence: bulk I recently received a copy of some code alleging to be source to the RC4 cryptosystem. On reading over it, I notice a few things. I'm not on cypherpunks, so I don't know whether any of these have been mentioned yet, but since the person I got it from sent it along without comment, and appears to be on cypherpunks, I suspect not. First is that it is catastrophically vulnerable to a known-plaintext attack, since it is just an XOR of the cleartext with a data stream depending on nothing but the key. Thus, even without deducing all the internal state, known-plaintext XOR corresponding-ciphertext gives you a data stream you can XOR in to decrypt any message encrypted with the same key. (Deducing the internal state and thus extending the key stream may be practical, but it's not immediately obvious to me how to go about it.) Second is that the code I received contains a latent bug. Anyone using it - including RSA, if this is their source (as opposed to someone else's reconstruction of it) - should be aware of this. > xorIndex = state[x] + (state[y]) % 256; > buffer_ptr[counter] ^= state[xorIndex]; This attempts to index into state[] with a value that can be as high as 255+254, or 509. But state[] is a 256-entry array. The first line probably should read xorIndex = (state[x] + state[y]) % 256; The reason this bug is only latent is that xorIndex is an "unsigned char". Thus, my replacement line is what is actually getting executed, assuming unsigned char has eight bits (as on most current machines), which is why I'm fairly sure it's correct. But on a machine/compiler where unsigned char is wider, this will cause trouble. der Mouse mouse@collatz.mcrcim.mcgill.edu From owner-cypherpunks@toad.com Fri Mar 17 00:42:01 1995 From: "L. McCarthy" Subject: Re: RC4 Cryptanalysis To: cypherpunks@toad.com Date: Thu, 16 Mar 1995 15:12:35 -0500 (EST) Reply-To: cypherpunks@toad.com In-Reply-To: <199503161335.IAA12780@Collatz.McRCIM.McGill.EDU> from "der Mouse" at Mar 16, 95 08:35:19 am X-Mailer: ELM [version 2.4 PL22] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 2434 Sender: owner-cypherpunks@toad.com Precedence: bulk der Mouse writes: > First is that it is catastrophically vulnerable to a known-plaintext > attack, since it is just an XOR of the cleartext with a data stream > depending on nothing but the key. Thus, even without deducing all the > internal state, known-plaintext XOR corresponding-ciphertext gives you > a data stream you can XOR in to decrypt any message encrypted with the > same key. Yes, this has been observed by a number of people: --- begin included article ------------------------------------------ Newsgroups: sci.crypt,alt.security,comp.security.misc,alt.privacy From: jamesd@netcom.com (James A. Donald) Subject: Re: RC4 Algorithm revealed. Date: Wed, 14 Sep 1994 17:15:23 GMT The RC4 cypher seems to me to vulnerable to a known plain text attack, and therefore should only be used in protocols where a random session key is generated for each session. This of course requires a source of truly random numbers, which is often inconvenient. --- end included article -------------------------------------------- --- begin included article excerpt ---------------------------------- Newsgroups: sci.crypt From: mpj@netcom.com (Michael Paul Johnson) Subject: Re: RC4 ? Date: Sat, 17 Sep 1994 00:18:13 GMT [...] 1. It is a pure stream cipher, with no dependencies on the data. This means that it is subject to a trivial known plain text attack if you ever re-use a key. In practical terms, this means that the only thing you should ever use a re-usable key for is to encrypt a random (or strong pseudorandom) key at the beginning of the message. You should then switch to the new session key for the remainder of the file. This results in some data expansion, but only by the length of the session key. This is not likely to be a problem in most applications. [...] --- end included article excerpt ------------------------------------ [...] > xorIndex = state[x] + (state[y]) % 256; [...should be...] > xorIndex = (state[x] + state[y]) % 256; This too has been observed by several people. The source code originally anonymously sent to the Cypherpunks list and posted to sci.crypt (on 94/09/13) contained this bug. A few months ago I wrote a short report on Alleged-RC4, and in the process I culled from the archives a more-or-less complete file of sci.crypt articles up to that time on the subject. If anyone would like a copy of this filtered RC4 archive, let me know. -L. Futplex McCarthy From owner-bugtraq@fc.net Sun Mar 26 05:19:31 1995 From: jfh@rpp386.cactus.org (John F. Haugh II) Subject: Re: Non-PK encryption not vulnerable via low key length?! To: smb@research.att.com Date: Sat, 25 Mar 95 8:18:39 CST Cc: softtest@wu1.wl.aecl.ca, elfchief@lupine.org, entropy@IntNet.net, vishy@sph.umich.edu, bugtraq@fc.net In-Reply-To: <199503171535.JAA09068@freeside.fc.net>; from "smb@research.att.com" at Mar 17, 95 10:11 am X-Mailer: ELM [version 2.3 PL11] Sender: owner-bugtraq@fc.net Precedence: bulk > RC2 and RC4 are both trade secrets of RSA Data Security, Inc. A > bootleg version of RC4 was posted to the net last year; from everything > I've heard, including some comments from Jim Bidzos, the president of > RSADSI, it was the real thing. If they are both trade secrets, then they aren't elligible for patent protection -- sauce for the gander. Does anyone on this list have the RC4 source or a pointer to it? -- John F. Haugh II [ NRA-ILA ] [ Kill Barney ] !'s: ...!cs.utexas.edu!rpp386!jfh Ma Bell: (512) 251-2151 [GOP][DoF #17][PADI][ENTJ] @'s: jfh@rpp386.cactus.org From owner-bugtraq@fc.net Sun Mar 26 07:24:58 1995 Subject: Re: Non-PK encryption not vulnerable via low key length?! To: jfh@rpp386.cactus.org (John F. Haugh II) Date: Sat, 25 Mar 1995 12:30:12 -0800 (PST) Cc: smb@research.att.com, softtest@wu1.wl.aecl.ca, elfchief@lupine.org, entropy@IntNet.net, vishy@sph.umich.edu, bugtraq@fc.net In-Reply-To: <9503251418.AA13113@rpp386.cactus.org> from "John F. Haugh II" at Mar 25, 95 08:18:39 am From: sameer Pgp-Strong-Print: 3C AE E4 00 C2 6A 81 FF 49 4E EE 0C CD CD 1D 80 X-Mailer: ELM [version 2.4 PL20] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 310 Sender: owner-bugtraq@fc.net Precedence: bulk ftp.csua.berkeley.edu:/pub/cypherpunks/ciphers/rc4.c ftp.csua.berkeley.edu:/pub/cypherpunks/ciphers/rc4.h -- sameer Voice: 510-841-2014 Network Administrator Pager: 510-321-1014 Community ConneXion: The NEXUS-Berkeley Dialin: 510-549-1383 http://www.c2.org (or login as "guest") sameer@c2.org From owner-cypherpunks@toad.com Mon Jun 12 11:53:22 1995 From: aba@atlas.ex.ac.uk Date: Mon, 12 Jun 95 10:53:22 +0100 To: cypherpunks@toad.com Cc: aba@atlas.ex.ac.uk Subject: Re: Perl-RSA encryption test Sender: owner-cypherpunks@toad.com Precedence: bulk Anonymous User writes: > This is encrypted for Adam Back using his PGP key. I hope to see a > decryption here. > > begin 666 perl-rsa-mail > M:[KVV!4?N\^20F6D%A]"#_]:N4XRMVQKD;M$)^DZ/$<-:L7C,G@\U>!Q8R$) > MI_[@RMO9" TLR=A\^FVDS]%DI^PJ/XN67-LR=Y?Q\))84O"NN$DAZ0BDF%'[ > F!'94T^_MW2FX(,PKJ]"VT%7M<;12S6BJ_"50.W7_GAR$5+O0J^XA > > end Heh, okay: % uudecode prsa % rsa -d [d] [n] < perl-rsa-mail Anonymous User wrote (plain text): > My chimp chews nuts. Ripe seeds need land. Try my juicy tobacco. > How much entropy in that? quite a lot I would have thought :-) The entropy point is interesting tho', as there is a problem with pure RSA as implemented by perl-rsa which can be improved in an analogous way to the way PGP manages things, by using the RSA part to encrypt a random session key, and then encrypting with a symmetric key cypher to encrypt the text. Fortunately I have a 3 line RC4 in perl handy for just such eventualities: #!/usr/local/bin/perl -- -export-a-crypto-system-sig -RC4-in-3-lines-of-PERL @k=unpack('C*',pack('H*',shift));sub S{@s[$x,$y]=@s[$y,$x];}for(@t=@s=0..255) {$y=($k[$i++]+$s[$_]+$y)%256;$x=$_;&S;$i%=@k;}$/=$x=$y=0;for(unpack('C*',<>)) {$x++;$y=($s[$x%=256]+$y)%256;&S;print pack(C,$_^=$s[($s[$x]+$s[$y])%256]);} So now you could sample your radioactive decay card to create a random session key, encode this as raw binary, pad with more random junk to just less than n in size, encrypt the padded session key with perl-rsa, then encrypt the message with RC4. Fun isn't it what you can do with a few lines of perl? The RC4 perl program is pure perl, no shells to dc. So this might be a more secure way of doing things: % pgp +makerandom=64 session % perl -e '$/=0;$s=<>;print unpack("H*",$s);' < session > hexkey % rc4 `cat hexkey` < msg > msg.rc4 % rsa -e [e] [n] session > session.rsa % uuencode session.rsa session.rsa | mail -s "session key" recipient % uuencode msg.rc4 msg.rc4 | mail -s message recipient (The pgp +makerandom thing creates 64 bytes = (512 bits) of random data in a file, this feature was only introduced in a fairly recent version of PGP, it's in pgp262, but might not be in say 2.3A). Basically the idea is that you want some secure random numbers. The second stage is because RC4 is setup to expect keys in hex rather than raw binary, it converts the session into hex representation. 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 From: Jim Gillogly Reply-To: jim@acm.org Date: Wed, 05 Jul 95 09:40:27 PDT Sender: owner-cypherpunks@toad.com Precedence: bulk > Andy Brown writes: > Does anyone have timings for how long, say, a Pentium-100 would take to > do an exhaustive search on RC4-40? Matthias Bruestle estimated 2.5 Pentium-120 years for RC4-40. YMMV. Jim Gillogly Mersday, 12 Afterlithe S.R. 1995, 16:40 From owner-cypherpunks@toad.com Wed Jul 5 17:47:19 1995 Date: Wed, 05 Jul 95 21:47:19 EDT From: merzbow@ibm.net (Dan Bailey) Reply-To: merzbow@ibm.net (Dan Bailey) To: jim@acm.org Cc: cypherpunks@toad.com X-Mailer: PMMail (v1.05 UNREGISTERED SHAREWARE) Subject: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk On Wed, 05 Jul 95 09:40:27 PDT you wrote: >> Andy Brown writes: >> Does anyone have timings for how long, say, a Pentium-100 would take to >> do an exhaustive search on RC4-40? > >Matthias Bruestle estimated 2.5 Pentium-120 years for RC4-40. YMMV. Can someone pass me a pointer to cryptanalysis of RC4? I'm curious to see source code for mounting a known-plaintext attack on a particular key. Specifically, I want the key Microsoft Access uses to encrypt its databases. (Yes, there's only one) I mainly would like to demonstrate to my clients the need for *real* crypto instead of the toys Microsoft includes with their products. In particular, I'd like to do the following: Using up to 9 200MHz DEC Alphas running Windows NT, Take a (or several) very large (>150 MB) database(s) A with fully known plaintext. Encrypt A with the only available key, K. Compare A and Ek(A) until the key is found. Alternately, I could use the RC4 implementation in Crypto++ with a much smaller plaintext to keep trying 40-bit keys until I find K. Unfortunately, even with 9 Alphas at my disposal, this should still take quite a while. According to Schneier, "assuming that cryptanalysts can test one million keys per second, it will take them 12.7 days to find the correct key." (260) Any estimates as to whether the brute-force approach is worth trying? Dan ****************************************************************************** Vote Speaker Newt Gingrich for President!! Dan Bailey Worcester Polytechnic Institute, class of 1997. merzbow@ibm.net ****************************************************************************** From owner-cypherpunks@toad.com Thu Jul 6 04:41:31 1995 Content-Type: text/plain Mime-Version: 1.0 (NeXT Mail 3.3 v112.1) From: Andrew Loewenstern Date: Thu, 6 Jul 95 09:41:31 -0500 To: merzbow@ibm.net (Dan Bailey) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Cc: cypherpunks@toad.com Sender: owner-cypherpunks@toad.com Precedence: bulk > Alternately, I could use the RC4 implementation in Crypto++ with > a much smaller plaintext to keep trying 40-bit keys until I find > K. Unfortunately, even with 9 Alphas at my disposal, this should > still take quite a while. According to Schneier, "assuming that > cryptanalysts can test one million keys per second, it will take > them 12.7 days to find the correct key." (260) Any estimates as > to whether the brute-force approach is worth trying? If what you say is true (that there is a single RC4 key embedded in Access), why not just use a debugger/disassembler to find the key when it encrypts? Sure sounds a lot easier (and cheaper) than brute-force with 9 alphas or any sort of real cryptanalysis. andrew From owner-cypherpunks@toad.com Thu Jul 6 17:16:56 1995 From: aba@atlas.ex.ac.uk Date: Thu, 6 Jul 95 16:16:56 +0100 To: merzbow@ibm.net (Dan Bailey) Cc: aba@atlas.ex.ac.uk, cypherpunks@toad.com In-Reply-To: merzbow@ibm.net's message of 5 Jul 1995 21:53:32 -0400 Subject: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk Dan Bailey writes: > Can someone pass me a pointer to cryptanalysis of RC4? I'm curious > to see source code for mounting a known-plaintext attack on a > particular key. Specifically, I want the key Microsoft Access uses > to encrypt its databases. (Yes, there's only one) I mainly would > like to demonstrate to my clients the need for *real* crypto instead > of the toys Microsoft includes with their products. A fun project! Show up micro$oft for peddling snake oil at the same time. I Don't know if anyone has a short-cut using lots of chosen plaintexts, but brute force may be enough. > Alternately, I could use the RC4 implementation in Crypto++ with a > much smaller plaintext to keep trying 40-bit keys until I find K. > Unfortunately, even with 9 Alphas at my disposal, this should still > take quite a while. According to Schneier, "assuming that > cryptanalysts can test one million keys per second, it will take > them 12.7 days to find the correct key." (260) Any estimates as to > whether the brute-force approach is worth trying? Here's let's try it out. I hacked up this brute forcer from what you describe, and I get 8k keys/sec on a 100 Mhz Indy. (Program included below as it's smallish.) Assuming your alphas are twice the speed, and as you have 9 of them, here, that becomes: 16k keys/sec per alpha processor and 144k keys/sec on all 9 alpha processors For a keyspace of 40 bits = 1099511627776 that translates to: 88 days or 44 days expected (if you get lucky.) Not bad. With a few volunteers you could get that down to a week or so. Maybe we could have a group effort, someone offering to dole out sections of keyspace to search in email. Like a small scale RSA129 project. Let me know how many keys/sec you get out of your Alphas, or anyone else with any hot boxes, nice to have a figure for P100, HPs, SPARC 10 etc. Use this perl RC4 to demo that it works: #!/usr/local/bin/perl -- -export-a-crypto-system-sig -RC4-in-3-lines-of-PERL @k=unpack('C*',pack('H*',shift));sub S{@s[$x,$y]=@s[$y,$x];}for(@t=@s=0..255) {$y=($k[$i++]+$s[$_]+$y)%256;$x=$_;&S;$i%=@k;}$/=$x=$y=0;for(unpack('C*',<>)) {$x++;$y=($s[$x%=256]+$y)%256;&S;print pack(C,$_^=$s[($s[$x]+$s[$y])%256]);} I did this: % cc -O2 -o brute bruterc4.c % cat > known hello world ^D % rc4 0000001234 < known > cypher % brute known cypher 0 16 start-key: 0000000000 iterations: 65536 known-text-size: 12 0x0000000123 Of course it finds that nearly instantly as it only has to search 0x123 = 292 keys. If you feed it some junk or start it off in the wrong place, then you can use time to tell you how long it would take (on unix at least, haven't a clue on NT): % time brc4 known cypher 0000100000 16 start-key: 0000100000 iterations: 65536 known-text-size: 12 From owner-cypherpunks@toad.com Thu Jul 6 18:15:37 1995 From: aba@atlas.ex.ac.uk Date: Thu, 6 Jul 95 17:15:37 +0100 To: droelke@com.alcatel.aud.spirit Cc: merzbow@net.ibm, aba@atlas.ex.ac.uk, cypherpunks@toad.com In-Reply-To: <9507061603.AA27772@spirit.aud.alcatel.com> (droelke@com.alcatel.aud.spirit) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk Hi Dan, > Could you email me (and /or the cypherpunks list) the > code fore bruterc4.c or a web/ftp pointer to it. Damn. My post got truncated somehow, maybe an editor error, I'll cc it now. > I have a set of Sparcs (5s, 10s & 20s) that I can throw at such a > problem :-) Cool, we'll have a team effort going soon. All we need now is a sample uuencoded known text, and uuencoded cyphertext from the other Dan, and we'll be away. I sussed what happened to my other post btw. it had a single '.' on a line on its own about half way down, immediately where it got cut off! Some unfriendly mailer must have decided that was the end of the text. Right, so reposting (sans offending . as printed by program to indicate progress :-( ): ======================================================================== Here's let's try it out. I hacked up this brute forcer from what you describe, and I get 8k keys/sec on a 100 Mhz Indy. (Program included below as it's smallish.) Assuming your alphas are twice the speed, and as you have 9 of them, here, that becomes: 16k keys/sec per alpha processor and 144k keys/sec on all 9 alpha processors For a keyspace of 40 bits = 1099511627776 that translates to: 88 days or 44 days expected (if you get lucky.) Not bad. With a few volunteers you could get that down to a week or so. Maybe we could have a group effort, someone offering to dole out sections of keyspace to search in email. Like a small scale RSA129 project. Let me know how many keys/sec you get out of your Alphas, or anyone else with any hot boxes, nice to have a figure for P100, HPs, SPARC 10 etc. Use this perl RC4 to demo that it works: #!/usr/local/bin/perl -- -export-a-crypto-system-sig -RC4-in-3-lines-of-PERL @k=unpack('C*',pack('H*',shift));sub S{@s[$x,$y]=@s[$y,$x];}for(@t=@s=0..255) {$y=($k[$i++]+$s[$_]+$y)%256;$x=$_;&S;$i%=@k;}$/=$x=$y=0;for(unpack('C*',<>)) {$x++;$y=($s[$x%=256]+$y)%256;&S;print pack(C,$_^=$s[($s[$x]+$s[$y])%256]);} I did this: % cc -O2 -o brute bruterc4.c % cat > known hello world ^D % rc4 0000001234 < known > cypher % brute known cypher 0 16 start-key: 0000000000 iterations: 65536 known-text-size: 12 0x0000000123 Of course it finds that nearly instantly as it only has to search 0x123 = 292 keys. If you feed it some junk or start it off in the wrong place, then you can use time to tell you how long it would take (on unix at least, haven't a clue on NT): % time brc4 known cypher 0000100000 16 start-key: 0000100000 iterations: 65536 known-text-size: 12 8.006u 0.046s 0:08.59 93.5% 0+0k 0+0io 1pf+0w ie, 16 bit key space searched = 65536 from key starting = 0x0000100000, so that's: 8186 keys/sec If you don't have a convienient 'time' like utility under NT, you could just sweep out a bigger key space say 20 bits = 1048576, and use wall clock time. Let me know how the Alpha stacks up, and how long you predict it will take, Adam The program as it's only 215 lines, saves uuencode/ascii armor hassles: =========================================================================== #include #include /* * Quick hacked up rc4 brute force attack program. * * (Slightly optimised, could do more) * * Gets me 8k keys/sec on a 100 Mhz SGI Indy * * Usage: * * bruterc4 start-key known cypher [keyspace] * * start-key = start brute forcing keys from this hex key * known = your known plaintext file * cypher = the plaintext file encrypted with 40 bit RC4 * keyspace = how many bits of keyspace to search (default 31) * * One dot gets printed for each 64k keys tried (every 8 seconds on Indy) * * Adam Back * */ #define KEY_SIZE 5 /* key size in bytes, ie 40 bits */ #define buf_size 1024 typedef struct rc4_key { unsigned char state[256]; unsigned char x; unsigned char y; } rc4_key; #define swap_byte(x,y) t = *(x); *(x) = *(y); *(y) = t void inc_key(char key[]) { int i; for (i=KEY_SIZE-1; i && key[i] == 255; i--) { key[i] = 0; } key[i]++; } const char* print_hex(char key[],int len) { static char space[513]; int i, lo, hi; for (i=0; istate[0]; memcpy(state,sequence,256); key->x = 0; key->y = 0; index1 = 0; index2 = 0; for(counter = 0; counter < 256; counter++) { index2 = (key_data_ptr[index1] + state[counter] + index2) % 256; swap_byte(&state[counter], &state[index2]); index1 = (index1 + 1) % key_data_len; } } int rc4_eq(unsigned char *buffer_ptr, unsigned char *known, unsigned char *cypher_txt, int buffer_len, rc4_key *key) { unsigned char t; unsigned char x; unsigned char y; unsigned char* state; unsigned char xorIndex; short counter; x = key->x; y = key->y; state = &key->state[0]; for(counter = 0; counter < buffer_len; counter++) { x = (x + 1) & 0xFF; y = (state[x] + y) & 0xFF; swap_byte(&state[x], &state[y]); xorIndex = (state[x] + state[y]) & 0xFF; buffer_ptr[counter] ^= state[xorIndex]; if (known[counter] != buffer_ptr[counter]) { memcpy(buffer_ptr,cypher_txt,counter+1); return 0; } } return 1; } int main(int argc, char* argv[]) { char data[KEY_SIZE*2+1]; char known[buf_size]; char cypher_txt[buf_size]; char try[buf_size]; char seed[256]; char digit[5]; int hex, rd,i; int n; unsigned int sweep = 1 << 31, done = 0; rc4_key key; FILE *known_fp, *cypher_txt_fp; if (argc < 4) { fprintf(stderr,"%s known cypher-txt start-key [bits-to-sweep]\n",argv[0]); exit(1); } strncpy(data,argv[3],KEY_SIZE*2); data[KEY_SIZE*2]=0; if (argc > 4) { sweep = atoi(argv[4]); if (sweep < 31) { sweep = (1 << sweep); } } n = strlen(data); if (n /* > * Quick hacked up rc4 brute force attack program. too quickly it would seem, I made a mistake with the comment > * Usage: > * > * bruterc4 start-key known cypher [keyspace] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ That should be > * bruterc4 known cypher start-key [keyspace] Also Dan Oelke says this change is necessary (it should be unsinged, I had no sign spec, so it may not work depending on the default signing of your compilers choice). > void inc_key(unsigned char key[]) --- < void inc_key(char key[]) Apart from that any volunteers to split up keyspace, Dan? you're the guy with the sample micro$oft access file, and all those nice alphas, you on for a group effort? I've had a couple of folks mail me, but I'd rather just supply the bruterc4.c software (safer for ITAR brain-deadness if there are any overseas volunteers of compute time) and let someone else (you?, another volunteer?) organise the key distribution. I was thinking maybe you could do it in sweeps of maybe 28 bits, then you could share the keys out like this (9 hour chunks on an indy): 000xxxxxxx 001xxxxxxx ... FFFxxxxxxxxx That gives 16^3 = 4096 chunks to manage. You could mail each person a few depending on what compute time they had available. Each person just does: % brute known cypher YYY0000000 28 Where YYY is the next prefix they have been given. If anyone want's fixed code (just the two changes above, comment and unsigned char fix by Dan Oelke), send me email, or look here: http://dcs.ex.ac.uk/~aba/rsabrute.c So who's organising key space? I'm in for say a set of 16 keys. 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 (message from aba on Thu, 6 Jul 95 18:34:45 +0100) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk > If anyone want's fixed code (just the two changes above, comment and > unsigned char fix by Dan Oelke), send me email, or look here: > > http://dcs.ex.ac.uk/~aba/rsabrute.c Arg! really *must* get in the habit of actually reading what I write. That should be http://dcs.ex.ac.uk/~aba/bruterc4.c of course (both work as I linked them together). Just tried it on an old SUN: SUN SPARC 4: 1489 keys/sec SGI Indy (100Mhz): 8186 keys/sec Any one have figures for other machines? Adam From owner-cypherpunks@toad.com Thu Jul 6 08:47:24 1995 Date: Thu, 6 Jul 95 13:47:24 CDT From: droelke@spirit.aud.alcatel.com (Daniel R. Oelke) To: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk As far as speed, I'll add mine to Adam's list: SUN SPARC 4: 1489 keys/sec SUN SPARC 5: 5221 keys/sec SGI Indy (100Mhz): 8186 keys/sec I am using gcc -O2 v2.6.3 and I have verified that it does find the key using Adam's rc4 Perl script. I also did a quicky profile, and found that prepare_key is called once for each attempt, and it is 57.1% of the execution time (optimization turned off). Time to see if stuff can be "cached" between calls to it... Dan ------------------------------------------------------------------ Dan Oelke Alcatel Network Systems droelke@aud.alcatel.com Richardson, TX http://spirit.aud.alcatel.com:8081/~droelke/ From owner-cypherpunks@toad.com Thu Jul 6 09:06:49 1995 From: klp@noc.cis.umn.edu X-From: klp Thu Jul 6 14:06:49 1995 remote from xserv Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: aba@atlas.ex.ac.uk Date: Thu, 6 Jul 1995 14:06:49 -0500 (CDT) Cc: merzbow@ibm.net, droelke@com.alcatel.aud.spirit, rmartin@com.alias, cypherpunks@com.toad In-Reply-To: <11331.9507061759@exe.dcs.exeter.ac.uk> from "aba@atlas.ex.ac.uk" at Jul 6, 95 06:59:31 pm X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 573 Sender: owner-cypherpunks@toad.com Precedence: bulk A little birdie told me that aba@atlas.ex.ac.uk said: > > Just tried it on an old SUN: > > SUN SPARC 4: 1489 keys/sec > SGI Indy (100Mhz): 8186 keys/sec > > Any one have figures for other machines? > CDC 4680 (EP/IX): 5346 keys/sec Sparc 10 (Solaris 5.4) 3674 keys/sec -- Kevin Prigge | Holes in whats left of my reason, CIS Consultant | holes in the knees of my blues, Computer & Information Services | odds against me been increasin' email: klp@cis.umn.edu | but I'll pull through... From owner-cypherpunks@toad.com Thu Jul 6 09:21:35 1995 From: klp@noc.cis.umn.edu Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: droelke@spirit.aud.alcatel.com (Daniel R. Oelke) Date: Thu, 6 Jul 1995 14:21:35 -0500 (CDT) Cc: cypherpunks@toad.com In-Reply-To: <9507061847.AA28914@spirit.aud.alcatel.com> from "Daniel R. Oelke" at Jul 6, 95 01:47:24 pm X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 626 Sender: owner-cypherpunks@toad.com Precedence: bulk A little birdie told me that Daniel R. Oelke said: > > > As far as speed, I'll add mine to Adam's list: > > SUN SPARC 4: 1489 keys/sec > SUN SPARC 5: 5221 keys/sec > SGI Indy (100Mhz): 8186 keys/sec > CDC 4680 (EP/IX) 5346 keys/sec SUN SPARC 10 (Solaris 5.4) 3674 keys/sec SUN SPARC 1000 (Sol 5.4) 4766 keys/sec -- Kevin Prigge | Holes in whats left of my reason, CIS Consultant | holes in the knees of my blues, Computer & Information Services | odds against me been increasin' email: klp@cis.umn.edu | but I'll pull through... From owner-cypherpunks@toad.com Thu Jul 6 12:39:07 1995 From: Glenn Powers Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: cypherpunks@toad.com Date: Thu, 6 Jul 1995 16:39:07 -0400 (EDT) In-Reply-To: <2ffc37bf25a2002@noc.cis.umn.edu> from "klp@noc.cis.umn.edu" at Jul 6, 95 02:21:35 pm X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 974 Sender: owner-cypherpunks@toad.com Precedence: bulk ^A little birdie told me that Daniel R. Oelke said: ^> ^> ^> As far as speed, I'll add mine to Adam's list: ^> ^> SUN SPARC 4: 1489 keys/sec ^> SUN SPARC 5: 5221 keys/sec ^> SGI Indy (100Mhz): 8186 keys/sec ^> ^ CDC 4680 (EP/IX) 5346 keys/sec ^ SUN SPARC 10 (Solaris 5.4) 3674 keys/sec ^ SUN SPARC 1000 (Sol 5.4) 4766 keys/sec ^ ^Kevin Prigge | Holes in whats left of my reason, (OR) SUN SPARC 10 (Sol 5.4) 6500 keys/sec (31 bit key space) [92% CPU] SUN SPARC 2 3200 keys/sec " " [??% CPU, prob. most] _____________________________ Live in fear or join the hunt. ($k,$n)=@ARGV;$m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2% Sa2/d0 Cc: cypherpunks@toad.com, aba@atlas.ex.ac.uk Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here In-Reply-To: Your message of "Fri, 07 Jul 1995 00:31:13 +0300." <199507062131.AAA17197@shadows.cs.hut.fi> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Thu, 06 Jul 1995 17:49:16 -0400 From: "Perry E. Metzger" Tatu Ylonen writes: > Any further improvements would probably require algorithmic > innovations. John Ioannidis squeezed out some additional cycles with some tricks that exploited word at a time operations. I'll ask him to remind me what they were. Perry From owner-cypherpunks@toad.com Thu Jul 6 06:31:14 1995 To: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here In-Reply-To: Your message of Thu, 06 Jul 95 14:21:35 -0500. <2ffc37bf25a2002@noc.cis.umn.edu> From: Jim Gillogly Reply-To: jim@acm.org Date: Thu, 06 Jul 95 13:31:14 PDT Sender: owner-cypherpunks@toad.com Precedence: bulk CDC 4680 (EP/IX) 5346 keys/sec Kevin Prigge CDC 4680 (EP/IX): 5346 keys/sec Kevin Prigge Intel 80486 40 MHz (Linux) 1476 keys/sec Jim Gillogly Intergraph 6480 (Clipper C400) 2529 keys/sec Paul Robichaux Intergraph TD-4 (2 x 90Mhz Pentium) 5041 keys/sec Paul Robichaux SGI Indy (100Mhz): 8186 keys/sec Adam Back SGI Indy (100Mhz): 8186 keys/sec Dan Oelke SUN SPARC 10 (Solaris 5.4) 3674 keys/sec Kevin Prigge SUN SPARC 1000 (Sol 5.4) 4766 keys/sec Kevin Prigge SUN SPARC 4: 1489 keys/sec Adam Back SUN SPARC 4: 1489 keys/sec Dan Oelke SUN SPARC 5: 5221 keys/sec Dan Oelke SUN Sparc-10 (Solaris 5.4) 3674 keys/sec Kevin Prigge SUN Sparc-20 3120 keys/sec Paul Robichaux Jim Gillogly Highday, 13 Afterlithe S.R. 1995, 20:30 From owner-cypherpunks@toad.com Fri Jul 7 03:31:13 1995 Date: Fri, 7 Jul 1995 00:31:13 +0300 From: Tatu Ylonen To: cypherpunks@toad.com, aba@atlas.ex.ac.uk Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Organization: Helsinki University of Technology, Finland Sender: owner-cypherpunks@toad.com Precedence: bulk If you are serious about brute-forcing rc4, you might first optimize the prepare_key function slightly. Eliminating the modulo operation alone doubles speed on a sparc (and probably gives major speedups on other machines as well): > index1 = (index1 + 1) % key_data_len; better be e.g. if (++index1 == key_data_len) index1 = 0; Then, using short variables is inefficient on many machines. Changing index1, index2 and counter to unsigned int again doubled performance on sparc. So far, performance has been quadrupled from the original. After these minor changes, a Sun 10/402, using only one processor, gets about 16k/sec (from the original about 4k). After some more twiddling it is now at 21k/sec on the same machine. Almost all time is still spent in prepare_key. Any further improvements would probably require algorithmic innovations. (Note: this code may not be optimal on your machine. Some of the optimations are a little machine-specific.) Below is the modified version of the code (note: this version can no longer handle arbitrary key lengths, but is hard-coded for 5 bytes). Tatu Ylonen void prepare_key(unsigned char *key_data_ptr, int key_data_len, rc4_key *key) { int i; unsigned int t, u; unsigned int index2; unsigned char* state; unsigned int counter; unsigned int k0, k1, k2, k3, k4; state = &key->state[0]; memcpy(state,sequence,256); key->x = 0; key->y = 0; index2 = 0; k0 = key_data_ptr[0]; k1 = key_data_ptr[1]; k2 = key_data_ptr[2]; k3 = key_data_ptr[3]; k4 = key_data_ptr[4]; for(counter = 0; counter < 255; counter += 5) { t = state[counter]; index2 = (index2 + k0 + t) & 0xff; u = state[index2]; state[index2] = t; state[counter] = u; t = state[counter + 1]; index2 = (index2 + k1 + t) & 0xff; u = state[index2]; state[index2] = t; state[counter + 1] = u; t = state[counter + 2]; index2 = (index2 + k2 + t) & 0xff; u = state[index2]; state[index2] = t; state[counter + 2] = u; t = state[counter + 3]; index2 = (index2 + k3 + t) & 0xff; u = state[index2]; state[index2] = t; state[counter + 3] = u; t = state[counter + 4]; index2 = (index2 + k4 + t) & 0xff; u = state[index2]; state[index2] = t; state[counter + 4] = u; } t = state[255]; index2 = (index2 + k0 + t) & 0xff; u = state[index2]; state[index2] = t; state[255] = u; } From owner-cypherpunks@toad.com Thu Jul 6 12:10:58 1995 Date: Thu, 6 Jul 1995 17:10:58 -0500 From: Phil Fraering To: droelke@spirit.aud.alcatel.com Cc: cypherpunks@toad.com In-Reply-To: Daniel R. Oelke's message of Thu, 6 Jul 95 13:47:24 CDT <9507061847.AA28914@spirit.aud.alcatel.com> Subject: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk Date: Thu, 6 Jul 95 13:47:24 CDT From: droelke@spirit.aud.alcatel.com (Daniel R. Oelke) As far as speed, I'll add mine to Adam's list: SUN SPARC 4: 1489 keys/sec SUN SPARC 5: 5221 keys/sec SGI Indy (100Mhz): 8186 keys/sec I am using gcc -O2 v2.6.3 and I have verified that it does find the key using Adam's rc4 Perl script. I also did a quicky profile, and found that prepare_key is called once for each attempt, and it is 57.1% of the execution time (optimization turned off). Time to see if stuff can be "cached" between calls to it... It's times like that that make me wish that a procedure or function could be delcared "register" or "static" in c; maybe today it would be better to declare a function "cache;" I mean, caches on the chip are probably large enough these days, not to mention L2 caches. (Does anyone here remember "register?" Oh well, at least the compilers and CPU's are supposed to do this sort of optimization automagically these days. From owner-cypherpunks@toad.com Thu Jul 6 12:14:13 1995 From: klp@noc.cis.umn.edu Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: aba@atlas.ex.ac.uk Date: Thu, 6 Jul 1995 17:14:13 -0500 (CDT) Cc: cypherpunks@toad.com In-Reply-To: <11259.9507061734@exe.dcs.exeter.ac.uk> from "aba@atlas.ex.ac.uk" at Jul 6, 95 06:34:45 pm X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 323 Sender: owner-cypherpunks@toad.com Precedence: bulk SGI Indy 134 mhz 10897 keys/sec -- Kevin Prigge | Holes in whats left of my reason, CIS Consultant | holes in the knees of my blues, Computer & Information Services | odds against me been increasin' email: klp@cis.umn.edu | but I'll pull through... From owner-cypherpunks@toad.com Thu Jul 6 12:22:18 1995 Date: Thu, 6 Jul 95 17:22:18 CDT From: droelke@spirit.aud.alcatel.com (Daniel R. Oelke) To: pgf@tyrell.net Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Cc: cypherpunks@toad.com Sender: owner-cypherpunks@toad.com Precedence: bulk > It's times like that that make me wish that a procedure or function > could be delcared "register" or "static" in c; maybe today it would be > better to declare a function "cache;" I mean, caches on the chip are > probably large enough these days, not to mention L2 caches. > > (Does anyone here remember "register?" > > Oh well, at least the compilers and CPU's are supposed to do this > sort of optimization automagically these days. "register" optimization can gain you some, but using gcc -O2 does all that for me. 99% of the time optimization can be done better by optimizing the algorithm. Try this for an optimization: Change index1 to an array of 256, with the contents 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, ...... Then - use that as the index into key_data_ptr. This removes a costly divide operation. Remove another such operation by remembering that index2 is an unsigned byte, and as such can not be > 255 - so why do the mod 256. (some compilers might catch this on their own). Doing this gives me a speed up of about 2.25x! Implementation is left as an exercise to a non-ITAR impared person. :-) Dan ------------------------------------------------------------------ Dan Oelke Alcatel Network Systems droelke@aud.alcatel.com Richardson, TX http://spirit.aud.alcatel.com:8081/~droelke/ From owner-cypherpunks@toad.com Thu Jul 6 08:57:46 1995 Date: Thu, 6 Jul 1995 15:57:46 -0700 From: pjm@ionia.engr.sgi.com (Patrick May) To: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk Jim Gillogly writes: > > CDC 4680 (EP/IX) 5346 keys/sec Kevin Prigge > CDC 4680 (EP/IX): 5346 keys/sec Kevin Prigge > Intel 80486 40 MHz (Linux) 1476 keys/sec Jim Gillogly > Intergraph 6480 (Clipper C400) 2529 keys/sec Paul Robichaux > Intergraph TD-4 (2 x 90Mhz Pentium) 5041 keys/sec Paul Robichaux > SGI Indy (100Mhz): 8186 keys/sec Adam Back > SGI Indy (100Mhz): 8186 keys/sec Dan Oelke > SUN SPARC 10 (Solaris 5.4) 3674 keys/sec Kevin Prigge > SUN SPARC 1000 (Sol 5.4) 4766 keys/sec Kevin Prigge > SUN SPARC 4: 1489 keys/sec Adam Back > SUN SPARC 4: 1489 keys/sec Dan Oelke > SUN SPARC 5: 5221 keys/sec Dan Oelke > SUN Sparc-10 (Solaris 5.4) 3674 keys/sec Kevin Prigge > SUN Sparc-20 3120 keys/sec Paul Robichaux > > Jim Gillogly > Highday, 13 Afterlithe S.R. 1995, 20:30 I got some stranger numbers: Challenge XL (4 x 200Mhz) 6687 (only one processor used) Challenge XL (8 x 150Mhz) 4927 (only one processor used) Indy (150Mhz) 4927 The bruterc4.c source was compiled with the Delta compiler using the -O2 option. Executable called as "bruterc4 junk junk 0 16" and the file junk contained the string "hello world". Who has the clear/ciphertext? pjm From owner-cypherpunks@toad.com Thu Jul 6 14:53:40 1995 From: "Richard Martin" Date: Thu, 6 Jul 1995 18:53:40 -0400 In-Reply-To: Jim Gillogly "Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here" (Jul 6, 1:31pm) References: <199507062031.NAA02255@mycroft.rand.org> X-Mailer: Z-Mail (3.2.0 26oct94 MediaMail) To: jim@acm.org, cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-cypherpunks@toad.com Precedence: bulk On Jul 6, 1:31pm, Jim Gillogly wrote: > Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here > > CDC 4680 (EP/IX) 5346 keys/sec Kevin Prigge > CDC 4680 (EP/IX): 5346 keys/sec Kevin Prigge > Intel 80486 40 MHz (Linux) 1476 keys/sec Jim Gillogly > Intergraph 6480 (Clipper C400) 2529 keys/sec Paul Robichaux > Intergraph TD-4 (2 x 90Mhz Pentium) 5041 keys/sec Paul Robichaux > SGI Indy (100Mhz): 8186 keys/sec Adam Back > SGI Indy (100Mhz): 8186 keys/sec Dan Oelke > SUN SPARC 10 (Solaris 5.4) 3674 keys/sec Kevin Prigge > SUN SPARC 1000 (Sol 5.4) 4766 keys/sec Kevin Prigge > SUN SPARC 4: 1489 keys/sec Adam Back > SUN SPARC 4: 1489 keys/sec Dan Oelke > SUN SPARC 5: 5221 keys/sec Dan Oelke > SUN Sparc-10 (Solaris 5.4) 3674 keys/sec Kevin Prigge > SUN Sparc-20 3120 keys/sec Paul Robichaux my entry: SGI Indy (134Mhz): 11094 keys/sec Richard Martin [frodo] I must be doing something wrong. Check me? Procedure: bruterc4 is compiled using -O2 to the SGI Delta compiler. Then: echo 'Hello world' > known ; rm crypt ~/bin/rc4 0000059999 < known > crypt time bruterc4 known crypt 0 16 echo '65536 5.907 / p' | dc [where 5.907 was the first number out of tcsh's time command--the user amount] Corrections would be welcomed. frodo =) -- Richard Martin Alias|Wavefront - Toronto Office [Software Developer, Games Team] rmartin@alias.com/g4frodo@cdf.toronto.edu Trinity College UofT ChemPhysCompSci 9T7+PEY=9T8 Shad Valley Waterloo 1992 From owner-cypherpunks@toad.com Thu Jul 6 12:39:20 1995 Date: Thu, 6 Jul 95 17:39:20 CDT From: droelke@spirit.aud.alcatel.com (Daniel R. Oelke) To: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk I cut some of the duplicates: CDC 4680 (EP/IX) 5346 keys/sec Kevin Prigge Intel 80486 40 MHz (Linux) 1476 keys/sec Jim Gillogly Intergraph 6480 (Clipper C400) 2529 keys/sec Paul Robichaux Intergraph TD-4 (2 x 90Mhz Pentium) 5041 keys/sec Paul Robichaux SGI Indy (100Mhz): 8186 keys/sec Adam Back SUN SPARC 10 (Solaris 5.4) 3674 keys/sec Kevin Prigge SUN SPARC 1000 (Sol 5.4) 4766 keys/sec Kevin Prigge SUN SPARC 4: 1489 keys/sec Adam Back SUN Sparc-10 (Solaris 5.4) 3674 keys/sec Kevin Prigge SUN Sparc-20 3120 keys/sec Paul Robichaux SUN SPARC 5: (Sun OS 4.1.x) 5221 keys/sec Dan Oelke SUN SPARC 5: (Sun OS 4.1.x)(w/speedup) 11640 keys/sec Dan Oelke SUN SPARC 20:(Sun OS 4.1.x)(w/speedup) 17476 keys/sec Dan Oelke My slight optimization of the code gave a 11640/5221 = 2.23 speedup factor. If you take the 90Mhz Pentium figure as a base and adjust accordingly: 5041 keys/sec * 2.23 optimization speedup * 120/90 Processsor speedup = 14988 keys/sec 2^40 keys 1 yr ---------------- x ------------- = 2.33 CPU years. 14988 keys/sec 31536000 sec This is *VERY* close to the estimate of 2.5 CPU years on a 120Mhz Pentium. Here is the line - but I lost the attribution: > Matthias Bruestle estimated 2.5 Pentium-120 years for RC4-40. YMMV. Dan ------------------------------------------------------------------ Dan Oelke Alcatel Network Systems droelke@aud.alcatel.com Richardson, TX http://spirit.aud.alcatel.com:8081/~droelke/ From owner-cypherpunks@toad.com Thu Jul 6 14:56:33 1995 To: droelke@spirit.aud.alcatel.com (Daniel R. Oelke) Cc: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here In-Reply-To: Your message of "Thu, 06 Jul 1995 17:39:20 CDT." <9507062239.AA00455@spirit.aud.alcatel.com> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Thu, 06 Jul 1995 18:56:33 -0400 From: "Perry E. Metzger" Sender: owner-cypherpunks@toad.com Precedence: bulk Daniel R. Oelke writes: > 2^40 keys 1 yr > ---------------- x ------------- = 2.33 CPU years. > 14988 keys/sec 31536000 sec You will only need 2^39th keys (average). That implies about 1.15 cpu/years. That implies this is a matter of a couple of hours work for a place with a couple thousand idle machines sitting around at night. Not very secure. Specialized hardware (not hard to build -- could even use PLAs) would make this even faster. I suspect several 40 bit RC4 crackers might be sitting in the NSA's basement, and that they don't cost more than a hundred to a couple hundred thou a pop -- cheaper than a DES cracker by far. Perry From owner-cypherpunks@toad.com Thu Jul 6 15:20:06 1995 From: Mark Hahn Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: cypherpunks@toad.com Date: Thu, 6 Jul 1995 19:20:06 -0400 (EDT) In-Reply-To: <199507062131.AAA17197@shadows.cs.hut.fi> from "Tatu Ylonen" at Jul 7, 95 00:31:13 am X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 239 Sender: owner-cypherpunks@toad.com Precedence: bulk with Tatu Ylonen's tweaks, I get: alpha 3400 3.9 16804.1 hp735/99 2.4 27306.7 linux p5/120 1.48 44281.1 regards, mark hahn. -- operator may differ from spokesperson. hahn@neurocog.lrdc.pitt.edu http://neurocog.lrdc.pitt.edu/~hahn From owner-cypherpunks@toad.com Thu Jul 6 17:17:43 1995 Date: Thu, 06 Jul 95 21:17:43 EDT From: merzbow@ibm.net (Dan Bailey) Reply-To: merzbow@ibm.net (Dan Bailey) To: andrew_loewenstern@il.us.swissbank.com Cc: cypherpunks@toad.com X-Mailer: PMMail (v1.05 UNREGISTERED SHAREWARE) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto Sender: owner-cypherpunks@toad.com Precedence: bulk On Thu, 6 Jul 95 09:41:31 -0500 you wrote: >If what you say is true (that there is a single RC4 key embedded in Access), >why not just use a debugger/disassembler to find the key when it encrypts? >Sure sounds a lot easier (and cheaper) than brute-force with 9 alphas or any >sort of real cryptanalysis. I thought about this approach, and opened MSACCESS.EXE and JETPACK.EXE up in Visual C++ and took a look at the Disassembly. Unfortunately, without debugging info or source code, it's a little hard to track down where the encryption takes place, since these are rather large file. I do know that the encryption function is called from the CompactDatabase function. I'll keep digging. Dan From owner-cypherpunks@toad.com Fri Jul 7 04:05:18 1995 From: johnl@radix.net Mime-Version: 1.0 Date: Thu, 06 Jul 95 23:05:18 +0500 To: cypherpunks@toad.com Reply-To: johnl@radix.net Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here X-Mailer: Ultimedia Mail/2 Lite, IBM T. J. Watson Research Center Content-Id: <23_71_1_805086319> Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: owner-cypherpunks@toad.com Precedence: bulk > SUN SPARC 4: 1489 keys/sec > SGI Indy (100Mhz): 8186 keys/sec > > Any one have figures for other machines? Intel 486DX4-100 3416 keys/sec OS/2 3.0, IBM C Set++ 2.1 //---------------------------------------------------------------------------- // John A. Limpert // johnl@radix.net From owner-cypherpunks@toad.com Fri Jul 7 04:48:51 1995 Mime-Version: 1.0 Date: Thu, 06 Jul 95 23:48:51 +0500 From: johnl@radix.net To: cypherpunks@toad.com Reply-To: johnl@radix.net Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here X-Mailer: Ultimedia Mail/2 Lite, IBM T. J. Watson Research Center Content-Id: <23_71_1_805088931> Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: owner-cypherpunks@toad.com Precedence: bulk With Tatu Ylonen's improved prepare_key(): Intel 486DX4-100 15650 keys/sec OS/2 3.0, IBM C Set++ 2.1 //---------------------------------------------------------------------------- // John A. Limpert // johnl@radix.net From owner-cypherpunks@toad.com Fri Jul 7 08:07:36 1995 Mime-Version: 1.0 Date: Thu, 06 Jul 95 23:20:55 From: hardin@cyberspace.com To: "Adam Back" , cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here X-Mailer: Ultimedia Mail/2 Lite, IBM T. J. Watson Research Center Content-Id: <40_62_1_805087312> Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Content-Description: Sender: owner-cypherpunks@toad.com Precedence: bulk bruterc4.c Benchmark for P100 Keysearch time Dell xps P100 [os/2 warp] using gcc -O2 bruterc4.c called as bruterc4 known cypher 0 20 known & cypher identical files containing string "hello world" 4369 keys/sec Willing to donate 9hrs/day indefinitely 1 P100 CPU for this project tjh From owner-cypherpunks@toad.com Fri Jul 7 09:08:26 1995 Mime-Version: 1.0 Date: Fri, 07 Jul 95 00:28:08 From: hardin@cyberspace.com To: "Tatu Ylonen" , "Adam Back" Cc: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here X-Mailer: Ultimedia Mail/2 Lite, IBM T. J. Watson Research Center Content-Id: <40_62_1_805091288> Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Sender: owner-cypherpunks@toad.com Precedence: bulk Tatu Ylonen's Optimization to bruterc4.c compiled on Dell XPS P100 [os/2 warp] gcc -O2 brutetaturc4.c invoked brutetaturc4 known cypher 0 20 known & cypher are text files containing "hello world" 48.5 seconds 21620 keys/sec Let's go, ready to rock & roll tjh From owner-cypherpunks@toad.com Fri Jul 7 11:21:43 1995 Date: Fri, 7 Jul 1995 10:21:43 +0100 (BST) From: Andy Brown To: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here In-Reply-To: <11259.9507061734@exe.dcs.exeter.ac.uk> Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-cypherpunks@toad.com Precedence: bulk On Thu, 6 Jul 1995 aba@dcs.exeter.ac.uk wrote: > [40 bit rc4 brute force effort tactics deleted] > I was thinking maybe you could do it in sweeps of maybe 28 bits, then > you could share the keys out like this (9 hour chunks on an indy): I'm going to knock up a nice user interface version for NT/Win95 over the weekend. I'll partially automate all the splitting of keyspace based on how the long the user is prepared to spend waiting. Source available Monday morning, weekend hangovers not withstanding. - Andy +-------------------------------------------------------------------------+ | Andrew Brown Internet Telephone +44 115 952 0585 | | PGP (2048/9611055D): 69 AA EF 72 80 7A 63 3A C0 1F 9F 66 64 02 4C 88 | +-------------------------------------------------------------------------+ From owner-cypherpunks@toad.com Fri Jul 7 02:50:51 1995 To: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here In-Reply-To: Your message of Thu, 06 Jul 95 13:31:14 -0800. <199507062031.NAA02255@mycroft.rand.org> From: Jim Gillogly Reply-To: jim@acm.org Date: Fri, 07 Jul 95 09:50:51 PDT Sender: owner-cypherpunks@toad.com Precedence: bulk With Tatu's speedup available, people announcing RC4 benchmarks should tell which version they're using. As others are reporting, I got two orders of magnitude improvement (binary orders of magnitude, of course): Intel 80486 40 MHz (Linux) (Adam) 1476 keys/sec Jim Gillogly Intel 80486 40 MHz (Linux) (Adam+Tatu) 6154 keys/sec Jim Gillogly I tried open-coding the main loop, so that there's no loop test and increment, and got almost no improvement from it. Compilers are quite nice these days compared to when I was starting out in the biz! Jim Gillogly Sterday, 14 Afterlithe S.R. 1995, 16:49 From owner-cypherpunks@toad.com Fri Jul 7 07:42:36 1995 From: Doug Hughes Date: Fri, 7 Jul 1995 12:42:36 -0500 Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: cypherpunks@toad.com In-Reply-To: <9507062222.AA00387@spirit.aud.alcatel.com> Sender: owner-cypherpunks@toad.com Precedence: bulk Sparc 670 with 4 ross 72MHZ running 4.1.3_U1 with fast mods gets 30,840 Sparc20/612 running Solaris2.3 with fast mods gets 28,339 Sparc2000 with 4 50mhz supersparc running 2.3 gets 23,831 compiler gcc -O3 -o brute brute.c -funroll-loops -finline-functions -ffast-math -- ____________________________________________________________________________ Doug Hughes Engineering Network Services System/Net Admin Auburn University doug@eng.auburn.edu "Real programmers use cat > file.as" From owner-cypherpunks@toad.com Fri Jul 7 13:11:58 1995 From: lmccarth@cs.umass.edu (L. McCarthy) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: cypherpunks@toad.com (Cypherpunks Mailing List) Date: Fri, 7 Jul 1995 17:11:58 -0400 (EDT) Reply-To: cypherpunks@toad.com (Cypherpunks Mailing List) In-Reply-To: from "Doug Hughes" at Jul 7, 95 12:42:36 pm X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 447 Sender: owner-cypherpunks@toad.com Precedence: bulk Doug Hughes writes: > compiler > gcc -O3 -o brute brute.c -funroll-loops -finline-functions -ffast-math Thanks for reminding me to read the cc man pages ! I changed the compilation options I'm using, and improved performance by about 30%. This is on a DEC 3000 Alpha: cc -migrate -O5 -o ylonen ylonen.c -D_FASTMATH 64K keys in 2.94 seconds ---> 22291 keys/s -L. Futplex McCarthy "is it any wonder I've got too much time on my hands ?" -Styx From owner-cypherpunks@toad.com Sat Jul 8 00:42:53 1995 From: aba@atlas.ex.ac.uk Date: Fri, 7 Jul 95 23:42:53 +0100 To: cypherpunks@toad.com Cc: aba@atlas.ex.ac.uk Subject: ANNOUNCE: CPUNKS KEY CRACKING RING demo Sender: owner-cypherpunks@toad.com Precedence: bulk Wrote a web page and accompanying CGI to allocate RC4 keys out, take a look: http://dcs.ex.ac.uk/~aba/brute-rc4.html DEMO ONLY Demo only so far as no-ones figured out what the correct cyphertext / plaintext interpretation is re differing sized files. Put your performance figures in: Feel free to play, take out keys etc, it stores all the keys/sec info, so I'll collate them tomorrow and add them at the bottom. When we figure out what the plaintext should be I'll reset the key allocation. If any one figures out the plaintext / cyphertext before Sat 9am GMT, feel free to take all the perl and html, and run it yourself with an annouce to cpunks. (Hope that page is accesible external, not checked the user cgi-bin invoke mechanism, admin just changed it, I'll be able to tell if it works when folks keys/sec to it). Back in 8 (hrs sleep), 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 <11331.9507061759@exe.dcs.exeter.ac.uk> Sender: owner-cypherpunks@toad.com Precedence: bulk >>>>> "A" == aba writes: A> Any one have figures for other machines? This is scary. I just benchmarked our large machine at 5371 keys/sec/processor. No big deal, right? The machine is a KSR1 with 128 processors. Given a bit of hacking to partition the key space and running the program 128 separate times would give 687590 keys/sec. That's 18.5 days to search the whole key space. (2^40 keys, right?) This machine is not cutting edge. - J< From owner-cypherpunks@toad.com Fri Jul 7 22:29:07 1995 Date: Fri, 7 Jul 1995 21:29:07 +0100 From: "Ed Carp [khijol Sysadmin]" Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here To: Jason L Tibbitts III Cc: cypherpunks@toad.com In-Reply-To: <9507080318.AA21073@tcamc.uh.edu> Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-cypherpunks@toad.com Precedence: bulk On Fri, 7 Jul 1995, Jason L Tibbitts III wrote: > >>>>> "A" == aba writes: > > A> Any one have figures for other machines? > > This is scary. I just benchmarked our large machine at 5371 > keys/sec/processor. No big deal, right? The machine is a KSR1 with 128 > processors. Given a bit of hacking to partition the key space and running > the program 128 separate times would give 687590 keys/sec. That's 18.5 > days to search the whole key space. (2^40 keys, right?) This machine is > not cutting edge. I seriously doubt that you'd get anywhere near that number of keys per second. The machine would spend a significant amount of time context switching, so it's conceviable that you wouldn't even get your original throughput. I do wonder, however, if running multiple processes would give an increase - and if so, how much. Probably not much, but they're doing amazing things with computers these days. ;) -- Ed Carp, N7EKG Ed.Carp@linux.org, ecarp@netcom.com 801/534-8857 voicemail 801/460-1883 digital pager Finger ecarp@netcom.com for PGP 2.5 public key an88744@anon.penet.fi Q. What's the trouble with writing an MS-DOS program to emulate Clinton? A. Figuring out what to do with the other 639K of memory. From owner-cypherpunks@toad.com Sat Jul 8 05:00:39 1995 Date: Fri, 07 Jul 1995 23:00:39 +0600 From: tibbs@sina.tcamc.uh.edu (Jason L Tibbitts III) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here In-Reply-To: "Ed Carp [khijol Sysadmin]"'s message of Fri, 7 Jul 1995 21:29:07 +0100 To: cypherpunks@toad.com Cc: "Ed Carp [khijol Sysadmin]" Content-Transfer-Encoding: 7BIT Content-Length: 1125 References: <9507080318.AA21073@tcamc.uh.edu> Sender: owner-cypherpunks@toad.com Precedence: bulk >>>>> "EC" == Ed Carp [khijol Sysadmin] writes: EC> I seriously doubt that you'd get anywhere near that number of keys per EC> second. The machine would spend a significant amount of time context EC> switching, so it's conceviable that you wouldn't even get your original EC> throughput. Huh? The machine has 128 separate processors. The memory system is quite odd, but for this purpose assume each processor has it's own memory. So the performance is similar to running the program on 128 separate workstations. Running 128 threads requires no context switches except the usual ones for OS calls. EC> I do wonder, however, if running multiple processes would give an EC> increase - and if so, how much. I just did it on four processors. It's linear (4x as fast), as should be expected since the problem is embarrassingly parallel. If someone wants to rewrite the thing in fortran I'll run it through a parallelizing compiler. ^_^ --- Jason L. Tibbitts III - tibbs@uh.edu - 713/743-8687 - 221SR1 System Admin: Texas Center for Advanced Molecular Computation 1994 PC800 "Kuroneko" DoD# 1723 From owner-cypherpunks@toad.com Fri Jul 7 20:56:25 1995 Date: Sat, 8 Jul 95 01:56:25 CDT From: Loren James Rittle To: tibbs@sina.tcamc.uh.edu Cc: cypherpunks@toad.com, aba@atlas.ex.ac.uk In-Reply-To: <9507080318.AA21073@tcamc.uh.edu> (tibbs@sina.tcamc.uh.edu) Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Reply-To: rittle@comm.mot.com Comments: Hyperbole mail buttons accepted, v3.16. Sender: owner-cypherpunks@toad.com Precedence: bulk >Date: Fri, 07 Jul 1995 22:18:02 +0600 >From: tibbs@sina.tcamc.uh.edu (Jason L Tibbitts III) >This is scary. I just benchmarked our large machine at 5371 >keys/sec/processor. No big deal, right? The machine is a KSR1 with 128 >processors. Given a bit of hacking to partition the key space and running >the program 128 separate times would give 687590 keys/sec. That's 18.5 >days to search the whole key space. (2^40 keys, right?) This machine is >not cutting edge. >Date: Fri, 7 Jul 1995 21:29:07 +0100 >From: "Ed Carp [khijol Sysadmin]" >I seriously doubt that you'd get anywhere near that number of keys per >second. The machine would spend a significant amount of time context >switching, so it's conceviable that you wouldn't even get your original >throughput. I do wonder, however, if running multiple processes would >give an increase - and if so, how much. Probably not much, but they're >doing amazing things with computers these days. ;) I just benchmarked a key-hack farm of `32 sparcstation 10/20s' at just under *750,000 keys/sec* (luckily, we can use coarse-grain parallelism :-). I figure my initial chunk of 33 bits of space will be checked in between 3 and 3 1/2 hours (maybe less if having only 8 bytes of plain text to encode per key is any faster than dealing with 12 bytes). Below is the custom software I use to do farming in our environment. It is only of use to people with 'es' and 'fping'. Also note that I hacked bruterc4.c to be less verbose at startup and during the run. Unless you have 32 machines and the brute program is in ~/rc4-key/, you will need to make some modifications to the script. #!/usr/local/bin/es # # Modified from the generic simulation farm code in use in the # Systems Technology Research Lab, Motorola # nodes must be a program on $PATH that prints the names of `up' machines. # Locally, we use an es script which calls `fping -a' with a list of # all sparcstation machines running sunos within the lab. # Expand starting points from argv[1] start = `{echo 'ib=16;ob=10;for (i=('$1'+1000);i<('$1'+1020);i++) i'| \ bc|sed s,1,,} echo Start points: $start # Find the 32 machines with the lowest loads: nodes = `nodes if {~ $nodes(32) ()} {echo Can\'t get 32 machines; exit 1} mach = `{{for (i = $nodes) \ {rsh $i {echo -n `hostname;uptime|sed 's,.*load average:,,'}}} \ |sort -n +3|sed -n '1,32s,\([^ .]*\).*,\1,p'} echo Machines: $mach # Farm the search: for (i = $mach; j = $start) \ {{rsh $i { cd rc4-key echo nice -10 brute plain cypher $j^0000000 28 '[' on $i ']' nice -10 brute plain cypher $j^0000000 28 echo nice -10 brute plain cypher $j^0000000 28 '[' done on $i ']' }} &} # Wait for jobs to finish for (i = $mach) wait -- Loren J. Rittle (rittle@comm.mot.com) Ripem-1.2 MD5OfPublicKey: Systems Technology Research (IL02/2240) D2CE4A0F2BABF33AEF10C8C669DD782D Motorola, Inc. PGP-2.6 Key fingerprint: (708) 576-7794 6810D8AB3029874DD7065BC52067EAFD From hardin@cyberspace.com Sat Jul 8 13:28:21 1995 Mime-Version: 1.0 Date: Fri, 07 Jul 95 00:28:08 From: hardin@cyberspace.com To: "Tatu Ylonen" , "Adam Back" Cc: cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here X-Mailer: Ultimedia Mail/2 Lite, IBM T. J. Watson Research Center Content-Id: <40_62_1_805091288> Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Tatu Ylonen's Optimization to bruterc4.c compiled on Dell XPS P100 [os/2 warp] gcc -O2 brutetaturc4.c invoked brutetaturc4 known cypher 0 20 known & cypher are text files containing "hello world" 48.5 seconds 21620 keys/sec Let's go, ready to rock & roll tjh From owner-cypherpunks@toad.com Sat Jul 8 04:50:06 1995 X-Nupop-Charset: English Date: Sat, 8 Jul 1995 08:50:06 -0400 (EDT) From: "Pat Farrell" Reply-To: pfarrell@netcom.com To: erc@khijol.intele.net, cypherpunks@toad.com Subject: Re: Cryptanalysis of RC4 (Was Re: MS Exchange: put crypto here Sender: owner-cypherpunks@toad.com Precedence: bulk In message Fri, 7 Jul 1995 21:29:07 +0100, "Ed Carp [khijol Sysadmin]" writes: >> This is scary. I just benchmarked our large machine at 5371 >> keys/sec/processor. No big deal, right? The machine is a KSR1 with >> 128 processors. Given a bit of hacking to partition the key space and >> running the program 128 separate times would give 687590 keys/sec. >> That's 18.5 days to search the whole key space. (2^40 keys, right?) >> This machine is not cutting edge. > I seriously doubt that you'd get anywhere near that number of keys per > second. The machine would spend a significant amount of time context > switching, so it's conceviable that you wouldn't even get your original > throughput. I don't know about a KSR1, but with any MIMD parallel machine, such as the Intel Hypercube that I work with, there are separate CPUs and and a meg memory for each. for the RC4 break, you can put the program into memory with with 1/4 meg of clear and cyphertext on each CPU, and let them run with no context switches, no interaction at all. This is an ideal application for MIMD parallel machines, as the interprocessor communications is what kills the efficiency of typical applications running in parallel. This app has no need for communications. You should expect to get linear speedup. But I think using spare cycles on the 700+ CPUs that this list owns is much more interesting (and probably faster) than any parallel system that I can get my hands on. Pat Pat Farrell Grad Student http://www.isse.gmu.edu/students/pfarrell Info. Systems & Software Engineering, George Mason University, Fairfax, VA PGP key available on homepage #include From owner-cypherpunks@toad.com Tue Jul 11 12:47:46 1995 From: aba@atlas.ex.ac.uk Date: Tue, 11 Jul 95 11:47:46 +0100 To: andrewr@realtime.co.za Cc: aba@atlas.ex.ac.uk, asb@nexor.co.uk, jshekter@alias.com, hfinney@shell.portal.com, jim@acm.org, cypherpunks@toad.com In-Reply-To: <2F630B6F38@real3.realtime.co.za> (ANDREWR@za.co.realtime.real3) Subject: Re: Let's try breaking an SSL RC4 key Sender: owner-cypherpunks@toad.com Precedence: bulk [this started in email, but to the list lest there are more people who have nice implementations or ideas] Things are warming up on the SSL breaking front, several folks have been looking at this independently Jon Shekter , Andy Brown , and Andrew Roos just emailed me his comments on a fast MD5 he had been playing with. > ...I read the archives and email Hal Finney, the original motivator, > asking whther I can help since I already have some of the required > source (like a nice fast MD5). If Hal isn't coordinating, and you > know who is, I'd appreciate a pointer. Sounds like we have all the ingredients for some more key-cracking fun, this one with a sure chance of success (assuming no sabatuers in the form of taking out keyspace and not searching it). I'm not sure who is coordinating, as with all things cypherpunkish it seems to be a bit anarchic, and more of a distributed effort, but there are a number of people with their own code, so far: code type location author RC4 only http://dcs.ex.ac.uk/~aba/bruter4.c aba@dcs.ex.ac.uk* fast MD5 ?? andrewr@realtime.co.za RC4+SSL? ?? (ITAR controlled as he's in US?) jshekter@alias.com RC4+SSL(soon) ?? asb@nexor.co.uk (* including speedups by ylo@cs.hut.fi) andrewr@realtime.co.za = Andrew Roos jshekter@alias.com = Jon Shekter asb@nexor.co.uk = Andy Brown ylo@cs.hut.fi = Tamu Ylonen aba@dcs.ex.ac.uk = me, Adam Back > BTW my benchmarks showed that a good MD5 implementation only > contributed about 10-15% overhead; I can search about 15 000 SSL > keys/sec on a standard 486DX2/66. So this for instance sounds like good news, the best speed on bruterc4.c was about ~10k keys/sec on a 486DX2/66 from the credits list on http://dcs.ex.ac.uk/~aba/credits. So MD5 isn't going to present a problem. Also if someone were to hand optimise the inner loop on prepare key, and the MD5 for a 486, quite a good speed up on those figures could probably be achieved. Andy Brown spent the weekend writing a SSL breaker, just needs to plug in some finishing parts for SSL I think. I think for best results we need non-US people to do the final put together of the parts otherwise non-US people can't join in, also the code distribution should be from a non-US site, and any USENET posts of source code should be done via non-US site. Parts missing so far, Andy is still working on his SSL cracker, which I believe he will post to cpunks for comment when he has finished. Hal or Jon are you able to provide a known plaintext/ciphertext pair. Stategy, is there anything we could do to increase the interest of the data broken, I mean a pair taken from Bill Gate's Netscape SSL session would be more controversial, but probably borderline illegal. Any ideas for a "real world" SSL. Not too big an issue as it'll do to have a proof of concept. I think we agree that this one should be advertised on sci.crypt, alt.security.pgp etc, to garner more CPU, and let everyone join in the fun. The Micro$oft Access RC4 break hasn't turned up anything yet, and 52% has already been swept, not bad for 3-4 days effort. 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 To: cypherpunks@toad.com Date: Tue, 11 Jul 95 09:39:31 TZ Subject: Re: Speedup of bruterc4.c X-Msxmtid: red-36-msg950711164049MTP[01.00.00]000001b5-5721 Sender: owner-cypherpunks@toad.com Precedence: bulk writes: | Good job Russell! | | On my P100 running OS/2 Warp compiling w/ gcc 2.6, I get | | original optimiziation | | A. 21620 keys/sec in OS/2 window on WPS desktop [GUI & other stuff loaded] | | B. 24892 keys/sec OS/2 command line full screen [No WPS GUI etc.] | | Russell Ross's optimization for Pentiums of original Tatu Yalonen optimization | | A. 25267 keys/sec in OS/2 window on WPS desktop [GUI & other stuff loaded] | | B. Haven't tried Russ's opt under condition B. yet. | | Let's hear from some NT folks on P's & also from *ix, Power Mac's, NT, etc. on | the various RISC architectures out there. | | Warp on, | | tjh | OS is Windows NT 3.51. Machine is a DEC P90. Compiler is VC 2.1 compiler. original optimization 25,575 keys/sec With Russell's optimization 27,349 keys/sec. Mike ===================================================== Mike Markley I'm not a Microsoft spokesperson. All opinions expressed here are mine. ===================================================== From owner-cypherpunks@toad.com Tue Jul 11 17:46:48 1995 Date: Tue, 11 Jul 1995 21:46:48 -0400 (EDT) From: "Timothy L. Nali" To: cypherpunks@toad.com Subject: Re: Speedup of bruterc4.c Cc: In-Reply-To: <9507111715.AA20916@netmail2.microsoft.com> References: <9507111715.AA20916@netmail2.microsoft.com> Sender: owner-cypherpunks@toad.com Precedence: bulk For linux boxes (or perhaps 486 and pentium machines in general), try adding the flag -funroll-all-loops to the compile line. gcc -O2 -funroll-all-loops -m486 -o brute bruterc4.c Here are my results on a Linux 486/33 Original code (Adam+Tatu) : 5405 keys/sec Original code with -funroll-all-loops : 5991 keys/sec Original code with Russell's changes and a couple of my own and -funroll-all-loops : 6393 keys/sec Here are the changes I made: If we assume that the length of the cyphertext and known text is less than 256 bytes, then the following works. This gives you a whopping 40 additional keys/sec. --------------------------------------------------------------------------- int rc4_eq(unsigned char *buffer_ptr, unsigned char *known, unsigned char *cypher_txt, int buffer_len, rc4_key *key) { unsigned int t; unsigned int y = 0; unsigned char* state; unsigned int xorIndex; unsigned int counter; state = &key->state[0]; for(counter=0;counter < buffer_len;counter++) { y = (state[counter+1] + y) & 0xFF; swap_byte(state[counter+1], state[y]); xorIndex = (state[counter+1] + state[y]) & 0xFF; buffer_ptr[counter] ^= state[xorIndex]; if (known[counter] != buffer_ptr[counter]) { memcpy(buffer_ptr,cypher_txt,counter+1); return 0; } } return 1; } -------------------------------------------------------------------------- Also, I could not get Russell's changes to work exactly as he posted them (I suspect it's because I'm using a very old linux system). Here's my prepare_key function. I basically took out the counter++ parts. -------------------------------------------------------------------------- /* excellent optimised prepare key by Tatu Ylonen ylo@cs.hut.fi */ void prepare_key(unsigned char *key_data_ptr, int key_data_len, rc4_key *key) { unsigned int t; unsigned int index2; unsigned char* state; unsigned int counter; unsigned int k0, k1, k2, k3, k4; state = &key->state[0]; memcpy(state,sequence,256); index2 = 0; k0 = key_data_ptr[0]; k1 = key_data_ptr[1]; k2 = key_data_ptr[2]; k3 = key_data_ptr[3]; k4 = key_data_ptr[4]; for(counter = 0; counter < 255; counter+=5) { t = state[counter]; index2 = (index2 + k0 + t) & 0xff; state[counter] = state[index2]; state[index2] = t; t = state[counter + 1]; index2 = (index2 + k1 + t) & 0xff; state[counter + 1] = state[index2]; state[index2] = t; t = state[counter + 2]; index2 = (index2 + k2 + t) & 0xff; state[counter + 2] = state[index2]; state[index2] = t; t = state[counter + 3]; index2 = (index2 + k3 + t) & 0xff; state[counter + 3] = state[index2]; state[index2] = t; t = state[counter + 4]; index2 = (index2 + k4 + t) & 0xff; state[counter + 4] = state[index2]; state[index2] = t; } t = state[255]; index2 = (index2 + k0 + t) & 0xff; state[255] = state[index2]; state[index2] = t; } ------------------------------------------------------------------------ _____________________________________________________________________________ Tim Nali \ "We are the music makers, and we are the dreamers of tn0s@andrew.cmu.edu \ the dreams" -Willy Wonka and the Chocolate Factory