  Hash-based message authentication codes are an extremely simple yet hugely
effective construction for producing keyed message digests using shared
secrets. HMACs have seen widespread use as ad-hoc digital signatures in many
Internet applications. While messages signed with an HMAC are secure against
sender impersonation and tampering in transit, if used alone they are
susceptible to replay attacks. We propose a construction that extends HMACs to
produce a keyed message digest that has a finite validity period. We then
propose a message signature scheme that uses this time-dependent MAC along with
an unique message identifier to calculate a set of authentication factors using
which a recipient can readily detect and ignore replayed messages, thus
providing perfect resistance against replay attacks. We further analyse
time-based message authentication codes and show that they provide stronger
security guarantees than plain HMACs, even when used independently of the
aforementioned replay attack resistant message signature scheme.
