# Tag Info

1

Putting some of my comments into writing. This is less than an answer but too much for a comment. In the comments I had claimed to apply SMT to solve case 1 - this is false, I was mistaken. I have had cases 2 and 3 running SMT (boolector, Z3, CVC4, yices) for some time without success. The closest thing to success is the identification of seeds that ...

2

This answer addresses Cases 1 and 2 from the question to provide a baseline, leaving Case 3 (which is the one I'm most interested in), unresolved. Case 1, Zero Increment In this case we'll consider a simple Lehmer-style LCG (a.k.a. an MCG), with a seed $s_1$, multiplier $a$ and $b$ bits of state and $r$ bits returned. The modulus $M = 2^b$, and the ...

1

This is a work-in-progress, mostly trying to address Case 3 in the question, since the problem of Case 2 is dealt with in another answer, and has been thoroughly researched: Jacques Stern: Secret linear congruential generators are not cryptographically secure, in proceedings of the 28th Annual Symposium on the Foundations of Computer Science, 1987 (try a ...

0

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

3

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

3

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

2

Short answer / tl;dr: Yes, that can occur, but it is no problem most cases. The sequence "1234" would be a perfectly normal output for a generator which ouputs a pattern of 4 numbers from 0 to 9. If every possible sequence has the same probability of being used as output (called being uniformly distributed), than "1234" is as likely as "7392" or even ...

0

This looks like one. It does say "non-cryptographic" so I assume it is repeatable given the same seed. A small noncryptographic PRNG. You could also do a an implementation of a Message Authentication Code (MAC) such as this one UMAC which says it is meant to be "well supported on contemporary machines".

4

Yes. This paper on nist.gov gives five such PRNGs. Three of them are based on hash functions and two of them are based on block ciphers.

Top 50 recent answers are included