Is a BB&S System "Proven Secure"?

Terry Ritter

A Ciphers By Ritter Page

Lenore Blum, Manuel Blum and Michael Shub (BB&S) are the authors of a famous mathematical article on the construction of an "unpredictable" random number generator (RNG), which we also call BB&S.

Blum, Blum and Shub. 1982. Comparison of Two Pseudo-Random Number Generators.

Advances in Cryptology -- CRYPTO '82. 61-78. Plenum Press.
SIAM Journal on Computing. 15(2): 364-383. (1986).

The BB&S RNG

The BB&S construction consists of finding two "large" primes, each of which is equivalent to 3 mod 4. But the BB&S article gives various other requirements, such as the primes being "special," requirements which are avoided by the modern cryptographic community. (Prime P is "special" when P = 2P1 + 1 and P1 = 2P2 + 1 where P1 and P2 are odd primes; finding special primes thus takes considerably more effort than just finding primes.) Much of the discussion here is about whether the results of the simplified system are the same as the special primes construction of the BB&S article.

In BB&S, the product N of the two large special primes P, Q, is used as a modulo to reduce a squaring computation: X_i+1 := X_i² mod N, (or X[i+1] := X[i]**2 mod N). This defines a mathematical system which always has multiple cycles, some of which will be shorter than the longest cycles, while others will be degenerate cycles with constant values. Choosing an initial X[0] thus chooses a particular cycle within the RNG (including, with very low probability, short and degenerate cycles) and thus a sequence of X values. The value reported out of the RNG is the least-significant bit (LSb) of X. Typically BB&S would be the RNG part of a conventional stream cipher. Any stream cipher confusion sequence which repeats in practice is appallingly weak, because -- after the first pass through the cycle -- it is absolutely predictable.

The Issue of Proof

BB&S is very slow, and so is unlikely to be used in practice. But if it is used, surely the reason for that is to attain the famed "proven security" property. Since the probability of selecting a short cycle at random is very low, short cycles are probably not an important weakness in practice.

But if the only reason to use BB&S is to attain "proven security" and the result is not in fact secure, somebody is being deceived. (Of course, even mathematical proofs do not prevent an opponent from choosing the correct key at random; proofs do not cover all possible weaknesses.) But short cycles are a known part of all BB&S constructions. Unless we guarantee otherwise, when we choose a starting value at random, we may land on and use a short cycle. If the system uses a short cycle (short enough to repeat), the system is unarguably insecure. It is hard to reconcile this possibility with claims of "proven security."

The BB&S article presents a "special primes" construction which guarantees that cycles of a known length will exist. While it is very hard to measure the length of an extremely long cycle, it is relatively easy to check that a cycle has a particular length. So, with the special primes construction, we can simply check that any x0 we choose is in fact on the long cycle. It is thus within our power to completely avoid the possibility of choosing and using a weak short cycle. Both the special primes construction and the cycle length check are non-trivial, but nothing about "proven security" says it must be easy.

Apparently the BB&S proofs imply that if we can predict the sequence, then we can do things otherwise thought impossible, such as factoring N. But proofs are based on particular mathematical models, and for any such proof to be useful in a real system, we must also guarantee various obvious things, such as the factors of N being otherwise protected. Surely, any system which exposes a factor of N is not going to make factoring N very difficult, no matter what the proof says. But it may be that the selection and use of a short cycle exposes a factor of N in just that way. Using a short cycle allows the length of the cycle to be observed by the opponent; if that allows N to be factored, it is the selection and use which has exposed that secret.

The usual argument is that the BB&S proof applies whether we arrange to avoid short cycles or not. It is certainly true that finding short cycles is not a good strategy for factoring N. The problem is that the system is supposed to be strong no matter what x0 we choose, but we actually know that some values of x0 are weak. BB&S inherently has a few weak keys. Choosing a short cycle at random may be extremely unlikely, but it is a risk of weakness beyond whatever other weaknesses exist.

In Practice

Robert Eachus has suggested that if someone were actually going to practice BB&S technology, one approach might be to use special primes of public-key size for P and Q, then just check for degenerate cycles. This is easy: just choose x0, take a step, record the value, then take another step. If the new value is the same as the old one, start over by choosing another x0. Apparently the special primes construction assures that the non-degenerate "short" cycles are "long enough" on their own, so we just use whatever comes up. Of course, special primes are significantly harder to find than ordinary primes.

The Message Order

Note that the messages are in a sort of depth-first tree-traversal order, rather than by date. This tends to keep messages in particular conversations close together. Unfortunately, the responses to the earlier messages also become widely separated.

2000-06-14 sarnold_intertrust@my-deja.com: ". . . When playing around with Blum Blum Shub, using small primes, I noticed very short cycles before repetition."
2000-06-15 Mok-Kong Shen: "The issue was discussed in the group some time back."
2000-06-14 lordcow77: "Essentially, the existence of exploitable cycles in BBS would neccesarily lead to an efficient algorithm for decomposing RSA moduli into primes."
2000-06-15 Terry Ritter: "BB&S did expect large primes; the requirement for "special" primes was to guarantee that the system had cycles of some long, known and computable length." "Short cycles certainly do exist in BB&S, and short cycles are "exploitable.""
2000-06-14 Nicol So: "lordcow77's interpretation is correct."
2000-06-14 tomstd: "I don't know why people still consider the BBS generator. It's not very safe."
2000-06-15 Nicol So: "I'm not aware of any real-life application that uses it. I think the BBS generator is mostly of theoretical interest only."
2000-06-15 James Felling: "Yes, it is big, ugly and slow. OTOH it is provably as good as the underlying intractible problem, and it is one of the only PRNG's with that property."
2000-06-15 Terry Ritter: "All real BB&S systems *do* have short cycles. And short cycles *are* weak. Yes, it is unlikely to select a short cycle at random. But unless the BB&S prescriptions are followed, that is *only* "unlikely" and *not* "impossible." In contrast, the BB&S prescriptions *guarantee* that one does not use a short cycle, and that is a qualitative difference."
2000-06-15 sarnold_intertrust@my-deja.com: "So, now, back to square one; BB&S had the property of being 'indexable' such that one could request a particular output. I would very much like to keep this property. Are there any other PRNGs available with this property?"
2000-06-16 Tim Tyler: "Yes. All completely "linear" systems have this property - e.g. an LFSR." "Also RNGs based on hashes, MACs or cyphers driven by counters offer random access capability."
2000-06-15 Nicol So: "My comment was directed at that of lordcow77, not yours. Refuting your reasoning was not my intent." "I stand by my assertion that asymptotically, it doesn't matter much whether you choose special primes . . . ." "OK, choosing special primes eliminates one particular weakness that occurs with negligible probability. Are you sure BBS has no other weaknesses that occur with negligible probability?"
2000-06-16 Bryan Olson: "Falling into a short cycle from a random starting point is no more likely than falling into a factorization."
2000-06-17 Bryan Olson: "Falling into a short cycle from a random starting point is no more likely than falling into a factorization."
2000-06-15 Tim Tyler: "It's not a simply a case of losing sleep - it's a case of knowing whether your system is secure." "Short cycles are weak and insecure - no matter what the probability of their arising is."
2000-06-16 David Hopwood: "AFAICS from Theorem 4 of the BBS paper, lordcow77's argument is correct. That theorem shows that breaking the BBS generator is as hard as factoring N = pq [...], regardless of what the cycle length is."
2000-06-16 sarnold_intertrust@my-deja.com: "To me, being able to guess the upcoming bits with probability 1 because you already saw them earlier in the cycle, *that* spells "broke"."
2000-06-23 David Hopwood: "Correction: it shows that breaking the BBS generator is as hard as breaking the quadratic residuosity assumption . . . ."
2000-06-16 lcs Mixmaster Remailer: "Take a look at:"
2000-06-16 Terry Ritter: "Now, did Blum, Blum and Shub simply get carried away with their own math abilities? Shall we assume that they were they so unaware of their first results that they simply did not understand that 2/3 of their work was "useless"?" ". . . the discussion here is about the concept of "proof" itself: I claim that if it is *POSSIBLE* to select a short cycle, it should be self-evident that any *proof* of security must be false. The alternative is a clear logic error -- an actual reasoning fault."
2000-06-17 Terry Ritter: "Looking at my old results, it appears that degenerate cycles are located at values P and Q, and so actually might the most direct way to factor N."
2000-06-17 David A. Wagner: "What was wrong with the old article at the URL above?"
2000-06-18 Terry Ritter: "All we need to find is one false case and the claim (that X^2 mod N is proven secure without short cycle checks) fails."
2000-06-18 David A. Wagner: "There is no contradiction here."
2000-06-19 Terry Ritter: "This discussion is about whether X^2 mod N is "proven secure." And all that is necessary for X^2 mod N insecurity is for the encrypting end to choose a wrong x0."
2000-06-19 David A. Wagner: "You seem to think that, if an algorithm is "provably secure", then it cannot have any weak keys (no matter how infrequent). This is just plain wrong, at least under the normal definitions of "provable security"."
2000-06-18 Mark Wooding: "Err... I thought that the BBS generator was secure given that factoring the modulus is hard."
2000-06-19 Terry Ritter: "The correct conclusion to be drawn from the demonstration is that the assumption is false *under* *particular* *circumstances*, in particular, when a short cycle is used."
2000-06-17 David A. Wagner: ". . . clearly it is *POSSIBLE* for the adversary to guess a factor of N just by dumb luck, and then you've broken BBS, but such a lucky guess is extremely unlikely to happen."
2000-06-18 Terry Ritter: ". . . the enciphering end has the chance to screw things up by selecting a weak key, or to avoid that by checking first." "This is not the same ordinary chance that opponents may happen on the correct key, but is instead an *additional* chance that -- even if the opponents do *not* find the correct key -- the result will be weak *anyway*. This is weakness *beyond* key selection."
2000-06-18 David A. Wagner: "You can never rule out the chance that the attacker gets lucky and guesses your private key correctly. It's simply unavoidable."
2000-06-19 Terry Ritter: "But weak keys bring weakness *without* the attacker guessing. A weak key (an X^2 mod N initial value on a short cycle) is selected by the enciphering end, not the attacker. They are an *additional* weakness, above and beyond the normal attacker guessing."
2000-06-19 Mok-Kong Shen: ". . . for a sequence from a non-linear generator there is normally an initial segment (which could be long) followed by a loop . . . ."
2000-06-19 Mark Wooding: "This doesn't happen in the BBS."
2000-06-19 Terry Ritter: "It can be extremely educational to build some fairly small examples of the generator, and then follow them through, state by state, until all states have been covered."
2000-06-19 Mok-Kong Shen: "It would be fine if someone could show the theoretical underpinning of this."
2000-06-20 Bryan Olson: "If we start at a random point in Z_p*, we get a non-residue 3/4 of the time, and thus a tail of length one. After that we're on the bijective map."
2000-06-20 Mark Wooding: "I earlier stated that, in the multiplicative group of quadratic residues Q_n of the integers mod n, the map x |-> x^2 is bijective."
2000-06-20 Terry Ritter: "Sure. I covered every possible state. That, of course, establishes the distribution encountered when choosing the starting state at random."
2000-06-20 Mok-Kong Shen: "Counter-example: p=3, q=7, n=21."
2000-06-21 Bryan Olson: ". . . it's not in the multiplicative group mod n."
2000-06-21 Mark Wooding: "Whoops! ;-)"
2000-06-20 d g: "If you choose random elements in the *multiplicative* cyclic subgroups and square them, you get a quadratic residue with 4 roots as the poster remarked."
2000-06-21 Doug Kuhlman: "His mistake lies in assuming that GCD(x,p)=1, i.e. that x mod p is distinct from -x mod p."
2000-06-18 Bryan Olson: "That is not how to read a scientific or mathematical paper. To draw conclusions, one must understand the math not count the words."
2000-06-17 Terry Ritter: "Now, did Blum, Blum and Shub simply get carried away with their own math abilities? Shall we assume that they were they so unaware of their first results that they simply did not understand that 2/3 of their work was "useless"?"
2000-06-19 Secret Squirrel: "Short cycles produce factors! That should be the beginning and ending of the discussion. No more is needed."
2000-06-20 Terry Ritter: "If you are willing to call something "proven secure," when the math itself says there is a small, but preventable probability of weakness, you are willing to bend more then I am." "Since the weakness is present, a proper mathematical treatment must reveal it."
2000-06-19 David A. Wagner: "The rest of the research community is also apparently willing to bend more than you are."
2000-06-19 d g: "Could you state what you mean by "provable security"?"
2000-06-20 Terry Ritter: ". . . "proven secure" is well-understood to be the goal of cryptography itself. It is not a term to be usurped and re-defined as something less."
2000-06-21 Klaus Pommerening: "Not even the OTP is secure against any possible attack . . . ."
2000-06-21 Terry Ritter: ". . . every user who cares to, can know, about keys, keyspace, key-guessing and brute force. All that is inherent in the concept of ciphering and applies to any cipher whatsoever. Short cycles, however, are a different kind of weakness."
2000-06-22 Tim Tyler: "It only claims to be as hard to break as factoring the modulus - and nobody really has any idea how hard that is."
2000-06-23 Klaus Pommerening: "This alternative limits the choice of parameters and seeds, so reduces the key space significantly."
2000-06-22 Tim Tyler: "That's not going to appeal very much to managers or marketing."
2000-06-22 David A Molnar: ". . . where has this kind of "provable security" come up in PR or marketing or management decisions?"
2000-06-19 David A. Wagner: "In the computational setting, security is inherently probabilistic."
2000-06-20 Terry Ritter: "The key-guessing issue is a special case because *all* ciphers need keys, and any key might be guessed. That is inherent in the concept of ciphers." "The use of short cycles, however, is *not* inherent, such *use* can be avoided, and it *is* under our control. All that is needed is the will to do it." "The issue is not practical security. The issue is being able to say that we have done all we can." "It is difficult to reconcile "proven secure" with the ability to do more, because if all holes were closed, there would be nothing left to be done."
2000-06-21 Klaus Pommerening: "Factoring the modulus is a much stronger attack than brute force."
2000-06-21 Terry Ritter: "Which, it would seem to me, is an argument for constructions which would tend to reduce the number of states in short cycles, as opposed to just taking what random chance hands us."
2000-06-19 David A. Wagner: "There is no contradiction here."
2000-06-20 Terry Ritter: "The goal of "proven security" is the basis for the entire field of cryptography; it is the need to find a system which is secure against any possible attack. Mathematics being presumably the way to reach such a result, "proven secure" is well-understood to be the goal of cryptography itself. It is not a term to be usurped and re-defined as something less by an academic subfield."
2000-06-20 Trevor L. Jackson, III: "In this particular case one can easily accept the remote possibility of a short BBS cycle because for all practical purposes the risk is negligible. However, the term "provably secure" applies in theory, not in practice. It rules out the possibility, no matter how remote, of any weakness. Thus it is an error to assert that unfiltered BBS systems are "provably secure", just as it is (*) an error to assert that filtering is required for practical security."
2000-06-20 Klaus Pommerening: "So what do you think of RSA? There you also have short cycles, and you can't avoid them . . . ."
2000-06-20 Tony T. Warnock: "It's not that RSA, etc. are not secure but that the BBS generator using all the BBS bells and whistles can be proven secure."
2000-06-20 Mark Wooding: "But the BBS generator, without the bells and whistles, can be proven secure under exactly the same assumptions, in particular that factoring is hard. The cycling behaviour in question contradicts the assumption, but that doesn't invalidate the proof."
2000-06-20 Terry Ritter: "If the assumption is contradicted, surely we cannot say the proof stands." [Ed. Note: Obviously, I missed the point.]
2000-06-21 Mark Wooding: "What the foregoing doesn't go into is that finding short cycles might be a sensible way to go about factoring."
2000-06-21 Terry Ritter: "I think we have shown the assumption false, or at least that it does not hold unconditionally, as stated."
2000-06-22 Mark Wooding: "The hypothesis stands and the assumption fails; thus, we conclude that the adversary cannot find short cycles." "From my point of view, it doesn't matter if we actually *use* a short cycle, just whether an adversary can find one, given the modulus on a silver platter."
2000-06-20 David A. Wagner: "BBS can be proven secure if you include all the bells and whistles. Or, it can also be proven secure if omit the bells and whistles."
2000-06-20 Terry Ritter: "* We *cannot* build a cipher which avoids key-guessing." "* We *can* build a generator which does not use short cycles." "I would say a distinction exists."
2000-06-21 Klaus Pommerening: "Is there any known result that some choice of parameters in BBS guarantees that the LSBs don't give short cycles?"
2000-06-21 Terry Ritter: "Not that I know of. I never even thought of investigating such a thing on my small models. I guess I assumed that sort of thing was exactly what the proofs guaranteed."
2000-06-21 Mok-Kong Shen: "I once also thought of that issue. But since I wasn't able to well understand the original paper, I took it for granted that others who have studied BBS have checked the point."
2000-06-21 Tim Tyler: "Since n = p * q (product of two primes), the /only/ way the lowest bit could exhibit a cycle (of length c) smaller than min(p,q) would be if it was always 0, or always 1."
2000-06-22 Mok-Kong Shen: "A counter-example to your claim: p=7, q=11, n=77. There is a cycle 4,16,25,9, giving rise to the period of the lowest bit 0011, i.e. a period length of 4<7."
2000-06-21 David A. Wagner: ". . . since the LSBs are indistinguishable from random bits (assuming factoring is hard), the LSBs have no better chance of cycling than random bits would."
2000-06-20 lcs Mixmaster Remailer: "You cannot consistently advise people to choose special moduli for BBS without advising them to choose those same moduli for RSA."
2000-06-20 Terry Ritter: "I have said many times that eliminating the use of rare short cycles is not necessary in practice. But eliminating the use of short cycles *is* necessary if we are to claim with a straight face that the system is as secure as it can be made to be. The existence of a known preventable weakness is an abomination in a cipher. Trying to sweep that under the rug of a technical definition is just hiding the truth."
2000-06-20 lcs Mixmaster Remailer: "BBS is as secure as factoring (actually quadratic reciprocity). That's all the BBS paper claims. They never said that the RNG was "secure against any possible attack"."

