From: Eric Murray <ericm@lne.com>
Date: Sat, 30 Nov 1996 13:20:07 -0800 (PST)
To: ichudov@algebra.com
Subject: Re: IPG algorithim
In-Reply-To: <199611301953.NAA14436@manifold.algebra.com>
Message-ID: <199611302118.NAA12825@slack.lne.com>
MIME-Version: 1.0
Content-Type: text/plain




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;

	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?) */
		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]);
			}
		}
	}
}



-- 
Eric Murray  ericm@lne.com  ericm@motorcycle.com  http://www.lne.com/ericm
PGP keyid:E03F65E5 fingerprint:50 B0 A2 4C 7D 86 FC 03  92 E8 AC E6 7E 27 29 AF