Cryptography Reference
In-Depth Information
Input: A window of w equations of the form 5.9, starting from
round r.
Output: The recovered initial state S
r
or FAIL.
Execute IR;
1
if a contradiction is reached then
2
return (recurse backward);
3
end
else if new equations are available then
4
Execute WE;
5
Go to Step 1;
6
end
else if all equations in the window are solved then
7
Execute GSi;
8
Go to Step 5 (recurse forward);
9
end
else
10
Execute MC;
11
Go to Step 1 (recurse forward);
12
end
Algorithm 5.8.1: RecoverState
Definition 5.8.2. (d-order Pattern) A d-order pattern is a tuple A =
{i,j,U,V}, where U and V are two vectors from Z
d
N
with pairwise distinct
elements.
Definition 5.8.3. (Compliant State) At time step r, the internal state is
compliant with A if i
r
= i, j
r
= j, and d cells of S
r
with indices from U
have corresponding values from V .
Definition 5.8.4. (w-generative Pattern) A pattern A is called w-
generative if for any internal state compliant with A, the next w clockings
allow to derive w equations of the form S
G
−1
r
[z
r
] = S
r
[i
r
] + S
r
[j
r
], i.e., if
consecutive w values of j
G
are known.
The basic strategy is to look for d-order w-generative patterns with small
d and large w. Whenever the observed keystream indicates such a pattern
of the internal state, iterative recovery of the unknowns is performed using
the RecoverState algorithm and the window w is dynamically expanded. A
general time complexity estimate is performed in [117, Appendix C]. The
success probability of the full attack turns out to be at least 98%.
A very recent work [61] revisits Maximov's attack and presents an itera-
tive probabilistic state reconstruction method. It also discusses how one can
practically approach the complexity of [116].