Subject: small subgroups in Blum Blum Shub
Date: Wed, 14 Jun 2000 21:10:44 GMT
From: sarnold_intertrust@my-deja.com
Message-ID: <8i8sc4$h3n$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 24

Greetings.

Another question --- When playing around with Blum Blum Shub, using
small primes, I noticed very short cycles before repetition.

As an example, using 7 and 11 as the prime factors, feed it 6: 6 --> 36
--> 64 --> 15 --> 71 --> 36 ... That is three cycles. Using 11 and 31
(341) feed it 6: 6 --> 36 --> 237 --> 191 --> 335 --> 36 ... That is
four cycles.

While I realize larger primes will lead to larger cycles, it seems to me
that an attacker patient enough to wait for a cycle could easily guess
forthcoming and some previous bits.

Are there any papers floating around that describe the behavior of these
subgroups [is that correct terminology? :] to allow for risk analysis?
How long will an attacker have to wait to see repetition from the bits
given 'n' bits in the modulus?

Thanks. ;)

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 01:33:38 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <39481651.B239A66F@t-online.de>
References: <8i8sc4$h3n$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 14

sarnold_intertrust@my-deja.com wrote:

> Another question --- When playing around with Blum Blum Shub, using
> small primes, I noticed very short cycles before repetition.

The issue was discussed in the group some time back. You may like
to read Terry Ritter's article:

      http://www.io.com/~ritter/ARTS/CRNG2ART.HTML

M. K. Shen

Bytes: 801

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 14 Jun 2000 18:08:23 -0700
From: lordcow77 <london222NOloSPAM@netzero.com.invalid>
Message-ID: <02500a92.964f4485@usw-ex0105-036.remarq.com>
References: <8i8sc4$h3n$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 14

Essentially, the existence of exploitable cycles in BBS would
neccesarily lead to an efficient algorithm for decomposing RSA
moduli into primes. As such, if you believe that the factoring
of numbers in that range is a difficult problem, you need not
loose sleep over the miniscule probability that you will land in
a short cycle. The nonsense about choosing "strong primes" or
good initialization values is a remnant to the past where it was
thought that a relatively small prime (if well chosen) would be
adaquately strong. These days (thanks to the NFS and related
algorithms), everybody should use large moduli as a matter of
course.

* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 01:39:29 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <39483384.2820636@news.io.com>
References: <02500a92.964f4485@usw-ex0105-036.remarq.com>
Newsgroups: sci.crypt
Lines: 38

On Wed, 14 Jun 2000 18:08:23 -0700, in
<02500a92.964f4485@usw-ex0105-036.remarq.com>, in sci.crypt lordcow77
<london222NOloSPAM@netzero.com.invalid> wrote:

>Essentially, the existence of exploitable cycles in BBS would
>neccesarily lead to an efficient algorithm for decomposing RSA
>moduli into primes. As such, if you believe that the factoring
>of numbers in that range is a difficult problem, you need not
>loose sleep over the miniscule probability that you will land in
>a short cycle. The nonsense about choosing "strong primes" or
>good initialization values is a remnant to the past where it was
>thought that a relatively small prime (if well chosen) would be
>adaquately strong. 

I think your interpretation is wrong, and I recommend the BB&S paper
to you: 

Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random
Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
Plenum Press: New York. 61-78. 

BB&S did expect large primes; the requirement for "special" primes was
to guarantee that the system had cycles of some long, known and
computable length.  The existence of cycles of known length made it
possible to efficiently check that any particular initial value x0 was
on such a cycle, and to choose another x0 if not.  Short cycles
certainly do exist in BB&S, and short cycles are "exploitable."  The
selection procedure thus eliminates the possibility that x0 is on a
short cycle, and so provides a *guarantee* of that form of strength.
That sort of a *guarantee* is simply not present when we just choose
x0 at random and hope for the best, even if x0 is very, very likely to
be on a long cycle.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 14 Jun 2000 23:56:51 -0400
From: Nicol So <nobody@no.spam.please>
Message-ID: <39485403.A0C7153D@no.spam.please>
References: <39483384.2820636@news.io.com>
Newsgroups: sci.crypt
Lines: 50

Terry Ritter wrote:
> 
> On Wed, 14 Jun 2000 18:08:23 -0700, in
> <02500a92.964f4485@usw-ex0105-036.remarq.com>, in sci.crypt lordcow77
> <london222NOloSPAM@netzero.com.invalid> wrote:
> 
> >Essentially, the existence of exploitable cycles in BBS would
> >neccesarily lead to an efficient algorithm for decomposing RSA
> >moduli into primes. As such, if you believe that the factoring
> >of numbers in that range is a difficult problem, you need not
> >loose sleep over the miniscule probability that you will land in
> >a short cycle. The nonsense about choosing "strong primes" or
> >good initialization values is a remnant to the past where it was
> >thought that a relatively small prime (if well chosen) would be
> >adaquately strong.
> 
> I think your interpretation is wrong, and I recommend the BB&S paper
> to you:
> 
> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random
> Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
> Plenum Press: New York. 61-78.
> 
> BB&S did expect large primes; the requirement for "special" primes was
> to guarantee that the system had cycles of some long, known and
> computable length.  The existence of cycles of known length made it
> possible to efficiently check that any particular initial value x0 was
> on such a cycle, and to choose another x0 if not.  Short cycles
> certainly do exist in BB&S, and short cycles are "exploitable."  The
> selection procedure thus eliminates the possibility that x0 is on a
> short cycle, and so provides a *guarantee* of that form of strength.
> That sort of a *guarantee* is simply not present when we just choose
> x0 at random and hope for the best, even if x0 is very, very likely to
> be on a long cycle.

lordcow77's interpretation is correct. The safety of using randomly
chosen primes of appropriate sizes is built into the underlying
intractability assumption. To put things in perspective, the whole point
of using cryptography is to reduce the probability of "bad things
happening" to some acceptably low level, say 2^{-L} for some
sufficiently large L. (There's no defense against dumb luck on the part
of the adversary). Not using special primes may affect the value of L
for a given choice of security parameter (so you may have to adjust your
security parameter), but it does not affect the asymptotic behavior of
security as a function of the security parameter.

-- 
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.

Bytes: 3215

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 14 Jun 2000 21:06:01 -0700
From: tomstd <tomNOtoSPAM@dasoft.org.invalid>
Message-ID: <0572ef05.5d8f9734@usw-ex0104-032.remarq.com>
References: <39485403.A0C7153D@no.spam.please>
Newsgroups: sci.crypt
Lines: 95

