Bloom filter to prevent replay attacks in signed HTTP requests
I'm thinking about an authentication sheme of a REST API in a setting where the only thing the server stores about a client, is their public key (the asymmetric encryption scheme should not matter). So I've come up with a scheme where the authenticated requests would look something like this:
{
body: {
<actual request body>
},
auth: {
pubKey: <user's public key and identifier as well>
nonce: <UUID generated by the client>
signature: <signature of [body, nonce]>
}
}
The signature is there obviously to ensure that the request was sent by the user and was not tampered with. The nonce is there to avoid replay attacks. Of course, the nonce can be used only once. The nonce is required to be a UUID, so the server can automatically discard nonces outside of a certain time frame (let's say +- 60 seconds), but I still have to deal with nonces within those 120 seconds window.
And here comes my main question - How to efficiently store the nonces used within a certain time frame?
I came up with using a bloom filter for that, but of course, it can get polluted after a certain time, so you want to reset it once in a while. And shortly after resetting it would be vulnerable. So my idea is to have two of them and rotate them - each nonce would pass through both, but I would ask for the (non)presence of it only the older one. Is that approach sound? Is there any "industry standard" for nonce repetition prevention suitable for my use case?
Another question - where would you put the "auth" part of the request? Is there some standard way to store the signature and nonce in the header or even a standard way to perform asymmetric key authentication in REST APIs that you would suggest?
