Re: Avalanche analysis of the Arc4 CSPRNG

Bill Frantz (frantz@communities.com)
Tue, 03 Nov 1998 16:55:16 -0800

• Next message: Bernardo B. Terrado: "knapsack..."
• Previous message: DNS Manager: "can anyone tell me how to subscribe to this list"
• 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"

In my to do list, I included:

>Investigate avalanche behavior with 256 bytes seeds. This size seed
>will result in only one bit difference in the expanded seed used by
>the key schedule.

Here are the results. Note that this test examined 4096 bytes of output
instead of only 1024 in anticipation that avalanche would take longer.
Note that there is still an obvious peek at the 768th byte
(zeroesByOrder[767]). It seems to me you should withdraw at least 1024
bytes to get good avalanche behavior with single bit differences in 2048
bit keys.

    LOOP_COUNT = 1000000, BYTES_PER_TEST = 4096;

expected number of zeroes=3906.25
zeroesByOrder[0]=963281, 24659%
zeroesByOrder[1]=949370, 24303%
zeroesByOrder[2]=936296, 23969%
zeroesByOrder[3]=923285, 23636%
zeroesByOrder[4]=910549, 23310%
zeroesByOrder[5]=898512, 23001%
zeroesByOrder[6]=886783, 22701%

zeroesByOrder[32]=643674, 16478%
zeroesByOrder[33]=636234, 16287%

zeroesByOrder[62]=455912, 11671%
zeroesByOrder[63]=450865, 11542%
zeroesByOrder[64]=445854, 11413%
zeroesByOrder[65]=440882, 11286%

zeroesByOrder[126]=222546, 5697%
zeroesByOrder[127]=219803, 5626%
zeroesByOrder[128]=217364, 5564%

zeroesByOrder[253]=42342, 1083%
zeroesByOrder[254]=41741, 1068%
zeroesByOrder[255]=295817, 7572%
zeroesByOrder[256]=41030, 1050%
zeroesByOrder[257]=40628, 1040%

zeroesByOrder[510]=5726, 146%
zeroesByOrder[511]=15407, 394%
zeroesByOrder[512]=5726, 146%
zeroesByOrder[513]=5759, 147%

zeroesByOrder[766]=4016, 102%
zeroesByOrder[767]=4420, 113%
zeroesByOrder[768]=4091, 104%

zeroesByOrder[859]=3826, 97%
zeroesByOrder[860]=4078, 104%

zeroesByOrder[1024]=4007, 102%

zeroesByOrder[4065]=4008, 102%
   skipped 6
zeroesByOrder[4072]=4012, 102%
zeroesByOrder[4073]=3791, 97%
   skipped 3
zeroesByOrder[4077]=4050, 103%
   skipped 9
zeroesByOrder[4087]=4016, 102%
   skipped 1
zeroesByOrder[4089]=3997, 102%
   skipped 1
zeroesByOrder[4091]=4026, 103%
   skipped 1
zeroesByOrder[4093]=4009, 102%
   skipped 2
MaxPercentOver=24659.992 MinPercentUnder=95.3344
expected bits per nonzero byte=4.0156865 observed=+0.0061588287,-0.007411957
totalzeroes=95953192 totalLeading=35362953

• Next message: Bernardo B. Terrado: "knapsack..."
• Previous message: DNS Manager: "can anyone tell me how to subscribe to this list"
• 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"