December 2003 - cypherpunks-legacy

general RC4 key searcher: optimisations anyone?
by Andy Brown 17 Dec '03

17 Dec '03

Hi, The following program is the part of my RC4 key search program that actually does the searching, adapted into a small speed test. It is designed to handle any size key, with any number of unknown bits, in any position within the key. There are, of course, problems with it in its current form: 1. It's too slow. I get 50% of the performance of the bruterc4.c on utopia.hacktic.nl (~9500/sec on a 60Mhz Pentium and ~12000/sec on a Sparc 20) 2. It can only handle bit offsets of 0 (i.e. the lower n bits of the key are unknown). I'm unsure of a really fast way of generalising this to any (contiguous) n bits. 3. There are probably bugs. The code is included below. Does anyone have any comments? - Andy --------------------------- begin code fragment ------------------------ /* RC4 Brute Force Key Searcher, by Andy Brown 1995 This part of the package is meant to be portable between most systems so that Unix users can take part in the searching. After all, the kind of really high powered systems that can make a large dent in the key space are not running Windows NT. You will, however, require an ANSII compiler */ #include <stdio.h> #include <time.h> #include <ctype.h> /* function declarations */ int main(void); char *search_range(char *,unsigned long,unsigned long,char *,int, unsigned char *,unsigned char *,int); static void hex_to_bytes(char *,unsigned char *); #define SwapByte(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) #define hexdigit(a) ((a)<10 ? (a)+'0' : (a)-10+'A') #define decdigit(a) (isdigit(a) ? (a)-'0' : toupper(a)-'A'+10) /*****************************/ /* Main function: test speed */ /*****************************/ int main(void) { /* The key has 20 "unknown" bits */ unsigned char *keyhex="0102030405060708090A0B0C0D000000"; unsigned char *first="0"; unsigned char ciphertext[11]= { 0xF2,0xA2,0xA0,0xF6,0x0F,0xBD,0x69,0x98,0xC0,0xFF,0x4C }; char *retval; time_t before,diff; before=time(NULL); retval=search_range(first,0xFFFFF,0,keyhex,0,"hello world",ciphertext,11); diff=time(NULL)-before; if(retval==NULL) fprintf(stderr,"Key not found, bug in key search code\n"); else fprintf(stderr,"Key is: %s\n%ld keys/sec\n",retval,0xFFFFFL/(long)diff); return 0; } /***********************************/ /* Search a region of the keyspace */ /*********************************** Arguments: start_str: ASCII hex representation of the first "search key" testsl: low order 32 bits of the number of keys to test testsh: high order 32 bits of the number of keys to test keyhex: ASCII hex representation of the key "skeleton" Zeros appear in the key throughout the search range firstbit: zero based index of the first unknown bit plaintext: known plaintext ciphertext: corresponding ciphertext textsize: number of bytes of plain/ciphertext NB: A "search key" is an offset into the searchable keyspace, not a full key in itself. It may vary from 0..(2^numbits)-1 Returns: NULL if the key is not found in the search range, otherwise an ASCII hex representation of the key is returned. This pointer must be dynamically allocated with malloc */ char *search_range(char *start_str,unsigned long testsl,unsigned long testsh, char *keyhex,int firstbit, unsigned char *plaintext,unsigned char *ciphertext, int textsize) { unsigned char *start,*key,*skeleton,state[256],index1,index2; char *retval; int keybytes,startbytes,x,y,counter,i,found=0; unsigned long lowcounter,highcounter; /* allocate space for the key bytes and our starting value */ keybytes=strlen(keyhex)/2; if(strlen(keyhex)&1) keybytes++; startbytes=strlen(start_str)/2; if(strlen(start_str)&1) startbytes++; start=(unsigned char *)malloc(keybytes); memset(start,'\0',keybytes); skeleton=(unsigned char *)malloc(keybytes); key=(unsigned char *)malloc(keybytes); /* convert the hex strings to bytes */ hex_to_bytes(start_str,start+keybytes-startbytes); hex_to_bytes(keyhex,skeleton); /* OK, now things get time-critical. We are about to drop into a loop that prepares and tests each candidate key */ for(highcounter=0;highcounter<=testsh;highcounter++) { for(lowcounter=0;lowcounter<testsl;lowcounter++) { /* construct the key from the skeleton and our part */ if(!firstbit) { memcpy(key,skeleton,keybytes); for(i=keybytes-1;i>startbytes;i--) key[i]|=start[i]; } /* prepare the key */ for(counter=0;counter<256;counter++) state[counter]=(unsigned char)counter; x=y=0; index1=index2=0; for(counter=0;counter<256;counter++) { index2=(key[index1]+state[counter]+index2) & 0xFF; SwapByte(state[counter],state[index2]); if(++index1==keybytes) index1=0; } /* do two RC4 operations as a preliminary test. If this fails then test the next one, then the rest. This should result in a lot of rejections before the rest of the loop is entered */ x=(x+1) & 0xFF; y=(state[x]+y) & 0xFF; SwapByte(state[x],state[y]); if(plaintext[0]==(ciphertext[0]^state[(state[x]+state[y]) & 0xFF])) { x=(x+1) & 0xFF; y=(state[x]+y) & 0xFF; SwapByte(state[x],state[y]); if(plaintext[1]==(ciphertext[1]^state[(state[x]+state[y]) & 0xFF])) { /* rest of the loop. This will only be entered, on average once every 65536 tests */ for(i=2;i<textsize;i++) { x=(x+1) & 0xFF; y=(state[x]+y) & 0xFF; SwapByte(state[x],state[y]); if(plaintext[i]!=(ciphertext[i]^state[(state[x]+state[y]) & 0xFF])) break; } /* if we got to the end of the loop then that's it. We have won */ if(i==textsize) { found=1; goto endloops; } } } /* increment our key segment */ i=keybytes-1; do { start[i]++; } while(!start[i--]); } } /* free memory */ endloops: free(start); free(skeleton); if(found) { retval=(char *)malloc((keybytes*2)+2); i=0; for(i=0;i<keybytes;i++) { retval[i*2]=hexdigit((key[i]&0xF0)>>4); retval[(i*2)+1]=hexdigit(key[i]&0xF); } retval[i*2]='\0'; return retval; } else return NULL; } /*******************************/ /* convert hex string to bytes */ /******************************* eg. "05FC9" would become 0x00,0x5F,0xC9 */ static void hex_to_bytes(char *str,unsigned char *bytes) { int i,firstzero=(strlen(str)&1) ? 1 : 0; unsigned char b; i=0; while(i<(int)strlen(str)) { if(firstzero) firstzero=0; else { b=(decdigit(str[i]))<<4; i++; } b|=decdigit(str[i]); *bytes++=b; i++; } } -------------------------- end code fragment -----------------------

