2 Catalog and Illustrative Examples of Lightweight Cryptographic Primitives
43
Table 2.11 Lightweight authenticated encryption schemes (best known attacks)
Best known attack: data complexity/memory/time
Name
Ref
complexity
ACORN v3
[581]
−
ALE
[103]
Forgery attack [324]: 2 40 /−/2 110
APE
[22]
−
ASC-1
[300]
−
Ascon
[186]
Key-recovery attack [371]: 2 103.9 time on 7 out of 12
rounds ASCON-128
C-QUARK
[36]
−
FIDES
[87]
State-recovery/forgery attacks [184]:
1KP/(2 15 , 2 18 )/(2 75 , 2 90 )
Hummingbird-2
[200]
Related key-recovery attack [525]: 24 pairs of related
keys/−/2 40
Helix
[215]
Key-recovery attack [432]: 2 17 CP/−/2 88
Joltik
[304]
−
KETJE
[82]
−
LAC
[596]
Differential forgery attack [368] with probability
2 −61.52
NORX32 v.3
[35]
−
NORX8/NORX16
[34]
−
Sablier
[594]
Practical state/key recovery attack [213]: −/−/2 44
SCREAM/iSCREAM
[246]
Practical forgery attack [530] with 2 queries
sLiSCP
[20]
−
TriviA-v2/uTriviA
[132]
−
One can pick out the point D = M = N 1/2 to get an overall complexity of
N 1/2 . Then, storing
√
N internal states with their outputs (keystream parts with an
appropriate length), one can recover a keystream used during encryption/decryption
if it is loaded in the table. We need roughly
√
N data to ensure a remarkable success
rate. So, it is conventionally adopted that
√
N should be larger than 2 k as a security
criterion just to ensure that the internal state recovery attack through tradeoff is
slower than the exhaustive search. This simply means that the internal state size
should be at least twice as large as the key size. This extremely strict criterion has
played a very crucial role in raising extra difficulties in designing lightweight stream
ciphers.
Another highly effective tradeoff attack for internal state recovery is the
Biryukov-Shamir attack [91]. This simply makes use of Hellman tables. But,
instead of recovering just one specific internal state, it is enough to recover only one
of D internal states. Then, preparing just one Hellman table is an optimum solution
and the table can contain N/D states. So, the precomputation phase is around
O(N/D) and the tradeoff curve is T M 2 D 2 = N 2 where D is bounded above by
√
T since the number of internal states contained in just one table is limited to
avoid merging of collisions. We can pick out the point on the curve where time and
43
Table 2.11 Lightweight authenticated encryption schemes (best known attacks)
Best known attack: data complexity/memory/time
Name
Ref
complexity
ACORN v3
[581]
−
ALE
[103]
Forgery attack [324]: 2 40 /−/2 110
APE
[22]
−
ASC-1
[300]
−
Ascon
[186]
Key-recovery attack [371]: 2 103.9 time on 7 out of 12
rounds ASCON-128
C-QUARK
[36]
−
FIDES
[87]
State-recovery/forgery attacks [184]:
1KP/(2 15 , 2 18 )/(2 75 , 2 90 )
Hummingbird-2
[200]
Related key-recovery attack [525]: 24 pairs of related
keys/−/2 40
Helix
[215]
Key-recovery attack [432]: 2 17 CP/−/2 88
Joltik
[304]
−
KETJE
[82]
−
LAC
[596]
Differential forgery attack [368] with probability
2 −61.52
NORX32 v.3
[35]
−
NORX8/NORX16
[34]
−
Sablier
[594]
Practical state/key recovery attack [213]: −/−/2 44
SCREAM/iSCREAM
[246]
Practical forgery attack [530] with 2 queries
sLiSCP
[20]
−
TriviA-v2/uTriviA
[132]
−
One can pick out the point D = M = N 1/2 to get an overall complexity of
N 1/2 . Then, storing
√
N internal states with their outputs (keystream parts with an
appropriate length), one can recover a keystream used during encryption/decryption
if it is loaded in the table. We need roughly
√
N data to ensure a remarkable success
rate. So, it is conventionally adopted that
√
N should be larger than 2 k as a security
criterion just to ensure that the internal state recovery attack through tradeoff is
slower than the exhaustive search. This simply means that the internal state size
should be at least twice as large as the key size. This extremely strict criterion has
played a very crucial role in raising extra difficulties in designing lightweight stream
ciphers.
Another highly effective tradeoff attack for internal state recovery is the
Biryukov-Shamir attack [91]. This simply makes use of Hellman tables. But,
instead of recovering just one specific internal state, it is enough to recover only one
of D internal states. Then, preparing just one Hellman table is an optimum solution
and the table can contain N/D states. So, the precomputation phase is around
O(N/D) and the tradeoff curve is T M 2 D 2 = N 2 where D is bounded above by
√
T since the number of internal states contained in just one table is limited to
avoid merging of collisions. We can pick out the point on the curve where time and