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.

  • 1
    $\begingroup$ 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)$. $\endgroup$ – 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).

  • $\begingroup$ 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.. $\endgroup$ – neubert Dec 15 '12 at 16:49
  • $\begingroup$ @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. $\endgroup$ – poncho Dec 15 '12 at 17:35
  • $\begingroup$ NIST now explicitly documents that you have to use an RNG from SP800-90A (in FIPS 186-4 for RSA signature generation). $\endgroup$ – Maarten Bodewes Oct 27 '14 at 10:54

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.)

  • 1
    $\begingroup$ Regarding "we can backtrack all previous values of $R$ and $V$, simply by inverting the encryption and then XORing $I$ away" -- the specification indicates that $I$ is to be computed from a unique $DT$ for each iteration: "Let $DT$ be a date/time vector which is updated on each iteration." If $I$ is implemented as described, and if $I$ or $DT$ is known for one iteration, you will not be able to backtrack to a prior $R$ or $V$ unless $I$ or $DT$ are also known for that iteration. $\endgroup$ – Chuck Batson Oct 27 '14 at 18:39

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Jan 16 '13 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.