3 Selected Design and Analysis Techniques for Contemporary Symmetric Encryption
55
functions with index i = i ∗ can be rewritten as Upd i (k, st) = Upd i (st). We call
Upd i ∗ (k, st) the keyed feedback function and denote it by f Upd (k, st).
When we say the “feedback value”, we mean the output of the keyed feedback
function f Upd (k, st). The most prominent examples of KSGs with a Boolean KUF
in the literature are Sprout [27] and its successor Plantlet [421] (see Sect. 3.2.3).
Even though several attacks against the cipher Sprout have been published [50, 203,
355, 387, 593], only little is known about the security of the underlying approach
(see Sect. 3.2.1) in general. In the following, we explain the only existing generic
attack [314] that implies a design criterion for this type of ciphers.
The attack is a guess-and-determine attack that is based on guessing internal
states from the observed output. Its efficiency heavily relies on the guess capacity,
which we define next:
Definition 4 For a given KSG with a Boolean KFF having a σ -bit internal state, a
κ-bit key, and f Upd as its Boolean keyed feedback function, we define the average
guess capacity as
Pr g =
1
2
+ 2
−σ
st
#{k : f Upd (k, st) = 0}
2 κ
−
1
2
.
The average guess capacity simply indicates how accurately we can guess the
feedback value f Upd (k, st) when we know the internal state but we do not know the
key. The following attack [314] applies to the case of Pr g > 1/2 which eventually
allows us to formulate a necessary design criterion.
The core of the attack is an internal state recovery algorithm (see Algorithm 1).
It tests, for a given internal state whether it can consistently continue producing
the observed output bits. To this end, it produces the feedback values (the outputs
of the Boolean keyed feedback function) for the next states by either determining
them from the output if that is possible or first checking and then guessing them.
It consists of two parts: determining the feedback value is done by Algorithm 2
and checking the candidate state and then guessing the feedback value if the state
survives, is achieved by Algorithm 3. It is obvious that Algorithm 2 produces
only one feedback value for each clock. Similarly, Algorithm 3 first checks if a
candidate state can produce the output. So, it survives with a probability of one half
and the surviving states will have two successors. Hence, neither Algorithm 2 nor
Algorithm 3 will propagate the total number of states to be checked.
Each candidate state has successors for consecutive clocks and a set of feedback
values produced by Algorithm 1. On the other hand, we count the number of
mismatches for each feedback value. We say that a feedback value is a mismatch
if it is not the suggested value obtained through its internal state. If the probability
that the feedback value is equal to 0 (or 1) for a given state is higher than one half,
then 0 (or 1) will be the suggested value of that state.
Assume we clock the generator α ter steps to check each state. Then, we expect
roughly α ter /2 mismatches for a wrong state and α ter (1 − Pr g ) mismatches for
55
functions with index i = i ∗ can be rewritten as Upd i (k, st) = Upd i (st). We call
Upd i ∗ (k, st) the keyed feedback function and denote it by f Upd (k, st).
When we say the “feedback value”, we mean the output of the keyed feedback
function f Upd (k, st). The most prominent examples of KSGs with a Boolean KUF
in the literature are Sprout [27] and its successor Plantlet [421] (see Sect. 3.2.3).
Even though several attacks against the cipher Sprout have been published [50, 203,
355, 387, 593], only little is known about the security of the underlying approach
(see Sect. 3.2.1) in general. In the following, we explain the only existing generic
attack [314] that implies a design criterion for this type of ciphers.
The attack is a guess-and-determine attack that is based on guessing internal
states from the observed output. Its efficiency heavily relies on the guess capacity,
which we define next:
Definition 4 For a given KSG with a Boolean KFF having a σ -bit internal state, a
κ-bit key, and f Upd as its Boolean keyed feedback function, we define the average
guess capacity as
Pr g =
1
2
+ 2
−σ
st
#{k : f Upd (k, st) = 0}
2 κ
−
1
2
.
The average guess capacity simply indicates how accurately we can guess the
feedback value f Upd (k, st) when we know the internal state but we do not know the
key. The following attack [314] applies to the case of Pr g > 1/2 which eventually
allows us to formulate a necessary design criterion.
The core of the attack is an internal state recovery algorithm (see Algorithm 1).
It tests, for a given internal state whether it can consistently continue producing
the observed output bits. To this end, it produces the feedback values (the outputs
of the Boolean keyed feedback function) for the next states by either determining
them from the output if that is possible or first checking and then guessing them.
It consists of two parts: determining the feedback value is done by Algorithm 2
and checking the candidate state and then guessing the feedback value if the state
survives, is achieved by Algorithm 3. It is obvious that Algorithm 2 produces
only one feedback value for each clock. Similarly, Algorithm 3 first checks if a
candidate state can produce the output. So, it survives with a probability of one half
and the surviving states will have two successors. Hence, neither Algorithm 2 nor
Algorithm 3 will propagate the total number of states to be checked.
Each candidate state has successors for consecutive clocks and a set of feedback
values produced by Algorithm 1. On the other hand, we count the number of
mismatches for each feedback value. We say that a feedback value is a mismatch
if it is not the suggested value obtained through its internal state. If the probability
that the feedback value is equal to 0 (or 1) for a given state is higher than one half,
then 0 (or 1) will be the suggested value of that state.
Assume we clock the generator α ter steps to check each state. Then, we expect
roughly α ter /2 mismatches for a wrong state and α ter (1 − Pr g ) mismatches for