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.
