Cryptography Reference
In-Depth Information
This gives,
√
2
κ
1
1−p
0
+ κ
2
(1 + ǫ) (1−p
0
(1 + ǫ))
n >
.
p
0
ǫ
2
When both p
0
,ǫ ≪ 1, the numerator is approximately equal to (κ
1
+ κ
2
)
2
,
and one needs at least
(κ
1
+κ
2
)
2
p
0
ǫ
2
many samples to perform the test.
Now κ
1
= κ
2
= 1 gives α = β = 1 − 0.8413, giving a success probability
0.8413. Similarly, κ
1
= κ
2
= 2 gives α = β = 1 − 0.9772, i.e., a success
probability 0.9772. Observe that κ
1
= κ
2
= 0.5 gives α = β = 1−0.6915 and
corresponds to the special case when the least number of samples needed is
1
p
0
ǫ
2
as mentioned in Theorem 6.1.1. The success probability associated with
this number of samples is 0.6915.
Since 0.6915 > 0.5 is a reasonably good success probability, Σ(
1
p
0
ǫ
2
) many
samples are enough to mount a distinguisher and this threshold is indeed used
as a benchmark to compare the data complexities of different distinguishing
attacks in practice.
6.2 Distinguishers Based on Initial Keystream Bytes
One of the early results in RC4 distinguishers is due to Golic [58]. This
work used linear approximations to non-linear functions to establish that the
second binary derivative of the least significant bit of the keystream bytes
(i.e., the LSB of z
r
⊕z
r+2
, for r ≥ 1) is correlated to 1 with the correlation
coe
cient 152
−3n
(with n = 8 for typical RC4). According to [58], this leads
to a distinguisher for RC4 requiring about 2
40.2
keystream bytes for a false
positive (i.e., detection of bias when there is none) and false negative (i.e., no
detection of bias when there is a bias) rate of 10%.
Subsequently, the work [51] used information theoretic bounds to show
that Golic's estimates were optimistic and in fact 2
44.7
keystream bytes are
needed to achieve the false positive and false negative rate of 10%. Analyzing
the probabilities of each successive pair of n-bit outputs, called the digraph
probabilities, the work [51, Section 3] presented a more e
cient distinguisher
that requires only 2
30.6
keystream bytes for the same success probability. In-
terestingly, the digraph distribution with positive biases can be attributed to
the classes of 2-predictive 3-states and 2-predictive 2-states (see Section 5.8.1).
The distinguisher of [52, Section 5.1] is based on the fact that for a signifi-
cant fraction of keys, many initial keystream bytes contain an easily recogniz-
able pattern and this pattern is not completely flattened even when the keys
are chosen from a uniform distribution. For 64-bit keys, it is claimed in [52]
that this distinguisher requires 2
21
keystream bytes for a 10% false positive
and false negative rate.
