What is an effective solution to replay attacks on password storage files?

Question

How can I effectively thwart a replay attack on a password file that contains usernames and their passwords hashed with salt (and/or pepper)? The attack I am interested in preventing is as follows:

1. Alice has password A.
2. Mallory comes to know password A.
3. Alice changes her password to B.
4. Mallory replaces the password file with the one that was used when Alice's password was A.
5. Mallory uses password A to authenticate as alice.

It clearly does not suffice to rely on OS read/write permissions or it would also suffice to store passwords unhashed as plaintext.

How do real systems do it? What if I replace my /etc/shadow with an older one?

Answer 1

The solution that I've arrived at is to store password timestamps alongside an audit log that records changes to the password file. The timestamps are integrity protected with an HMAC. Using an HMAC directly on the password is an alternate solution but the audit log was already present in the system so it seemed acceptable to leverage it.