Cryptography Reference
In-Depth Information
can be formed, where each equation contains only two unknowns,
(S
t
)
−1
[z
t
],S
t
[j
t
],
(5.10)
instead of four unknowns j
G
,S
G
[i
G
],S
G
[j
G
],(S
G
)
−1
[z] as in Knudsen's at-
tack. The set of w equations of the above form is called a window of length
w.
The algorithm for recovery is a recursive one. It begins with a window
of w equations of the form 5.9 and tries solving them. An equation is called
solved or processed if the corresponding unknowns (5.10) have been either
explicitly derived or guessed, and an equation is termed as active if it is not
yet processed. The window dynamically grows and shrinks. When window
length w is su
ciently long (say, w = 2N), all equations are likely to be solved
and the initial state S
r
is likely to be fully recovered. The algorithm has four
major components.
1. Iterative Recovering (IR) Block. It receives a number of active
equations in the window as input and attempts to derive as many un-
knowns (S
t
)
−1
[z
t
],S
t
[j
t
] as possible. Upon contradiction, the recur-
sion steps backward.
2. Find and Guess Maximum Clique (MC) Block. If no more active
equation can be solved, (S
t
)
−1
[z
t
] for one t needed to be guessed. Con-
struct a graph using the active equations as vertices v
t
. Two vertices v
t
1
and v
t
2
are connected by an edge, if either z
t
1
= z
t
2
or S
t
1
[j
t
1
] = S
t
2
[j
t
2
].
Guessing any unknown variable in such a subgraph solves all the equa-
tions involved and hence these subgraphs are cliques. The role of the
MC block is to search for a maximum clique and guess one (S
t
)
−1
[z
t
]
for one of the equations belonging to the clique.
3. Window Expansion (WE) Block. A new equation is added to the
system as soon as the missing value S
t
[i
t
] in the beginning or in the
end of the window is derived. The WE block checks for this event and
dynamically extends the window.
4. Guessing One S[i] (GSi) Block. If no active equations are left and
the initial state is not yet fully recovered, the window is then expanded
by a direct guess of S
t
[i
t
], at one end (in front or in back) of the
window.
Algorithm 5.8.1 gives the sequence of steps that need to be executed in
order to perform the state recovery.
Some precomputation may be performed to identify a certain position in
the keystream where the internal state is compliant to a specific pattern.
In [116], many different kinds of patterns and their effects on the key recovery
algorithm are discussed. For the sake of simplicity, we only define the pri-
mary patterns and sketch the technique of utilizing these patterns. Interested
readers may look into [116, Sections 3, 4] for more details.
