Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:17:17
Bill Frantz (frantz@communities.com)
Fri, 13 Nov 1998 17:05:40 -0800
>Investigate whether using Knuth's algorithm P instead of the Arc4 key
>schedule makes any difference.
I have heard it said that the most exciting thing to hear in a laboratory
is not "Eureka!", but rather a quite, "That's strange". Well, I had one of
those when I tried applying algorithm P to the Arc4 key schedule. Here is
sample code of the best key schedule with notes:
public synchronized void reseed(byte[] seed) {
for (int k=0; k<256; k++) {
//int i = k; //Note 1
//int i = (255-k); //Note 2
int i = 0xff & (myArc4I - k); //Note 3
int rand = i
+ (myArc4SBox[i] & 0xff) //Note 4
+ (seed[i%seed.length] & 0xff);
rand = rand & 0xff; //Note 5
int modulus = 1 + (255 - k);
int pNum = ( rand % (modulus));
int j = (i - pNum) & 0xff;
// Swap bytes S[i] and S[j]
byte s = myArc4SBox[i];
myArc4SBox[i] = myArc4SBox[j];
myArc4SBox[j] = s;
}
}
To review: Each test consisted of reseeding an Arc4 PRNG and it's clone
with two randomly selected seeds that differed in only one bit. The
outputs were combined with XOR and the number of zeros vs. birth order were
calculated. The results are calculated as the number observed as a percent
of the number expected.
In all trials, I did 1,000,000 tests. Some of the tests extracted 1024
bytes from each Arc4 instance. These tests left the value myArc4I at zero
for the start of each trial. Other tests extracted 1021 bytes. These
tests explored the behavior where all 256 values of myArc4I are equally
probable. All the tests showed an improvement in avalanche as the birth
order increased. All of them became reasonable (within my measurements)
after 256 bytes had been withdrawn. All of the tests with 1024 byte
withdrawals showed an anomalous peak on the [255] output, as previously noted.
Note 1: Using algorithm P running up was a bust. It was no better that the
standard Arc4 key schedule. Algorithm P running up:
MaxPercentOver=16418.406 MinPercentUnder=95.6416, Standard schedule:
MaxPercentOver=14594.176 MinPercentUnder=95.5648
Note 2: Running the schedule from 255 to 0 made things a lot better with
algorithm P. It is strange it didn't with the normal key schedule.
MaxPercentOver=1687.3217 MinPercentUnder=94.7968
Note 3: Testing with 1021 showed that with algorithm P, anon's suggestion
of running backwards from myArc4I to 0 and then back to myArc4I+1 was
needed. From 255: MaxPercentOver=12458.112 MinPercentUnder=94.4384, from
myArc4I: MaxPercentOver=1866.24 MinPercentUnder=95.6672
Note 4: Masking the inputs to positive values is a help. (Java has signed
bytes.) With masking: MaxPercentOver=1862.8096 MinPercentUnder=95.1296,
Without masking: MaxPercentOver=12145.613 MinPercentUnder=95.3344
Note 5: A program bug resulted in the best avalanche of all. Masking rand
to one byte resulted in: MaxPercentOver=1687.2704 MinPercentUnder=93.7984
Conclusions: Running algorithm P backwards gets a significant improvement
in avalanche at the cost of a divide instruction. I think the most
interesting conclusion is that Arc4 avalanche is very sensitive to the
calculation of the value "j". Because it is not random, small tweaks (like
that in Note 5) have difficult to predict effects.
Bill Frantz Electric Communities
Capability Security Guru 10101 De Anza Blvd.
frantz@communities.com Cupertino, CA 95014
408/342-9576 http://www.communities.com
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:17:17