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?

  • $\begingroup$ In order to avoid replay attacks, you pretty much have either some sort of timestamp, keep track of previous tokens, or a little of both. $\endgroup$ Mar 6, 2017 at 3:26
  • 1
    $\begingroup$ Please explain, what you mean exactely by "state". Because there is no state (as I would understand it) in TOTP, both parties just have to store a shared secret. If you do not allow for any storage of any data on any side, you are going to end up with just some random data. $\endgroup$
    – mat
    Apr 14, 2017 at 10:35

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.