Will X9.31 remain a secure & acceptable deterministic random generator beyond 2015? 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) ?
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.