From: ichudov@algebra.com (Igor Chudov @ home)
Date: Sat, 30 Nov 1996 14:16:03 -0800 (PST)
To: ericm@lne.com (Eric Murray)
Subject: Re: IPG algorithim
In-Reply-To: <199611302118.NAA12825@slack.lne.com>
Message-ID: <199611302150.PAA15126@manifold.algebra.com>
MIME-Version: 1.0
Content-Type: text


[This is an addition to my previous reply to Eric]

It bugs me that you are using rand() (a fairly lame pseudo-random
function that was never intended to be used in cryptographic
applications) to seed A, B, C and JV and then test the A(JV) for
randomness. Some may object to that. Just for fun, I am attaching a hex
dump of output from my /dev/random (Linux 2.0.24). You could simply take
these truly random values and put them in initial A, B, C and JV, just
to be sure.

I doubt though that your results (poor randomness of A(JV)) will be
any different.

igor

0000000 c76d 74ac b253 ffc3 ae97 e092 629c 7a53
0000010 087a 21e6 8c2c 0ab6 a03a ea3c 0c71 a748
0000020 68f0 540d a4f2 0a2b b62b 4ab6 ddaa d3e4
0000030 a795 51f3 7dff 067d 2f6b 8d18 fa23 0200
0000040 99df 1d97 e232 b8d5 381f cf1e 7ea8 d971
0000050 8aa0 df0b cf41 53e2 a9f5 5304 dc28 c242
0000060 c01b 5990 75a1 688d 497f cc54 d336 217e
0000070 7dd7 4800 09d4 ff5b 53b8 6308 d38f 60f5
0000080 513a 3ea7 90f6 4cdf e783 6a14 145a e2b1
0000090 2041 6bb5 f417 6109 6101 fecd b7f1 7287
00000a0 f31a 6cb4 d559 ed7c 1be8 e0ca 21f9 8779
00000b0 701e bbcc 8909 7743 bfef c5ef 0f60 cd6a
00000c0 565b 30b5 e710 5f66 aa83 0751 5bc7 867e
00000d0 87a8 8511 9969 d101 c1bb 871b a2e5 f579
00000e0 5e14 9167 480a 9fc2 8354 5769 4ee0 7765
00000f0 faf5 c29f 25ad 77ea 9ecf 39b4 2d11 969f
0000100 099c f85a 7240 9922 0513 d607 41ea ba29
0000110 1886 2611 e577 50c6 87af 393a 782a 6666
0000120 9ae0 221e ec58 ce2e de77 b6de 5821 82e9
0000130 db17 5027 7e57 567a 2e82 f056 01d0 2cde
0000140 0314 ac33 78bd d569 215e b8d7 6a3b 0caa
0000150 b44f 8c6c 04de 4cf2 e111 2803 a073 7d27
0000160 f78c 9d28 70ca 1cd4 ce53 5dea 3141 efa9
0000170 8246 c7ee 4ed3 e49a 8d97 8ded d818 327a
0000180 f999 e044 ff28 ffe9 0254 535c 7e70 a09c
0000190 af58 bcd2 07b0 8146 f4cc 7568 751c c6ee
00001a0 b6b7 be3f d870 84ce 7f8c 3ec4 1427 09fc
00001b0 706e 93f8 9752 230b 74cd 0b0b 38be ba5b
00001c0 a9a6 062a cdee f11d d367 37e2 ec4f 90e4
00001d0 9019 d9ff 2ff9 fb5d 559b 4dd0 2ab0 7e35
00001e0 184a 3e90 f072 7349 007f 5d41 c176 8d8a
00001f0 a30c 1a68 eca6 63f4 256f 88e1 2cec dc1a
0000200 a0ac 90f0 b515 2fbc 2778 4e66 2323 7528
0000210 59c3 c3a9 3ccd e29d 315a fa6a 7821 f6e4
0000220 7977 5e9f df6c f87e 5d15 5693 3da8 9790
0000230 faaf d028 0c05 f5f0 160a 8cb7 f726 18cf
0000240 796d 77c5 3c2e 5ddb f770 7183 3c17 81b7
0000250 b0ff ad01 a4d3 26a1 7821 d210 376a 8283
0000260 3860 61a9 c509 e34c 46a4 7f70 b2ff 18db
0000270 24ad 97b5 e474 eee2 9036 c125 3fdb 88ce
0000280 824a 3096 98fc 0b9f 2f3a 6ac3 25e1 8d08
0000290 46c6 7218 ea87 3c6d 6395 6fc5 34b0 1447
00002a0 ddb3 b3af fdbf b545 5f47 0fe6 bfd0 e799
00002b0 99f6 1fc6 c70b 524f 717f a25d 9f08 f78a
00002c0 e230 b4b9 2045 5652 9677 5ce3 a827 9e8f
00002d0 261f 4650 c731 afbb e257 8410 621a 09aa
00002e0 d991 7a3b bb68 4995 fd15 2afc 8e26 842b
00002f0 cdf7 2d13 4055 9d22 be44 aa16 ed06 db8a
0000300 4210 714b 330d 6c9e 3f81 c993 4d8b 2f6b
0000310 134f 1566 8170 9cc6 4cff d188 78c4 29ae
0000320 27ec 731f 391c 6241 ffaf 2967 8756 1517
0000330 5d1a e807 c477 7757 bd6a ff4c 1cf1 01ce
0000340 dfa7 25b4 5a4f 9cf0 e96e 2d69 0de0 c24e
0000350 0a2c 9ec8 112d 0851 c028 917b b00b f9a0
0000360 0b07 b9f0 c4ef 4426 1cce c8c8 7186 8c24
0000370 9868 fe68 9136 1316 1e58 e883 5aa9 1298
0000380 c0ed eaa4 aaa2 7f23 48d1 5056 8837 06ec
0000390 5f69 ce3a 3d5b 1e7a 7545 e237 352d d887
00003a0 df9c 734d a441 7fa5 6685 eff0 4ce8 1876
00003b0 f9c9 2e18 f825 3a3a a6b8 e0cc 5d49 136a
00003c0 853d dd88 c0f8 befc 8b87 e261 fd73 09af
00003d0 b392 3afa f38e 6a25 cc5d b624 1012 49f3
00003e0 31b0 196c aa02 b3f2 454a 7817 2198 5ad7
00003f0 84c5 f22d 8b6e cdc9 12c3 d0b5 b866 9976
0000400 97a7 3b5e dedf 201d 50f5 99a6 bf54 04ab
0000410 a34e 3a66 538c 51a0 c00b 7ae8 f2ae 6343
0000420 c5f1 1ef1 1f8f 7415 5b50 53a4 33ad d046
0000430 13b6 62a2 cc34 feee 7fda 671a 2b28 a36c
0000440 a806 15be 1ccc b5b9 ef85 04ca 168c 8cd0
0000450 c44e d117 a6c8 cbaf 3b5b 581c d94a 8469
0000460 effb 0f18 cd45 5c77 6ab1 1289 e385 9771
0000470 199f 5610 8095 be8b e257 2ef8 a221 99ee
0000480 1d8b c81c 9781 e803 e4ab 4afb 5669 efb1
0000490 b31f 36e2 5930 b838 e84c 4f6e a709 0c40
00004a0 fefe c530 4ee2 ee3a aa2e e278 de99 8b1e
00004b0 4e83 c98a 47cd 4715 081d 7c7d 5f6f 657c
00004c0 49b5 70c0 937a d4c2 39ff d282 8768 1d7c
00004d0 40fe 1ed1 59b9 d0f7 b4cc 55b3 5da2 4118
00004e0 14dc 4b71 202a fb96 0bed 6d2a 03d6 2f2d
00004f0 9056 8d84 8b6e 948b 4b89 efd1 53ba 9a13
0000500 ea01 770a dc40 fcad bf69 cf60 7884 3f66
0000510 b057 2e82 3745 2839 f68d f637 ad95 5463
0000520 ff3c 353d 08b2 44c2 72bb b25b f60d 0dbf
0000530 455a e9b4 8bbf 3307 071a f720 f00e 0217
0000540 f8cc f7cc 2cc4 ef14 e6b6 7dbc ceff 2dea
0000550 fc34 ed72 d59b 8cd2 794c 2d11 e470 ba44
0000560 bff3 c531 b38b 5398 4a46 63be d86b ae19
0000570 d6a4 2e8d da0d 0ff9 a3db 2cc4 0494 72b1
0000580 b871 1f7e b8da a2f0 2f63 b522 3212 43da
0000590 f910 374e b1f5 5462 8db0 65ef 5e5b 9bf1
00005a0 9337 5003 31fc 47a9 8c06 d0d8 c8ab 8732
00005b0 ff5e 7fe3 b43c 9ba0 14dd f31f cf4c a5b5
00005c0 5552 b1ee 0ee6 a38f dc2b 32ac ab80 e12d
00005d0 be8c ad7d 89e9 5cda 0781 f30c b1d1 3163
00005e0 72f9 bcbe 5972 1862 3a15 660f 4227 b168
00005f0 280d 35fa 1765 46f3 468b 0538 44fc 216e
0000600 30f6 8340 6805 7f5c a280 fcdf 563d 9751
0000610 50c9 fb04 065c 12ec 9ce3 34ee 2a3d f821
0000620 d43e b64e 067f fd26 5e94 b7d1 9b28 fbcf
0000630 811b 4631 6018 5385 1297 e37a b0ea c6fd

Eric Murray wrote:
> 
> 
> 
> 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
> 



	- Igor.