3 Selected Design and Analysis Techniques for Contemporary Symmetric Encryption
57
Algorithm 3 Check-and-guess procedure
1: if the output of st is equal to the actual output at the corresponding clock then
2:
Make two copies st 0 , st 1 of st with #MM(st 0 ) = #MM(st 1 ) := #MM(st)
3:
Set the feedback value to 0 for st 0 and update st 0 and 1 for st 1 and update st 1
4:
if f b sugg = 0 then
5:
Increment #MM(st 1 ) by one
6:
else
7:
Increment #MM(st 0 ) by one
8:
end if
9:
if #MM(st 0 ) ≤ α thr then
10:
Add st 0 along with #MM(st 0 ) to NEW and set the root of S as its root
11:
end if
12:
if #MM(st 1 ) ≤ α thr then
13:
Add st 1 along with #MM(st 1 ) to NEW and set the root of st as its root
14:
end if
15: end if
determined by the success rate of the algorithm which in turn is dominated by the
guess capacity (Definition 4) as stated in the following Theorem 1 [314]:
Theorem 1 Let Pr g > 1/2 be the guess capacity of a given KSG with Boolean KFF
having internal state size σ . For a given 0 < < < 1, if α ter is greater than or equal
to
1
(2 Pr g −1) 2
√ −2 ln +
2 ln 2 · (σ − 1)
2
,
then the success rate of the attack in Algorithm 1 is at least 1 − and the number of
false alarms is less than one in total.
The average guess capacity of Sprout is 0.75. Hence it is possible to recover
its correct state without knowing the key by eliminating a wrong state in roughly
122 clocks [314]. Checking roughly 2 40 states (which are called “weak states” and
loaded into a table in the precomputation phase), one can recover the key in roughly
2 38 encryptions [314]. On the other hand, Algorithm 1 becomes infeasible when Pr g
approaches 1/2. Plantlet (Sect. 3.2.3) has a guess capacity of 1/2, so Algorithm 1
is not applicable to Plantlet. Concluding, the attack above implies a new security
criterion: the guess capacity of the feedback function of a KSG with Boolean KFF
should be one half in order to avoid state recovery attacks that bypass the key.
57
Algorithm 3 Check-and-guess procedure
1: if the output of st is equal to the actual output at the corresponding clock then
2:
Make two copies st 0 , st 1 of st with #MM(st 0 ) = #MM(st 1 ) := #MM(st)
3:
Set the feedback value to 0 for st 0 and update st 0 and 1 for st 1 and update st 1
4:
if f b sugg = 0 then
5:
Increment #MM(st 1 ) by one
6:
else
7:
Increment #MM(st 0 ) by one
8:
end if
9:
if #MM(st 0 ) ≤ α thr then
10:
Add st 0 along with #MM(st 0 ) to NEW and set the root of S as its root
11:
end if
12:
if #MM(st 1 ) ≤ α thr then
13:
Add st 1 along with #MM(st 1 ) to NEW and set the root of st as its root
14:
end if
15: end if
determined by the success rate of the algorithm which in turn is dominated by the
guess capacity (Definition 4) as stated in the following Theorem 1 [314]:
Theorem 1 Let Pr g > 1/2 be the guess capacity of a given KSG with Boolean KFF
having internal state size σ . For a given 0 < < < 1, if α ter is greater than or equal
to
1
(2 Pr g −1) 2
√ −2 ln +
2 ln 2 · (σ − 1)
2
,
then the success rate of the attack in Algorithm 1 is at least 1 − and the number of
false alarms is less than one in total.
The average guess capacity of Sprout is 0.75. Hence it is possible to recover
its correct state without knowing the key by eliminating a wrong state in roughly
122 clocks [314]. Checking roughly 2 40 states (which are called “weak states” and
loaded into a table in the precomputation phase), one can recover the key in roughly
2 38 encryptions [314]. On the other hand, Algorithm 1 becomes infeasible when Pr g
approaches 1/2. Plantlet (Sect. 3.2.3) has a guess capacity of 1/2, so Algorithm 1
is not applicable to Plantlet. Concluding, the attack above implies a new security
criterion: the guess capacity of the feedback function of a KSG with Boolean KFF
should be one half in order to avoid state recovery attacks that bypass the key.