Newsgroups: sci.crypt.research Path: illuminati.io.com!uunet!news.mathworks.com!udel!gatech!howland.reston. + ans.net!newsserver.jvnc.net!nntpserver.pppl.gov!princeton!tucson. + princeton.edu!dawagner From: suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk) Subject: Re: A cryptographic pseudorandom number generator Message-ID: <1995Mar20.055735.1953@Princeton.EDU> Originator: news@hedgehog.Princeton.EDU Sender: dawagner@princeton.edu (sci.crypt.research co-moderator) Nntp-Posting-Host: tucson.princeton.edu Organization: University of South Carolina - Columbia - Computer Science Date: Mon, 20 Mar 1995 05:57:35 GMT Approved: crypt-request@cs.aukuni.ac.nz Lines: 70 beaver@castor.cse.psu.edu (Don Beaver) writes: >suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk) writes: >>beaver@castor.cse.psu.edu (Don Beaver) writes: >[much deleted] > ============ 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. This is polynomial? >2. List all cycles x,x^2,x^4,... modulo n. This is polynomial? You're going to have to provide a proof for this one. For general graphs, listing cycles is exponential worst-case. Of course, you're only going to get one cycle here, unless you are dropping all but the lg lg n LSB's. >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. Please re-read the revious posts. You are indeed getting N = pq and n = ceil(lg(N)) mixed up. >(Okay, I overstepped human knowledge in one place, but it's not where >you might think. This is *indeed* a polynomial-time algorithm. Oh, sure. How about the following 'algorithms' for n<1000000: 1. Factor all numbers up to 2**1000001 - 1. Place your results in a convenient lookup table somewhere... 2. Generate all BBS generator sequences for N up to 2**1000001 - 1. Place your results in a handy dandy lookup table... >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. So, in other words, your 'algorithm' has no proof of correctness. >None of the cited references are talking about this, however. I've tried >to pose a simple candidate solution for the sake of illustration.) I would guess that you've succeeded to an extent you didn't originally expect. Moderation on this group seems to have produced a false positive in this case. For my part, I'll admit that I'm just a precocious student who chimed in with a suggestion. (In retrospect, it wasn't such a great suggestion in any case.) Clearly, further discussion on this subject would just be a waste of bandwidth. --PKS