Re: Avalanche analysis of the Arc4 CSPRNG

Bill Frantz (frantz@communities.com)
Wed, 04 Nov 1998 14:48:39 -0800

• Next message: Andreas Bogk: "Re: Euro-Telecoms Standards gives access to GSM & other specs"
• Previous message: Robert Hettinga: "DigiCash Inc. to File Reorganization, Seeks Partners to Drive eCash Forward"
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"
• Next in thread: Bill Frantz: "Re: Avalanche analysis of the Arc4 CSPRNG"

>Investigate whether using 20 byte seeds (e.g. from SHA1) makes
>any difference in avalanche effect.

It appears to make a small difference. The below 10% deviation level is
not reached until zeroesByOrder[146] instead of 137 in the 16 byte seed
case. It appears that withdrawing 256 bytes before use will work for 20
byte seeds about as well as for 16 byte seeds, and it is needed to suppress
the [255] peak.

 LOOP_COUNT = 1000000, BYTES_PER_TEST = 1024;

expected number of zeroes=3906.25
zeroesByOrder[0]=630284, 16135%
zeroesByOrder[1]=524553, 13428%
zeroesByOrder[2]=437205, 11192%
zeroesByOrder[3]=365629, 9360%
zeroesByOrder[4]=308231, 7890%
zeroesByOrder[5]=259988, 6655%
zeroesByOrder[6]=219915, 5629%

zeroesByOrder[31]=13302, 340%
zeroesByOrder[32]=12552, 321%
zeroesByOrder[33]=11906, 304%
zeroesByOrder[34]=11587, 296%

zeroesByOrder[62]=6431, 164%
zeroesByOrder[63]=6214, 159%
zeroesByOrder[64]=6142, 157%
zeroesByOrder[65]=6144, 157%

zeroesByOrder[126]=4485, 114%
zeroesByOrder[127]=4541, 116%
zeroesByOrder[128]=4401, 112%

zeroesByOrder[146]=4346, 111%
   skipped 108 - less than 10% difference from expected
zeroesByOrder[255]=119380, 3056%
   skipped 768 - less than 10% difference from expected

MaxPercentOver=16135.2705 MinPercentUnder=93.2864
expected bits per nonzero byte=4.0156865 observed=+0.0053930283,-0.0043730736
totalzeroes=8354549 totalLeading=1782837

16 byte seeds (repeated from earlier post)

 LOOP_COUNT = 1000000, BYTES_PER_TEST = 1024;

expected number of zeroes=3906.25
zeroesByOrder[0]=570085, 14594%
zeroesByOrder[1]=455614, 11663%
zeroesByOrder[2]=366720, 9388%
zeroesByOrder[3]=295586, 7567%
zeroesByOrder[4]=238699, 6110%
zeroesByOrder[5]=193725, 4959%
zeroesByOrder[6]=157646, 4035%
 the values continue descending (following are samples)
zeroesByOrder[33]=8940, 228%
zeroesByOrder[34]=9063, 232%

zeroesByOrder[62]=5997, 153%
zeroesByOrder[63]=5935, 151%
zeroesByOrder[64]=5917, 151%
zeroesByOrder[65]=5831, 149%

zeroesByOrder[126]=4321, 110%
zeroesByOrder[127]=4324, 110%
zeroesByOrder[128]=4349, 111%

zeroesByOrder[137]=4303, 110%
   skipped 117 - less than 10% difference from expected
zeroesByOrder[255]=113991, 2918%
   skipped 768 - less than 10% difference from expected

MaxPercentOver=14594.176 MinPercentUnder=95.5648
expected bits per nonzero byte=4.0156865 observed=+0.0037994385,-0.014258385
totalzeroes=7318254 totalLeading=1382696

Bill Frantz Electric Communities
Capability Security Guru 10101 De Anza Blvd.
frantz@communities.com Cupertino, CA 95014
408/342-9576 http://www.communities.com

• Next message: Andreas Bogk: "Re: Euro-Telecoms Standards gives access to GSM & other specs"
• Previous message: Robert Hettinga: "DigiCash Inc. to File Reorganization, Seeks Partners to Drive eCash Forward"
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"
• Next in thread: Bill Frantz: "Re: Avalanche analysis of the Arc4 CSPRNG"