40
A. Mileva et al.
Table 2.9 Lightweight MACs (best known attacks)
Best known attack: data / time complexity
Chaskey
[428]
Differential-linear attack [369] 2 48 / 2 67 on 7 rounds
LightMAC
[384]
−
SipHash -2-4
[32]
−
TuLP
[238]
−
2.3.1 Reconsidering TMD Tradeoff Attacks for Lightweight
Stream Cipher Designs
We can simply divide the tradeoff attacks against ciphers into two groups, key
recovery attacks and internal state recovery attacks. The first tradeoff attack against
symmetric ciphers was introduced by Hellman [268] to illustrate that the key length
of DES was indeed too short. Hellman prepared several tables containing DES keys.
In general, the tradeoff curve is T M 2 = N 2 where T is the time complexity and
M is the memory complexity. N is the cardinality of the key space. Here, the data
complexity D = 1 since only one chosen plaintext is used to define a one way
function which produces the (reduction of the) ciphertext of the chosen plaintext
for a given key. Then, the tables are prepared during the precomputation phase. In
practice, one generally considers the point T = M = N 2/3 on the curve since
the overall complexity also becomes N 2/3 . The precomputation phase costs roughly
O(N) encryptions. This is a generic attack which is applicable to any block cipher.
Therefore, we can say that the security level diminishes to 2k/3-bit security during
the online phase of the Hellman tradeoff attack where k is the key length of a block
cipher. However, one must pay a cost equivalent to exhaustive search to prepare the
tables during the precomputation phase.
Stream ciphers also suffer from the same affliction by tradeoff attacks in that
their keys can be recovered with an effort of 2 2k/3 for each of them during the online
phase. Stream ciphers consist of two parts. The initialization part uses an I V and a
key to produce a seed value S 0 . Then, S 0 is used to produce the keystream sequence
through a keystream generator. While a state update function updates the internal
states S i , an output function produces the keystream bits (or words) z i . It is possible
to define a one way function from the key to the first k bits of the keystream sequence
by choosing an I V value and fixing it. This is similar to the case of tradeoff attacks
on block ciphers with a chosen plaintext. However, the attack may only be mounted
on a decryption mechanism since it may not be possible to choose the I V during
the encryption. Then, by preparing the Hellman tables, one can recover a key in
2 2k/3 encryptions using 2 2k/3 memory. The precomputation is 2 k . This is similar to
the Hellman attack. Therefore, stream ciphers are prone to tradeoff attacks as with
block ciphers in the key recovery case.
The other category of tradeoff attacks is aimed at recovering internal states of
stream ciphers, rather than keys. Babbage [47] and Goli´ c [236], independently,
introduced another type of tradeoff curve DM = N to recover an internal state.
A. Mileva et al.
Table 2.9 Lightweight MACs (best known attacks)
Best known attack: data / time complexity
Chaskey
[428]
Differential-linear attack [369] 2 48 / 2 67 on 7 rounds
LightMAC
[384]
−
SipHash -2-4
[32]
−
TuLP
[238]
−
2.3.1 Reconsidering TMD Tradeoff Attacks for Lightweight
Stream Cipher Designs
We can simply divide the tradeoff attacks against ciphers into two groups, key
recovery attacks and internal state recovery attacks. The first tradeoff attack against
symmetric ciphers was introduced by Hellman [268] to illustrate that the key length
of DES was indeed too short. Hellman prepared several tables containing DES keys.
In general, the tradeoff curve is T M 2 = N 2 where T is the time complexity and
M is the memory complexity. N is the cardinality of the key space. Here, the data
complexity D = 1 since only one chosen plaintext is used to define a one way
function which produces the (reduction of the) ciphertext of the chosen plaintext
for a given key. Then, the tables are prepared during the precomputation phase. In
practice, one generally considers the point T = M = N 2/3 on the curve since
the overall complexity also becomes N 2/3 . The precomputation phase costs roughly
O(N) encryptions. This is a generic attack which is applicable to any block cipher.
Therefore, we can say that the security level diminishes to 2k/3-bit security during
the online phase of the Hellman tradeoff attack where k is the key length of a block
cipher. However, one must pay a cost equivalent to exhaustive search to prepare the
tables during the precomputation phase.
Stream ciphers also suffer from the same affliction by tradeoff attacks in that
their keys can be recovered with an effort of 2 2k/3 for each of them during the online
phase. Stream ciphers consist of two parts. The initialization part uses an I V and a
key to produce a seed value S 0 . Then, S 0 is used to produce the keystream sequence
through a keystream generator. While a state update function updates the internal
states S i , an output function produces the keystream bits (or words) z i . It is possible
to define a one way function from the key to the first k bits of the keystream sequence
by choosing an I V value and fixing it. This is similar to the case of tradeoff attacks
on block ciphers with a chosen plaintext. However, the attack may only be mounted
on a decryption mechanism since it may not be possible to choose the I V during
the encryption. Then, by preparing the Hellman tables, one can recover a key in
2 2k/3 encryptions using 2 2k/3 memory. The precomputation is 2 k . This is similar to
the Hellman attack. Therefore, stream ciphers are prone to tradeoff attacks as with
block ciphers in the key recovery case.
The other category of tradeoff attacks is aimed at recovering internal states of
stream ciphers, rather than keys. Babbage [47] and Goli´ c [236], independently,
introduced another type of tradeoff curve DM = N to recover an internal state.