8
$\begingroup$

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?

$\endgroup$

3 Answers 3

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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*? $\endgroup$
    – neubert
    Dec 14, 2012 at 14:37
  • $\begingroup$ @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$. $\endgroup$ Dec 17, 2012 at 8:27
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ A simple counter is easier to implement than something really secret, though. $\endgroup$ Sep 6, 2011 at 17:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Sep 6, 2011 at 23:50
  • 2
    $\begingroup$ @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). $\endgroup$ Sep 7, 2011 at 0:43
  • $\begingroup$ @Paŭlo Ebermann: do you have a source where "the designers" use "increment"? I read "update". $\endgroup$ Sep 12, 2011 at 4:09
  • $\begingroup$ @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. $\endgroup$ Sep 12, 2011 at 10:51
1
$\begingroup$

It's easy enough to show that if the key is unknown, and the block cipher is secure, then all bits of both future and past outputs are unpredictable; hence, there is no requirement that the date/time vector be unpredictable.

I believe that the main reason they inserted the date/time vector is to prevent the output running into a short cycle. The X9.31 state function is invertible (with a fixed key and date/time vector), and the state consists of one block of data (sized according to the block cipher it uses). Hence with a 64 bit block cipher (which it original used) which we model as a random permutation, and you fix the date/time vector, you'd start to outputting a cycle after N states with probability N/2^64 (for N<=2^64). This yields the probability of falling into a cycle as 2^-32 after 2^32 outputs; the designers may have considered that probability too large.

$\endgroup$
5
  • $\begingroup$ Is it maybe possible that dt vector prevent any cycle ? $\endgroup$
    – user536
    Sep 6, 2011 at 15:19
  • $\begingroup$ I known one requirement for prng is, that it's must be for an adversary impossible to detect that a prng is used to create random numbers. If the adversary is able to detect a cycle no matter if short or long he knows that a prng is used. But if he is not able to detect a cycle than he can not distinguish if a prng or a truer rng is used. $\endgroup$
    – user536
    Sep 6, 2011 at 15:26
  • $\begingroup$ 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. $\endgroup$ Sep 6, 2011 at 17:38
  • $\begingroup$ As I mentioned earlier, if we model the state update as a random permutation, and there are N states (N==2**64 for 3DES), then the probability that you'll run into a cycle after K outputs is K/N. Hmmmm, I just noticed: with fixed I, the state update is actually the square of a random permutation; this means that if the cycle length for the square root permutation is even, then the cycle length for the state update is halved. This reduces the expected cycle length somewhat. $\endgroup$
    – poncho
    Sep 6, 2011 at 18:25
  • $\begingroup$ What makes it unlikely to run into a short cycle is iterating a function Vold -> Vnew that is a pseudo-random mapping (rather than a pseudo-random function). What dt does is influence I, which (together with K) controls what pseudo-random mapping is used. See my answer on why dt is a date/time vector. $\endgroup$ Sep 7, 2011 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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