Refresh token replay detection

Question

I'm trying to detect refresh token reuse / replay.

A typical approach:

• send refresh token (on login or refresh)
  • create refresh token as opaque value (e.g. buffer from a CSPRNG)
  • base64 encode value and send to user
  • salt and hash value, store in database (store hash rather than value, in case db is stolen)
• receive refresh token (for rotation)
  • deserialise from base64
  • hash using original salt
  • compare to corresponding hash in database
  • if revoked then redirect to login, else respond with new refresh token

However in modern systems this is insufficient - a user might login from home, work and on his mobile. Identity providers (Azure, AWS, Auth0, etc.) thus refer to refresh token "families" for multiple devices. So there would be three refresh token families for that user. And that can be used to detect replay attacks - and revoke an entire family's descendant tokens, when one token in that family is replayed.

Modified approach:

• all refresh tokens in a family are stored (for 2 weeks)
• assuming typical values - the access token lives for 20 minutes, the refresh token for 2 weeks, and we delete old (revoked/expired) refresh tokens when the family expires after 2 weeks
• so for a single refresh token family, we must store a maximum of 2 * 7 * 24 * 60 / 20 = 1008 refresh tokens
• if there are three or more families, that's ~3000, or more

PROBLEM

Every time a refresh is performed, I must find the corresponding hash in the database. So I must perform ~ 3000 hashes. And that's just one user. Every 20 minutes!

POSSIBLE SOLUTION

I'm wary of reusing salts, but in this case it could be acceptable. I could use a single salt for every user, or a single salt per refresh token family per user (but that requires an id of some sort to separate families?). Thus I'd need to hash the received token just once, and then compare to all ~3000 stored hashes; that still smashes the database, but on the other hand I perform only one CPU-bound operation instead of 3000!

If using a single salt per refresh token family: if an attacker compromises a refresh token then he automatically compromises the whole family, so he can get the newest (valid) token. But the risk is limited to one device.

If using a single salt per user, then all the user's devices could be at risk.

MY QUESTION

I think this tradeoff is reasonable, but I'm unsure. Are there any other considerations I've neglected? Can you think of a way to make this more performant (e.g. by addressing that 3000 record search every 20 minutes)?

Answer 1

Per request you will only hash what you get from the client, not the whole set in the db.

Prevention: You do not need to store all refresh tokens of a user. You just store all valid tokens. Valid is „not revoked“ and „fresh“. Freshness can be ne handled by setting an expiration date in the database. That limited it to one refresh token + one access token per user per device.

Detection: In case you not only want to prevent, but also detect replayed tokens it is enough to just hash the token you get from the client and store it in a „already used“ buffer. Since these tokens are already invalidated it should be enough to just hash them. Optionally with a salt for good measure.

Assuming that the entropy of the token is >100 bit even salting should not be necessary because it would be infeasible to reverse the hash (to get a token that is no longer valid anyway). To be precise: if the token does not leak any other information useful to an attacker, then I would argue that even hashing it is icing on the cake

If this does not help, it might help to re-state your question:

• What is the regular flow
• where and why would replay be an issue
• What exactly are you trying to prevent

Answer 2

My solution was to send the user a refresh token AND its primary key.

It's non-standard, but when I receive it in a refresh request, it avoids all those table lookups.