10
$\begingroup$

I am actually looking for available crypto libraries including a deterministic random generator for the purpose of a dedicated crypto key generator unit.
I have a simple question about the X9.31 based PRNG as proposed for instance in Botan library, since I noted that NIST SP800-131 document indicates that use of the X9.31 prng is disallowed from 2015:

  • Has a PRNG based on X9.31 (as Botan's one) some weaknesses that make that it is no more considered as sufficiently secure and so it is effectively preferable to use another (i.e. CS-PRNG) ?
  • or NIST recommendation is driven by other objectives (as to limit to CS-PRNG defined in NIST SP800-90A standard) ?
Improve this question
$\endgroup$
1
  • $\begingroup$ @fgrieu- Thanks for clarification. My post was not sufficiently precise : effectively I implicitely referred to the PRNG as defined in Appendix 2.4 of ANSI X9.31-1998 standard . And so my trouble is that NIST agreed it in FIPS-140-2 (Annex C dated from 2012) while recommending use of 3-keys triple DES or AES, while NIST SP800-131A doc dated from January 2011, indicates that X9-31 -1998 PRNG is disallowed from 2015. So it seems to me that finally as you indicate, use of such X9.31 -1998 Appendix 2.4 PRNG with using AES-256 might not be concerned and so disallowed by NIST SP800-131A doc. $\endgroup$
    – william_fr
    Dec 5, 2014 at 10:46

3 Answers 3

Reset to default
6
$\begingroup$

X9.31-based PRNGs as used in current practice (including in the Botan library) tend to be extensions of the generator of ANSI X9.31-1998 appendix A.2.4 (which designated purpose is as a submodule of a prime generator for RSA keys). This really is the PRNG of ANSI X9.17-1985 Appendix C (which designated purpose is generating DES keys), also described in modern form in section 5.3.1 of the HAC. This generator has a sound and time-tested structure; however I know no theoretical argument reducing security to that of the underlying block cipher. Update: and, as pointed by Gilles in another answer, it lacks backtracking resistance: past output can be deduced from the current state, which is a concern in some applications where the state is kept for extended period, rather than safely disposed of after use, and could get compromised.

This original generator, designated ANSI931_TDES2 in NIST test vectors, does show its age in the use of Triple-DES with two keys, which has limited 64-bit block size, 112-bit key entropy, theoretical vulnerability to meet-in-the-middle variants, and poor suitability for software implementation, with in particular risk of timing attacks on CPUs with caches, and other side-channel attacks. All this is reason enough for ANSI931_TDES2 to be abandoned with a deadline at the end of 2015, per NIST SP800-131A Table 3.

Four common extensions have been defined in NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms (2005). ANSI931_TDES3 just widens the key to an effective key size of 168 bits. ANSI931_AES128, ANSI931_AES192, ANSI931_AES256 use AES, with the corresponding key size; and make all variable data 128-bit wide. As far as I can tell these generators are in an administrative state of limbo: neither explicitly deprecated, nor with recent re-approval. I sure would not want to use ANSI931_TDES3 for any new development.

It seems inconceivable to me that a practically useful cryptanalytic attack of ANSI931_AES256 (the variant claimed to be used in the Botan library) could emerge within a human lifetime, assuming an adversary knowing nothing about secret key and primary seed material chosen uniformly at random, trying to predict some of the output, knowing all other external data (other output and auxiliary seed material), and not in a position to conduct side-channel or fault injection attacks on the internal state of the generator (Update: including as left after the PRNG's intended use). I base this assessment on the lack of published attack on the original PRNG after 30 years of exposure, and the dramatic security boost given by the widening of key and state.

Note: After I dug ANSI X9.31-1998 from my chest of purchased standards, I intended to make this answer a detailed analysis of the birth, life and fall of the 3 generators in appendix A, and their descendants. This turned out to be inextricably difficult, because the algorithm in appendix A.2.1 as written is dead wrong in step 4e where the output is supposedly generated, and there's no test vectors as a lifebuoy; also I could not determine which of it or FIPS 186-1 Appendix 3.1 (nearly identical except for the defective step) predates the other.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks for that great detailed , precise & pedagogic answer which provides rationale for confidence in NIST recommended extension of ANSSI X9.31 Appendix 2.4 PRNG with AES-256. $\endgroup$
    – william_fr
    Dec 5, 2014 at 16:41
  • 1
    $\begingroup$ Do you consider the lack of backtracking resistance to be a concern? $\endgroup$
    – Gilles 'SO- stop being evil'
    Dec 5, 2014 at 19:29
  • $\begingroup$ @Gilles: yes, in some uses the lack of backtracking resistance can be an issue. I semi-consciously worded the hypothesis of my endorsement so that it excludes this concern, but in retrospect should have mentioned it. You did, very well. $\endgroup$
    – fgrieu ♦
    Dec 5, 2014 at 19:46
4
$\begingroup$

NIST SP800-131A (Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, 2011) §4 specifies that the RNGs from ANSI X9.31 are disallowed after 2015, but as fgrieu notes this is a 3DES-based algorithm; the NIST specification does not explicitly mention the commonly-used AES variant.

NIST does however recommend (but not mandate) the algorithms described in SP800-90A (Recommendation for Random Number Generation Using Deterministic Random Bit Generators, 2012). These are:

  • Hash_DRBG (§10.1.1), an algorithm based on iterating hash functions (SHA-1 or SHA-2 — SHA-1 is still acceptable for this use according to SP800-131A §9).
  • HMAC_DRBG (§10.1.2), a broadly similar algorithm based on iterating HMAC functions;
  • CTR_DRBG (§10.2.1), an algorithm based on a block cipher (AES or 3DES — 3-key 3DES is still acceptable according to SP800-131A §2, 2-key 3DES is disallowed after 2015).

SP800-90A also used to propose Dual_EC_DRBG but it has been pulled.

The French cryptographic standards used to cite the AES variant of ANSI X9.31 (RGS 1.20 §2.4.3) as being explicitly conforming, in parallel with the SP800-90 algorithms. This is no longer the case since July 2014; RGS 2.03 §2.4 gives the following requirements for a random number generator:

  • Impossible to reconstruct the internal state from outputs. (RègleAlgoGDA-2)
  • Impossible to reconstruct outputs if the internal state is compromised. (RègleAlgoGDA-3)
  • The internal state must be at least 128 bits with “sufficient” entropy injection, and must be at least 160 bits in the absent of a frequently-called hardware entropy source. (RègleArchiGDA-3)

In particular, if the internal state is compromised, this must not affect the confidentiality of past outputs. This property is called backtracking resistance. See SP800-90A §8.8, a CryptoSys description, and Definition of a CSPRNG for more information on this topic.

The X9.31 PRNG does not have backtracking resistance: given the internal state, an attacker can easily calculate output for past timestamps, and timestamps are usually guessable. Therefore it is no longer permitted by French recommendations. The SP800-90A algorithms (Hash_DRBG, HMAC_DRBG, CTR_DRBG) all have backtracking resistance.

While X9.31 is not fundamentally broken, the lack of backtracking resistance is a weakness in practice. It is preferable to use an algorithm with backtracking resistance if your use scenarios include cases where you want to maintain the security of past transactions after a compromise (a kind of forward secrecy).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I understand your warning about lack of backtracking resistance. In the concrete case of Botan library I noted that the complete prng was : entropy source => Botan random pool => x9.31 prng => random output. So with x9.31 seed key and date/time vector issued from Botan proper random pool output. So in that case i understand the threat assumed both knowkedge of overall combined prng state plus botan proper random pool prng not based on a one way function. Is it correct ? I precise that prng is to be used for keys generation so prng state value disclosing is a major threat. $\endgroup$
    – william_fr
    Dec 5, 2014 at 21:37
  • $\begingroup$ @william_fr I'm not familiar with Botan. From reading the manual, I gather that it periodically mixes in entropy. Mixing entropy into the RNG state makes backtracking harder, so if this happens at a sufficient rate, you have backtracking resistance. I can't tell from reading the manual how fast that happens or what entropy sources are used; that would determine how many recently-generated keys are compromised if your server is compromised at some point. $\endgroup$
    – Gilles 'SO- stop being evil'
    Dec 5, 2014 at 21:46
  • $\begingroup$ Ok clear. I will check more in detail Botan documentation and internal prng operation. I just add for info that in my application criticity of key generator makes that it might be implemented on a standalone Linux computer. So no more network access but inversely low activity and so low entropy available within the kernel through /dev/random device and to be compensated by a companion hardware entropy source as Intel drng for instance. $\endgroup$
    – william_fr
    Dec 5, 2014 at 22:15
  • $\begingroup$ @william_fr Reseeding (at a sufficient rate) from /dev/urandom would be enough to provide backtracking resistance, since /dev/urandom has backtracking resistance. $\endgroup$
    – Gilles 'SO- stop being evil'
    Dec 5, 2014 at 22:29
0
$\begingroup$

As far as I know, the backtracking resistance of all non-hardware GRN's is suffering generally, despise of an algo, but it's a question of re-seeding frequency/procedure from a true hardware entropy source. Double-transistor avalanche noise or Geiger tube is supposed to mend this problem nowdays, especially regarding it's simplicity and price. But it's just my personal opinion.

Improve this answer
$\endgroup$

Your Answer

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

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