104
X. Carpent et al.
• The IDS is the current pseudonym, which the tag sends to the reader and initiates
the subsequent authentication protocol.
• The sequence of values A 1 , A 2 , . . . , A n , computed by the reader, is usually
used in the following form: the first values are a sort of carriers for fresh
randomly or pseudorandomly generated numbers, while the last ones are the
true authenticators, computed by using the random numbers, the secret keys and
information shared between the reader and the tag. From some of the A i ’s, the
tag, by using the secret keys, retrieves the random numbers chosen by the reader.
Then, by using the secret keys, the retrieved random numbers and some other
shared information, the tag recomputes the remaining A i ’s and checks that they
match the ones received. Such a check aims at ensuring the integrity and the
authenticity of the transmitted values.
• The values B 1 , B 2 , . . . , B k are, finally, used by the reader as an acknowledgment
that the tag has authenticated the reader, and to complete the authentication of
the tag to the reader. They are generated and used in a similar way to the values
A 1 , A 2 , . . . , A n .
At the end of a successful execution, the reader and the tag change the pseudonym
IDS of the tag, and all the secret keys, by applying some updating functions. The
updating functions use the IDS and the secret keys, as well as some of the random
numbers, used in the last execution of the protocol. In particular, the updating
function for the IDS uses also the static tag ID.
In practice, many protocols require the reader and tag to store both the new
IDS and the sequence of secret keys, as well as the previous IDS and the previous
sequence of secret keys. The reason is that the tag completes the protocol before
the reader. If for some reason, adversarial or not, the reader does not complete the
protocol, the tag updates the IDS and the secret keys while the reader does not.
Then, at the subsequent execution, the reader and the tag do not recognize each
other. Technically speaking, they are not synchronized anymore. By also keeping
the old tuple of values, the authentication protocol can be modified in such a way
that, if the reader does not reply to the new IDS, then the tag sends the old IDS again
and the authentication protocol is executed using the old sequence of secret keys.
To exemplify the general framework, notice that in M 2 AP and EMAP three
values are sent from the reader to the tag, and two values are sent from the tag
to the reader. In LMAP, SASI, and Gossamer [463], three values are sent from the
reader to the tag and one value is sent from the tag to the reader. Moving ahead to
more recent protocols, in KMAP [323], RCIA [431] and SASI + [431], three values
are sent from the reader to the tag and one value is sent from the tag to the reader,
while in SLAP [383] two values are sent from the reader to the tag, and one value
is sent from the tag to the reader. However, some protocols slightly deviate from the
general framework, e.g., RAPP [554] has one more round.
To get an idea of the computations, let us look at SASI. Denote by K 1 and
K 2 two secret keys shared between the reader and tag, and by n 1 and n 2 two
fresh random values generated by the reader. Moreover, we denote by ⊕, ∨, + the
xor, or and modular addition operators. Finally, denote with Rot (s, ,) a bit-string
X. Carpent et al.
• The IDS is the current pseudonym, which the tag sends to the reader and initiates
the subsequent authentication protocol.
• The sequence of values A 1 , A 2 , . . . , A n , computed by the reader, is usually
used in the following form: the first values are a sort of carriers for fresh
randomly or pseudorandomly generated numbers, while the last ones are the
true authenticators, computed by using the random numbers, the secret keys and
information shared between the reader and the tag. From some of the A i ’s, the
tag, by using the secret keys, retrieves the random numbers chosen by the reader.
Then, by using the secret keys, the retrieved random numbers and some other
shared information, the tag recomputes the remaining A i ’s and checks that they
match the ones received. Such a check aims at ensuring the integrity and the
authenticity of the transmitted values.
• The values B 1 , B 2 , . . . , B k are, finally, used by the reader as an acknowledgment
that the tag has authenticated the reader, and to complete the authentication of
the tag to the reader. They are generated and used in a similar way to the values
A 1 , A 2 , . . . , A n .
At the end of a successful execution, the reader and the tag change the pseudonym
IDS of the tag, and all the secret keys, by applying some updating functions. The
updating functions use the IDS and the secret keys, as well as some of the random
numbers, used in the last execution of the protocol. In particular, the updating
function for the IDS uses also the static tag ID.
In practice, many protocols require the reader and tag to store both the new
IDS and the sequence of secret keys, as well as the previous IDS and the previous
sequence of secret keys. The reason is that the tag completes the protocol before
the reader. If for some reason, adversarial or not, the reader does not complete the
protocol, the tag updates the IDS and the secret keys while the reader does not.
Then, at the subsequent execution, the reader and the tag do not recognize each
other. Technically speaking, they are not synchronized anymore. By also keeping
the old tuple of values, the authentication protocol can be modified in such a way
that, if the reader does not reply to the new IDS, then the tag sends the old IDS again
and the authentication protocol is executed using the old sequence of secret keys.
To exemplify the general framework, notice that in M 2 AP and EMAP three
values are sent from the reader to the tag, and two values are sent from the tag
to the reader. In LMAP, SASI, and Gossamer [463], three values are sent from the
reader to the tag and one value is sent from the tag to the reader. Moving ahead to
more recent protocols, in KMAP [323], RCIA [431] and SASI + [431], three values
are sent from the reader to the tag and one value is sent from the tag to the reader,
while in SLAP [383] two values are sent from the reader to the tag, and one value
is sent from the tag to the reader. However, some protocols slightly deviate from the
general framework, e.g., RAPP [554] has one more round.
To get an idea of the computations, let us look at SASI. Denote by K 1 and
K 2 two secret keys shared between the reader and tag, and by n 1 and n 2 two
fresh random values generated by the reader. Moreover, we denote by ⊕, ∨, + the
xor, or and modular addition operators. Finally, denote with Rot (s, ,) a bit-string