Cryptography Reference
In-Depth Information
Input: Secret key array K[0...N −1].
Output: Scrambled permutation array S[0...N −1].
Initialization:
for i = 0,...,N −1 do
S[i] = i;
j = 0;
end
Perform scrambling layer 1: basic scrambling as in RC4 KSA;
1
Perform scrambling layer 2: scrambling with IV;
2
Perform scrambling layer 3: zigzag scrambling;
3
Algorithm 9.4.1: KSA
+
of RC4
+
are three similar scrambling layers instead of one, each with N iterations. As
the key scheduling is run only once, this does not affect the performance of
the cipher much.
Next we discuss how the new KSA
+
avoids many weaknesses of the original
KSA.
Removal of secret key correlation with the permutation bytes
After Layer 1, the values in the first quarter of the permutation are biased
to linear combinations of the secret key bytes. In Layer 1, the deterministic
index i is moved from the middle to the left end so that the above biases fade
away. This takes care of Item (1) in the list of the weaknesses of the RC4
KSA. A similar operation is performed in the second half of the permutation
to get rid of the biases of the inverse permutation as described in Item (4).
Next, the XOR operation helps further to wipe out these biases. The biases
involving the nested indexing mentioned in Item (3) and Item (4) arise due
to the biases of direct indexing. So, the removal of the biases at the direct
indices of S
N
and S
−1
automatically eliminates those at the nested indices
N
also.
The bias of Item (2) are generalization of the biases of Item (1). They
originate from the incremental update of j which helps to form a recursive
equation involving the key bytes. In the new design, the bit-by-bit XOR
operation as well as the zigzag scrambling in Layer 3 prevents one from forming
such recursive equations connecting the key bytes and the permutation bytes.
Extensive experimentation has not revealed any correlation between the
permutation entries S
N
+
[y] with f
y
. Also, the nested entries S
N
+
[S
N
+
[y]],
S
N
+
[S
N
+
[S
N
+
[y]]] etc. are also found to be unbiased.
Item (7) is about the movement frequency of the permutation entries. The
following experimental results show that such weaknesses of RC4 KSA are
absent in the new design. The data is generated by averaging over 100 million
runs of KSA
+
with 16 bytes key in each run. We find that as v increases from
