On Sat, 30 Nov 1996, Igor Chudov @ home wrote:

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.

Thanks for an interestnig approach to testing (see below).

...

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.

A good point.

...

Corrections are welcome.

see below.

...

#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;

how about doing randomize()?

...

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++) {

2809 is a too small limit. For example, if ALL B == 1, A == 16385, and C == 20361, the loop may need (20361-16385) passes to get to the < 16384 value.

Again, if all A = 16385, all B = 0, all C = 16386, the loop will never end with a correct A (your code reflects that).

...

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

You are also bringing a good point that Chi-squared tests are not sufficient to make any conclusions about usefulness of this particular pseudo random number generator.

- Igor.

Chi Squares alone are not sufficient but we are only talking about the seed algorithm, and at our web sites, you will find Standard Deviations, Chi Squares, Delta ICs, autocorrelations, cross correlations, and a variety of other tests done on single characters, couplets - pairs, first differences, second differences, offset differences and all kinds of other tests.

[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.

Eric Murray wrote:

Igor Chudov @ home writes:

...

[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.

Yea, you're right, rand() is lame.

I added /dev/random to my Linux box and changed my small test to use it. I also changed the way that I use JV- I had been setting it to a random value for each trip through the "engine", but since I beleive that its value can't really be random (if you want to be able to have someone decrypt your stuff :-) but must be exchanged in the key, I set it to a random value once and then let it float. It's also a lot faster that way, /dev/random is pretty slow (because it's looking for real random material).

Oh yes! Surely, jv should be set to a random value during the setup. Thereafter it should simply be incremented modulo 53.

My results from xnoisesph were wrong- xnoisesph wants random bytes instead of random integers in ascii format as I was producing. Changing it (as I have below) makes the xnoisesph output look much better, but it still isn't all that random. The random seed generators

Can you publish the results? And what does xnoisesph do exactly?

I have written that get their randomness from repeated calls to high-resolution timers and hashes of system log files do better. I also fixed a minor bug in arg processing.

#include <stdio.h> #include <fcntl.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. ** V0.2 */

typedef unsigned char byte; typedef unsigned short uint16;

/* tables: */ uint16 A[53]; uint16 B[53]; uint16 C[53];

#ifndef NO_DEV_RANDOM uint16 getrand() { uint16 ret; int fd = open("/dev/random",O_RDONLY); if (fd <= 0) { perror("/dev/random"); exit(-1); } read(fd,(unsigned char *)(&ret),sizeof(ret)); close(fd); return(ret); } #else /* do something appropriate for your OS here, rand() is lame. */ #define getrand rand #endif

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 used /dev/random here, so there's no question that ** I'm starting out with pretty good random values. */ int i; int count, r;

for(i = 0; i < 53; i++) { table[i] = min + (getrand() % (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",2) == 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: */ /* jv is "random" (where's it seeded from?) */ jv = (uint16)(getrand() % 53); for(; n > 0; n--) {

/* count limits the number of traverses to 53^2 so we don't get stuck */ /* 2809 is actually too low per Chudov: ** "For example, if ALL B == 1, A == 16385, and C == 20361, the ** loop may need (20361-16385) passes to get to the < 16384 value." */ for(count = 0; count < 2809; count++) { ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

replace 2809 with (20361-16385) * 53 + 1000

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");

^^^^^^ and here

else { if (!diehard) { write(1,(unsigned char *)&A[jv],sizeof(uint16)); } 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.

Everything is still screwed up. The As, Bs and Cs are selected in much the same fashion as LOTTO numbers except that the pools are much larger and order is significant. They are not random, that would never work. On Sat, 30 Nov 1996, Eric Murray wrote:

Igor Chudov @ home writes:

...

[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.

Yea, you're right, rand() is lame.

I added /dev/random to my Linux box and changed my small test to use it. I also changed the way that I use JV- I had been setting it to a random value for each trip through the "engine", but since I beleive that its value can't really be random (if you want to be able to have someone decrypt your stuff :-) but must be exchanged in the key, I set it to a random value once and then let it float. It's also a lot faster that way, /dev/random is pretty slow (because it's looking for real random material).

My results from xnoisesph were wrong- xnoisesph wants random bytes instead of random integers in ascii format as I was producing. Changing it (as I have below) makes the xnoisesph output look much better, but it still isn't all that random. The random seed generators I have written that get their randomness from repeated calls to high-resolution timers and hashes of system log files do better. I also fixed a minor bug in arg processing.

#include <stdio.h> #include <fcntl.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. ** V0.2 */

typedef unsigned char byte; typedef unsigned short uint16;

/* tables: */ uint16 A[53]; uint16 B[53]; uint16 C[53];

#ifndef NO_DEV_RANDOM uint16 getrand() { uint16 ret; int fd = open("/dev/random",O_RDONLY); if (fd <= 0) { perror("/dev/random"); exit(-1); } read(fd,(unsigned char *)(&ret),sizeof(ret)); close(fd); return(ret); } #else /* do something appropriate for your OS here, rand() is lame. */ #define getrand rand #endif

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 used /dev/random here, so there's no question that ** I'm starting out with pretty good random values. */ int i; int count, r;

for(i = 0; i < 53; i++) { table[i] = min + (getrand() % (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",2) == 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: */ /* jv is "random" (where's it seeded from?) */ jv = (uint16)(getrand() % 53); for(; n > 0; n--) {

/* count limits the number of traverses to 53^2 so we don't get stuck */ /* 2809 is actually too low per Chudov: ** "For example, if ALL B == 1, A == 16385, and C == 20361, the ** loop may need (20361-16385) passes to get to the < 16384 value." */ 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) { write(1,(unsigned char *)&A[jv],sizeof(uint16)); } 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, Eric, As I have noted to Eric, I appreciate that at least both of you are trying to understand and implement the algorithm. My comments follow: On Sat, 30 Nov 1996, Igor Chudov @ home wrote:

[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.

I agree, and as I have indicated elsewhere, either the B or the C is is a prime number. The numbers in A, B, and C are not random numbers, they are only selected randomly in a manner almost identical to a LOTTO selections, except that the pools are much larger and the order is very significant. There are so many things that are wrong with the Murray implementation that it would be takes days to clarify it. It is simply not the algorithm, nor even any significant part of it. The actual As, Bs and Cs are specified at the Web ,site as is the algorithm for using the Key to select the ones actually used. In the example, 53 of 512 As, 53 of 600 plus Bs, and 53 of some 500 plus Cs.

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

--

- Igor.

With Kindest Regards, Don Wood

Eric Murray wrote:

I have translated the IPG algorithim's "engine" to C, to generate

[snippo] Now that's what I call amazing. Maybe I could rewrite PGP tomorrow (hee hee).

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.