# Length of a Challenge in Challenge and Response Protocol

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?

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.

Question: How long shall the challenge be? If the challenge is too 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?

TL;DR: If humans aren't directly involved in the protocol, choose a random 256-bit challenge, and you should be fine.

The answer depends on how challenges are generated (which is currently underspecified) and what the maximum number of authentication attempts allowed is. There are two approaches:

1. Generate challenges as a counter sequentially until the maximum number of challenges is reached.
2. Generate challenges at random for each attempt.

Naturally, approach one works and only needs challenges length long enough so they can take all values. Challenges never repeat; therefore, the adversary can never reuse a previous response to cheat. This has the downside of perhaps allowing the adversary to DoS the system and exhaust the challenge space. However, if that space is large, like $$2^{64}$$, it's not clear an attacker would commit to doing this much work. The other issue is that this requires some persistent memory to keep the values of the counter to prevent reuse.

The second method is preferable in practice since there is usually no clear maximum number of sessions. Additionally, there's no need for storage of counters. But, it has the risk of challenging collisions (and bad randomness, etc..). So, the challenge space has to be large enough. If you choose a 256-bit challenge at random, collisions are practically impossible, even for many authentication sessions. See this answer to analyse collision probabilities for 256-bit values.

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

To some extent, but not only. The 128-bit security value is also a function of the other components in the system. In particular, if the signature scheme had 64-bit keys, this authentication scheme would never have 128 bits of security, even if the challenges were 10.000 bits long.