44
A. Mileva et al.
memory are equal and maximize the data, namely T = M = N 1/2 and D = N 1/4 .
We need N 1/2 to be larger than 2 k if we want the online phase of the attack to be
slower than an exhaustive search. This again simply implies that the internal state
size should be at least twice as large as the key size.
The condition on the size of the internal states of stream ciphers makes
designing ultralightweight stream ciphers too difficult. Indeed, there are several ultralightweight (say less than 1000 GE) block ciphers recently designed,
such as PRESENT [101], LED [252], KTANTAN [126], Piccolo [526], and
SIMON/SPECK [65], whereas there are almost no modern stream ciphers with
hardware area cost less than 1000 GE.
The security margin for state recovery attacks through tradeoff techniques is k
bits, whereas it is much less, 2k/3 bits, for the key recovery attacks, although any
information about the key is assumed to be more sensitive than any information
about the internal states. One can produce any internal state once the key is
recovered. However, recovery of an internal state may reveal only one session of
the encryption/decryption with the corresponding I V . Hence, it seems that the more
sensitive data are, contradictorily, protected less against tradeoff attacks!
The security level of tradeoff attacks to recover internal states should be the
same as the security level of tradeoff attacks to recover keys, just to be fair.
So, the online phase of a tradeoff attack should be at least 2 2k/3 instead of 2 k .
Similarly, the precomputation should be not faster than exhaustive search. In this
case, D = M = N 1/2 ≥ 2 2k/3 for the Babbage-Goli´ c attack. Then, N should be at
least 2 4k/3 . The same bound is valid for Biryukov-Shamir attack since the smallest
overall complexity is attained when T = M = N 1/2 .
The precomputation phase of the Biryukov-Shamir attack is roughly N/D; which
is simply N 3/4 when D = N 1/4 . So, the precomputation phase is more than
2 k . This means that it is slower than an exhaustive search. On the other hand,
the precomputation phase of the Babbage-Goli´ c attack is M, and hence if the
data is restricted to at most 2 k/3 for each key we have M ≥ 2 k and hence the
precomputation phase will be slower than an exhaustive search.
It seems it is enough to take the internal state size as at least 4k/3, not at least 2k,
for security against tradeoff attacks. This simply implies that it is possible to design
lightweight stream ciphers with much smaller internal states. However, it is an open
question how to design stream ciphers with very small internal states. The security
is generally based on the largeness of the states.
2.3.2 Guess-and-Determine Based Cryptanalysis Employing
Dedicated TMD-TO
This section presents an illustrative framework for cryptanalysis employing guessand-determine and time-memory-data trade-off (TMD-TO) methods using the
results of security evaluations of the lightweight stream ciphers Grain-v1, Grain128 and LILI-128, reported in [415, 416], and [417], respectively.
A. Mileva et al.
memory are equal and maximize the data, namely T = M = N 1/2 and D = N 1/4 .
We need N 1/2 to be larger than 2 k if we want the online phase of the attack to be
slower than an exhaustive search. This again simply implies that the internal state
size should be at least twice as large as the key size.
The condition on the size of the internal states of stream ciphers makes
designing ultralightweight stream ciphers too difficult. Indeed, there are several ultralightweight (say less than 1000 GE) block ciphers recently designed,
such as PRESENT [101], LED [252], KTANTAN [126], Piccolo [526], and
SIMON/SPECK [65], whereas there are almost no modern stream ciphers with
hardware area cost less than 1000 GE.
The security margin for state recovery attacks through tradeoff techniques is k
bits, whereas it is much less, 2k/3 bits, for the key recovery attacks, although any
information about the key is assumed to be more sensitive than any information
about the internal states. One can produce any internal state once the key is
recovered. However, recovery of an internal state may reveal only one session of
the encryption/decryption with the corresponding I V . Hence, it seems that the more
sensitive data are, contradictorily, protected less against tradeoff attacks!
The security level of tradeoff attacks to recover internal states should be the
same as the security level of tradeoff attacks to recover keys, just to be fair.
So, the online phase of a tradeoff attack should be at least 2 2k/3 instead of 2 k .
Similarly, the precomputation should be not faster than exhaustive search. In this
case, D = M = N 1/2 ≥ 2 2k/3 for the Babbage-Goli´ c attack. Then, N should be at
least 2 4k/3 . The same bound is valid for Biryukov-Shamir attack since the smallest
overall complexity is attained when T = M = N 1/2 .
The precomputation phase of the Biryukov-Shamir attack is roughly N/D; which
is simply N 3/4 when D = N 1/4 . So, the precomputation phase is more than
2 k . This means that it is slower than an exhaustive search. On the other hand,
the precomputation phase of the Babbage-Goli´ c attack is M, and hence if the
data is restricted to at most 2 k/3 for each key we have M ≥ 2 k and hence the
precomputation phase will be slower than an exhaustive search.
It seems it is enough to take the internal state size as at least 4k/3, not at least 2k,
for security against tradeoff attacks. This simply implies that it is possible to design
lightweight stream ciphers with much smaller internal states. However, it is an open
question how to design stream ciphers with very small internal states. The security
is generally based on the largeness of the states.
2.3.2 Guess-and-Determine Based Cryptanalysis Employing
Dedicated TMD-TO
This section presents an illustrative framework for cryptanalysis employing guessand-determine and time-memory-data trade-off (TMD-TO) methods using the
results of security evaluations of the lightweight stream ciphers Grain-v1, Grain128 and LILI-128, reported in [415, 416], and [417], respectively.