From: ichudov@algebra.com (Igor Chudov @ home)
Date: Wed, 11 Dec 1996 07:41:55 -0800 (PST)
To: wichita@cyberstation.net
Subject: Re: IPG algorithim
In-Reply-To: <Pine.BSI.3.95.961211020454.11832D-100000@citrine.cyberstation.net>
Message-ID: <199612111534.JAA00488@manifold.algebra.com>
MIME-Version: 1.0
Content-Type: text


Don, Eric -- 

I think that Eric simply tried to test the PRNG without the tables,
to see how good it is.

igor

wichita@cyberstation.net wrote:
> 
> 
> 
> 
> On Sat, 30 Nov 1996, Eric Murray wrote:
> 
> 
> Eric, unlike all the other forespeakers, I do appreciate the fact that
> you tried to understand the algorithm and implement it. However, you
> have several things wrong, the most important being that the PRNG
> produces ONLY a seed for the main algorithm and over short sequences, 
> for example 53^2, that is only slightly over  an average occurrence
> of 8 each for the 256 ASC II characters, and the seed streams are
> congruent. However, the algorithm uses a 3 dimensional table lookup to
> translate the numbers to the Encryptor stream. 
> 
> I suggest that you get a free copy of the operating program, generate your
> own key, and then run the output through any meaningful test that you
> might desire. That would indeed establish whether or not our system does 
> what we claim it will do or not. It does, but neither my words or your
> partial tests prove anything. 
> 
> The expected occurrence of an identical repeat, that is a where the same
> seed gives the same result is 1 in 2^36. Of course that does not mean that
> the same resultant encryptor character might not be generate because there
> are only 256 possibilities, so the same character would result from the
> same seed at least 1 in 256 times, and of course statistically more
> frequently than that, but the over sequence of events leading to the
> production of that character is different. 
> 
> While I do appreciate your effort to understand and implement the
> algorithm, it would be helpful if you would contact me first and get a
> copy of the keys and everything detailed in the web site. I take it that
> you used the abbreviated version, or failed to read all the information etal.
> If you use the tables and so forth detailed at the web site and use the
> full algorithm, the results will be far different as you will find.
> 
>    
> 
> 
>  > > 
> > I have translated the IPG algorithim's "engine" to C, to generate
> > some random values from it for testing purposes.  It does not
> > look very random in either the xnoisesph program or the DIEHARD
> > test battery.   However I may well have misinterprested Mr. Wood's
> > description (his writing is, as Mr. Chudov points out, difficult to
> > understand) or written my code incorrectly.  Here it is, play
> > with it yourself.  To my untrained eye the lack of randomness
> > in what's essentially a stream cipher would be disturbing.
> > However I am not a cryptoanalysist so I do not know to
> > what extent this weakens the cipher.
> > 
> > 
> > The IPG description does not say (but implies to me) that
> > the various tables that are to be filled in by "random" values must
> > be filled in by PRNGs that are seeded with the same seeds by
> > each of the party that knows the key.  Otherwise the "encryptor
> > streams" that are generated will be unrelated and decryption will not
> > be possible.  To make my test work I have used the simple rand()
> > function to fill in the tables.
> > 
> > 
> > Corrections are welcome.
> > 
> > 
> > 
> > #include <stdio.h>
> > 
> > /* a C translation of the IPG "EUREKA" algorithim's "engine".
> > ** This is supposed to produce random numbers for the IPG
> > ** "encryptor stream".
> > ** See http://www.netprivacy.com/ for the original description.
> > ** Eric Murray  ericm@lne.com  This code placed under GNU copyleft.  */
> > 
> > /* machine-dependent stuff, change to suit different platforms: */
> > typedef unsigned char byte;
> > typedef unsigned short uint16;
> > 
> > 
> > /* tables: */
> > uint16 A[53];
> > uint16 B[53];
> > uint16 C[53];
> > 
> > 
> > int init_table(uint16*table, uint16 min, uint16 max)
> > {
> > 	/* IPG specifies no algorithim for producing the "random"
> > 	** initial values in the ABC tables, but it's obvious that
> > 	** it requires a PRNG that's somehow seeded from the "key".
> > 	** I've just used rand() here.  In UNIX rand() called with no
> > 	** seed is supposed to seed itself with 0. */
> > 	int i;
> > 	int count, r;
> >
> Wrong - the algorithms are specified at the web site - look again. You
> cannot just use rand(). That is patently absurd.
>  
> > 	for(i = 0; i < 53; i++) {
> > 		table[i] = min + (rand() % (max - min));
> > 	}
> > }
> > 
> > main(int argc, char **argv)
> > {
> > 	uint16 jv;
> > 	int argcnt, i, n, count, diehard, nelem;
> > 
> > 	diehard = 0;
> > 	argcnt = 1;
> > 	if (argc >= 2) {
> > 		if (strncmp(argv[argcnt],"-d") == 0) {
> > 			diehard++;
> > 			argcnt++;
> > 		}
> > 	}
> > 	if (argc > argcnt - 1 ) {
> > 		n = atoi(argv[argcnt]);
> > 		fprintf(stderr,"Generating %d values\n",n);
> > 	}
> > 	else {
> > 		n = 2000;
> > 	}
> > 
> > 	/* seed tables: */
> > 	fprintf(stderr,"Seeding:  A");  fflush(stderr);
> > 	init_table(A,0,65535);
> > 	fprintf(stderr," B");  fflush(stderr);
> > 	init_table(B,0,12227);
> > 	fprintf(stderr," C");  fflush(stderr);
> > 	init_table(C,16384,20361);
> > 	fprintf(stderr,"\n");  fflush(stderr);
> > 
> > 	/* generate n values: */
> > 	for(; n > 0; n--) {
> > 		/* jv is "random" (where's it seeded from?) */
> from the key 
> 
> > 		jv = (uint16)(rand() % 53);
> > 
> > 		/* count limits the number of traverses to 53^2 so we don't get stuck */
> > 		for(count = 0; count < 2809; count++) {
> > 			jv++;
> > 			if (jv == 53) jv = 0;
> > 			A[jv] = (A[jv] + B[jv]) % C[jv];
> > 			if (A[jv] < 16384) break;
> > 		}
> > 		if (count == 2809) fprintf(stderr,"Oops.\n");
> > 		else {
> > 			if (!diehard) {
> > 				printf("%d\n",A[jv]);
> > 			}
> > 			else {
> > 				/* print output in DIEHARD required format:
> > 				** actually since we have 16-bit ints and DIEHARD
> > 				** wants 32-bit ints, we print 20 per line instead of 10 */
> > 				if (nelem++ > 19) {printf("\n"); nelem = 0;}
> > 				printf("%4.4x",(unsigned int)A[jv]);
> > 			}
> > 		}
> > 	}
> > }
> > 
> > 
> > 
> > -- 
> But they do not reference the same table entries either as is plain to see.
> Your implementation, while appreciated, is plain flawed in many respects. We do not use any
> special As, Bs and Cs. Any selection will do.  
> 
> If you are going to implement that algorithm, please use all of it, not
> just the seed generator. I grant you that with only 53 different
> equations, the resultant seed numbers do not give a random CHI square,
> especially over short frame sizes. Certainly over 53^2, it would give you
> staccato results. Not only that, but they are congruent. Nevertheless,
> this is more of the supercilious half ass crap that writers post. If you
> implement the rest  of the algorithm, you will find that it does always
> meet the Chi Square tests for randomness, not sometimes but always. I have
> posted  over 200 megabytes of data to our web site and it is still there.
> Pick any spot in the data, and run your chi squares tests on it. 
> 
> If you are going to try to critiqued the IPG algorithm, please use the
> entire algorithm set out. There are so many things wrong with your
> implementation, that it would take me days to cover everything.
> I suggest that you get a sample copy of our operating program , generate
> your own Keys and then analyze the output data. Then if it does not
> perform as we have stated you can tear us apart. But your meaningless
> jabberwocky means nothing other than you have at least tried to understand
> the algorithm, which to repeat, we appreciate.
>  
> 
> 



	- Igor.