1 0

Re: Num Rat
by rah＠shipwright.com 17 Dec '03

17 Dec '03

>Does anyone know more of this program? Or care to summarize >Benford's Law? I can't wait to learn it. ;-). One more bit of market efficiency for the regulatory arbitrage business. I can see it now: an application of the "BabeWatch" idea to the 1040 form.... Cheers, Bob Hettinga ----------------- Robert Hettinga (rah(a)shipwright.com) Shipwright Development Corporation, 44 Farquhar Street, Boston, MA 02131 USA (617) 323-7923 "Reality is not optional." --Thomas Sowell >>>>Phree Phil: Email: zldf(a)clark.net http://www.netresponse.com/zldf <<<<<

1 0

17 Down, 696 to go.......
by Censored Girls Anonymous 17 Dec '03

17 Dec '03

Hey! if I can do it, any clueful c'punk can do it! Love Always, Carol Anne PGP.ZIP PART [017/713] This just cycles through: when part 713 is reached, part 0 will be recycled. We are on export 0 at the moment. _________________________________________________________________ ------------------ PGP.ZIP Part [017/713] ------------------- M8H,),S$8G>&.WP(8IRA`-M['+`Q%&_C"">5-F%LX@<_Q$;*P'',Q$Z/AA[8M MF=O0H+*%(-S%&>S%+FS&<LS%3(Q&#W1"<]2%`H^;,]^1C$'HBN8PX$4SYAU^ MPGD<Q0ZLA0D+,`MCT!LA**4M[-JPAK9F?40!AJ,CW"'%DR#:'9?Q)3[%<DQ` ------------------------------------------------------------- for next chunk to export --> http://dcs.ex.ac.uk/~aba/export/ Member Internet Society - Certified BETSI Programmer - WWW Page Creation ------------------------------------------------------------------------- Carol Anne Braddock <--now running linux 1.0.9 for your pleasure carolann(a)censored.org __ __ ____ ___ ___ ____ carolab(a)primenet.com /__)/__) / / / / /_ /\ / /_ / carolb(a)spring.com / / \ / / / / /__ / \/ /___ / ------------------------------------------------------------------------- A great place to start My Cyber Doc...

1 0

Re: The FTP Bounce Attack
by danisch＠ira.uka.de 17 Dec '03

17 Dec '03

Also a nice way to walk through firewalls. Perhaps you could write a SATAN script to check it. And you should send a copy of your description to CERT. Hadmut

1 0

