Cryptography Reference
In-Depth Information
(3) If i
G
= 0,1, then
8
<
(N −2)!
if z = 1;
if z = i
G
;
2(N −2)!−(N −3)!
ψ(i
G
,j
G
,z) =
if z = i
G
+ 1;
(N −2)!−(N −3)!
:
(N −2)!−2(N −3)!
otherwise.
See [9] for the detailed proof.
5.4.2 Two Steps of RC4 PRGA
The complete characterization of two steps may be attempted as in The-
orem 5.4.1, though it will be extremely complicated. Instead of enumerating
all such cases, we look into one particular two-step scenario that reveals new
weaknesses in RC4.
First let us provide the proof that the hidden index j
G
is not produced
uniformly at random conditioning on the value of j
G
two steps before. Fol-
lowing this, we note another evidence different from Corollary 5.4.2 that the
keystream of RC4 leaks information on j
G
.
Lemma 5.4.4. For any r ≥ 0, the following three are equivalent.
1. S
r
[i
r+1
] = i
r
−j
r
+ 2.
2. j
r+1
= i
r
+ 2.
3. j
r+2
= 2j
r+1
−j
r
.
Proof: First, we will show that (1) ⇐⇒ (2). In RC4 PRGA,
j
r+1
= j
r
+ S
r
[i
r+1
],
from which it immediately follows that
S
r
[i
r+1
] = i
r
−j
r
+ 2
j
r+1
= i
r
⇐⇒
+ 2.
Next, we are going to show that (2) ⇐⇒ (3). In the next round,
j
r+2
= j
r+1
+ S
r+1
[i
r+2
]
= j
r+1
+ S
r+1
[i
r
+ 2].
So,
j
r+1
= i
r
+ 2
if and only if
j
r+2
= j
r+1
+ S
r+1
[j
r+1
]
= j
r+1
+ S
r
[i
r+1
]
= j
r+1
+ (j
r+1
−j
r
)
2j
r+1
−j
r
.
=
