3
$\begingroup$

The following excerpt is taken from the “Cryptographically secure pseudorandom number generator” article on Wikipedia:

CSPRNG designs are divided into three classes:

  1. those based on cryptographic primitives such as ciphers and cryptographic hashes,
  2. those based upon mathematical problems thought to be hard, and
  3. special-purpose designs.

The last often introduces additional entropy when available and, strictly speaking, are not "pure" pseudorandom number generators, as their output is not completely determined by their initial state.

I am interested in the question: does there exist a cryptographically secure pseudorandom bits generator that satisfies all of the three following requirements?

  1. It belongs to class 2 according to the classification described above. Assuming that CSPRNG uses multiple iterations of some function $F$ to generate the output of the desired length, this requirement implies that the description of $F$ does not mention different versions of the function that are explicitly constructed for different word sizes. Examples of algorithms that satisfy this requirement: Blum Blum Shub, Blum–Micali algorithm;
  2. It does not require generating prime numbers (or testing primality of any number);
  3. If the algorithm uses any precomputed values, then there should be an open algorithm that demonstrates how these values are generated (with the detailed explanation of why it is required to use these values and why other values might impact the desired properties of the output).
$\endgroup$
  • 1
    $\begingroup$ Does 2 prevent using a large public provable prime? $\endgroup$ – fgrieu Nov 2 '18 at 9:01
  • 2
    $\begingroup$ Unless you define stream cipher tobe a CSPRNG it will be very hard to find a CSPRNG that isn't at least based on one. A stream cipher basically is a CSPRNG that uses a single fixed seed - the key. $\endgroup$ – Maarten - reinstate Monica Nov 2 '18 at 11:51
  • $\begingroup$ @fgrieu: The dependence on primality is definitely undesirable, but I can answer "No" to this question, with the following clarification: the public prime should be replaceable by any other prime of the same (or larger) length. Additionally, there should be no "weak"/"bad" seeds for the algorithm. If you know such algorithm, you can include it in the answer. $\endgroup$ – lyrically wicked Nov 3 '18 at 10:41
  • $\begingroup$ I've now read this question multiple times. I'm however more and more curious behind the reason behind the question. What are you trying to accomplish? $\endgroup$ – Maarten - reinstate Monica Nov 3 '18 at 19:05
5
$\begingroup$

Yes, at least for a definition of "based on a particular mathematical problem" allowing the problem to be breaking the generator!

Restricting to constructions that can be efficiently implemented, one of the simplest conjecturally Cryptographically Secure Pseudo Random Number Generator in the literature is the Alternating Step Generator, proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. Its best known cryptanalysys is by Shahram Khazaei, Simon Fischer, and Willi Meier: Reduced Complexity Attacks on the Alternating Step Generator, in proceedings of SAC 2007

The ASG consists of three Linear Feeedback Shift Registers, which have a well known reduction to arithmetic in $GF(2^k)$. To produce a bit:

  • advance LFSR2
  • according to it's low-order bit, advance LFSR0 or LFSR1
  • output the XOR of the low order bits of LFSR0 and LFSR1

To choose the (public) LFSR parameters, select the desired security parameter $n$. Then pick three binary primitive polynomials of degree $n_0$, $n_1$, $n_2$ with $\alpha\,n<n_0<n_1<n_2$ so that $2^{n_0}-1$, $2^{n_1}-1$, $2^{n_2}-1$ are pairwise coprime. The best known attacks are for $\alpha=\frac32$, but $\alpha=2$ is more reasonable.
Note: in the initial exposition, LFSR2 is modified to generate a de Bruijn sequence, that is the output sequence has an extra zero inserted after $n_2−1$ consecutive zeroes. But this detail makes no cryptanalytic difference, since that point in the sequence is reached with negligible probability for $n_2$ large enough to thwarts attacks guessing the state of a single LFSR.

Per comment: Checking if two integers are pairwise coprime does not require "testing primality of any number". It can be done with Euclid's algorithm (or others that efficiently compute the Greatest Common Divisor), and checking that the GCD is 1. Also, parameter choice is performed just once, then we can have multiple instances of the generator using these parameters and different keys.

