Cryptography Reference
In-Depth Information
the number of samples required is (see Theorem 6.1.1)
p
0
ǫ
2
=
N
1
.
φ
2
N
For N = 256, the value of this expression is 1870.
When the IV Precedes the Secret Key
Consider that the same message is broadcast after being encrypted by RC4
with uniformly distributed keys for multiple recipients. If the first three bytes
of each of the keys are known, then one can compute
m
′
1
= c
1
⊕(K[0] + K[1] + K[2] + 3)
for each of the keys. According to Theorem 5.5.2, the most frequent value of
m
′
1
gives the actual value of m
1
with high probability.
Knowing the first three bytes of the key is not always impractical. In
Wireless Equivalent Privacy (WEP) protocol [92] a secret key is used with
known IV modifiers in RC4 [52, 108]. If the IV bytes precede the secret key
bytes then the first three bytes of the key are actually known. This analysis
is different from [52, 108], as only the first byte of the ciphertext output is
used. In [107], on the other hand, the second byte of the ciphertext is used
for cryptanalysis in broadcast RC4.
Further, if one can ensure that the first two bytes of the key add to zero,
then following Theorem 5.5.4, one can perform the attack more e
ciently.
Experimental data establish that only 25 samples su
ce to recover m
1
with
an average probability of success exceeding 0.80 in this case.
Condition
#Samples n
min
max
avg
sd
Unconditional
1870
0.020000 0.062000
0.037990
0.008738
Unconditional
25000
0.574000 0.667000
0.628230
0.019447
Unconditional
50000
0.914000 0.955000
0.933380
0.007945
K[0] + K[1] = 0
25
0.740000 0.922000
0.806840
0.039063
K[0] + K[1] = 0
50
0.957000 0.989000
0.975410
0.007297
K[0] + K[1] = 0
100
0.998000 1.000000
0.999790
0.000431
TABLE 5.3: Results with 3-byte IV preceding 5-byte secret key.
Table 5.3 shows the success probabilities of recovering m
1
when a 3-byte
IV is preceded by the 5-byte secret key. For a given m
1
, we choose n (values of
n appear in the second column of the table) number of samples, i.e., n number
of first bytes c
1
of the ciphertexts corresponding to n runs of RC4, each time
with a randomly chosen < IV (3 bytes),Key(5 bytes) > pair. We calculate
m
′
1
= c
1
⊕(K[0] + K[1] + K[2] + 3)
