I've been working on my course project lately and got stuck with the problem which I reduced to the following abstract protocol:
- Alice generates an ID key and gives it to Bob.
- Bob generates some random data, combines it with that ID key to produce a token and sends it back to Alice. It is essential that data is random, i.e. Bob does not maintain any state.
- Alice verifies that token is generated by Bob and also is able to tell whether it was used before. This can obviously be achived by keeping all previous tokens in a database, but if we are talking about passwords for example, it would be great to maintain as little state as possible.
The idea behind these requirements is that existing one-time password schemes require either interaction with the service (challenge-based OTPs) or maintaining some state (TOTP, HOTP, etc). What I would like to do is, basically, to generate a new password for every session, be able to generate those passwords upfront and be sure that once used, password can never be used again.
Is there any one-time password scheme that would satisfy these requirements?