Example, with the help of the compact table of primitive binary trinomials compiled by Jörg Arndt (and a caveat: I have no clear-cut argument that using trinomials leaves the ASG secure): $n=192$, $n_0=385$, $n_1=386$, $n_2=393$ and

  • LFSR0: $x^{385}+x^{142}+1$
  • LFSR1: $x^{386}+x^{83}+1$
  • LFSR2: $x^{393}+x^{91}+1$
    $n_0$ and $n_1$ are minimal given the choice $n=192$ and $\alpha=2$. $n_2\in\{387, 388, 389, 392\}$ was not used due to absence of trinomials. $n_2=390$ was not used because $\gcd(2^{386}-1,2^{390}-1)=3\ne1$. $n_2=391$ was not used so that the center terms (otherwise minimal) are farther than 64-bit from each side (in hope to ease constant-time software implementation).

The key is the initial state of the three LFSRs (with say the high-order bit of each LFSR set to the complement of the XOR of the others in order to ensure non degenerate states). This is an inconveniently long key, of $n_0+n_1+n_2-3>3\,\alpha\,n$ bits, and the security conjecture is for uniformly random independent key bits.

Some formal definitions of a CSPRNG (and practical robustness) require it's key to be of size equal to the security parameter. If that's wanted, coming up with a safe initialization procedure starting from a key of $n$ bits is non-trivial: we need some auxiliary CSPRNG to expand from $n$ to $n_0+n_1+n_2-3$ bits (from 192 to 1159 in the above example).

$\endgroup$
  • $\begingroup$ Regarding the "pairwise coprime" property — doesn't this contradict the second requirement? $\endgroup$ – lyrically wicked Nov 3 '18 at 10:28
0
$\begingroup$

The 2nd and 3rd requirement are easily satisfied as soon as you're not using Dual_EC_DRBG.

The first requirement is a bit pointless -- as one can argue that any mathematical problem used in cryptography is a cryptographic primitive.

All of the other 3 DRBGs in NIST SP 800-90A are based on some primitive -- block cipher in counter mode, and hash function (directly or HMAC).

The previous 2 paragraphs are striken-through in response to comment, because now I'm sure someone can come up with a lattice-based CSPRNG, by combining linear and non-linear operations, uniform rejection sampling, and state-truncating output. Except there isn't such construct widely known for now.

From conventional wisdom, we know that all (CS)PRNGs are modes-of-operation of underlaying primitives. For example, if SHAKE-{128,256} were to be used directly as PRNGs, then they'd be XOFs operated in Sponge mode. And your BBS and B-M example are not so different -- they also outputs partial states of their iterated unary function; except instead of a cryptographic permutation, a mathematical one is used.

Side note: BBS is not a "cryptographically secure" PRNG, as it's vulnerable to back-tracing attack: assuming the current state of the PRNG and the factorization of $M$ is known, past states can be recovered with decryption exponent $d=gcd(2, \lambda(M))$

$\endgroup$
  • $\begingroup$ I don't understand the second paragraph ("the first requirement is definitely never satisfied"). But I edited the question to give two examples of algorithms that definitely satisfy the first requirement. $\endgroup$ – lyrically wicked Nov 2 '18 at 8:26
  • $\begingroup$ @lyricallywicked I've reworded appropriately so as to not to be too absolute. $\endgroup$ – DannyNiu Nov 2 '18 at 8:53
  • $\begingroup$ Regarding [one can argue that any mathematical problem used in cryptography is a cryptographic primitive] and [all (CS)PRNGs are modes-of-operation of underlaying primitives] — these facts do not contradict the first requirement. I edited the question to add a clarification. Regarding [BBS is not a "cryptographically secure" PRNG] — both Blum Blum Shub and Blum–Micali are included in the "Number-theoretic designs" section in the corresponding article on Wikipedia. This is why I referred to them. $\endgroup$ – lyrically wicked Nov 3 '18 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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