102
X. Carpent et al.
only elementary operations are needed. It should therefore not come as a surprise
that achieving the same security levels as those offered by standard authentication
protocols might be much more difficult, or perhaps even impossible.
Thus, the real challenge posed by ultra-lightweight authentication is obtaining
the highest possible level of security, given the hardware constraints. Part of the
challenge concerns the development of a formal model that can be used to assess
the security and privacy achieved by ultra-lightweight authentication protocols.
Nowadays, security assertions are expressed in terms of formal mathematical
models for describing problems and analyzing proposed solutions. In particular,
security assertions are expressed in formal mathematical terms, cryptographic
protocols are built upon computational hardness assumptions, and proofs assume
the form of mathematical reductions. As we will argue in the following sections,
ultra-lightweight cryptography should be tackled with a similar rigorous approach.
We might have to rethink, or to appropriately adapt, the formal framework within
which ultra-lightweight protocols are designed and security and privacy assertions
about them are assessed.
6.1.4 Organization of the Chapter
In Sect. 6.2 we provide a general concise framework which captures the common
structure of known ultra-lightweight authentication protocols, and we discuss the
design strategies and properties they aim to achieve. Then, in Sect. 6.3, we point
out the limits of achieving security by using very constrained computing devices
which allow only simple operations. Specifically, we survey the weaknesses and
the common pitfalls in the design of ultra-lightweight authentication protocols. In
Sect. 6.4, we elaborate on the importance of using security and privacy models, and
provide suggestions for sound design strategies. Finally, in Sect. 6.5 we provide
some conclusions.
6.2 Ultra-lightweight Authentication Protocols
Ultra-lightweight mutual authentication protocols appeared in the literature around
2006. M 2 AP [467], LMAP [466] and EMAP [465] were the first protocols designed
to be executed on circuits equipped with only a few hundred gates. They were collectively identified as the UMAP family. In the following year, another protocol, called
SASI [139], addressed some of the weaknesses present in those protocols. SASI
received considerable attention both from cryptanalysts and designers. However,
like its predecessors, it was quickly broken in a few months. Surprisingly, plenty of
similar protocols followed, and its “structure” is still being used.
Almost all proposed ultra-lightweight mutual authentication protocols can be
seen as instances of one general framework. Three entities are involved: a tag, a
X. Carpent et al.
only elementary operations are needed. It should therefore not come as a surprise
that achieving the same security levels as those offered by standard authentication
protocols might be much more difficult, or perhaps even impossible.
Thus, the real challenge posed by ultra-lightweight authentication is obtaining
the highest possible level of security, given the hardware constraints. Part of the
challenge concerns the development of a formal model that can be used to assess
the security and privacy achieved by ultra-lightweight authentication protocols.
Nowadays, security assertions are expressed in terms of formal mathematical
models for describing problems and analyzing proposed solutions. In particular,
security assertions are expressed in formal mathematical terms, cryptographic
protocols are built upon computational hardness assumptions, and proofs assume
the form of mathematical reductions. As we will argue in the following sections,
ultra-lightweight cryptography should be tackled with a similar rigorous approach.
We might have to rethink, or to appropriately adapt, the formal framework within
which ultra-lightweight protocols are designed and security and privacy assertions
about them are assessed.
6.1.4 Organization of the Chapter
In Sect. 6.2 we provide a general concise framework which captures the common
structure of known ultra-lightweight authentication protocols, and we discuss the
design strategies and properties they aim to achieve. Then, in Sect. 6.3, we point
out the limits of achieving security by using very constrained computing devices
which allow only simple operations. Specifically, we survey the weaknesses and
the common pitfalls in the design of ultra-lightweight authentication protocols. In
Sect. 6.4, we elaborate on the importance of using security and privacy models, and
provide suggestions for sound design strategies. Finally, in Sect. 6.5 we provide
some conclusions.
6.2 Ultra-lightweight Authentication Protocols
Ultra-lightweight mutual authentication protocols appeared in the literature around
2006. M 2 AP [467], LMAP [466] and EMAP [465] were the first protocols designed
to be executed on circuits equipped with only a few hundred gates. They were collectively identified as the UMAP family. In the following year, another protocol, called
SASI [139], addressed some of the weaknesses present in those protocols. SASI
received considerable attention both from cryptanalysts and designers. However,
like its predecessors, it was quickly broken in a few months. Surprisingly, plenty of
similar protocols followed, and its “structure” is still being used.
Almost all proposed ultra-lightweight mutual authentication protocols can be
seen as instances of one general framework. Three entities are involved: a tag, a