56
V. Mikhalev et al.
Algorithm 1 Internal state recovery
1: Input: Non-empty set of internal state candidates, S; keystream {z t+1+θ f , . . . , z t+θ f +αter };
the maximum number of clocks for each test, α ter ; average guess capacity, Pr g ; miss event
probability
2: Set ter =
− ln
2αter and α thr = α ter (1 − Pr g + ter )
3: Initialize CUR and NEW as two empty sets and load all the states in S into CUR
4: Set #MM(st) to 0 for each state st in CUR and make a copy of CUR as the roots
5: for each clock i from t to (t + α ter − 1) do
6:
for each state st in CUR do
7:
Compute Pr g (st) f
8:
if Pr g (st) f = 0.5 then
9:
Set f b sugg = 0
10:
else
11:
Set f b sugg as the feedback value of st suggested through f Upd
12:
end if
13:
if f Upd (k, st) of st can be determined from the output bit z i+1+θ f then
14:
Run Determine Procedure (Algorithm 2)
15:
else
16:
Run Check-and-guess Procedure (Algorithm 3)
17:
end if
18:
end for
19:
Terminate if NEW is empty and give no output
20:
Copy NEW to CUR
21:
Empty NEW
22: end for
23: Output: the roots in CUR as the candidates for the correct state at clock t
Algorithm 2 Determine procedure
1: Determine the feedback value as f Upd (k, st) from the corresponding output bit
2: Update st by clocking it with the feedback value f b det
3: if f b sugg = f b det (it is a mismatch) then
4:
Increment #MM(st) by one
5: end if
6: if #MM(st) ≤ α thr then
7:
Add updated st with #MM(st) and its root to NEW
8: end if
a correct state. This provides us with a distinguisher to recover the correct state
without knowing the key. We set a threshold value α thr , between α ter (1 − Pr g )
and α ter /2 and simply eliminate the states whose number of mismatches exceeds
α thr . We expect all the wrong internal states to be eliminated for a well-chosen pair
(α ter , α thr ) and only the correct state is expected to survive. Theorem 1 suggests
appropriate values for α ter so as to obtain a given success rate. Then we fix the
threshold value accordingly, in Algorithm 1 in its third line.
The performance of Algorithm 1 depends heavily on how many clocks we should
go further to eliminate all the wrong states without missing the correct state. This is
V. Mikhalev et al.
Algorithm 1 Internal state recovery
1: Input: Non-empty set of internal state candidates, S; keystream {z t+1+θ f , . . . , z t+θ f +αter };
the maximum number of clocks for each test, α ter ; average guess capacity, Pr g ; miss event
probability
2: Set ter =
− ln
2αter and α thr = α ter (1 − Pr g + ter )
3: Initialize CUR and NEW as two empty sets and load all the states in S into CUR
4: Set #MM(st) to 0 for each state st in CUR and make a copy of CUR as the roots
5: for each clock i from t to (t + α ter − 1) do
6:
for each state st in CUR do
7:
Compute Pr g (st) f
8:
if Pr g (st) f = 0.5 then
9:
Set f b sugg = 0
10:
else
11:
Set f b sugg as the feedback value of st suggested through f Upd
12:
end if
13:
if f Upd (k, st) of st can be determined from the output bit z i+1+θ f then
14:
Run Determine Procedure (Algorithm 2)
15:
else
16:
Run Check-and-guess Procedure (Algorithm 3)
17:
end if
18:
end for
19:
Terminate if NEW is empty and give no output
20:
Copy NEW to CUR
21:
Empty NEW
22: end for
23: Output: the roots in CUR as the candidates for the correct state at clock t
Algorithm 2 Determine procedure
1: Determine the feedback value as f Upd (k, st) from the corresponding output bit
2: Update st by clocking it with the feedback value f b det
3: if f b sugg = f b det (it is a mismatch) then
4:
Increment #MM(st) by one
5: end if
6: if #MM(st) ≤ α thr then
7:
Add updated st with #MM(st) and its root to NEW
8: end if
a correct state. This provides us with a distinguisher to recover the correct state
without knowing the key. We set a threshold value α thr , between α ter (1 − Pr g )
and α ter /2 and simply eliminate the states whose number of mismatches exceeds
α thr . We expect all the wrong internal states to be eliminated for a well-chosen pair
(α ter , α thr ) and only the correct state is expected to survive. Theorem 1 suggests
appropriate values for α ter so as to obtain a given success rate. Then we fix the
threshold value accordingly, in Algorithm 1 in its third line.
The performance of Algorithm 1 depends heavily on how many clocks we should
go further to eliminate all the wrong states without missing the correct state. This is