Is it possible to have a secure challenge/response authentication protocol, authenticated immediately?

Too slow: a client request -> server challenge -> client response -> server response

Fast enough: client request -> server response

  • How do you want to defend against replay attacks in the second scenario? This is impossible (efficiently) without keeping state on both ends.
    – SEJPM
    Mar 19, 2016 at 17:42
  • @SEJPM that's exactly what i was asking. Keeping state is one way of doing it (see my answer below). Are there any better alternatives?
    – mappu
    Apr 3, 2016 at 0:26
  • Seems you're trying to solve One Time Password (OTP) problem. There are two good known solutions to it, but are state based: time (TOTP) and counter (HOTP).
    – HTLee
    Jun 18, 2016 at 8:26

2 Answers 2


Short answer:

No. By sending a response to the request, you are not challenging the client, making it a different kind of authentication scheme.

Longer answer:

The method you describe doesn't provide a challenge. There can be credentials provided such as a username/password pair, but it doesn't challenge the client to provide anything beyond what what it has already provided.

Let's take a look at an old example of challenge/response:

mappu sends me an email. Before my server accepts it at face value, it provides a challenge back to mappu. That is where mappu has the opportunity to confirm his identity and allow the email to be sent to my mailbox. Without that challenge, it is no longer a challenge authentication.

  • Is that really a necessary property of challenge/response? For instance, if i knew you were going to challenge me by asking for a scanned government ID, then my providing it with the original email is just an optimization. It's still a challenge.
    – mappu
    Feb 18, 2016 at 7:30
  • 2
    @mappu Your definition of "challenge" is different from the definition of "challenge" used in such protocols. The purpose of such a challenge is to prove that the client knows information that is not transmitted during the communication. This way the transmission theoretically does not leak enough information for someone to impersonate the client if any session encryption is broken. In your case, if you email all your secrets (the scanned government ID), anyone who saw that email now knows how to authenticate as you.
    – Cort Ammon
    Feb 18, 2016 at 7:43
  • 1
    Typically a challenge involves some random element, so that someone who observes the session now knows how to impersonate the client if the server happens to provide the exact same challenge in the future, but does not know how to impersonate them for any arbitrary challenge.
    – Cort Ammon
    Feb 18, 2016 at 7:43
  • "The purpose of such a challenge is to prove that the client knows information that is not transmitted during the communication." // I agree. I understand this. I understand replay attacks. If you're hung up on definitions i'll rephrase the question: I'm looking for ways to demonstrate knowledge of a shared secret (as in challenge auth) in only a single roundtrip, while keeping challenge-auth's properties such as replay-attack safety.
    – mappu
    Feb 18, 2016 at 9:07
  • PSK, or Pre-Shared Key, does provide the shared secret, but doesn't provide challenge-response. Knowing the question ahead of time is a different authentication mechanism; "What's the password" and the answer is always going to be "abc123" whereas a challenge won't always have the same question or answer.
    – h4ckNinja
    Feb 19, 2016 at 0:16

These proposals are based around the client generating both the challenge nonce and the challenge response. They all have downsides.


Client generates random challenge nonces. The server has to cache them to prevent replay attacks.

  • Con: The server's cache size is unbounded.


Client generates random challenge nonces along with a timestamp parameter. The server ensures the timestamp is recent and can expire sufficiently-old challenges from its cache.

  • Con: The server and client must keep similar time.


Client generates monotonically-increasing challenge nonces. The server keeps track of only the last challenge, and enforces that lower-valued nonces are not accepted. It prevents relay attacks despite storing only a single value.

  • Con: The client must keep persistent state to know the next possible nonce.
  • Another major con for all approaches other than the second is that an attacker who can get the client to issue challenge nonces which are not heard by the server can then replay those nonces at its leisure. Time stamps don't completely guard against mischief, but they considerably narrow its scope.
    – supercat
    Apr 21, 2016 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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