52
V. Mikhalev et al.
Now, let us consider an arbitrary KSG with state space S . As any state is a
member of exactly one equivalence class, the state space can be divided into
distinct equivalence classes:
S =
st
(1)
.
∪ . . .
.
∪
st
(()
(3.1)
Assume a TMDTO attacker who is given some keystream (z t ), based on an unknown
initial state st 0 . In this case if none of the precomputations are done for values in
[st 0 ], the attack will fail. This implies that the attack effort is at least linear in the
number of equivalence classes. Hence we can see that if we design a cipher such
that ≥ 2 κ , such a cipher will have the required security level against trade-off
attacks.
Let us now take a look at the minimum time effort for a TMDTO attack against
a KSG with a KUF. We make in the following the assumption that any two different
states ST = (st, k) and ST = (st , k ) with k = k never produce the same
keystream, that is F
compl.
Out
(ST ) ≡ kse F
compl.
Out
(ST ). Hence, we have at least 2 κ
different equivalence classes. As the effort grows linearly with the number of
equivalence classes, we assume in favor of the attacker that we have exactly 2 κ
equivalence classes. This gives a minimum time complexity of 2 κ . This means that,
in theory, it is possible to design a cipher with a security level of κ regardless of the
length σ of its variable state.
3.2.2 On Continuously Accessing the Key
In most cases the workflow of ciphers looks as follows. After the encryption or
decryption process is started, the key is loaded from some non-volatile memory
NVM into some registers, i.e., into some volatile memory VM. We call the value in
VM a volatile value as it usually changes during the encryption/decryption process
and the value stored in NVM, the non-volatile value or non-volatile key which
remains fixed. It holds for most designs that after the key has been loaded from NVM
into VM, the NVM is usually not involved anymore (unless the key schedule or the
initialization process needs to be restarted). But the design approach discussed in
Sect. 3.2.1 requires that the key which is stored on the device has to be accessed not
only for initialization of the registers but continuously in the encryption/decryption
process. The feasibility of this approach for different scenarios was investigated
in [421].
It has been argued there that continuously accessing the key can impact the
achievable throughput. To this end, two different cases need to be considered. The
first one is when the key is set once and is never changed and the second one is when
it is possible to rewrite the key. The types of NVM (e.g., MROM and PROM) which
can be used in the first case, allow for efficient implementations where accessing the
key bits induces no overhead. However, the key management is very difficult here.
V. Mikhalev et al.
Now, let us consider an arbitrary KSG with state space S . As any state is a
member of exactly one equivalence class, the state space can be divided into
distinct equivalence classes:
S =
st
(1)
.
∪ . . .
.
∪
st
(()
(3.1)
Assume a TMDTO attacker who is given some keystream (z t ), based on an unknown
initial state st 0 . In this case if none of the precomputations are done for values in
[st 0 ], the attack will fail. This implies that the attack effort is at least linear in the
number of equivalence classes. Hence we can see that if we design a cipher such
that ≥ 2 κ , such a cipher will have the required security level against trade-off
attacks.
Let us now take a look at the minimum time effort for a TMDTO attack against
a KSG with a KUF. We make in the following the assumption that any two different
states ST = (st, k) and ST = (st , k ) with k = k never produce the same
keystream, that is F
compl.
Out
(ST ) ≡ kse F
compl.
Out
(ST ). Hence, we have at least 2 κ
different equivalence classes. As the effort grows linearly with the number of
equivalence classes, we assume in favor of the attacker that we have exactly 2 κ
equivalence classes. This gives a minimum time complexity of 2 κ . This means that,
in theory, it is possible to design a cipher with a security level of κ regardless of the
length σ of its variable state.
3.2.2 On Continuously Accessing the Key
In most cases the workflow of ciphers looks as follows. After the encryption or
decryption process is started, the key is loaded from some non-volatile memory
NVM into some registers, i.e., into some volatile memory VM. We call the value in
VM a volatile value as it usually changes during the encryption/decryption process
and the value stored in NVM, the non-volatile value or non-volatile key which
remains fixed. It holds for most designs that after the key has been loaded from NVM
into VM, the NVM is usually not involved anymore (unless the key schedule or the
initialization process needs to be restarted). But the design approach discussed in
Sect. 3.2.1 requires that the key which is stored on the device has to be accessed not
only for initialization of the registers but continuously in the encryption/decryption
process. The feasibility of this approach for different scenarios was investigated
in [421].
It has been argued there that continuously accessing the key can impact the
achievable throughput. To this end, two different cases need to be considered. The
first one is when the key is set once and is never changed and the second one is when
it is possible to rewrite the key. The types of NVM (e.g., MROM and PROM) which
can be used in the first case, allow for efficient implementations where accessing the
key bits induces no overhead. However, the key management is very difficult here.