Appropriate length of the challenge string for challenge-response authentication? How to select the necessary length of the challenge string for challenge-response authentication to claim that there is no threat of the shared secret exposure?

I can think of the following:


Possible number of given responses in some time considered as "reasonable".
Algorithm used for calculating the response.


Are there other factors?

How to calculate the "safe" challenge size if, for example, my system can respond 10^12 times during the lifetime of the key, and the response is calculated with HMAC-MD5(key || challenge)?
Standard approach:


$n=10^{12}$ challenges are drawn;
assume each challenge is $k$ unbiased independent random bits;
odds that there is a collision is less than $(n^2/2)\cdot2^{-k}$, by a first order approximation of the birthday problem, always erring on the safe side, and negligibly so for large $n$ and low odds of collision (our goal);
we want the odds to be less than some acceptable residual odds $\epsilon$ that the challenge will repeat (potentially allowing replay); like, $\epsilon=2^{-30}$ (less than one chance in a thousand million).


Now, solve for $k$. Mentally: 3 decimal digits are worth 10 binary orders of magnitude, thus (slightly erring on the safe side) $n$ is 40 BOMs, $n^2$ is twice that, $n^2/2$ is 1 less, dividing by $\epsilon$ adds 30 BOMs, thus we need 109 bits; rounding up to the next multiple of 8, we want at least 14 bytes.

Beware: it is uneasy to build a random generator that will generate independent random bits if power loss between uses or adversarial upset is a possibility.



If we want to reduce $k$ to the max in order to conserve bandwidth, and have secure remanent read/write memory for a counter, and an secret extra key, we can use a 40-bit counter (numbers of BOMs in $n$), encrypted with a 40-bit block cipher and the key (which needs to be known only by the entity generating the challenge).

Not only will the challenge be smaller, it is guaranteed to never repeat (this is part of the Format Preserving Encryption folklore).

Beware: a reliable counter is extremely hard to get right if power loss during uses or adversarial upset is a possibility; thus if possible, the prudent approach is to stick to pure random challenge.



I second the opinion voiced by @CodesInChaos that a challenge-response should be part of an overall protocol giving the required security insurance; and in particular that it should not be possible to hijack a channel after the challenge/response; or/and insert in there as a Man in the Middle.