Cryptography Reference
In-Depth Information
Interestingly, if we go for R = N runs, i.e., if we have a total of N
2
(= 2
16
for N = 256) many keystream output bytes, we can construct the permutation
in just O(N) time. From Lemma 8.4.11, when ρ = N, we have
S
ρN
= < a
0
,a
1
,a
2
,...,a
N−1
> = S
0
.
In this case, after the first N runs, the structure of the permutation, the
output indices as well as the keystream output bytes start repeating in the
same order. Considering the keystream output bytes coming from a fixed
index a
y−1
+ a
y
, i.e., the values z
ρN+ρ+y
for a fixed y, 0 ≤ρ ≤ N −1, we can
readily get a resolved permutation, without requiring to perform exhaustive
assignments.
8.4.3 State Recovery when Both Indices Are Unknown
So far we have considered that the value at which j
G
is stuck is zero.
All the results above can easily be extended when j
G
is stuck at any value
x ∈{0,...,N − 1}. Suppose r
st
is the round at which j
G
gets stuck at x for
the first time and from round r
st
onwards it remains stuck at x, r
st
≥ 1. The
value of the deterministic index i
G
at round r
st
is i
st
= r
st
mod N. Then
after d = (x−i
st
) mod N more rounds, i.e., at round r
st
+ d + 1, i
G
becomes
x + 1 for the first time after j
G
got stuck. We can denote the indices of the
permutation and the corresponding values after the end of round r
st
+ d as
follows.
Indices
0
1
. . .
x−
1
x
x
+ 1
. . .
N −
2
N −
1
Values
b
N−x
b
N−x+1
. . .
b
N−1
b
0
b
1
. . .
b
N−2−x
b
N−1−x
Thus, we have the following result.
Proposition 8.4.20. “The evolution of the permutation from round r
st
+d+1
onwards, given j
G
stuck at x from round r
st
” is analogous to “the x-rotation
of the permutation evolving from round 1 onwards, given j
G
stuck at 0 from
round 1.”
Suppose that the attacker can access the keystream bytes from the point
when j
G
got stuck. Because of the cyclic pattern mentioned in Proposi-
tion 8.4.20, and because of the relative gap of N + 1 rounds between the
elements of any candidate pair (as discussed following Theorem 8.4.12 in Sec-
tion 8.4.1), the attacker does not need to know r
st
or i
st
. If the attacker starts
counting the first run from the point when he has the first keystream byte at
his disposal, he can e
ciently recover the permutation at the point when j
G
got stuck. In the subsequent analysis, we assume that the attacker does not
know
1. the round r
st
from which j
G
got stuck,
2. the value i
st
of the deterministic index i
G
when j
G
got stuck and
