6 Ultra-lightweight Authentication
111
community is dedicated to so-called “lightweight cryptography”, with countless
applications.
In particular, significant efforts have been made to develop ciphers and hash
functions suitable for lightweight authentication. A notable example is the KECCAK hash function [81], winner of the SHA-3 competition, that has excellent
hardware performance. Furthermore, there are many ongoing efforts to develop
special primitives with a stronger focus towards hardware footprint/performance,
possibly trading off “some” security (e.g., reducing 128 or 256-bit security to 80)
or other aspects, such as reducing block size, or software performance. Examples
include the PRESENT block cipher [101] or the hash functions PHOTON [251] and
QUARK [33].
Some of these, like BLAKE [37] or RC5 [502] are so-called Add-Rotate-Xor
algorithms, that use the very same set of operations as ultra-lightweight protocols.
While not quite fitting the same extreme constraints imposed on ultra-lightweight
protocols just yet, they are a stepping stone in that direction. They also benefit from
much wider exposure and scrutiny, which bodes better for their overall security.
Ultra-lightweight protocols take a unique approach in that the entire scheme is
designed, for instance, without using cryptographic building blocks as black boxes.
It seems instead perhaps more promising to use standard authentication protocols
with these lightweight primitives.
6.4.3 The Reductionist Approach
A deeply studied approach to the design of lightweight authentication protocols
for RFID tags is the one provided by the H B+ protocol [310], which builds on
the earlier H B protocol [284], introduced to efficiently authenticate a human to a
computer. The security of these protocols is based on the difficulty of solving the
learning parity with noise (LPN) problem [284]. Subsequently, several variants of
H B+ have been proposed but almost all of them present some problems, e.g., [231–
233, 457]. Unfortunately, according to [26], the H B-like protocols are not suitable
for implementation on ultra-constrained devices. However, the identification of hard
problems which allow the design of ultra-lightweight authentication protocols is a
research direction which should not be abandoned.
Another interesting approach to designing an authentication protocol for RFID
tags was proposed in [520]. Therein, a lightweight hash function, which can be
used in RFID authentication, was described. The security of such a hash function
is related to the security of the Rabin public key scheme. The idea is to compute
an excellent numerical approximation for a short window of bits in the middle of
the ciphertext produced by the Rabin encryption function. The Rabin encryption
function uses a modulus of a particular form, in such a way that computing these
bits for an adversary is as hard as breaking the full Rabin scheme. A basic version
of the scheme was analyzed in [458]. As far as we know, the approach of [520] has
not been followed by other significant proposals. We believe that this research line,
111
community is dedicated to so-called “lightweight cryptography”, with countless
applications.
In particular, significant efforts have been made to develop ciphers and hash
functions suitable for lightweight authentication. A notable example is the KECCAK hash function [81], winner of the SHA-3 competition, that has excellent
hardware performance. Furthermore, there are many ongoing efforts to develop
special primitives with a stronger focus towards hardware footprint/performance,
possibly trading off “some” security (e.g., reducing 128 or 256-bit security to 80)
or other aspects, such as reducing block size, or software performance. Examples
include the PRESENT block cipher [101] or the hash functions PHOTON [251] and
QUARK [33].
Some of these, like BLAKE [37] or RC5 [502] are so-called Add-Rotate-Xor
algorithms, that use the very same set of operations as ultra-lightweight protocols.
While not quite fitting the same extreme constraints imposed on ultra-lightweight
protocols just yet, they are a stepping stone in that direction. They also benefit from
much wider exposure and scrutiny, which bodes better for their overall security.
Ultra-lightweight protocols take a unique approach in that the entire scheme is
designed, for instance, without using cryptographic building blocks as black boxes.
It seems instead perhaps more promising to use standard authentication protocols
with these lightweight primitives.
6.4.3 The Reductionist Approach
A deeply studied approach to the design of lightweight authentication protocols
for RFID tags is the one provided by the H B+ protocol [310], which builds on
the earlier H B protocol [284], introduced to efficiently authenticate a human to a
computer. The security of these protocols is based on the difficulty of solving the
learning parity with noise (LPN) problem [284]. Subsequently, several variants of
H B+ have been proposed but almost all of them present some problems, e.g., [231–
233, 457]. Unfortunately, according to [26], the H B-like protocols are not suitable
for implementation on ultra-constrained devices. However, the identification of hard
problems which allow the design of ultra-lightweight authentication protocols is a
research direction which should not be abandoned.
Another interesting approach to designing an authentication protocol for RFID
tags was proposed in [520]. Therein, a lightweight hash function, which can be
used in RFID authentication, was described. The security of such a hash function
is related to the security of the Rabin public key scheme. The idea is to compute
an excellent numerical approximation for a short window of bits in the middle of
the ciphertext produced by the Rabin encryption function. The Rabin encryption
function uses a modulus of a particular form, in such a way that computing these
bits for an adversary is as hard as breaking the full Rabin scheme. A basic version
of the scheme was analyzed in [458]. As far as we know, the approach of [520] has
not been followed by other significant proposals. We believe that this research line,