In article <39485403.A0C7153D@no.spam.please>, Nicol So
<nobody@no.spam.please> wrote:
>Terry Ritter wrote:
>>
>> On Wed, 14 Jun 2000 18:08:23 -0700, in
>> <02500a92.964f4485@usw-ex0105-036.remarq.com>, in sci.crypt
lordcow77
>> <london222NOloSPAM@netzero.com.invalid> wrote:
>>
>> >Essentially, the existence of exploitable cycles in BBS would
>> >neccesarily lead to an efficient algorithm for decomposing
RSA
>> >moduli into primes. As such, if you believe that the
factoring
>> >of numbers in that range is a difficult problem, you need not
>> >loose sleep over the miniscule probability that you will
land in
>> >a short cycle. The nonsense about choosing "strong primes" or
>> >good initialization values is a remnant to the past where it
was
>> >thought that a relatively small prime (if well chosen) would
be
>> >adaquately strong.
>>
>> I think your interpretation is wrong, and I recommend the
BB&S paper
>> to you:
>>
>> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-
Random
>> Number Generators. Advances in Cryptology: CRYPTO '82
Proceedings.
>> Plenum Press: New York. 61-78.
>>
>> BB&S did expect large primes; the requirement for "special"
primes was
>> to guarantee that the system had cycles of some long, known
and
>> computable length.  The existence of cycles of known length
made it
>> possible to efficiently check that any particular initial
value x0 was
>> on such a cycle, and to choose another x0 if not.  Short
cycles
>> certainly do exist in BB&S, and short cycles
are "exploitable."  The
>> selection procedure thus eliminates the possibility that x0
is on a
>> short cycle, and so provides a *guarantee* of that form of
strength.
>> That sort of a *guarantee* is simply not present when we just
choose
>> x0 at random and hope for the best, even if x0 is very, very
likely to
>> be on a long cycle.
>
>lordcow77's interpretation is correct. The safety of using
randomly
>chosen primes of appropriate sizes is built into the underlying
>intractability assumption. To put things in perspective, the
whole point
>of using cryptography is to reduce the probability of "bad
things
>happening" to some acceptably low level, say 2^{-L} for some
>sufficiently large L. (There's no defense against dumb luck on
the part
>of the adversary). Not using special primes may affect the
value of L
>for a given choice of security parameter (so you may have to
adjust your
>security parameter), but it does not affect the asymptotic
behavior of
>security as a function of the security parameter.

I don't know why people still consider the BBS generator.  It's
not very safe.

Let's ask some questions:

1.  How do you use it?  Well construct "special" primes and use
a relatively prime root.  I have seen to use 3 mod 4 primes and
p- strong primes...

2.  What is the period?  Gosh-geez I dunno, pretty darn big!

3.  How fast is it?  Well at 2kb/sec we now have the fastest
prng.

Woopy.  It's hard to use, big and slow.  BAD IDEA!

Tom

* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 00:56:45 -0400
From: Nicol So <nobody@no.spam.please>
Message-ID: <3948620D.FDB99075@no.spam.please>
References: <0572ef05.5d8f9734@usw-ex0104-032.remarq.com>
Newsgroups: sci.crypt
Lines: 39

tomstd wrote:
> 
> I don't know why people still consider the BBS generator.  It's
> not very safe.

I'm not aware of any real-life application that uses it. I think the BBS
generator is mostly of theoretical interest only. It is interesting
because it has some well-understood properties--for exmaple, its
security is (demonstrably) reducible to a well-known intractability
assumption.

On what basis did you come to the conclusion that it is "not very safe"?

> Let's ask some questions:
> 
> 1.  How do you use it?  Well construct "special" primes and use
> a relatively prime root.  I have seen to use 3 mod 4 primes and
> p- strong primes...
> 
> 2.  What is the period?  Gosh-geez I dunno, pretty darn big!

The overwhelming probability that a randomly chosen element will fall on
a long cycle is an automatic consequence of the underlying
intractability assumption, if you accept it. (If you don't, the security
proof is just another interesting intellectual exercise).

> 3.  How fast is it?  Well at 2kb/sec we now have the fastest
> prng.
> 
> Woopy.  It's hard to use, big and slow.  BAD IDEA!

You may dislike the BBS generator for its inefficiency, but how many
*rigorous* analytic results can you find about the behavior/security of
actually deployed PRNG's can you find?

-- 
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 14:50:27 -0500
From: James Felling <james.felling@mail.arcanelogic.com>
Message-ID: <39493383.8ABBF402@mail.arcanelogic.com>
References: <0572ef05.5d8f9734@usw-ex0104-032.remarq.com>
Newsgroups: sci.crypt
Lines: 106

tomstd wrote:

> In article <39485403.A0C7153D@no.spam.please>, Nicol So
> <nobody@no.spam.please> wrote:
> >Terry Ritter wrote:
> >>
> >> On Wed, 14 Jun 2000 18:08:23 -0700, in
> >> <02500a92.964f4485@usw-ex0105-036.remarq.com>, in sci.crypt
> lordcow77
> >> <london222NOloSPAM@netzero.com.invalid> wrote:
> >>
> >> >Essentially, the existence of exploitable cycles in BBS would
> >> >neccesarily lead to an efficient algorithm for decomposing
> RSA
> >> >moduli into primes. As such, if you believe that the
> factoring
> >> >of numbers in that range is a difficult problem, you need not
> >> >loose sleep over the miniscule probability that you will
> land in
> >> >a short cycle. The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it
> was
> >> >thought that a relatively small prime (if well chosen) would
> be
> >> >adaquately strong.
> >>
> >> I think your interpretation is wrong, and I recommend the
> BB&S paper
> >> to you:
> >>
> >> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-
> Random
> >> Number Generators. Advances in Cryptology: CRYPTO '82
> Proceedings.
> >> Plenum Press: New York. 61-78.
> >>
> >> BB&S did expect large primes; the requirement for "special"
> primes was
> >> to guarantee that the system had cycles of some long, known
> and
> >> computable length.  The existence of cycles of known length
> made it
> >> possible to efficiently check that any particular initial
> value x0 was
> >> on such a cycle, and to choose another x0 if not.  Short
> cycles
> >> certainly do exist in BB&S, and short cycles
> are "exploitable."  The
> >> selection procedure thus eliminates the possibility that x0
> is on a
> >> short cycle, and so provides a *guarantee* of that form of
> strength.
> >> That sort of a *guarantee* is simply not present when we just
> choose
> >> x0 at random and hope for the best, even if x0 is very, very
> likely to
> >> be on a long cycle.
> >
> >lordcow77's interpretation is correct. The safety of using
> randomly
> >chosen primes of appropriate sizes is built into the underlying
> >intractability assumption. To put things in perspective, the
> whole point
> >of using cryptography is to reduce the probability of "bad
> things
> >happening" to some acceptably low level, say 2^{-L} for some
> >sufficiently large L. (There's no defense against dumb luck on
> the part
> >of the adversary). Not using special primes may affect the
> value of L
> >for a given choice of security parameter (so you may have to
> adjust your
> >security parameter), but it does not affect the asymptotic
> behavior of
> >security as a function of the security parameter.
>
> I don't know why people still consider the BBS generator.  It's
> not very safe.
>
> Let's ask some questions:
>
> 1.  How do you use it?  Well construct "special" primes and use
> a relatively prime root.  I have seen to use 3 mod 4 primes and
> p- strong primes...
>
> 2.  What is the period?  Gosh-geez I dunno, pretty darn big!
>
> 3.  How fast is it?  Well at 2kb/sec we now have the fastest
> prng.
>
> Woopy.  It's hard to use, big and slow.  BAD IDEA!
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!

Yes, it is big, ugly and slow. OTOH it is provably as good as the underlying
intractible problem, and it is one of the only PRNG's with that property.

Given we want something PROVABLY difficult to attack with a long period, it
really is the only game in town. Sure it isn't a great game, but its all that is
available.

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 05:32:53 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <39486a4b.3228899@news.io.com>
References: <39485403.A0C7153D@no.spam.please>
Newsgroups: sci.crypt
Lines: 85

On Wed, 14 Jun 2000 23:56:51 -0400, in
<39485403.A0C7153D@no.spam.please>, in sci.crypt Nicol So
<nobody@no.spam.please> wrote:

>Terry Ritter wrote:
>> 
>> On Wed, 14 Jun 2000 18:08:23 -0700, in
>> <02500a92.964f4485@usw-ex0105-036.remarq.com>, in sci.crypt lordcow77
>> <london222NOloSPAM@netzero.com.invalid> wrote:
>> 
>> >Essentially, the existence of exploitable cycles in BBS would
>> >neccesarily lead to an efficient algorithm for decomposing RSA
>> >moduli into primes. As such, if you believe that the factoring
>> >of numbers in that range is a difficult problem, you need not
>> >loose sleep over the miniscule probability that you will land in
>> >a short cycle. The nonsense about choosing "strong primes" or
>> >good initialization values is a remnant to the past where it was
>> >thought that a relatively small prime (if well chosen) would be
>> >adaquately strong.
>> 
>> I think your interpretation is wrong, and I recommend the BB&S paper
>> to you:
>> 
>> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random
>> Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
>> Plenum Press: New York. 61-78.
>> 
>> BB&S did expect large primes; the requirement for "special" primes was
>> to guarantee that the system had cycles of some long, known and
>> computable length.  The existence of cycles of known length made it
>> possible to efficiently check that any particular initial value x0 was
>> on such a cycle, and to choose another x0 if not.  Short cycles
>> certainly do exist in BB&S, and short cycles are "exploitable."  The
>> selection procedure thus eliminates the possibility that x0 is on a
>> short cycle, and so provides a *guarantee* of that form of strength.
>> That sort of a *guarantee* is simply not present when we just choose
>> x0 at random and hope for the best, even if x0 is very, very likely to
>> be on a long cycle.
>
>lordcow77's interpretation is correct. The safety of using randomly
>chosen primes of appropriate sizes is built into the underlying
>intractability assumption. To put things in perspective, the whole point
>of using cryptography is to reduce the probability of "bad things
>happening" to some acceptably low level, say 2^{-L} for some
>sufficiently large L. (There's no defense against dumb luck on the part
>of the adversary). Not using special primes may affect the value of L
>for a given choice of security parameter (so you may have to adjust your
>security parameter), but it does not affect the asymptotic behavior of
>security as a function of the security parameter.

"To put things in perspective," I suggest you try to follow my
reasoning before trying to refute it.  

As you would have seen had you actually read and understood my
comments, the statement in question was:

>> >The nonsense about choosing "strong primes" or
>> >good initialization values is a remnant to the past where it was
>> >thought that a relatively small prime (if well chosen) would be
>> >adaquately strong.

And that is nonsense.  I am unaware of any such "thoughts."  Exactly
where do you disagree, and what is your evidence?  

On the other hand, the larger question of X^2 mod N security (not part
of my earlier comments) is swept under your asymptotic rug.  But real
systems are *not* asymptotic.  All real BB&S systems *do* have short
cycles.  And short cycles *are* weak.  Yes, it is unlikely to select a
short cycle at random.  But unless the BB&S prescriptions are
followed, that is *only* "unlikely" and *not* "impossible."  In
contrast, the BB&S prescriptions *guarantee* that one does not use a
short cycle, and that is a qualitative difference.  

As I see it, the issue is *not* strength in practice, it is instead
the claim to have a provably secure system.  I think we can accept
that all cryptography is vulnerable to opponents choosing the right
key at random.  But I claim that no system can be provably secure if
it includes the possibility of selecting and using weakness, no matter
how small that possibility may be.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 17:47:48 GMT
From: sarnold_intertrust@my-deja.com
Message-ID: <8ib4rs$5tr$1@nnrp1.deja.com>
References: <39486a4b.3228899@news.io.com>
Newsgroups: sci.crypt
Lines: 31

In article <39486a4b.3228899@news.io.com>,
  ritter@io.com (Terry Ritter) wrote:

> >> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two
> >> Pseudo-Random Number Generators. Advances in Cryptology:
> >> CRYPTO '82 Proceedings. Plenum Press: New York. 61-78.

Does anyone know an electronically available source for this paper?

Ok.I learned an important lesson --- Bruce might be good, but he doesn't
have the space nor the time in his books to completely cover material.
Relying on the one source is a Bad Idea.

Terry, thank you for the wonderful resources on your web page.

So, now, back to square one; BB&S had the property of being 'indexable'
such that one could request a particular output. I would very much like
to keep this property. Are there any other PRNGs available with this
property?

My current thinking is to use an HMAC construction to generate these
things. By using a key with an 'index' being simply tossed into HMAC
as-is, my gut feeling tells me I can get reasonably random-looking
numbers out of it, with low ability to predict from a lot of known
outputs to another output (thanks to our key).

Have I missed something similarly blatant with this construction?

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: Fri, 16 Jun 2000 22:19:07 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <Fw9pzv.HvG@bath.ac.uk>
References: <8ib4rs$5tr$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 15

sarnold_intertrust@my-deja.com wrote:
:   ritter@io.com (Terry Ritter) wrote:

: So, now, back to square one; BB&S had the property of being 'indexable'
: such that one could request a particular output. I would very much like
: to keep this property. Are there any other PRNGs available with this
: property?

Yes.  All completely "linear" systems have this property - e.g. an LFSR.

