Lets consider a challenge and response protocol with the following setup.

Two entities $A$ and $B$. $A$ is generating the challenge and $B$ is generating the response using a digital signature scheme. Lets suppose, that $A$ already has the certificate of $B$. So the procedure is as follows:

  1. $B$ wants to access some service, that $A$ provides.
  2. $A$ would like to know whether $B$ is authorized. Therefore, $A$ generates a challenge ch and sends it over to $B$.
  3. $B$ is generating a response, by signing the ch with its private key and sending the signature over to $A$.
  4. $A$ verifies the received response using the public key inside the available certificate.

This is just a common challenge and response procedure.

Question: How long shall the challenge be? If the challenge is to small, it repeats in a short amount of time. Are there any common methods that are "good-practice" in order to determine a suitable length?

Does this have anything to do with the security level of 128-bit that shall be satisfied in any case?


1 Answer 1


If your challenge is random bits, the security level is about $2^{bitlen}$, but since you are using it in challenge response you might want to avoid collisions as you said, especially if $O(2^{bitlen/2})$ storage is feasible, so you should set the length about twice required security level. But if you use determinisic random bit generator, your actual entropy won't be higher than its seed. For example, if the seed is just 64 bits, even if you produce 1K long sequence, we can expect collision in about four billion challenges since PRN generators produce a sequence deterministic to the seed which an attacker who is recording can replay using someone else's signature to complete authentication. But $k$ bit long seed from some source of entropy does not necessarily mean $k$ bits of entropy if the source of entropy used for seeding is not very good. And the PRNG must be cryptographically strong as well. In a nutshell, assuming cryptographically secure PRNG, you can expect repetition as you said in about half the actual bit entropy of the seed.


Your Answer

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

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