I did some more experiments with the IPG stream-cipher algorithim and random number tests. Since IPG claim that their algorithim passes chi-square tests of randomness, I found a chi-square test program. It's written by Peter Boucher and was posted to sci.crypt in '93 (<2bum8sINN98j@roche.csl.sri.com>). I found it on the web site crypto.com, sorry I don't remember the exact URL but I can send it on request. From the comments:
New, and improved anal.c, uses chi-square.
Does the 'runs up' (or 'runs down') test with run-length equal to two get me anything over the standard chi-square test? I left it in.
BTW, the buf[i] = (((seed = (1103515245*seed +12345)) >> 16) & 0xff); test fails this one at high numbers. It's too evenly distributed.
-Peter
/* *************************************************************** * anal.c -- * * Copyright 1993 Peter K. Boucher * Permission to use, copy, modify, and distribute this * software and its documentation for any purpose and without * fee is hereby granted, provided that the above copyright * notice appear in all copies. * * Usage: anal [input_file [output_file]] * * This program counts the occurances of each character in a file * and notifies the user when a the distribution is too ragged or * too even. * * Because the chance of getting byte B after byte A should be 1:256 * (for all A's and B's), the program also checks that the successors * to each byte are randomly distributed. This means that for each byte * value (0 - 255) that occurs in the text, a count is kept of the * byte value that followed in the text, and the frequency distribution * of these succeeding bytes is also checked. * */
[..]
#define Vmin (205.33) /* 1% chance it's less */ #define Vlo (239.39) /* 25% chance it's less */ #define Vhi (269.88) /* 75% chance it's less */ #define Vmax (310.57) /* 99% chance it's less */
First I ran the output from my version of the IPG algorithim that I posted a couple days ago : % ./boucher < ipg.out Occurances: n = 12000000, V=-8375833.71 Character occurances non-random Successions: n = 46875, V=62287.82 Character successions non-random Then I ran output from a test RNG that's basically a loop around random(): % ./boucher < myrandom/out Occurances: n = 3414720, V=213050.62 Character occurances non-random Successions: n = 13338, V=1143.41 Character successions non-random As you'd expect, it doesn't look like the output from random() is all that great. Finally I generated some output from a random seed generator I wrote a while back. It gets randomness from high-resolution timers and hashing system files. It's not as fast as repeated calls to rand() but is faster than reading from /dev/random: % ./boucher < out Occurances: n = 594352, V=269.75 ================ Frequency distribution excellent! ==================== Successions: n = 2321, V=256.12 ================= Successor randomness excellent! ===================== So, from these tests it looks like IPGs PRNG, which their stream cipher is based on, is not a very good source of random values. Hence anything encrypted with it is succeptable to cryptoanalysis. How succeptable, I do not know. I am sort of curious, since IPG claimed that their PRNG produces "perfect" random data as measured by chi-square analysis, yet my analysis shows otherwise. Perhaps I have coded the algorithim incorrectly (I don't think so, it's pretty simple). Or perhaps IPG chose their keys for the ABC tables carefully to produce good results. Unfortunately that would mean that keys would have to be carefully chosen, something that's not very practical. Based on the work I've done, and the work Igor Chudov posted, it looks like the IPG algorithim is probably not very strong. If two relative crypto neophytes can find serious problems with it, imagine what might happen if experienced cryptoanalists look at it. If you were one of the people who said "it's snake oil unless it's been been tested for a zillion years" etc. you can pat yourself on the back now 'cause you were right. However I think that some of us owe Mr Wood, if not an apology for the excessive abuse he got on this list, at least some respect for putting his money where his mouth is and posting his algorithims. Maybe he'll do some research, tone down the hype, and come back with something better. -- 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