Also RNGs based on hashes, MACs or cyphers driven by counters offer random
access capability.
-- 
__________  Lotus Artificial Life  http://alife.co.uk/  tt@cryogen.com
 |im |yler  The Mandala Centre   http://mandala.co.uk/  The end.

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 22:31:48 -0400
From: Nicol So <nobody@no.spam.please>
Message-ID: <39499194.60C6D640@no.spam.please>
References: <39486a4b.3228899@news.io.com>
Newsgroups: sci.crypt
Lines: 65

Terry Ritter wrote:
> 
> "To put things in perspective," I suggest you try to follow my
> reasoning before trying to refute it.

My comment was directed at that of lordcow77, not yours. Refuting your
reasoning was not my intent.

As I wrote in another message, I think BBS is mainly of theorectical
interests only. I stand by my assertion that asymptotically, it doesn't
matter much whether you choose special primes--the advantage that an
adversary can correctly predict the output of a BBS generator will not
change from "negligible" to "non-negligible".

> As you would have seen had you actually read and understood my
> comments, the statement in question was:
> 
> >> >The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it was
> >> >thought that a relatively small prime (if well chosen) would be
> >> >adaquately strong.

That's not the part I was commenting on when I said lordcow77's
interpretation was correct. I have no comment on the text quoted above.

> On the other hand, the larger question of X^2 mod N security (not part
> of my earlier comments) is swept under your asymptotic rug.  But real
> systems are *not* asymptotic.  All real BB&S systems *do* have short
> cycles.  And short cycles *are* weak.  Yes, it is unlikely to select a
> short cycle at random.  But unless the BB&S prescriptions are
> followed, that is *only* "unlikely" and *not* "impossible."  In
> contrast, the BB&S prescriptions *guarantee* that one does not use a
> short cycle, and that is a qualitative difference.

OK, choosing special primes eliminates one particular weakness that
occurs with negligible probability. Are you sure BBS has no other
weaknesses that occur with negligible probability?

> As I see it, the issue is *not* strength in practice, it is instead
> the claim to have a provably secure system.  I think we can accept
> that all cryptography is vulnerable to opponents choosing the right
> key at random.  But I claim that no system can be provably secure if
> it includes the possibility of selecting and using weakness, no matter
> how small that possibility may be.

You're certainly entitled to have your own criteria for security, but
the one you have (as suggested by your last sentence) is not what
theoretical computer scientists use.

[Philosophy is a highly personal thing and can be a source of endless
debates. The following is intended for people who care to know mine. For
practical security, irrational worries about threats that occur with
extremely low probability go against the rational risk management
approach to security advocated by pretty much all authors I've read who
do security engineering/administration for a living. No organization has
the resources to defend against all *conceivable* threats. At some
point, irrational worries about extremely unlikely threats must be
controlled and paranoia must be kept in check. Obsession with
unrealistic threats can cause resources to be directed away from where
they can be profitably expended to defend against more serious threats.]

-- 
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.

Subject: Re: small subgroups in Blum Blum Shub
Date: Fri, 16 Jun 2000 03:03:41 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8ic5ed$tbq$1@nnrp1.deja.com>
References: <39486a4b.3228899@news.io.com>
Newsgroups: sci.crypt
Lines: 112

Terry Ritter wrote:
>
> Nicol So
>
> >Terry Ritter wrote:
> >>
> >> lordcow77
> >> >Essentially, the existence of exploitable cycles in BBS would
> >> >neccesarily lead to an efficient algorithm for decomposing RSA
> >> >moduli into primes. As such, if you believe that the factoring
> >> >of numbers in that range is a difficult problem, you need not
> >> >loose sleep over the miniscule probability that you will land in
> >> >a short cycle. The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it was
> >> >thought that a relatively small prime (if well chosen) would be
> >> >adaquately strong.
> >>
> >> I think your interpretation is wrong, and I recommend the BB&S
paper
> >> to you:
> >>
> >> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two
Pseudo-Random
> >> Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
> >> Plenum Press: New York. 61-78.
[...]
> >lordcow77's interpretation is correct. The safety of using randomly
> >chosen primes of appropriate sizes is built into the underlying
> >intractability assumption. To put things in perspective, the whole
point
> >of using cryptography is to reduce the probability of "bad things
> >happening" to some acceptably low level, say 2^{-L} for some
> >sufficiently large L. (There's no defense against dumb luck on the
part
> >of the adversary). Not using special primes may affect the value of L
> >for a given choice of security parameter (so you may have to adjust
your
> >security parameter), but it does not affect the asymptotic behavior
of
> >security as a function of the security parameter.
>
> "To put things in perspective," I suggest you try to follow my
> reasoning before trying to refute it.

I think you didn't understand lordcow77's or Nicol So's
reasoning.  There's is correct.  The long-cycle analysis in
the BBS paper is interesting but not the major result.

> As you would have seen had you actually read and understood my
> comments, the statement in question was:
>
> >> >The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it was
> >> >thought that a relatively small prime (if well chosen) would be
> >> >adaquately strong.
>
> And that is nonsense.  I am unaware of any such "thoughts."  Exactly
> where do you disagree, and what is your evidence?

You are unaware of the refutation of the notion of "strong
primes" for factorization-based systems?  The logic here is
the same: we do not worry about special cases, other than to
choose our keys so that they are of negligible probability.

The disagreement was explained.  Falling into a short cycle
from a random starting point is no more likely than falling
into a factorization. The major result of the BBS paper is
that prediction of the sequence is intractable under the
assumption that factoring the modulus is also intractable.

> On the other hand, the larger question of X^2 mod N security (not part
> of my earlier comments) is swept under your asymptotic rug.  But real
> systems are *not* asymptotic.  All real BB&S systems *do* have short
> cycles.  And short cycles *are* weak.  Yes, it is unlikely to select a
> short cycle at random.  But unless the BB&S prescriptions are
> followed, that is *only* "unlikely" and *not* "impossible."  In
> contrast, the BB&S prescriptions *guarantee* that one does not use a
> short cycle, and that is a qualitative difference.

Users of a broken system don't care if the system was broken
by calculating the state or finding a cycle.  We cannot
reduce the chance of failure to zero, so we settle for
vanishingly unlikely.  The weakest point in the "proof" of
security is of course the assumption of the intractability
of factoring.

> As I see it, the issue is *not* strength in practice, it is instead
> the claim to have a provably secure system.  I think we can accept
> that all cryptography is vulnerable to opponents choosing the right
> key at random.  But I claim that no system can be provably secure if
> it includes the possibility of selecting and using weakness, no matter
> how small that possibility may be.

Nonsense.  Any individual key or small set of keys is weak.
If we accept the danger of the key-guessing attack, then
dumb luck ensures that we will use a system the attacker can
break with some vanishingly small probability.

If we cannot tolerate any chance of "using weakness, no
matter how small", then we must join the newbies who object
to the one-time pad on the grounds that a truly random pad
*might* be all zero.

--Bryan
--
email: bolson at certicom dot com

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: Sat, 17 Jun 2000 00:22:47 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8iegcg$hmg$1@nnrp1.deja.com>
References: <39486a4b.3228899@news.io.com>
Newsgroups: sci.crypt
Lines: 114

Terry Ritter wrote:
>
> Nicol So
>
> >Terry Ritter wrote:
> >>
> >> lordcow77
> >> >Essentially, the existence of exploitable cycles in BBS would
> >> >neccesarily lead to an efficient algorithm for decomposing RSA
> >> >moduli into primes. As such, if you believe that the factoring
> >> >of numbers in that range is a difficult problem, you need not
> >> >loose sleep over the miniscule probability that you will land in
> >> >a short cycle. The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it was
> >> >thought that a relatively small prime (if well chosen) would be
> >> >adaquately strong.
> >>
> >> I think your interpretation is wrong, and I recommend the BB&S
paper
> >> to you:
> >>
> >> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two
Pseudo-Random
> >> Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
> >> Plenum Press: New York. 61-78.
[...]
> >lordcow77's interpretation is correct. The safety of using randomly
> >chosen primes of appropriate sizes is built into the underlying
> >intractability assumption. To put things in perspective, the whole
point
> >of using cryptography is to reduce the probability of "bad things
> >happening" to some acceptably low level, say 2^{-L} for some
> >sufficiently large L. (There's no defense against dumb luck on the
part
> >of the adversary). Not using special primes may affect the value of L
> >for a given choice of security parameter (so you may have to adjust
your
> >security parameter), but it does not affect the asymptotic behavior
of
> >security as a function of the security parameter.
>
> "To put things in perspective," I suggest you try to follow my
> reasoning before trying to refute it.

I think you didn't understand lordcow77's or Nicol So's
reasoning.  They are correct.  The long-cycle analysis in
the BBS paper is interesting but not the major result.

> As you would have seen had you actually read and understood my
> comments, the statement in question was:
>
> >> >The nonsense about choosing "strong primes" or
> >> >good initialization values is a remnant to the past where it was
> >> >thought that a relatively small prime (if well chosen) would be
> >> >adaquately strong.
>
> And that is nonsense.  I am unaware of any such "thoughts."  Exactly
> where do you disagree, and what is your evidence?

You are unaware of the refutation of the notion of "strong
primes" for factorization-based systems?  The logic here is
the same: we do not worry about special cases, other than to
choose our keys so that they are of negligible probability.

Falling into a short cycle from a random starting point is
no more likely than falling into a factorization. The major
result of the BBS paper is that prediction of the sequence
is intractable under the assumption that factoring the
modulus is also intractable.

> On the other hand, the larger question of X^2 mod N security (not part
> of my earlier comments) is swept under your asymptotic rug.  But real
> systems are *not* asymptotic.  All real BB&S systems *do* have short
> cycles.  And short cycles *are* weak.  Yes, it is unlikely to select a
> short cycle at random.  But unless the BB&S prescriptions are
> followed, that is *only* "unlikely" and *not* "impossible."  In
> contrast, the BB&S prescriptions *guarantee* that one does not use a
> short cycle, and that is a qualitative difference.

Users of a broken system don't care if the system was broken
by calculating the state or finding a cycle.  We cannot
reduce the chance of failure to zero, so we settle for
vanishingly unlikely.

On a different issue, the weakest point in the "proof" of
security is of course the assumption of the intractability
of factoring.

> As I see it, the issue is *not* strength in practice, it is instead
> the claim to have a provably secure system.  I think we can accept
> that all cryptography is vulnerable to opponents choosing the right
> key at random.  But I claim that no system can be provably secure if
> it includes the possibility of selecting and using weakness, no matter
> how small that possibility may be.

That's a misunderstanding of the consequent of the proof.
BBS does not provide a proof of a secure system in that
sense whether one filters for cycle length or not.

If we cannot tolerate any chance of "using weakness, no
matter how small", then we must join the newbies who object
to the one-time pad on the grounds that a truly random pad
*might* be all zero.

--Bryan
--
email: bolson at certicom dot com

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 16:09:44 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <Fw7E88.GJF@bath.ac.uk>
References: <02500a92.964f4485@usw-ex0105-036.remarq.com>
Newsgroups: sci.crypt
Lines: 22

lordcow77 <london222NOloSPAM@netzero.com.invalid> wrote:

: Essentially, the existence of exploitable cycles in BBS would
: neccesarily lead to an efficient algorithm for decomposing RSA
: moduli into primes. As such, if you believe that the factoring
: of numbers in that range is a difficult problem, you need not
: loose sleep over the miniscule probability that you will land in
: a short cycle. [...]

It's not a simply a case of losing sleep - it's a case of knowing
whether your system is secure.

Short cycles are weak and insecure - no matter what the probability of
their arising is.

If you're using a system with short cycles in it, do you lose sleep over it?

That depends on the relationship of the chance of such cycles arising and
how much the privacy of your data is worth to you.
-- 
__________  Lotus Artificial Life  http://alife.co.uk/  tt@cryogen.com
 |im |yler  The Mandala Centre   http://mandala.co.uk/  Goodbye cool world.

Subject: Re: small subgroups in Blum Blum Shub
Date: Fri, 16 Jun 2000 04:24:02 +0100
From: David Hopwood <hopwood@zetnet.co.uk>
Message-ID: <39499DD2.3E39F0F7@zetnet.co.uk>
References: <Fw7E88.GJF@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 61

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

Tim Tyler wrote:
> lordcow77 <london222NOloSPAM@netzero.com.invalid> wrote:
> 
> : Essentially, the existence of exploitable cycles in BBS would
> : neccesarily lead to an efficient algorithm for decomposing RSA
> : moduli into primes. As such, if you believe that the factoring
> : of numbers in that range is a difficult problem, you need not
> : loose sleep over the miniscule probability that you will land in
> : a short cycle. [...]
> 
> It's not a simply a case of losing sleep - it's a case of knowing
> whether your system is secure.
> 
> Short cycles are weak and insecure - no matter what the probability of
> their arising is.

