106
X. Carpent et al.
desiderata that need to be achieved. No rigorous model is used to state clearly the
goals and to prove the merits of a given protocol. The proofs are arguments aiming
at convincing the reader of the goodness of the design. As shown in [169] in a casestudy for the SASI protocol, this approach opens doors to unexpected consequences.
6.3 Weaknesses and Pitfalls
Ultra-lightweight protocols strive to achieve a strong level of both security and
privacy while fitting extreme design constraints due to limited space, energy, and
cost on RFID tags. Unsurprisingly, attacks on virtually all proposals in the literature
have been published. 2
As a result, no such protocol could reasonably be used in practice. 3 Although
some lessons have been learned from these failures, and despite much advocacy for
better screening from the research community, protocols repeatedly fall victim to
common pitfalls, even in recent proposals. What follows is a short description of the
prevailing weaknesses.
6.3.1 Poor Diffusion and Linearity
Many protocols use the so-called “T-functions” extensively. These are functions for
which each bit in the output depends only on bits in the same or lower positions
in the input. Binary operations (e.g., and, or, xor) and modular addition are Tfunctions.
By definition, in a T-function it is not possible that all output bits depend on
all input bits, which is the ideal scenario for maximizing “diffusion”, an important
property in cryptographic primitives. This is particularly dangerous in cryptographic
applications, lightweight or otherwise. The only reasonable way to address this
shortcoming is by combining these operations with others which do not exhibit this
characteristic. Unfortunately many designers do not follow this simple combination
rule, and have proposed schemes entirely based on T-functions which are doomed
to fail. LMAP [466] is an example of a protocol that uses T-functions exclusively,
which was exploited in its cryptanalysis [464].
2 It has been observed that ultra-lightweight protocols are “broken” with relative ease, very
shortly after their publication. Avoine et al. [43] shows a short statistical study and concludes
conservatively that most are broken in under 4 months.
3 To the best of our knowledge, the Gossamer protocol [463] is the sole instance to not have any
published attacks, although a number of weaknesses in its construction have been identified [130].
In addition, Gossamer is definitely more involved and, arguably, could hardly be considered “ultralightweight”.
X. Carpent et al.
desiderata that need to be achieved. No rigorous model is used to state clearly the
goals and to prove the merits of a given protocol. The proofs are arguments aiming
at convincing the reader of the goodness of the design. As shown in [169] in a casestudy for the SASI protocol, this approach opens doors to unexpected consequences.
6.3 Weaknesses and Pitfalls
Ultra-lightweight protocols strive to achieve a strong level of both security and
privacy while fitting extreme design constraints due to limited space, energy, and
cost on RFID tags. Unsurprisingly, attacks on virtually all proposals in the literature
have been published. 2
As a result, no such protocol could reasonably be used in practice. 3 Although
some lessons have been learned from these failures, and despite much advocacy for
better screening from the research community, protocols repeatedly fall victim to
common pitfalls, even in recent proposals. What follows is a short description of the
prevailing weaknesses.
6.3.1 Poor Diffusion and Linearity
Many protocols use the so-called “T-functions” extensively. These are functions for
which each bit in the output depends only on bits in the same or lower positions
in the input. Binary operations (e.g., and, or, xor) and modular addition are Tfunctions.
By definition, in a T-function it is not possible that all output bits depend on
all input bits, which is the ideal scenario for maximizing “diffusion”, an important
property in cryptographic primitives. This is particularly dangerous in cryptographic
applications, lightweight or otherwise. The only reasonable way to address this
shortcoming is by combining these operations with others which do not exhibit this
characteristic. Unfortunately many designers do not follow this simple combination
rule, and have proposed schemes entirely based on T-functions which are doomed
to fail. LMAP [466] is an example of a protocol that uses T-functions exclusively,
which was exploited in its cryptanalysis [464].
2 It has been observed that ultra-lightweight protocols are “broken” with relative ease, very
shortly after their publication. Avoine et al. [43] shows a short statistical study and concludes
conservatively that most are broken in under 4 months.
3 To the best of our knowledge, the Gossamer protocol [463] is the sole instance to not have any
published attacks, although a number of weaknesses in its construction have been identified [130].
In addition, Gossamer is definitely more involved and, arguably, could hardly be considered “ultralightweight”.