108
X. Carpent et al.
the time (similarly for and, of course). In some cases it is more than enough, after
seeing some exchanges, to be able to completely recover all the inputs.
In LMAP, the reader sends B = (I DS ∨ K 2 ) + n 1 . The attacker can thus use
B + (2 L − 1) as a very good approximation to the unknown “shielded” nonce n 1
(on average, 75% of the bits are correct), and this approximation can be used later
in other parts of the protocol to approximate the secret (see e.g. [44] for a full attack
partially based on this).
6.3.4 Rotations
Rotations have been used for a long time in cryptography. Many modern block
ciphers and hash functions such as BLAKE [37] or RC5 [502] rely on the ARX
(addition, rotation, XOR) paradigm. Rotations are extremely cheap to implement
in hardware, and they introduce diffusion, which complements nicely the modular
addition and the XOR (which exhibit poor diffusion properties). Fixed-amount
rotations are typically used in ARX designs, but data-dependent rotations, as first
featured in the RC5 block cipher [502], also exist.
The SASI [139] protocol was the first ultra-lightweight authentication protocol to
feature data-dependent rotations. Since then, most ultra-lightweight protocols have
used them, and in many cases they are the weak spot for ad hoc attacks. In addition
to linearity, the most important shortcoming of data-dependent rotations is that there
are only L possible outputs. Mod n cryptanalysis [319] is also a promising tool for
attacking schemes using rotations and additions, although it has never been applied
in the cryptanalysis of an ultra-lightweight protocol, to the best of our knowledge. It
has, on the other hand, been used to successfully attack block ciphers such as RC5P
and M6, which use the same kinds of operation.
6.3.5 Vulnerability to Knowledge Accumulation
If partial leakage of a static secret occurs in a protocol, there is an obvious
traceability issue. Indeed, it becomes possible for an attacker to correlate two leaked
traces of an eavesdropped exchange. A typical example is recovering the least
significant bit of the static identifier (see for instance [473], the first traceability
attack on SASI). More importantly, an attacker is sometimes able to recover the
full static secret after a few rounds. Indeed, different observations can be combined
using Bayesian inference. An example of such an attack was the full cryptanalysis
of SASI [44].
X. Carpent et al.
the time (similarly for and, of course). In some cases it is more than enough, after
seeing some exchanges, to be able to completely recover all the inputs.
In LMAP, the reader sends B = (I DS ∨ K 2 ) + n 1 . The attacker can thus use
B + (2 L − 1) as a very good approximation to the unknown “shielded” nonce n 1
(on average, 75% of the bits are correct), and this approximation can be used later
in other parts of the protocol to approximate the secret (see e.g. [44] for a full attack
partially based on this).
6.3.4 Rotations
Rotations have been used for a long time in cryptography. Many modern block
ciphers and hash functions such as BLAKE [37] or RC5 [502] rely on the ARX
(addition, rotation, XOR) paradigm. Rotations are extremely cheap to implement
in hardware, and they introduce diffusion, which complements nicely the modular
addition and the XOR (which exhibit poor diffusion properties). Fixed-amount
rotations are typically used in ARX designs, but data-dependent rotations, as first
featured in the RC5 block cipher [502], also exist.
The SASI [139] protocol was the first ultra-lightweight authentication protocol to
feature data-dependent rotations. Since then, most ultra-lightweight protocols have
used them, and in many cases they are the weak spot for ad hoc attacks. In addition
to linearity, the most important shortcoming of data-dependent rotations is that there
are only L possible outputs. Mod n cryptanalysis [319] is also a promising tool for
attacking schemes using rotations and additions, although it has never been applied
in the cryptanalysis of an ultra-lightweight protocol, to the best of our knowledge. It
has, on the other hand, been used to successfully attack block ciphers such as RC5P
and M6, which use the same kinds of operation.
6.3.5 Vulnerability to Knowledge Accumulation
If partial leakage of a static secret occurs in a protocol, there is an obvious
traceability issue. Indeed, it becomes possible for an attacker to correlate two leaked
traces of an eavesdropped exchange. A typical example is recovering the least
significant bit of the static identifier (see for instance [473], the first traceability
attack on SASI). More importantly, an attacker is sometimes able to recover the
full static secret after a few rounds. Indeed, different observations can be combined
using Bayesian inference. An example of such an attack was the full cryptanalysis
of SASI [44].