AFAICS from Theorem 4 of the BBS paper, lordcow77's argument is correct.
That theorem shows that breaking the BBS generator is as hard as factoring
N = pq even if the only constraints are that p and q are congruent to
3 mod 4 and x_0 is a quadratic residue, regardless of what the cycle
length is.

> If you're using a system with short cycles in it, do you lose sleep
> over it?

Not if the probability of it having a short cycle is no greater than
the probability of a randomly generated RSA modulus being easily
factorable. Any cryptosystem based on factoring will have weak keys
(that occur with negligable probability for large enough moduli);
the constraints given in Theorem 6 of the BBS paper only eliminate one
category of them.

> That depends on the relationship of the chance of such cycles arising
> and how much the privacy of your data is worth to you.

If you trust integer factorisation-based cryptosystems at all, you
are implicitly trusting that the chance of such cycles arising is
negligable.

- -- 
David Hopwood <hopwood@zetnet.co.uk>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01

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

iQEVAwUBOUmdhjkCAxeYt5gVAQHlIwf+IOZR/MD3SnmJ6OenztFZ+qYv8/CG+RFr
1OsMC8WPy3KWS3YBM0eIMoozJlq7Y6CWjOd3LRZGKXfV2K2d5YElfSsfQdvXc6k9
bVYUSdYhg1tqPBgppOEFnv4rM/TRjR857+Rm+MUc3cJCr7DIWz4xFq6oPs5pn/JI
Xa7chB/4rczna0sssEFgU1/KCLYs46s1ZnwWC//iIIo34tMRyogXlYmK0xzY06a3
SwU+Q8/yATkx0UY6e0J8nNovuHyoAKvU6zN1xFZkVFYBdqfTmlArtl69OKaVNRN1
C6iL5qK85kLs2a1vrDDHjsQDV1KeF/8ZHJazNNZfkxF/Mhp9xV/U1g==
=w3b6
-----END PGP SIGNATURE-----

Subject: Re: small subgroups in Blum Blum Shub
Date: Fri, 16 Jun 2000 17:13:09 GMT
From: sarnold_intertrust@my-deja.com
Message-ID: <8idn6h$vvf$1@nnrp1.deja.com>
References: <39499DD2.3E39F0F7@zetnet.co.uk>
Newsgroups: sci.crypt
Lines: 18

In article <39499DD2.3E39F0F7@zetnet.co.uk>,
  hopwood@zetnet.co.uk wrote:
> AFAICS from Theorem 4 of the BBS paper, lordcow77's argument
> is correct. That theorem shows that breaking the BBS generator
> is as hard as factoring N = pq even if the only constraints
> are that p and q are congruent to 3 mod 4 and x_0 is a
> quadratic residue, regardless of what the cycle length is.

Please define "breaking". :) To me, being able to guess the upcoming
bits with probability 1 because you already saw them earlier in the
cycle, *that* spells "broke". I don't know how I would go backwards from
knowing the sequence to knowing the factorization, but I do know I could
guess upcoming bits quite easily. :)

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: Fri, 23 Jun 2000 01:54:15 +0100
From: David Hopwood <hopwood@zetnet.co.uk>
Message-ID: <3952B536.3FB770AE@zetnet.co.uk>
References: <39499DD2.3E39F0F7@zetnet.co.uk>
Newsgroups: sci.crypt
Lines: 54

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

David Hopwood wrote:
> Tim Tyler wrote:
> > lordcow77 <london222NOloSPAM@netzero.com.invalid> wrote:
> >
> > : Essentially, the existence of exploitable cycles in BBS would
> > : neccesarily lead to an efficient algorithm for decomposing RSA
> > : moduli into primes. As such, if you believe that the factoring
> > : of numbers in that range is a difficult problem, you need not
> > : loose sleep over the miniscule probability that you will land in
> > : a short cycle. [...]
> >
> > It's not a simply a case of losing sleep - it's a case of knowing
> > whether your system is secure.
> >
> > Short cycles are weak and insecure - no matter what the probability of
> > their arising is.
> 
> AFAICS from Theorem 4 of the BBS paper, lordcow77's argument is correct.
> That theorem shows that breaking the BBS generator is as hard as factoring
> N = pq even if the only constraints are that p and q are congruent to
> 3 mod 4 and x_0 is a quadratic residue, regardless of what the cycle
> length is.

Correction: it shows that breaking the BBS generator is as hard as breaking
the quadratic residuosity assumption (as defined in the BBS paper, i.e.
for all but a negligable fraction of moduli N = pq and seeds), even if
the only constraints are that p and q are primes congruent to 3 mod 4
and x_0 is a randomly selected quadratic residue.

The QRP has not been proven to be equivalent to the integer factorisation
problem.

- -- 
David Hopwood <hopwood@zetnet.co.uk>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01

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

iQEVAwUBOVF0uzkCAxeYt5gVAQE8Rgf/dbpPnQS9Agll7bFqtV2kx7J2Bqn7+eq0
GlxLm7wA/bBnXfYn8yrEC2JOphyT7IdFa7iuxroWZ9EgoYUg6jT5l7krMI6ypGCp
qHJnkpDH58fGTvdfy8KPPnQH3CRVSA8NfW/4r8yRAgbZaYMm/q2V73Rre6abEblY
ZLKwxo6xlewYd5/2Oyy7iuSwXU98qxrYNTOzVhvZomV5L2uongEBzpqesiAyiws5
pWIsQRCZorXar6Myk5YWJyUv6UVNNIPNX3MK/Wn8l74Et2Fp2wNJub60SSyyTn1H
YdVL4xBlm322Vc8UOElLht+5tiX+qdpHbyHOWuE80jiY61eBC1PyrQ==
=8iPa
-----END PGP SIGNATURE-----

Subject: Re: small subgroups in Blum Blum Shub
Date: 16 Jun 2000 23:00:30 -0000
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Message-ID: <20000616230030.9025.qmail@nym.alias.net>
References: <8i8sc4$h3n$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 14

> Please define "breaking". :) To me, being able to guess the upcoming
> bits with probability 1 because you already saw them earlier in the
> cycle, *that* spells "broke". I don't know how I would go backwards from
> knowing the sequence to knowing the factorization, but I do know I could
> guess upcoming bits quite easily. :)

Take a look at:
http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072

It shows a way to factor RSA moduli if you can find short BBS cycles
(or any cycles for that matter).

It would be a miracle if we could get agreement on this issue though.
Every time it comes up, the falsehoods fly.

Subject: Re: small subgroups in Blum Blum Shub
Date: Fri, 16 Jun 2000 23:51:10 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394abd1a.5134385@news.io.com>
References: <20000616230030.9025.qmail@nym.alias.net>
Newsgroups: sci.crypt
Lines: 77

On 16 Jun 2000 23:00:30 -0000, in
<20000616230030.9025.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster
Remailer <mix@anon.lcs.mit.edu> wrote:

>> Please define "breaking". :) To me, being able to guess the upcoming
>> bits with probability 1 because you already saw them earlier in the
>> cycle, *that* spells "broke". I don't know how I would go backwards from
>> knowing the sequence to knowing the factorization, but I do know I could
>> guess upcoming bits quite easily. :)
>
>Take a look at:
>http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072

I saw that when it came out, and a short summary is:

"it follows from the RSA assumption that finding short cycles is
impossible, for moduli large enough that factorization is
intractable."

and

"The advice to choose moduli with guaranteed long cycles, and to
choose seeds that way, is completely useless."

Oddly for useless advice, the last 2/3 of the BB&S published article
concerns just this issue.  The response involves forming a special
construction for N which is guaranteed to have long cycles of a
computable length, and then finding an algorithm to traverse those
cycles of known length, to show that a long cycle has been selected.
Now, did Blum, Blum and Shub simply get carried away with their own
math abilities?  Shall we assume that they were they so unaware of
their first results that they simply did not understand that 2/3 of
their work was "useless"?  

The world gasps at such arrogance.  

>It shows a way to factor RSA moduli if you can find short BBS cycles
>(or any cycles for that matter).

The cycles in an arbitrary primes construction will have various
lengths, but as far as I know, there are always some cycles of length
1 (which I call "degenerate").  I doubt they will be much help in
factoring N.  But they undoubtedly *are* the weakest possible
"sequence" (which would be, in practice, a "constant").  

It may be that some of those on the other side have not really
understood the weakness of a short cycle.  BB&S type systems probably
would be used as the generator of the confusion sequence for stream
ciphers.  The stream cipher requires its sequence to be random-like,
and *ALSO* to not repeat.  But if the BB&S happens to be on a short
cycle, it *will* repeat, and *that* is a weakness.  Sufficiently short
cycles *are* weak, and there simply is nothing to debate about it.  

>It would be a miracle if we could get agreement on this issue though.
>Every time it comes up, the falsehoods fly.

Then I suggest that you follow the discussion and point out those
falsehoods in detail.  That will be tricky for you, though, because
you are on the wrong side.  

As I see it, the principle falsehood here is the suggestion that the
discussion pertains to practical security.  It does not.  In practice,
selecting a short cycle would indeed be very, very unlikely.  But
"unlikely" is *not* the same as "impossible."  

Instead, the discussion here is about the concept of "proof" itself:
I claim that if it is *POSSIBLE* to select a short cycle, it should be
self-evident that any *proof* of security must be false.  The
alternative is a clear logic error -- an actual reasoning fault.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: Sat, 17 Jun 2000 01:03:15 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394ace3c.9521012@news.io.com>
References: <394abd1a.5134385@news.io.com>
Newsgroups: sci.crypt
Lines: 18

On Fri, 16 Jun 2000 23:51:10 GMT, in <394abd1a.5134385@news.io.com>,
in sci.crypt ritter@io.com (Terry Ritter) wrote:

>[...]
>The cycles in an arbitrary primes construction will have various
>lengths, but as far as I know, there are always some cycles of length
>1 (which I call "degenerate").  I doubt they will be much help in
>factoring N.  

Looking at my old results, it appears that degenerate cycles are
located at values P and Q, and so actually might the most direct way
to factor N.  If one could find them.  One could not, in general.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: 17 Jun 2000 17:34:22 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8ih5ee$l5v$1@blowfish.isaac.cs.berkeley.edu>
References: <394abd1a.5134385@news.io.com>
Newsgroups: sci.crypt
Lines: 27

In article <394abd1a.5134385@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> >Take a look at:
> >http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072
> 
> I saw that when it came out, and a short summary is:
> 
> "it follows from the RSA assumption that finding short cycles is
> impossible, for moduli large enough that factorization is
> intractable."
> 
> and
> 
> "The advice to choose moduli with guaranteed long cycles, and to
> choose seeds that way, is completely useless."
> 
> Oddly for useless advice, the last 2/3 of the BB&S published article
> concerns just this issue.  [...]
> Now, did Blum, Blum and Shub simply get carried away with their own
> math abilities?  Shall we assume that they were they so unaware of
> their first results that they simply did not understand that 2/3 of
> their work was "useless"?  
> 
> The world gasps at such arrogance.  

Well, now I'm curious.  What was wrong with the old article at
the URL above?  It looked correct to me.  What am I missing?
I'd love to hear a technical refutation, if there is one...

Subject: Re: small subgroups in Blum Blum Shub
Date: Sun, 18 Jun 2000 07:45:12 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394c7dee.7527575@news.io.com>
References: <8ih5ee$l5v$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 36

On 17 Jun 2000 17:34:22 -0700, in
<8ih5ee$l5v$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:

>[...]
>Well, now I'm curious.  What was wrong with the old article at
>the URL above?  It looked correct to me.  What am I missing?
>I'd love to hear a technical refutation, if there is one...

Sure.  Very easy.  Disproof by contrary example, or false case.  All
we need to find is one false case and the claim (that X^2 mod N is
proven secure without short cycle checks) fails.  

Call the parameter to X^2 mod N (and N = P*Q) as x0.  Make each of the
possible parameter values a proof case.  Most of those cases will in
fact select or "be on" a long cycle, and when they are, call each of
these cases "secure."  The issue is whether the system is proven to be
secure, which is to say, is it secure in every possible case?  

We know that some cases will *not* select a long cycle, and indeed
some of those will select a degenerate or one-state cycle, which is a
static result from what is supposed to be a dynamic value generator.
Such cases are obviously not secure.  That means that any proof which
claims that X^2 mod N without the BB&S recipe is secure, is thus shown
to be false.  

It not coincidence that the true BB&S recipe eliminates such cases, so
there will be no cases which are insecure due to short cycle length.
Thus we see that the true BB&S does in fact pass at least this simple
proof check.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: 18 Jun 2000 16:09:20 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8ijkr0$lss$1@blowfish.isaac.cs.berkeley.edu>
References: <394c7dee.7527575@news.io.com>
Newsgroups: sci.crypt
Lines: 17

