```Path: illuminati.io.com!uunet!in1.uu.net!EU.net!uknet!lyra.csx.cam.ac.uk!news
From: beaver@castor.cse.psu.edu (Don Beaver)
Newsgroups: sci.crypt.research

Subject: Re: A cryptographic pseudorandom number generator
Date: 15 Mar 1995 00:32:54 GMT
Organization: Penn State Computer Science
Lines: 134
Approved: crypt@cs.aukuni.ac.nz
Message-ID: <3k5cjm\$2dl@lyra.csx.cam.ac.uk>
NNTP-Posting-Host: nene.cl.cam.ac.uk

suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk) writes:
>beaver@castor.cse.psu.edu (Don Beaver) writes:
>>suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk) writes:
>>
>>>with a 512 bit modulus?  We could run a fast 64-bit block cipher in
>>>OFB mode, and occasionally flush the shift register and insert 63 bits
>>>from seven iterations of the BBS generator.  (We have lg(512) = 9 bits
>>>available from an iteration.)
>
>>Not to quibble, but why are you assuming lg(512) bits are secure?
>>
>>It would be misleading to use theoretical results to assume this.
>
>If the _Applied Cryptography_ blurb is not in error, then two things:

(You stated BBS correctly and read Schneier correctly.  I'll suggest
a polynomial-time attack on 512-bit BBS using 9-bit windows below.)

============ The Literature ==============

I just took a look at Schneier.  On p. 366:

As it turns out, you can use more than the least significant bit
of each x_i as a pseudo-random bit.  According to [863,864,865,19,20],
if  l  is the length of x_i, the least significant log_2 l bits
of x_i can be used.

This is a slight misinterpretation of the theoretical results.

(On the other hand, a more precise explanation would have probably
expanded Bruce's book into a twelve-volume work.  But there is
an immense danger in applying the theoretical results, one that
serendipity may avoid.  But serendipity is not a trusted friend.)

Let's take [20], for example: Alexi/Chor/Goldreich/Schnorr,
Siam J. Comput., 17:2, 1988, 194--209.   On p. 208:

In section 5 (6), we have shown simultaneous security results of
O(log n) bits in RSA (Rabin) encryption function.  ...

The BBS generator uses the same technique as the Rabin encryption function
(squaring modulo n).  As far as I know (and apparently also, Bruce knows),
O(log n) is the best rating.

============ Getting Rid of Big Oh ==============

>>A proof that O(lg n) bits are secure doesn't help.  It merely says
>>that if you design a method to predict bits, it won't work in the
>>limit if it's given O(lg n) bits.  This says nothing about what happens
>>in initial cases.
>>
>>For example, I can request that you use  1000 lg n  bits
>>(which is O(lg n)) and I'll then predict the sequence trivially
>>for n = 512.  Surely, my prediction method will fail when n gets larger,
>>but not yet.
>
>        2) Where the heck did "Big-Oh" get into this?  I think there's
>           some confusion here between N = pq and n = ceil(lg(N)).

Big-Oh got into it from the published theoretical literature,
which I guessed was the ultimate source of the original "log_2 n."

It makes no great difference.  Let's forget about O(lg n) and
just stick to  lg n.

============ Polytime Attacks on BBS ==============

>Do you know of any actual polynomial-time attacks on BBS?  As I
>understand it, these would imply polynomial-time factoring.  Please
>post some references, I would be very interested in these.

Here is a polynomial-time attack on BBS [using  lg n  windows]
that works fine for n up to 1000000 bits.

0. If n>1000000, then flip a random bit and return it as the prediction
for the next bit.  Else do 1-6:
1. Factor n.
2. List all cycles  x,x^2,x^4,...  modulo n.
3. Request a sequence of n^1000000 BBS bits.
4. Divide that sequence into  lg n  sized chunks.
5. Match those chunks up to one of the cycles we found in step 2.
6. Predict the n^1000000+1'st  bit by using the next number in the cycle.

(Okay, I overstepped human knowledge in one place, but it's not where
you might think.  This is *indeed* a polynomial-time algorithm.

The only problem is that there may be more than one cycle from step 2
that matches the sequence.  You'd get the idea immediately if we weren't
using only a 1-bit window.  This is an easy algorithm to state, but for
all I know it could be as hard as FLT to prove or disprove the existence
of multiple subsequences matching a given pattern.

to pose a simple candidate solution for the sake of illustration.)

Context of Alexi/Chor/Goldreich/Schnorr:

No problem if this attack works for n up to 1000000 bits.
It will eventually fail on much larger n.  (And this is
*all* that you can say, in this context!)

Context of Schneier:

Okay, so this attack works.  It's even polynomial time.  Big deal.
It's a polynomial with a very big constant!  The constant is so big
that nobody would use this method.  "Polynomial" does not mean
"efficient."

The point is that there may be very simple and very "efficient"
*polynomial-time* attacks that predict BBS for n<1000000.

Alexi/Chor/Goldreich/Schnorr would not be contradicted in the least.
Such attacks would merely _eventually_ fail.  *How big*  n  has to be
is not a part of the theoretical rating.  There is no theoretical
support to deny the existence of "efficient," polynomial-time attacks
on BBS for n<1000000.

In fact, BBS may well be fine for n=512 and  lg n = 9-bit windows.
For that matter, it may even be fine for n=512 and 256-bit windows!
The theoretical results won't tell you anything.  Whether BBS is fine
with 9-bit windows or 256-bit windows is a matter for "hackers" and
modern technology to decide.  Not the cited papers!

Don
```