# ANSI X9.31: the purpose of the date/time vector in the PRNG?

What is the exact purpose of the date/time vector $dt$ in the ANSI X9.31 PRNG?

$$I := E_K(dt)$$ $$R := E_K(I \oplus V_{old})$$ $$V_{new} := E_K(R \oplus I)$$

Specifically, the document seems to imply that the seed $V_*$ and key $K$ must be kept secret, but makes no claims on the secrecy of the $dt$ vector, only that it should be increased on each iteration. Can it be known by an adversary? Are there any implications if it is known to an adversary?

-

From ANSI X9.31:1988, Appendix A.2.4 (Generating Pseudo Random Numbers Using the DEA):

"Let DT be a date/time vector which is updated on each iteration."

The purpose of $dt$ is to supply a value that is different each time the algorithm is seeded, so as to generates a different sequence, even if $V_*$ (the initial value of $V_{old}$) is a fixed secret.

The algorithm seems to be secure even if $dt$ is known, and predictable, e.g. a 64-bit counter starting from 0; at least, that's the design goal. However it must not be possible to return $dt$ to an earlier value. In other words, $dt$ needs to be a "number used once", sometime called nonce.

Beware that an adversary could set the clock, hence $dt$. In the absence of a specific mechanism, that might allow her to re-generate a previous sequence!

It is probably best if the adversary can not choose $dt$ (and that makes it much easier to insure that $dt$ is unique).

-
What if v* isn't a fixed secret? Plus, it seems to me that Ek() would need to have random keys / IVs anyway so if you could generate a random key / IV with what's available in your entropy pool why not just do the same for V*? –  neubert Dec 14 '12 at 14:37
@neubert: If $V_*$ is revealed, even after use, the unpredictability of the output is compromised. If $V_*$ is random rather than fixed, it helps if $V_*$ is uniformly random; on the other hand if $V_*$ is badly biased (say each bit is 0 with 95% odds), $V_*$ would be a weak secret, enumerable, and thus again unpredictability of the output compromised. Bottom line is that the generator assume a fixed uniformly random secret key $V_*$, and a variable non-secret seed $dt$. –  fgrieu Dec 17 '12 at 8:27

Since V is kept secret, it probably doesn't matter if DT is kept secret, but it definitely doesn't hurt if it is kept secret. This is a pretty standard practice with PRNGs---mix in as much potentially high entropy data as possible.

-
A simple counter is easier to implement than something really secret, though. –  Paŭlo Ebermann Sep 6 '11 at 17:39
@Paŭlo, I suspect mikeazo's point is that each DT value might have a little bit of entropy; it can't hurt to mix it in, and it might help (i.e., might help increase the entropy of the generator). In contrast, a counter has no entropy whatsoever, and thus no possibility of helping increase the entropy of the generator. So that's a possible reason why the designers might have specified DT instead of a counter. –  D.W. Sep 6 '11 at 23:50
@D.W.: The designers also specified that DT is incremented for each iteration, though. One could say it is a mixture of a simple date-time vector (which might have the same value for several iterations for an imprecise clock) and a counter (which might repeat for several runs of the same program), combining both to achieve uniqueness (as long as the clock isn't set back between program runs). –  Paŭlo Ebermann Sep 7 '11 at 0:43
@Paŭlo Ebermann: do you have a source where "the designers" use "increment"? I read "update". –  fgrieu Sep 12 '11 at 4:09
@fgrieu: It says Let DT be a date/time vector which is updated on each iteration. (I read only the document linked in the question). Seems my memory pulled a trick on me here. –  Paŭlo Ebermann Sep 12 '11 at 10:51
Actually, as the block cipher is bijective, with fixed $I$ all outputs would be on a cycle, not just leading into one (like in a random function). The question is just how long the cycle would be. –  Paŭlo Ebermann Sep 6 '11 at 17:38