In article <394c7dee.7527575@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> Sure.  Very easy.  Disproof by contrary example, or false case.  All
> we need to find is one false case and the claim (that X^2 mod N is
> proven secure without short cycle checks) fails.  

No, I think you misunderstood the claim.

You present a disproof of the (false) claim "there are no short cycles".
The post presents a proof of the (apparently true) claim
"if you select a starting point at random as given in the post, then
the chances of hitting a short cycle are negligible, assuming factoring
is hard".  There is no contradiction here.

In other words, if you're going to worry that you choose a starting
point that begins on a short cycle, you might as well spend your time
worrying that the adversary gets lucky and guesses a prime factor of N.
(And we know that worrying about _that_ is a waste of time...)

Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 00:09:03 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394d63ff.3961667@news.io.com>
References: <8ijkr0$lss$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 58

On 18 Jun 2000 16:09:20 -0700, in
<8ijkr0$lss$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:

>In article <394c7dee.7527575@news.io.com>, Terry Ritter <ritter@io.com> wrote:
>> Sure.  Very easy.  Disproof by contrary example, or false case.  All
>> we need to find is one false case and the claim (that X^2 mod N is
>> proven secure without short cycle checks) fails.  
>
>No, I think you misunderstood the claim.
>
>You present a disproof of the (false) claim "there are no short cycles".
>The post presents a proof of the (apparently true) claim
>"if you select a starting point at random as given in the post, then
>the chances of hitting a short cycle are negligible, assuming factoring
>is hard".  There is no contradiction here.

No.  Here is the beginning issue:

>>>>>> >The nonsense about choosing "strong primes" or
>>>>>> >good initialization values is a remnant to the past where it was
>>>>>> >thought that a relatively small prime (if well chosen) would be
>>>>>> >adaquately strong.

The claim is absurd.  The reason for the BB&S special primes
construction is to guarantee long cycles, and then select x0 on such a
cycle.  All that is necessary to complete a proof of security.  Proven
security is what the BB&S construction brings to the party, and why
one might use it.  Note how the issue has just become "proven
security."  

Then the issue is whether the BB&S construction is needed for proven
security.  That is, the issue is whether X^2 mod N by itself -- absent
BB&S protocols -- is "proven secure."  It is not, unless you think
"proof" is the same as "almost certainly."  I don't.   

>In other words, if you're going to worry that you choose a starting
>point that begins on a short cycle, you might as well spend your time
>worrying that the adversary gets lucky and guesses a prime factor of N.
>(And we know that worrying about _that_ is a waste of time...)

I don't worry about it at all.  I have said repeatedly that this
discussion is not about practical security.  

This discussion is about whether X^2 mod N is "proven secure."  And
all that is necessary for X^2 mod N insecurity is for the encrypting
end to choose a wrong x0.  That danger can be completely eliminated,
but if it is not, X^2 mod N, in practice, is not necessarily secure.
It is probably secure, almost surely secure, good enough secure, but
for all that is *not* "proven secure."  And that is why the BB&S
article has all that stuff on the end that nobody ever reads.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: 19 Jun 2000 00:06:19 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8ikgpb$m2b$1@blowfish.isaac.cs.berkeley.edu>
References: <394d63ff.3961667@news.io.com>
Newsgroups: sci.crypt
Lines: 7

You seem to think that, if an algorithm is "provably secure", then it
cannot have any weak keys (no matter how infrequent).  This is just
plain wrong, at least under the normal definitions of "provable security".

You could always pick your own favorite definition which excludes weak
keys, of course, but this isn't the standard meaning of the term, and
I see no reason to stop using the standard definitions.

Subject: Re: small subgroups in Blum Blum Shub
Date: 18 Jun 2000 23:44:36 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8kqnn4.q2.mdw@tux.nsict.org>
References: <394c7dee.7527575@news.io.com>
Newsgroups: sci.crypt
Lines: 25

Terry Ritter <ritter@io.com> wrote:
> daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
> 
> >Well, now I'm curious.  What was wrong with the old article at
> >the URL above?  It looked correct to me.  What am I missing?
> >I'd love to hear a technical refutation, if there is one...
> 
> Sure.  Very easy.  Disproof by contrary example, or false case.  All
> we need to find is one false case and the claim (that X^2 mod N is
> proven secure without short cycle checks) fails.  

Err...  I thought that the BBS generator was secure given that factoring
the modulus is hard.  I also thought that the article referred to showed
a way to factor the modulus easily given a short cycle, by finding a
pair of square roots of a quadratic residue.  This (to my mind, at any
rate) violates the hypothesis that factoring the modulus is hard.

The argument given is that a similar cycling attack also works against
general RSA moduli, although nobody bothers choosing RSA moduli
carefully to avoid this attack because finding short cycles is too
difficult anyway.  Since 1/4 of RSA moduli are Blum integers, a problem
with finding short cycles in Blum integers specifically would also
imperil a large class of RSA moduli.

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 00:31:05 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394d699e.5400474@news.io.com>
References: <slrn8kqnn4.q2.mdw@tux.nsict.org>
Newsgroups: sci.crypt
Lines: 51

On 18 Jun 2000 23:44:36 GMT, in <slrn8kqnn4.q2.mdw@tux.nsict.org>, in
sci.crypt mdw@nsict.org (Mark Wooding) wrote:

>[...]
>Err...  I thought that the BBS generator was secure given that factoring
>the modulus is hard.  I also thought that the article referred to showed
>a way to factor the modulus easily given a short cycle, by finding a
>pair of square roots of a quadratic residue.  This (to my mind, at any
>rate) violates the hypothesis that factoring the modulus is hard.

Quite right.  If we start out by *assuming* security, we are quite
unlikely to be able to get any lesser results.  Surely this is a wrong
mathematical construction to use if we are interested in finding
insecurity.  The correct conclusion to be drawn from the demonstration
is that the assumption is false *under* *particular* *circumstances*,
in particular, when a short cycle is used.  

>The argument given is that a similar cycling attack also works against
>general RSA moduli, although nobody bothers choosing RSA moduli
>carefully to avoid this attack because finding short cycles is too
>difficult anyway.  Since 1/4 of RSA moduli are Blum integers, a problem
>with finding short cycles in Blum integers specifically would also
>imperil a large class of RSA moduli.

Again right.  But RSA is a practical system.  In practice, the
probability of choosing a short cycle is very, very low.  The issue,
however, from the time I came into the construction, was something
like "why would anyone use the complex special primes BB&S
construction":

>>>>>> >The nonsense about choosing "strong primes" or
>>>>>> >good initialization values is a remnant to the past where it was
>>>>>> >thought that a relatively small prime (if well chosen) would be
>>>>>> >adaquately strong.

And that is nonsense.  The BB&S construction brings something to the
party which plain X^2 mod N does not, and that is the recipe for
assuring that a short cycle is not chosen.  This is not, as far as I
know, a practical issue.  Instead, this is an issue of *proof*: the
ability to claim to be using a system with "proven security."  Such a
claim requires that short cycles be avoided somehow, for short cycles
surely exist, and if a short cycle *is* selected, the system is
unarguably insecure.  *That* is the reason for the complex "special
primes" BB&S construction.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: 17 Jun 2000 17:41:09 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8ih5r5$l6j$1@blowfish.isaac.cs.berkeley.edu>
References: <394abd1a.5134385@news.io.com>
Newsgroups: sci.crypt
Lines: 24

In article <394abd1a.5134385@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> In practice,
> selecting a short cycle would indeed be very, very unlikely.  But
> "unlikely" is *not* the same as "impossible."  
> 
> Instead, the discussion here is about the concept of "proof" itself:
> I claim that if it is *POSSIBLE* to select a short cycle, it should be
> self-evident that any *proof* of security must be false.

Well, personally, I think you're wrong here.
You can never prevent the adversary from winning if he can make a lucky guess.
All you can do is make it exceedingly unlikely that the adversary wins.

For instance, clearly it is *POSSIBLE* for the adversary to guess a
factor of N just by dumb luck, and then you've broken BBS, but such a
lucky guess is extremely unlikely to happen.  You might as well worry
about getting struck by lightning over and over again.

Fortunately, the definitions of what it means to be secure don't require
us to do the impossible.  Thus, a proof of security roughly means that
we can bound the success probability as the adversary by a extremely small
quantity, so small that it can be essentially ignored in practice.

Absolute perfection here is neither required not attainable.

Subject: Re: small subgroups in Blum Blum Shub
Date: Sun, 18 Jun 2000 07:47:37 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394c7e0b.7556651@news.io.com>
References: <8ih5r5$l6j$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 76

On 17 Jun 2000 17:41:09 -0700, in
<8ih5r5$l6j$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:

>In article <394abd1a.5134385@news.io.com>, Terry Ritter <ritter@io.com> wrote:
>> In practice,
>> selecting a short cycle would indeed be very, very unlikely.  But
>> "unlikely" is *not* the same as "impossible."  
>> 
>> Instead, the discussion here is about the concept of "proof" itself:
>> I claim that if it is *POSSIBLE* to select a short cycle, it should be
>> self-evident that any *proof* of security must be false.
>
>Well, personally, I think you're wrong here.
>You can never prevent the adversary from winning if he can make a lucky guess.
>All you can do is make it exceedingly unlikely that the adversary wins.

You attempt to make the issue the same as the usual key selection, but
that is a false analogy.  For most of our ciphers, key selection is
arbitrary.  But here, key selection is *not* arbitrary, because weak
keys exist.  So the enciphering end has the chance to screw things up
by selecting a weak key, or to avoid that by checking first.  

This is not the same ordinary chance that opponents may happen on the
correct key, but is instead an *additional* chance that -- even if the
opponents do *not* find the correct key -- the result will be weak
*anyway*.  This is weakness *beyond* key selection.  

It is false to say that "All you can do is make it exceedingly
unlikely," because all we have to do is follow the BB&S recipe and
then we will not use weak keys.  Likelihood does not enter into it.
Clearly, we *can* do something about this weakness, and, clearly, BB&S
themselves thought this weakness sufficiently important to form a
complex construction so this weakness could be avoided.  

>For instance, clearly it is *POSSIBLE* for the adversary to guess a
>factor of N just by dumb luck, and then you've broken BBS, but such a
>lucky guess is extremely unlikely to happen.  You might as well worry
>about getting struck by lightning over and over again.

Yes, but the issue is not *about* practical security.  The issue is
whether the X^2 mod N generator -- without the BB&S recipe that
eliminates weak keys -- is "proven secure."  But when a weak key is
chosen, X^2 mod N is weak without dispute.  Any proof of security
which allows the choice of weak keys is thus simply false.  

The implications of this are severe:  They may mean that it is
impossible in practice for even advanced crypto people to properly
interpret the results of strength proofs.  The results may mean that
such proofs simply cannot take into account the various additional
requirements that a real system may need.  And, in this case, they may
mean that there are other additional requirements not yet known which
also negate the supposed "proof."  Now we need a "proof" which clearly
shows that we must eliminate weak keys, and also a sub-proof that no
other limitations are needed.  

>Fortunately, the definitions of what it means to be secure don't require
>us to do the impossible.  Thus, a proof of security roughly means that
>we can bound the success probability as the adversary by a extremely small
>quantity, so small that it can be essentially ignored in practice.
>
>Absolute perfection here is neither required not attainable.

Absolute perfection in the avoidance of weak keys *is* attainable
simply by reading beyond the first part of the BB&S article, and there
may be easier ways to accomplish the same goal.  But actively avoiding
weak keys is required to correctly state that X^2 mod N is "proven
secure" with no need for short-cycle checks.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: 18 Jun 2000 16:12:23 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8ijl0n$ltg$1@blowfish.isaac.cs.berkeley.edu>
References: <394c7e0b.7556651@news.io.com>
Newsgroups: sci.crypt
Lines: 16

In article <394c7e0b.7556651@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> You attempt to make the issue the same as the usual key selection, but
> that is a false analogy.  For most of our ciphers, key selection is
> arbitrary.  But here, key selection is *not* arbitrary, because weak
> keys exist.  So the enciphering end has the chance to screw things up
> by selecting a weak key, or to avoid that by checking first.  

No, I'm not talking about key selection.  This has nothing to do with
weak keys.

Whatever N the enciphering end chooses, there is a chance (albeit a very
small one!) that the attacker guesses a prime factor of N just by luck.
This is true _no matter how the enciphering end chooses N_.

You can never rule out the chance that the attacker gets lucky and guesses
your private key correctly.  It's simply unavoidable.

Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 00:16:36 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394d65f5.4463415@news.io.com>
References: <8ijl0n$ltg$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 44

On 18 Jun 2000 16:12:23 -0700, in
<8ijl0n$ltg$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:

