6 Ultra-lightweight Authentication
101
What exactly are the limitations imposed by these inexpensive devices? In [26]
the authors provide a detailed description of the constraints. 1 These constraints are
mostly influenced by hardware factors: chip size, power consumption, and clock
speed. A standard measure for the computing power of such devices is the number
of Gate Equivalent (GE) elements, which reflects the number of logic gates that the
circuit integrated on the device consists of.
Let us consider RFID tags as an example. An RFID tag can communicate at very
slow rates (typically under 200 kb/s), and this imposes, assuming that authentication
has to happen within a reasonable time limit (e.g., 150 ms), an upper bound on
the size of the total communication that the protocol can use. RFID tags usually
consists of no more than 2000 GEs. Such a limit is imposed by the available physical
area and by the cost of the device. Most of the gates are used for the tag’s basic
functionalities, and only a small fraction of them remain available to implement
an authentication protocol. The cheapest RFID tags are passively powered. They
receive power through an electromagnetic field, radiated from the reader; this limits
the total power consumption that can be used in a single run of the authentication
protocol. The power available to the tag is inversely proportional to the maximum
distance at which the tag and the reader have to operate: a greater distance implies
less available power and this imposes limits on the clock speed (a typical limit is
100 kHz) and, consequently, on the number of instructions that the tag is allowed to
execute to finish a run of the protocol within a given time bound. Another limitation
of RFID tags is the total number of memory bits: a typical limit is 2048 bits.
Finally, notice that authentication protocols often rely on random or pseudorandom number generators. Passive RFID tags can hardly afford such a component.
There exist low-cost pseudo-random generators, but they still pose a substantial
burden for an RFID tag. A generator might require the use of more than 1000
GEs, which is more than half of the total number of GEs usually available on these
devices.
6.1.3 Design Challenges
Authentication can be achieved in several ways. Standard authentication protocols
exhibit a challenge-and-response structure, and exploit public-key or symmetrickey cryptography. Sometimes they require the presence of a trusted third party.
In all cases, the parties involved in the protocols must be able to execute the
required cryptographic algorithms (e.g., encrypting a piece of data using AES).
So it goes without saying that standard authentication protocols are not tailored
for ultra-lightweight devices. Thus, ultra-lightweight authentication protocols using
1 The title of [26] uses the term “lightweight”, but its authors do not use the classification proposed
in [139]. The discussion provided in [26] is, indeed, about ultra-constrained devices, like RFID
tags.
101
What exactly are the limitations imposed by these inexpensive devices? In [26]
the authors provide a detailed description of the constraints. 1 These constraints are
mostly influenced by hardware factors: chip size, power consumption, and clock
speed. A standard measure for the computing power of such devices is the number
of Gate Equivalent (GE) elements, which reflects the number of logic gates that the
circuit integrated on the device consists of.
Let us consider RFID tags as an example. An RFID tag can communicate at very
slow rates (typically under 200 kb/s), and this imposes, assuming that authentication
has to happen within a reasonable time limit (e.g., 150 ms), an upper bound on
the size of the total communication that the protocol can use. RFID tags usually
consists of no more than 2000 GEs. Such a limit is imposed by the available physical
area and by the cost of the device. Most of the gates are used for the tag’s basic
functionalities, and only a small fraction of them remain available to implement
an authentication protocol. The cheapest RFID tags are passively powered. They
receive power through an electromagnetic field, radiated from the reader; this limits
the total power consumption that can be used in a single run of the authentication
protocol. The power available to the tag is inversely proportional to the maximum
distance at which the tag and the reader have to operate: a greater distance implies
less available power and this imposes limits on the clock speed (a typical limit is
100 kHz) and, consequently, on the number of instructions that the tag is allowed to
execute to finish a run of the protocol within a given time bound. Another limitation
of RFID tags is the total number of memory bits: a typical limit is 2048 bits.
Finally, notice that authentication protocols often rely on random or pseudorandom number generators. Passive RFID tags can hardly afford such a component.
There exist low-cost pseudo-random generators, but they still pose a substantial
burden for an RFID tag. A generator might require the use of more than 1000
GEs, which is more than half of the total number of GEs usually available on these
devices.
6.1.3 Design Challenges
Authentication can be achieved in several ways. Standard authentication protocols
exhibit a challenge-and-response structure, and exploit public-key or symmetrickey cryptography. Sometimes they require the presence of a trusted third party.
In all cases, the parties involved in the protocols must be able to execute the
required cryptographic algorithms (e.g., encrypting a piece of data using AES).
So it goes without saying that standard authentication protocols are not tailored
for ultra-lightweight devices. Thus, ultra-lightweight authentication protocols using
1 The title of [26] uses the term “lightweight”, but its authors do not use the classification proposed
in [139]. The discussion provided in [26] is, indeed, about ultra-constrained devices, like RFID
tags.