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.
- 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
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!
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.
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)?