Entity Authentication - Everyday Cryptography - page 262

Note that an alternative technique would be to associate each newmessage with
a unique identification number, but not necessarily one that is bigger than the last
one sent. In this case Bob would have to maintain a database that consisted of
all previous identification numbers sent (not just the most recent one). He would
then have to search this database every time that a new message was received in
order to check that the identification number had not been used before. Clearly
this would be inefficient in terms of time and storage space.
In the above example, note that Alice increments her sequence number N AB by
one each time that she sends a message, but Bob only checks whether T new > T old ,
not that T new = T old + 1, which is what we might expect. If T new > T old + 1 then
this suggests that, between the last message Bob received and the current message,
some messages from Alice to Bob have got lost. This might itself be a problem,
so Bob will need to decide whether the fact that there are missing messages is
important. However, the sequence number is primarily there to provide freshness .
The fact that T new > T old is enough to gain this assurance. It also allows Bob to
resynchronise by updating his version of N AB to the latest sequence number T new .
It is worth briefly considering the extent to which sequence numbers address
the four concerns that we raised with clock-based mechanisms:

Existence of clocks . The communicating parties no longer require clocks.
Synchronisation . In order to stay synchronised, communicating parties need
to maintain a database of the latest sequence numbers. Our simple example
included a mechanism for making sure that this database is kept up to date.
Communication delays . These only apply if messages are sent so frequently that
there is a chance that two messages arrive at the destination in the reverse
order to which they were sent. If this is a possibility then there remains a need
to maintain the equivalent of a window of acceptability, except that this will
be measured in terms of acceptable sequence number differences, rather than
time. For example, Bob might choose to accept the message as fresh not just if
T new > T old , since there is a chance that the previous

message from Alice to Bob has not yet arrived. Note that this issue is not
relevant if either:

T old , but also if T new =

• delays of this type are not likely (or are impossible);
• Bob is more concerned about the possibility of replays than the implications of
rejecting genuine messages.
Integrity of sequence numbers . Just as for clock-based time, an attacker who
can freely manipulate sequence numbers can cause various problems in any
protocol that relies on them. Thus sequence numbers should have some level
of cryptographic integrity protection when they are sent.

The obvious cost of using sequence numbers is the need to maintain databases
of their latest values. Another possible problem arises if sequence numbers
have a limited size and eventually cycle around again. Nonetheless, this type of
mechanism is popular in applications where maintaining synchronised clocks