>In article <394c7e0b.7556651@news.io.com>, Terry Ritter <ritter@io.com> wrote:
>> You attempt to make the issue the same as the usual key selection, but
>> that is a false analogy.  For most of our ciphers, key selection is
>> arbitrary.  But here, key selection is *not* arbitrary, because weak
>> keys exist.  So the enciphering end has the chance to screw things up
>> by selecting a weak key, or to avoid that by checking first.  
>
>No, I'm not talking about key selection.  This has nothing to do with
>weak keys.

Sure it does.  Avoiding weakness in the keying is what BB&S brings to
the party, above and beyond X^2 mod N by itself.  It is the reason for
the complex BB&S "special primes" construction.  

>Whatever N the enciphering end chooses, there is a chance (albeit a very
>small one!) that the attacker guesses a prime factor of N just by luck.
>This is true _no matter how the enciphering end chooses N_.

But weak keys bring weakness *without* the attacker guessing.  A weak
key (an X^2 mod N initial value on a short cycle) is selected by the
enciphering end, not the attacker.  They are an *additional* weakness,
above and beyond the normal attacker guessing.  

>You can never rule out the chance that the attacker gets lucky and guesses
>your private key correctly.  It's simply unavoidable.

Fine, but the issue here is weakness *beyond* guessing the key.  It is
the (theoretical) possibility that a stream cipher is using a
generator with a short cycle.  It is the possibility that, having
deciphered only the short cycle, the attacker can now run that
repeating sequence through the end of the message without further
work.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 10:56:15 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <394DE02F.FB91DB0F@t-online.de>
References: <394d65f5.4463415@news.io.com>
Newsgroups: sci.crypt
Lines: 24

Terry Ritter wrote:

> daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
>
> >You can never rule out the chance that the attacker gets lucky and guesses
> >your private key correctly.  It's simply unavoidable.
>
> Fine, but the issue here is weakness *beyond* guessing the key.  It is
> the (theoretical) possibility that a stream cipher is using a
> generator with a short cycle.  It is the possibility that, having
> deciphered only the short cycle, the attacker can now run that
> repeating sequence through the end of the message without further
> work.

I am not commenting on the chance of using a 'weak key' but like
to mention that for a sequence from a non-linear generator there
is normally an initial segment (which could be long) followed by
a loop, so that the chance of getting problems due to the loop is
likely to be higher if one uses longer sequences from the generator.

M. K. Shen

Subject: Re: small subgroups in Blum Blum Shub
Date: 19 Jun 2000 10:22:19 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8krt2q.u85.mdw@mull.ncipher.com>
References: <394DE02F.FB91DB0F@t-online.de>
Newsgroups: sci.crypt
Lines: 13

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

> I am not commenting on the chance of using a 'weak key' but like
> to mention that for a sequence from a non-linear generator there
> is normally an initial segment (which could be long) followed by
> a loop, so that the chance of getting problems due to the loop is
> likely to be higher if one uses longer sequences from the generator.

This doesn't happen in the BBS.  To see this, it suffices to note that,
within the subgroup of quadratic residues mod n where n is a Blum
integer, the map x |-> x^2 is bijective.

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 18:15:49 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394e633c.5152417@news.io.com>
References: <slrn8krt2q.u85.mdw@mull.ncipher.com>
Newsgroups: sci.crypt
Lines: 35

On 19 Jun 2000 10:22:19 GMT, in <slrn8krt2q.u85.mdw@mull.ncipher.com>,
in sci.crypt mdw@nsict.org (Mark Wooding) wrote:

>Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
>> I am not commenting on the chance of using a 'weak key' but like
>> to mention that for a sequence from a non-linear generator there
>> is normally an initial segment (which could be long) followed by
>> a loop, so that the chance of getting problems due to the loop is
>> likely to be higher if one uses longer sequences from the generator.
>
>This doesn't happen in the BBS.  To see this, it suffices to note that,
>within the subgroup of quadratic residues mod n where n is a Blum
>integer, the map x |-> x^2 is bijective.

It can be extremely educational to build some fairly small examples of
the generator, and then follow them through, state by state, until all
states have been covered.  I did this by computer program, but some of
the smaller versions might be as easy and more meaningful when done by
hand, or calculator.  The complex internal structure of these systems
is simply not apparent from their simple description.  

In my published experimental results:

   http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2

I call the number of states which lead to a cycle an "arc," and all of
the experimental BB&S versions -- both proper and improper -- had an
arc length of exactly one.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 22:10:14 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <394E7E26.E7C92A50@t-online.de>
References: <394e633c.5152417@news.io.com>
Newsgroups: sci.crypt
Lines: 18

Terry Ritter wrote:

> In my published experimental results:
>
>    http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2
>
> I call the number of states which lead to a cycle an "arc," and all of
> the experimental BB&S versions -- both proper and improper -- had an
> arc length of exactly one.

It would be fine if someone could show the theoretical underpinning
of this.

M. K. Shen

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 09:25:56 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8indav$tum$1@nnrp1.deja.com>
References: <394E7E26.E7C92A50@t-online.de>
Newsgroups: sci.crypt
Lines: 85

Mok-Kong Shen wrote:

> It would be fine if someone could show the theoretical
> underpinning
> of this.

Given a prime p, for each x in Z_p*  (Z_n* is the
multiplicative group modulo n),

    x^2 == (p-x)^2 mod p

