Re: BBS PRNG strength recommendation parameters

From: David Hopwood (david.hopwood@zetnet.co.uk)
Date: 04/05/03


Date: Sat, 05 Apr 2003 00:39:55 +0000
From: David Hopwood <david.hopwood@zetnet.co.uk>


-----BEGIN PGP SIGNED MESSAGE-----

Sean O'Connell wrote:
> Reference the Blum Blum Shub PRNG, has anyone out there done any study or
> know of one on recommended values for the constant, c where j <= c log log n,
> and what is the maximum safe number of least significant bits that can be
> extracted from the RNG at any one time.
> For example, if I have a 1024 bit modulus and extract 512 LSBs each time,
> then c =51 approx. I haven't found any references to studies
> which have looked at the strength of this RNG other than the intractability
> of factoring the modulus, n.

Here's a previous post on this subject:

Colin Andrew Percival wrote:
> John Savard <jsavard@ecn.asblokb.canada.invalid> wrote:
> > It produces *one bit* from performing a large modular exponentiation.
>
> Is my memory playing tricks on me, or was it proven to be secure to take
> the lowest log log n bits?

It's a little more complicated than that. BBS is "polynomially secure" if
you take O(log log n) bits, but that isn't really very useful in deciding
how many bits to take for a specific length of n. What you need for that
is an exact security analysis of BBS, as given by the
Alexi-Chor-Goldreich-Schnorr theorem [ACGS88].

Since I'm too lazy to do the math right now, here's an example that was
given previously by Dan Bernstein, which assumes one bit per iteration
(search groups.google.com for subject "Is BBS provably secure?" in
sci.crypt to see the whole thread):

> The Alexi-Chor-Goldreich-Schnorr theorem, for example, tells you how to
> factor N using 10^54 (lg N)^3 applications of an algorithm that has a
> 1/1000 chance of seeing a pattern in a billion bits produced by a BBS
> generator mod N.
>
> The theorem does not say that predicting the generator is as hard as
> factoring N. It allows a ratio of speeds as large as 10^54 (lg N)^3.
>
> There are newer theorems that clamp down on the ratio somewhat more.
> However, it's still theoretically possible that the ratio is noticeably
> larger than 1, even though we don't have any evidence along those lines.

As an anonymous poster commented:

> Obviously using > 10^54 oracle calls (which is 2^170) to factor say a
> 1024 bit N is not useful, because it takes less work than this to factor
> such an N without a BBS oracle (probably under 2^80 steps). On the other
> hand, this is an extremely weak BBS oracle, one which is only a tiny bit
> better than chance. Stronger oracles will give more effective results.

Since arguably the BBS security proofs aren't strong enough for practical
modulus lengths even if only one bit per iteration is taken, it's a dubious
idea to take more, at least if you want to rely strictly on those proofs.

OTOH, it would not be completely unreasonable to view security proofs that
are not "tight" as heuristic arguments, suggesting that the scheme is probably
stronger than actually proven (AFAIK, none of the schemes that have security
proofs that are not tight, have been broken *because* the proof is not tight).
That is effectively what people are doing when they rely on the (corrected)
security proof of, say, RSA-OAEP, and use it with a 1024-bit modulus.

[ACGS88] Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr,
         "RSA and Rabin Functions: Certain Parts Are as Hard As the Whole",
         SIAM Journal on Computing vol. 17, no. 2, 1988, pp. 194--209.

- --
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPo4lgTkCAxeYt5gVAQGVgwf+MXBXtB9Rkx4y/BUXgdRBBvSbDIKNumvy
X3c2DG98oQfJXt7lERHz1xXj3pyaGAlMza04DCuS9QzSsYSYXx/cwHzRe8kQtOFG
j49jtqcI3Oxa852hNbdA6NrsoWjnQGJbFDL/S6ywDoyG5rRQrmIyXuQmWijWVEHR
BmF5UkyFXBW83qou2p/4gk4lWjspHgOAm7g2lMUzulXqPUM5MrDuJwUUS0eq0aKg
2b1Eo3nLkXvix/LlW0ycB28So6PygvehYJuIsfZ0+G7bjehp/Maw2NU7qZC7WKU7
PkEn3OVaSMHUX2pCwouenqxofSjqrWciQQ/Crs/PmIYrUAoC8DorTg==
=uFb5
-----END PGP SIGNATURE-----



Relevant Pages

  • Re: Semiramis not broken yet
    ... > (also known as Blum Blum Shub generator or BBS). ... > It is almost provably secure. ...
    (sci.crypt)
  • Re: Semiramis not broken yet
    ... BBS is a quadratic residue random number generator ... (also known as Blum Blum Shub generator or BBS). ... It is almost provably secure. ...
    (sci.crypt)
  • outboard bearings, simple question
    ... this is in reference to bbs and cranks. ... could google, but i'd rather get the forum response. ...
    (rec.bicycles.tech)