# ANSI X9.31 standards for generating random numbers

The NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms has 3DES being used three times for each 64-bit block of random data desired, e.g.

$I = ede_K (DT)$, $R = ede_K(I \oplus V)$ and a new $V$ is generated by $V = ede_K(R \oplus I)$.

OpenSSL seems to be using 3DES in ECB mode (fips_rand.c).

My question is... if you have a cipher running in CTR mode could you just encrypt a string of null bytes as long as desired instead of doing three different encryption rounds on each block?

Also, what is the recommended format for DT? Normally timestamps are 32-bits, not 64-bits.

-
Actually, the OpenSSL implementation of the PRNG you linked uses just what the NIST document describes. 3DES in ECB-mode is used for the single block encryptions, e.g. $ede_K(\dots)$. –  Paŭlo Ebermann Dec 16 '12 at 13:43

If you're asking why the X9.31 rng was designed the way it was, rather than some other way, I'm not certain if anyone other than the original authors could say. The core design dates back to at least 1985 (it was included in X9.17), and it originally used DES (and was later upgraded to use 3DES). I suspect that the original authors would not have been confident in using DES in counter mode.

As for the DT format, well, the requirement in X9.31 is that the value is distinct everytime you generate a block. It's there to make sure that the RNG doesn't fall into a short cycle, and so it wouldn't be horrible if DT changed only occasionally (e.g. if you generated 256 values with the same DT, the probability that the cipher runs into a cycle during those 256 values is about $2^{-56}$). A secondary reason is to feed a slight amount of additional entropy into the RNG -- it doesn't do that all that well, though. As long as you abide by that, any format works. In your case, it's easy enough to abide by both the spirit and the letter of the law; formulate a DT where the top 32 bits are the Timestamp you get from the system, and the lower 32 bits is just a counter which is incremented everytime you generate a block. That way, the DT value changes everytime (because the lower 32 bits always change), and you feed the slight amount of entropy from the current data/time.

As for OpenSSL, well, it appears to be an implementation of the X9.31 (using 2-key 3DES; that is what X9.31 originally asked for, however the NIST document you gave now specifies 3-key 3DES).

Also, if you need a secure RNG, I would suggest you look at these RNGs, especially the CTR_DRBG (whose base idea is just an block cipher in counter mode just like you suggested).

-
Is there some reason DES in counter mode shouldn't instill confidence? I could lack confidence over RSA encryption with a 4096-bit key but I'd probably be silly to do so without a specific reason.. –  neubert Dec 15 '12 at 16:49
@neubert: Well, remember that we were talking about 1985 (at the latest, that's the earliest publication I could find); back then, the designers may well have worried that giving related inputs to the DES function would expose some weakness. Now, 27 years later, we're pretty sure that's not the case. However, it seems unfair to pass judgement on their design decisions based on information they didn't have. –  poncho Dec 15 '12 at 17:35

I think another reason for using the complicated construction which replaces $V$ after each production of a new $R$ is a (maybe implicit) requirement that the state of the PRNG should not allow recovering previous outputs.

For a block cipher in CTR mode, recovering previous outputs is easy, as you still have all the input available, or easily reconstructible (by subtracting the increment).

The X9.31–A.2.4 PRNG seems to avoid this by generating a new $V$ after each $R$.

But actually, as long as $K$ and $I$ are known (which means $K$ and $DT$ are known), we can backtrack all previous values of $R$ and $V$, simply by inverting the encryption and then XORing $I$ away.

(This PRNG is something like CBC-mode encryption of a repeated $I$ vector, using only every second output block.)

-

I disagree with Paulo, or maybe we are not talking about the same thing. To avoid the problem that previous outputs may be recoverable, we can do the following:

1. call

nextkey := AES(key, 0)
output := AES(key, 1)
key = nextkey
return output

2. call

nextkey := AES(key, 2)
output := AES(key, 3)
key = nextkey
return output

3. etc.

Using this, it is not possible retrieve previous outputs.

-
Paulo was talking about the X9.31 generator, not a counter mode based one. Obviously, you can create a random number generator you can't backtrack; the X9.31 designers just didn't do so. –  poncho Jan 16 '13 at 20:14