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.