Length of a Challenge in Challenge and Response Protocol

Question

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?

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.