AoHell
by cman＠communities.com 17 Dec '03

17 Dec '03

Does anybody know about where to get this? (If this was discussed here during my cypherpunks-viewing hiatus, I apologize).

1 0

FW: Edupage 7/9/95 (fwd)
by Phil Fraering 17 Dec '03

17 Dec '03

Date: Tue, 11 Jul 1995 18:58:54 +0200 From: danisch(a)ira.uka.de (Hadmut Danisch) X-Sun-Charset: US-ASCII Sender: owner-cypherpunks(a)toad.com Precedence: bulk > I've never seen any actual nazism on the net anywhere, but this "strict > regulation" tactic is obviously fascist in nature. There are certain nazi pages in America. They were showing them in a german tv magazine some time ago, but they didn't tell the URLs. The URL field in the Mosaic window was painted over. Hadmut How do you know they weren't local?

1 0

Re: Anti-Racketeering Act
by foodie＠netcom.com 17 Dec '03

17 Dec '03

> "(a) It shall be unlawful-- > > . . . > > "(2) to distribute computer software that encodes or encrypts > electronic or digital communications to computer networks that the > person distributing knows, or reasonably should know, is accessible to > foreign nationals and foreign governments, regardless of whether such > software has been designated nonexportable." Oh no - I can already see the T-shirt ideas congealing in people's minds: LbhÕer Ohfgrq in big block letters. -j -- On the internet, nobody knows you're a deity. __________________________________________________________________________ Jamie Lawrence and Bryna Bank <foodie(a)netcom.com>

1 0

Re: QED_jak
by Duncan Frissell 17 Dec '03

17 Dec '03

At 09:53 AM 7/12/95 -0400, John Young wrote: > 7-12-95. NYPaper: > > > "U.S. Tells How It Found Soviets Sought A-Bomb: Discloses > Clues That Led to Code-Breaking." > > The American intelligence establishment today unveiled > one of its oldest secrets: how a small team of > codebreakers found the first clues that the Soviet Union > sought to steal the blueprints for the atomic bomb in > World War II. Using just brain power -- no computers, > no stolen skeleton keys -- the cryptographers slowly > cracked what was thought to be an unbreakable code. > service. The messages were like a jigsaw puzzle with a > billion pieces -- all black. They had been double-coded > by a system called a one-time pad -- a unique random > code for each message, converting words to numbers in a > pattern used only once. HOO_doo Note Julius Rosenberg's code name was "liberal". The NSA said that the Soviets were using a one-time-pad. The implication is that sloppy encryption practice caused Soviet code clerks to sometimes reuse the random material thus converting the code into a code book system that could be read. DCF "A man perfects himself by working. Foul jungles are cleared away, fair seed-fields rise instead, and stately cities; and withal the man himself first ceases to be a jungle, and foul unwholesome desert thereby. . . . The man is now a man." -- Carlyle

1 0

pgp.zip
by Michael J. Axelrod 17 Dec '03

17 Dec '03

So this is what it is like living on the edge ;-{ Warning: it may be illegal to use one of these as a sig file in the US ------------------ PGP.ZIP Part [019/713] ------------------- MPGD<Q0ZLA0D+,`MCT!LA**4M[-JPAK9F?40!AJ,CW"'%DR#:'9?Q)3[%<DQ` M=P1!C]JXUTH0KN`[',0'>!-C$8&.:`1/Y-,6[Z,-Y?O"`PK&X=$W*`,;L1HI MF(JAZ(A:$/`XF)C!]4W(Q>?(Q!*\C0YHC!+R+4`>EB`>_7%/4`86X19NX!HN ------------------------------------------------------------- for next chunk to export --> http://dcs.ex.ac.uk/~aba/export/

2 1

Re: Moby ints [Re: Num Rat]
by James A. Donald 17 Dec '03

17 Dec '03

At 07:31 PM 7/11/95 -0400, Ray Cromwell wrote: > However, it's only worthwhile for large > numbers (>512 bits). At n=512, if your bigints are stored as polynomials > with a 32-bit radix, then N=512/32=16. 16^1.5 = 64, 16 * lg(16) = 64 > (so the FFT method and the Karatsuba method are equivalent for numbers > of that size) I conjecture that the constant factor is rather smaller for the Karatsuba method, so the turnover should be somewhat higher than 512 bits. Does anyone have any real experimental data on this question. I assume Schonage has real experimental data? -- ------------------------------------------------------------------ We have the right to defend ourselves | http://www.jim.com/jamesd/ and our property, because of the kind | of animals that we are. True law | James A. Donald derives from this right, not from the | arbitrary power of the omnipotent state.| jamesd(a)echeque.com

2 1