Stateless user-generated one-time passwords

Question

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?

Answer 1

What you are asking for is demonstratively impossible.

Say you only have some initial shared state, for instance a shared secret key and some values. Now you are asking to disallow a previously used authentication; however without additional state, there is no way that you can even detect that a previous authentication has happened.

So you need some kind of state, even if it is just a simple counter, for instance to identify which one-time-passwords have been used.