Cryptography Reference
In-Depth Information
3.2.1 Biased Sign of RC4 Permutation
The sign of a permutation Π = (π
0
,π
1
,...,π
n−1
) is defined as
sgn(Π) = (−1)
|I(Π)|
,
where
}
is the set of inversions. Alternatively, if Π can be decomposed into a product
of m transpositions, then the sign is given by
I(Π) = {(u,v) : u < v & π
u
> π
v
+1, if m is even;
−1, if m is odd.
Although such a decomposition is not unique, the parity (i.e., oddness or
evenness) of the number of transpositions in all decompositions of a permu-
tation is the same, implying that the sign of a permutation is unique.
In [122, Section 4], the theory of random shu
es has been used to establish
the following result on the sign of the RC4 permutation after the KSA is over.
Theorem 3.2.2. Assume that the index j takes its value from Z
N
indepen-
dently and uniformly at random at each round of the KSA. Then the sign of
the permutation after the KSA can take the two possible values (−1)
N
sgn(Π) = (−1)
m
=
and
(−1)
N−1
with the following probabilities.
≈
1
sgn(S
N
) = (−1)
N
2
(1 + e
−2
)
P
sgn(S
N
) = (−1)
N−1
≈
1
2
(1−e
−2
).
Proof: The RC4 KSA begins with an identity permutation, i.e.,
sgn(S
0
) = +1. At any step, if i = j, the probability of which is
and P
1
N
, there
is no change of sign. On the other hand, if i = j, which happens with a
probability of 1 −
N
, there is a sign change. Thus, the probability that the
sign changes exactly k times and does not change the other N −k times is
given by
N
k
(1−
N
)
k
1
N
N−k
. Hence,
k
N
k
1−
1
N
1
N
N−k
sgn(S
N
) = (−1)
N
P
=
k=N,N−2,N−4,...
1 +
1
2!
+
1
≈ e
−1
4!
+
=
1
2
(1 + e
−2
).
In the above derivation, it is assumed that N is su
ciently large. The other
probability is given by 1−P
.
The implication of this result is that one can predict the sign of the per-
mutation after the key scheduling with an advantage of
sgn(S
N
) = (−1)
N
1
2
e
−2
≈ 6.7% over
random guess.