(Using == to mean 'is congruent to).

No element other than x and p-x is a square root of x^2,
since for y to be a square root of x^2 we need,

    p | x^2 - y^2
    p | (x+y)(x-y)

(The verical bar reads "divides").  Since p is prime it has
to divide one of the factors (x+y) or (x-y), so the two
solution are y=x and y=p-x.  Thus each (mod p) square has
exactly two square roots and half the elements of Z_p* are
squares, (usually called "quadratic residues") and half are
non-residues.

The multiplicative group mod p always has a generator, call
some generator x.  The even powers of x are quadratic
residues, so the odd powers must be the non-residues.

Similarly, in the multiplicative group mod pq (distinct
primes) each quadratic residue x^2 has exactly four square
roots: x, pq-x, and the two unique elements a and b where a
is congruent to x mod p and to -x mod q, and b is vice-versa.
The quadratic residues mod pq are exactly those x that are
both quadratic residues modulo p and modulo q.

If a prime p is congruent to 3 mod 4, then negative one
(A.K.A. p-1) is never a mod p quadratic residue. Proof:
Consider a generator x, we know from Fermat that
x^(p-1) == 1, so x^((p-1)/2) is the other square root
of 1, which is -1, and that's an odd power of the
generator.

The product of a quadratic residue and a non-residue must be
a non-residue.  Thus if p == 3 mod 4, exactly one of (x, -x)
is a mod p quadratic residue (for any x in Z_p*).

Blum integers are the product of two distinct primes both
congruent to 3 mod 4.  Now look at a quadratic residue,
call it x^2, of pq, where pq is a Blum integer.  The four
roots of x^2 are:

    x
    -x
    a where a == x  mod p and a == -x mod q
    b where b == -x mod p and b == x mod q

These are the four combinations of x and -x, mod p and mod
q. Exactly one must be a residue of both p and q, and thus:

    Exactly one of the four square roots of a quadratic
    residue modulo a Blum integer is itself a quadratic
    residue.

So Mark Wooding was correct when he wrote:
| within the subgroup of quadratic residues mod n
| where n is a Blum integer, the map x |-> x^2 is
| bijective.

If we start at a random point in Z_p*, we get a non-residue
3/4 of the time, and thus a tail of length one.  After that
we're on the bijective map.

--Bryan

--
email: bolson at certicom dot com

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 10:04:09 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8kugcn.u85.mdw@mull.ncipher.com>
References: <394E7E26.E7C92A50@t-online.de>
Newsgroups: sci.crypt
Lines: 85

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

> It would be fine if someone could show the theoretical underpinning
> of this.

OK.  Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
Choose an integer x, 0 < x < n.  Then y = x^2 (mod n) is a quadratic
residue, mod n.

I claim (a) that y has four square roots, mod n, and (b) that exactly
one of these square roots is a quadratic residue.

Firstly, it's (fairly) clear that x is a square root of y, mod p.
Writing the assertion that y = x^2 (mod n) as y = x^2 + k p q makes this
obvious.  By symmetry, we also have y = x^2 (mod q).

Let x_p = x (mod p), x_q = x (mod q), with 0 < x_p < p, 0 < x_q < q.

Clearly, -x_p is the other square root of y (mod p), and -x_q is the
other square root of y (mod q).  By the Chinese Remainder Theorem, we
can show, using the result above, that y has precisely four square roots
mod n.  To see this, let z be a square root of y (mod n).  We know that
z_p is a square root of y (mod p), so z_p must be congruent to either
x_p or -x_p.  By symmetry, a similar argument applies to z_q.  Hence, y
has four square roots, as claimed in (a).

Now to prove that exactly one of the square roots is a quadratic
residue.  Let g be a primitive element in GF(p), and choose \alpha such
that x_p = g^\alpha (mod p); then y = g^{2\alpha} (mod p).  Now,

  -x_p = g^{\alpha + (p - 1)/2} (mod p)

To see this, note that g^{(p - 1)/2} = -1 (mod p).  Since p = 3 (mod 4),
(p - 1)/2 is odd.  Hence, precisely one of x_p and -x_p has an odd index
and is therefore a quadratic residue.  Similarly, one of x_q and -x_q is
a quadratic residue.  Again using the Chinese Remainder Theorem, we see
that one of the square roots of y (mod n) is a quadratic residue mod
each of p and q.  To prove (b), I must now show that this square root
(let's call it z) is a quadratic residue mod n.

Since z is a quadratic residue mod p it has a square root[1] mod p --
call this r_p.  It also has a square root mod q -- call it r_q.  By the
Chinese Remainder Theorem, we can find a unique integer r, 0 < r < n,
where r = r_p (mod p) and r = r_q (mod q).  A final application of the
Chinese Remainder Theorem shows that r^2 = z (mod n).  This proves claim
(b).

I earlier stated that, in the multiplicative group of quadratic residues
Q_n of the integers mod n, the map x |-> x^2 is bijective.  This is a
simple corollary of the above claims -- x^2 has exactly one square root
mod n which is in Q_n.  This map is therefore a permutation on Q_n.

Finally, let S be any finite set, and let f : S -> S be any permutation
on S.  Define the relation C_f on S by

  C_f(x, y) <==> there exists an integer i such that f^i(x) = y;

I claim that C_f(x, y) is an equivalence relation.  To do this, I must
show:

  (a) relexivity: that C_f(x, x) for all x;
  (b) commutivity: that C_f(x, y) <==> C_f(y, x); and
  (c) transitivity: that C_f(x, y) and C_f(y, z) imply C_f(x, z)

(c) is obvious from the definition of C_f.

Choose any element x of S.  Consider the sequence x, f(x), f^2(x), ...
Since S is finite, this sequence must cycle.  So, we must have i != j
where f^i(x) = f^j(x).  If i > 0, I can apply f^{-i} to both sides to
show that x = f^{j-i}(x).  Let c = j - i be the cycle length.  Claim (a)
is now proven trivially; (b) is proven by noting that if x = f^i(y) then
y = f^{c-i}(x) (apply f^{c-i} to both sides: f^{c-i}(x) = f^{i+c-i}(y) =
f^c(y) = y).

Finally, I suspect Terry found an arc length of one because he started
with a non-residue.

[1] Of course, it actually has two, but I don't care about the other
    one.

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:21:47 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394fa827.6277873@news.io.com>
References: <slrn8kugcn.u85.mdw@mull.ncipher.com>
Newsgroups: sci.crypt
Lines: 19

On 20 Jun 2000 10:04:09 GMT, in <slrn8kugcn.u85.mdw@mull.ncipher.com>,
in sci.crypt mdw@nsict.org (Mark Wooding) wrote:

>[...]
>Finally, I suspect Terry found an arc length of one because he started
>with a non-residue.

Sure.  I covered every possible state.  That, of course, establishes
the distribution encountered when choosing the starting state at
random.  

In a BB&S system there are a lot of arcs of length 1 feeding into
cycles.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 22:20:02 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <394FD1F2.F01FF4F9@t-online.de>
References: <slrn8kugcn.u85.mdw@mull.ncipher.com>
Newsgroups: sci.crypt
Lines: 19

Mark Wooding wrote:

> [snip]
>
> OK.  Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
> Choose an integer x, 0 < x < n.  Then y = x^2 (mod n) is a quadratic
> residue, mod n.
>
> I claim (a) that y has four square roots, mod n, and (b) that exactly
> one of these square roots is a quadratic residue.

Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
7^2 = 49 = 7 mod n. However 7 has only 2 square roots: 7 and 14.
(Bryan Olson's proof must also have a bug somewhere.)

M. K. Shen

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 00:17:34 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8ip1ii$4aj$1@nnrp1.deja.com>
References: <394FD1F2.F01FF4F9@t-online.de>
Newsgroups: sci.crypt
Lines: 26

Mok-Kong Shen wrote:

> Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
> 7^2 = 49 = 7 mod n.

No it isn't - it's not in the multiplicative group mod n.

> However 7 has only 2 square roots: 7 and 14.
> (Bryan Olson's proof must also have a bug somewhere.)

I can't promise there are no mistakes in my presentation,
but that case is no counterexample.

The 'bug' in Mark's proof was that in that line he should
have said "x in Z_n*", not just "0 < x < n"; it's a trivial
typo-class mistake since he was clear in several other
places that the domain is the multiplicative group.

--Bryan
--
email: bolson at certicom dot com

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 09:16:11 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8l11uq.pij.mdw@mull.ncipher.com>
References: <8ip1ii$4aj$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 8

Bryan Olson <bryanolson@my-deja.com> wrote:

> The 'bug' in Mark's proof was that in that line he should have said "x
> in Z_n*", not just "0 < x < n";

Yes, indeed.  Whoops! ;-)

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 18:08:39 -0700
From: d g <d_g_go@yahoo.com>
Message-ID: <ur99rdenc.fsf@detector.mayfield.hp.com>
References: <394FD1F2.F01FF4F9@t-online.de>
Newsgroups: sci.crypt
Lines: 60

> > OK.  Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
> > Choose an integer x, 0 < x < n.  Then y = x^2 (mod n) is a quadratic
> > residue, mod n.

This part is OK.

> > I claim (a) that y has four square roots, mod n, and (b) that exactly
> > one of these square roots is a quadratic residue.

There is a problem here.

> 
> Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
> 7^2 = 49 = 7 mod n. However 7 has only 2 square roots: 7 and 14.
> (Bryan Olson's proof must also have a bug somewhere.)

Consider the structure of the ring of integers mod n - in particular,
if you look at the multiplicative group (Z/(n))*, it is isomorphic to:

(Z/(p))* X (Z/(q))*

that is, it is the cross product of two cyclic groups of sizes (p-1)
and (q-1) respectively.

If you consider the ring homomorphism f that takes a number mod n to a
tuple (a,b) of numbers mod p and q, this map is onto.  The kernel of f
is the ideal (3*7).

If you choose random elements in the *multiplicative* cyclic subgroups
and square them, you get a quadratic residue with 4 roots as the
poster remarked.

However, if one of the choices is 0 (mod p) or (mod q), then you get
only two square roots.  To wit:

7 = 1 mod 3
  = 0 mod 7

If you take roots in the cyclic subgroups, you get (-1,0) and (1,0)
which map to 14 and 7 mod 21 respectively.

This is because 0 is not a member of the multiplicative group mod q -
that is, the residue 7 lies in the kernel of the homomorphism f.

There are (p-1) + (q-1) + 1 = p + q - 1 elements in the kernel.  Out
of these, the kernel of f has ((p+q-2)/2) quadratic residues with 2
square roots each, and an equal number of quadratic nonresidues.

You will find that mod 21, there are four residues in f's kernel: (7,
9, 15, 18), which have two square roots each.  The quadratic
nonresidues in f's kernel are (3, 6, 12, 14).  Of course, if you came
upon any (nontrivial) element of the kernel of f, you could factor the
modulus by taking the gcd of the element and the modulus; that is,
there is an efficient reduction from finding a nontrivial element of
the kernel of the homomorphism f to factoring n.

== 
Dipankar
d_g_go@yahoo.com

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 15:20:53 -0500
From: Doug Kuhlman <dougk@labs.mot.com>
Message-ID: <395123A5.497EF330@labs.mot.com>
References: <394FD1F2.F01FF4F9@t-online.de>
Newsgroups: sci.crypt
Lines: 25

Mok-Kong Shen wrote:
> 
> Mark Wooding wrote:
> 
> > [snip]
> >
> > OK.  Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
> > Choose an integer x, 0 < x < n.  Then y = x^2 (mod n) is a quadratic
> > residue, mod n.
> >
> > I claim (a) that y has four square roots, mod n, and (b) that exactly
> > one of these square roots is a quadratic residue.
> 
> Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
> 7^2 = 49 = 7 mod n. However 7 has only 2 square roots: 7 and 14.
> (Bryan Olson's proof must also have a bug somewhere.)
> 
> M. K. Shen

His mistake lies in assuming that GCD(x,p)=1, i.e. that x mod p is
distinct from -x mod p.  Add the assumption that x is relatively prime
to p and q and he's safe.  Often this is done by assuming x<p<q which is
not really such a major assumption.

Doug

Subject: Re: small subgroups in Blum Blum Shub
Date: Sun, 18 Jun 2000 21:50:35 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8ijg79$fhv$1@nnrp1.deja.com>
References: <394abd1a.5134385@news.io.com>
Newsgroups: sci.crypt
Lines: 64

Terry Ritter wrote:
> anon wrote:

> >Take a look at:
> >http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072
>
[...]
> Oddly for useless advice, the last 2/3 of the BB&S published article
> concerns just this issue. [...]

That is not how to read a scientific or mathematical
paper.  To draw conclusions, one must understand the
math not count the words.

I presented the same mathematical argument as Anon in:

http://x68.deja.com/[ST_rn=ps]/getdoc.xp?AN=494536680

and asked:

| Is anything wrong with the following argument?  It shows
| that under the assumption that factoring Blum integers is
| hard, short cycles are of no concern.

To which Ritter replied:

: I am not qualified to judge the argument about the
: probability of short cycles, so I assume it is
: correct.  What I would call wrong is what that means: [...]

[...]
> >It would be a miracle if we could get agreement on this issue though.
> >Every time it comes up, the falsehoods fly.
>
> Then I suggest that you follow the discussion and point out those
> falsehoods in detail.

I think the most important misconception to correct is
the notion that the reason the standard references, such as
/Handbook of Applied Cryptography/ do not state that one
should apply the cycle-length filter from the BBS paper
is out of laziness or ignorance.  That is of course not
the case.  The authors of HAC were not limited to judging
results by volume of text.

[...]
> Instead, the discussion here is about the concept of "proof" itself:
> I claim that if it is *POSSIBLE* to select a short cycle, it should be
> self-evident that any *proof* of security must be false.  The
> alternative is a clear logic error -- an actual reasoning fault.

The beauty of probability is that it enables us to
reason with mathematical certainty even as chance
plays upon the subjects of our reasoning.

--Bryan
--
email: bolson at certicom dot com

Sent via Deja.com http://www.deja.com/
Before you buy.

Subject: Re: small subgroups in Blum Blum Shub
Date: Sat, 17 Jun 2000 22:10:35 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394bf755.2163447@news.io.com>
References: <20000616230030.9025.qmail@nym.alias.net>
Newsgroups: sci.crypt
Lines: 77

On 16 Jun 2000 23:00:30 -0000, in
<20000616230030.9025.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster
Remailer <mix@anon.lcs.mit.edu> wrote:

>> Please define "breaking". :) To me, being able to guess the upcoming
>> bits with probability 1 because you already saw them earlier in the
>> cycle, *that* spells "broke". I don't know how I would go backwards from
>> knowing the sequence to knowing the factorization, but I do know I could
>> guess upcoming bits quite easily. :)
>
>Take a look at:
>http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072

I saw that when it came out, and a short summary is:

"it follows from the RSA assumption that finding short cycles is
impossible, for moduli large enough that factorization is
intractable."

and

"The advice to choose moduli with guaranteed long cycles, and to
choose seeds that way, is completely useless."

Oddly for useless advice, the last 2/3 of the BB&S published article
concerns just this issue.  The response involves forming a special
construction for N which is guaranteed to have long cycles of a
computable length, and then finding an algorithm to traverse those
cycles of known length, to show that a long cycle has been selected.
Now, did Blum, Blum and Shub simply get carried away with their own
math abilities?  Shall we assume that they were they so unaware of
their first results that they simply did not understand that 2/3 of
their work was "useless"?  

The world gasps at such arrogance.  

>It shows a way to factor RSA moduli if you can find short BBS cycles
>(or any cycles for that matter).

The cycles in an arbitrary primes construction will have various
lengths, but as far as I know, there are always some cycles of length
1 (which I call "degenerate").  I doubt they will be much help in
factoring N.  But they undoubtedly *are* the weakest possible
"sequence" (which would be, in practice, a "constant").  

It may be that some of those on the other side have not really
understood the weakness of a short cycle.  BB&S type systems probably
would be used as the generator of the confusion sequence for stream
ciphers.  The stream cipher requires its sequence to be random-like,
and *ALSO* to not repeat.  But if the BB&S happens to be on a short
cycle, it *will* repeat, and *that* is a weakness.  Sufficiently short
cycles *are* weak, and there simply is nothing to debate about it.  

>It would be a miracle if we could get agreement on this issue though.
>Every time it comes up, the falsehoods fly.

Then I suggest that you follow the discussion and point out those
falsehoods in detail.  That will be tricky for you, though, because
you are on the wrong side.  

As I see it, the principle falsehood here is the suggestion that the
discussion pertains to practical security.  It does not.  In practice,
selecting a short cycle would indeed be very, very unlikely.  But
"unlikely" is *not* the same as "impossible."  

Instead, the discussion here is about the concept of "proof" itself:
I claim that if it is *POSSIBLE* to select a short cycle, it should be
self-evident that any *proof* of security must be false.  The
alternative is a clear logic error -- an actual reasoning fault.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Comments: Please report problems with this automated remailing service to
	<squirrel-admin@echelon.alias.net>. The message sender's identity
	is unknown, unlogged, and not replyable.

Subject: Re: small subgroups in Blum Blum Shub
Date: 19 Jun 2000 22:19:07 -0000
From: Secret Squirrel <squirrel@echelon.alias.net>
Message-ID: <d04bc19681191c848535d3c1dbb5d838@anonymous.poster>
References: <20000616230030.9025.qmail@nym.alias.net>
Newsgroups: sci.crypt
Lines: 97

[Apologies if a duplicate of this message appears.]

[The discussion below references
 http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072 ]

Terry Ritter writes:

> I saw that when it came out, and a short summary is:
>
> "it follows from the RSA assumption that finding short cycles is
> impossible, for moduli large enough that factorization is
> intractable."
>
> and
>
> "The advice to choose moduli with guaranteed long cycles, and to
> choose seeds that way, is completely useless."
>
> Oddly for useless advice, the last 2/3 of the BB&S published article
> concerns just this issue.  The response involves forming a special
> construction for N which is guaranteed to have long cycles of a
> computable length, and then finding an algorithm to traverse those
> cycles of known length, to show that a long cycle has been selected.
> Now, did Blum, Blum and Shub simply get carried away with their own
> math abilities?  Shall we assume that they were they so unaware of
> their first results that they simply did not understand that 2/3 of
> their work was "useless"?

This is not an argument.  This is innuendo.  This is speculation.  Not one
word of what you have written here contradicts the proof referenced
above that being able to find short cycles allows you to factor.

There is no reason to speculate on what anyone's motives are.  That's
not math, it's soap opera.  Let us stick to mathematics here.  This
is a mathematical question and we have a mathematical answer.

> >It shows a way to factor RSA moduli if you can find short BBS cycles
> >(or any cycles for that matter).
>
> The cycles in an arbitrary primes construction will have various
> lengths, but as far as I know, there are always some cycles of length
> 1 (which I call "degenerate").  I doubt they will be much help in
> factoring N.  But they undoubtedly *are* the weakest possible
> "sequence" (which would be, in practice, a "constant").  

If x^2 = x mod n, with n an RSA modulus, then x^2 = x mod p where p is one
of the factors.  Therefore x^2 - x is a multiple of p, and equivalently
x(x-1) is a multiple of p.  But by the unique factorization theorem then
either x or x-1 must be a multiple of p.  The same thing is true with
respect to q, the other factor.

Therefore, such x values are extremely rare.  There are only 4 of them
less than n, two of which are 0 and 1.  Hence the chance of hitting one
at random is the same as the chance of factoring n by just guessing a
factor at random and seeing if you are right.

Furthermore, even if you did manage to hit one of the two non-trivial
values, it is a multiple of either p or q, and so if you do gcd(x,n)
you recover a factor of n.  (But it doesn't matter because you would
never hit one, not in the lifetime of the universe.)

> It may be that some of those on the other side have not really
> understood the weakness of a short cycle.  BB&S type systems probably
> would be used as the generator of the confusion sequence for stream
> ciphers.  The stream cipher requires its sequence to be random-like,
> and *ALSO* to not repeat.  But if the BB&S happens to be on a short
> cycle, it *will* repeat, and *that* is a weakness.  Sufficiently short
> cycles *are* weak, and there simply is nothing t