3 Selected Design and Analysis Techniques for Contemporary Symmetric Encryption
51
st 0 := Init(iv, k) ∈ S . Afterwards, the keystream generation phase executes the
following operations repeatedly (for t ≥ 0):
1. Output the next keystream bit z t = Out(st t )
2. Update the internal state st t to st t +1 := Upd(k, st t )
The main difference between KSGs with KUF and the KSGs traditionally used as
a core of stream ciphers is that the next state is now computed not only from the
current variable state st t (as is commonly done) but also from the fixed key k.
We now explain why stream ciphers built based on the KSGs with KUF have
advantages in resisting TMDTO attacks over classical KSGs. The goal of the
TMDTO attacker is the following: given a function F : N → N and D images
y 1 , . . . , y D of F , find a preimage for any of these points, i.e., determine a value
x i ∈ N such that F (x i ) = y i . Typically, these attacks consist of two phases: a
precomputation (offline) phase, and a real-time (online) phase. At first the attacker
precomputes a large table using the function F (offline phase). In the online phase
the attacker gets D outputs of F and checks if any of these values is included in the
precomputed table. In the case of success, a preimage has been found. Obviously,
an attacker can increase the success probability by either precomputing more values
in the offline phase or collecting more data in the online phase where the optimal
trade-off is usually given as |D| =
√
|N |.
The goal of a TMDTO attack in the context of KSGs is to recover one internal
state as this allows us to compute the complete keystream. To this end, let F Out :
GF(2) σ → GF(2) σ be the function that takes the internal state st t ∈ GF(2) σ at
some clock t as input and outputs the σ keystream bits z t , . . . , z t +σ −1 . Then, the
attack translates to finding a preimage of F Out for a given keystream segment with
the search space being N = S and an effort of at least
√
|S | = 2 σ/2 . This implies
the above-mentioned rule of selecting σ ≥ 2κ.
To understand the motivation behind the design principle given in Definition 1,
we introduce the notion of keystream-equivalent states which is important for
analyzing the effectiveness of a TMDTO attack. Let F
compl.
Out
be the function that
takes as input the initial state and outputs the maximum number of keystream bits.
If no bound is given by the designers, we assume that the maximum period of 2 σ
keystream bits is produced. An attacker is interested in any internal state that allows
the keystream to be computed:
Definition 2 (Keystream-Equivalent States) Consider a KSG with a function
F
compl.
Out
that outputs the complete keystream. Two states st, st ∈ S are said to
be keystream-equivalent (in short st ≡ kse st ) if there exists an integer r ≥ 0 such
that F
compl.
Out
(Upd
r (st)) = F
compl.
Out
(st ). Here, Upd
r means the r-times application
of Upd.
For any state st ∈ S , we denote by [st] its equivalence class, that is [st] =
{st ∈ S |st ≡ kse st }.
51
st 0 := Init(iv, k) ∈ S . Afterwards, the keystream generation phase executes the
following operations repeatedly (for t ≥ 0):
1. Output the next keystream bit z t = Out(st t )
2. Update the internal state st t to st t +1 := Upd(k, st t )
The main difference between KSGs with KUF and the KSGs traditionally used as
a core of stream ciphers is that the next state is now computed not only from the
current variable state st t (as is commonly done) but also from the fixed key k.
We now explain why stream ciphers built based on the KSGs with KUF have
advantages in resisting TMDTO attacks over classical KSGs. The goal of the
TMDTO attacker is the following: given a function F : N → N and D images
y 1 , . . . , y D of F , find a preimage for any of these points, i.e., determine a value
x i ∈ N such that F (x i ) = y i . Typically, these attacks consist of two phases: a
precomputation (offline) phase, and a real-time (online) phase. At first the attacker
precomputes a large table using the function F (offline phase). In the online phase
the attacker gets D outputs of F and checks if any of these values is included in the
precomputed table. In the case of success, a preimage has been found. Obviously,
an attacker can increase the success probability by either precomputing more values
in the offline phase or collecting more data in the online phase where the optimal
trade-off is usually given as |D| =
√
|N |.
The goal of a TMDTO attack in the context of KSGs is to recover one internal
state as this allows us to compute the complete keystream. To this end, let F Out :
GF(2) σ → GF(2) σ be the function that takes the internal state st t ∈ GF(2) σ at
some clock t as input and outputs the σ keystream bits z t , . . . , z t +σ −1 . Then, the
attack translates to finding a preimage of F Out for a given keystream segment with
the search space being N = S and an effort of at least
√
|S | = 2 σ/2 . This implies
the above-mentioned rule of selecting σ ≥ 2κ.
To understand the motivation behind the design principle given in Definition 1,
we introduce the notion of keystream-equivalent states which is important for
analyzing the effectiveness of a TMDTO attack. Let F
compl.
Out
be the function that
takes as input the initial state and outputs the maximum number of keystream bits.
If no bound is given by the designers, we assume that the maximum period of 2 σ
keystream bits is produced. An attacker is interested in any internal state that allows
the keystream to be computed:
Definition 2 (Keystream-Equivalent States) Consider a KSG with a function
F
compl.
Out
that outputs the complete keystream. Two states st, st ∈ S are said to
be keystream-equivalent (in short st ≡ kse st ) if there exists an integer r ≥ 0 such
that F
compl.
Out
(Upd
r (st)) = F
compl.
Out
(st ). Here, Upd
r means the r-times application
of Upd.
For any state st ∈ S , we denote by [st] its equivalence class, that is [st] =
{st ∈ S |st ≡ kse st }.