[dns-operations] Why non-repeating transaction IDs?

[Paul Vixie]

> I see that people use lots of home-grown algorithms to get random, but
> mostly non-repeating transaction IDs in their resolvers.  I can't find the
> rationale for this; a straightforward PRNG or stream cipher seems sufficient
> for this task.  Any pointers to RFCs or papers are appreciated.

when i asked vernon schryver about this topic, he gave me the following.  note
that true randomness experts would say that anything in libc is predictable,
but for DNS purposes, it's a 16 bit field, so all values are "predictable".

/* Return some random bits, pulling them through an in-process entropy pool.
 */
static u_int
my_random(int bits) {
        static u_long randbuf;          /* up to next 32 random bits */
        static int randbuf_len;         /* bits remaining in randbuf */
        static int recrypt;             /* reseed with true random bits then */
        u_long mask;
        u_int ret;

        if (bits >= NBBY * (int)sizeof(u_int)) {
                assert(bits <= NBBY * (int)sizeof(u_int));
                mask = (u_int)-1;
        } else {
                assert(bits >= 0);
                mask = (1 << bits) - 1;
        }
        if (randbuf_len < bits) {
                /* We ought to use the remaining bits in the pool even if they
                 * are not enough to satisfy the current operation.  In the
                 * name of speed, hope we won't introduce any significant
                 * biases by cheating and refilling the pool early.
                 *
                 * The internal state of a non-cryptographic PRNG like random()
                 * can be deduced by an adversary with a relatively small
                 * number of operations.  Be optimistic and assume that
                 * random() is safe for more than 10 times as many outputs
                 * as the size in bits of its 992 bit internal state. */
                if (--recrypt <= 0) {
                        recrypt = 10000;
                        srandomdev();
                }
                randbuf = random();
                randbuf_len = NBBY * (int)sizeof(u_int);
        }
        randbuf_len -= bits;
        ret = randbuf & mask;
        randbuf >>= bits;
        return (ret);
}