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 to debate about it.  

It seems that it is you who do not understand.  Short cycles produce
factors!  That should be the beginning and ending of the discussion.
No more is needed.

For more than five years you have been spreading misinformation on
this topic by insisting that you do not have provable security in a BBS
generator unless you use special primes and do tests so that your initial
seed does not put you on a short cycle.  Again and again over the years
you have been presented with mathematical proof that you are wrong.

All you ever respond with is "but why then did the BBS paper analyze
cycle lengths?"

This is the weakest form of argument by authority, because you can't
even find a quote from the authority which justifies your position.
Instead you have to speculate: they must have analyzed cycle lengths
because they believed that unless you check for short cycles, the BBS
cipher is weak!  Of course, they never say that.  They do not have one
word in any of their papers which says this.  It is purely an invention
which you have conjured up, an inference which you have reached on the
basis of your guess at their psychological motivations.

Such arguments have no place in a technical forum.  If you cannot
respond with a mathematical argument, you should go away until you can.
You certainly should not be making unsupported technical claims purely
on the basis of what your imagination suggests is the motivation of
other researchers.

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 00:55:03 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394ec029.4137859@news.io.com>
References: <d04bc19681191c848535d3c1dbb5d838@anonymous.poster>
Newsgroups: sci.crypt
Lines: 203

On 19 Jun 2000 22:19:07 -0000, in
<d04bc19681191c848535d3c1dbb5d838@anonymous.poster>, in sci.crypt
Secret Squirrel <squirrel@echelon.alias.net> wrote:

>[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.

I've got your "innuendo," and it was the implication that 2/3 of the
BB&S article was "completely useless."  See above.

>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.

Oddly, the mathematical answer is straightforward and obvious:  Nobody
disputes that short cycles occur in all X^2 mod N constructions.
Nobody disputes that the conventional approach to X^2 mod N generators
does not eliminate the possibility of choosing an initial x0 on a
short cycle.  Nobody disputes that if one uses a short cycle, the
generator is weak.  So exactly what kind of answer are you looking
for?  As I said in a previous posting, the issue here is nothing less
than the meaning of "proof" itself:  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.  

>> >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.

I thought we were talking discrete math here, not calculus.  Simply
because we have just a few values does not mean we have zero values.  

Nor is that chance "the same" as guessing a factor of N.  That chance
is *in* *addition* to guessing a factor of N.  Simply using the short
cycle is a weakness; it is *not* necessary to factor N to exploit
weakness.  

The short cycle weakness is a weakness which does not have to exist,
but which is normally allowed to exist.  The fact that this additional
weakness possibility is not eliminated is sufficient to show that any
resulting system cannot be "proven secure."  End of story.   

>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 to debate about it.  
>
>It seems that it is you who do not understand.  Short cycles produce
>factors!  That should be the beginning and ending of the discussion.
>No more is needed.

That is a non-sequitur.  What do *you* think the implications are of
"short cycles produce factors"?  Do you imagine that because "short
cycles produce factors" (except, I suppose, for 0 and 1 which you
mentioned above but apparently forgot), they thus cannot exist?  Well,
they *do* exist, so they are an obvious weakness, aren't they?

>For more than five years you have been spreading misinformation on
>this topic by insisting that you do not have provable security in a BBS
>generator unless you use special primes and do tests so that your initial
>seed does not put you on a short cycle.  

The information I present is fact, and it does not depend upon me,
because it does not take a rocket scientist to reason out:  

Any person with some contact to stream cipher cryptography knows that
it is important to have a generator with a sequence which is known to
be long.  Any person can construct a simple BB&S type system out of
small primes and prove by demonstration that such systems *can* have
short cycles.  In fact, BB&S do and must have short cycles.  Any
person can put these two facts together and know that unless steps are
taken to avoid short cycles, there is some possibility of using a weak
short cycle.  Asserting that the possibility is almost zero in
practice does not make it zero.  

>Again and again over the years
>you have been presented with mathematical proof that you are wrong.

The mathematical demonstration presented here actually *proved* *my*
*point*; it described one way a short cycle is weak (by allowing
factoring, though there is another weakness, the effect on systems
which need sequences of substantial length).  Clearly, using such a
cycle is a weakness in the system.  Finding such a cycle is a
*practical* problem, since, in theory, the weakness is present unless
construction and testing avoid it.  Since the weakness is present, a
proper mathematical treatment must reveal it.  A mathematical showing
of weakness in the system, however, will require that one not first
*assume* that the system is secure.  

>All you ever respond with is "but why then did the BBS paper analyze
>cycle lengths?"

Oh, I think I've responded with more than that.  Just what is *your*
position?  Do you imagine that short cycles do not exist?  Are you
prepared for a surprise?  

>This is the weakest form of argument by authority, because you can't
>even find a quote from the authority which justifies your position.
>Instead you have to speculate: they must have analyzed cycle lengths
>because they believed that unless you check for short cycles, the BBS
>cipher is weak!  Of course, they never say that.  They do not have one
>word in any of their papers which says this.  It is purely an invention
>which you have conjured up, an inference which you have reached on the
>basis of your guess at their psychological motivations.

Nonsense.  My argument does require someone to actually *read* past
the first third of the article, however.  Normally, one who actually
reads an article can summarize what it means.  And in a mathematical
construction article, one should be able to summarize the purpose for
the construction, or what the construction accomplishes.  Just exactly
what would be *your* summary of the purpose for the last 2/3 of the
BB&S article?  Surely you must know what it is if you agree it is
useless (you included the quote).  

>Such arguments have no place in a technical forum.  

It is a telling argument for which you have presented no alternative.
You do not address the content of the BB&S article, yet are somehow
satisfied there is no reason to use that content.  Odd.  

>If you cannot
>respond with a mathematical argument, you should go away until you can.
>You certainly should not be making unsupported technical claims purely
>on the basis of what your imagination suggests is the motivation of
>other researchers.

And you have not been able to describe *your* position at all.  Do you
imagine that short cycles do or do not exist in BB&S constructions?
Do you imagine that using such a cycle would be weak or not?  Do you
imagine that it is actually impossible for a short cycle to be
selected?  Or perhaps you simply missed the many times I have stated
that -- as far as I know -- this is not a problem in practice.  But it
is a *theoretical* problem, and as such stands directly in the way of
any serious claim of "proven security."  

---
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 19:17:49 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8imk8d$nhf$1@blowfish.isaac.cs.berkeley.edu>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 16

In article <394ec029.4137859@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> As I said in a previous posting, the issue here is nothing less
> than the meaning of "proof" itself:  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.  

Ahh, but here's the rub: The rest of the research community is also
apparently willing to bend more than you are.

In particular, the accepted definitions of provable security say that
something is secure if the probability of weakness is acceptably small
(say, smaller than 1/poly(k) for all polynomials, where k is a security
parameter chosen by the good guys, like the length of the RSA modulus).

Go read the standard definitions in the literature!  Really.

Subject: Re: small subgroups in Blum Blum Shub
Date: 19 Jun 2000 19:22:32 -0700
From: d g <d_g_go@yahoo.com>
Message-ID: <uzoohccrb.fsf@detector.mayfield.hp.com>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 26

ritter@io.com (Terry Ritter) writes:

> [...] As I said in a previous posting, the issue here is nothing
> less than the meaning of "proof" itself: 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.

Could you state what you mean by "provable security"?  As an example,
see the definition in chapter 5 of Goldreich's "Foundations of
Cryptography":

http://www.wisdom.weizmann.ac.il/home/oded/public_html/foc-book.html

A preprint of chapter 5 is available online - semantic security is
defined in : #5.2.1, #5.2.2.  Semantic security as defined by
Goldreich is essentially probabilistic.  Perhaps you have a different
model of computation.

Do you agree with his construction and analysis of Blum-Goldwasser
(which is based on the same QR intractability assumption as BBS) in
section 5.3 in the monograph?

== 
Dipankar
d_g_go@yahoo.com

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:21:12 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394fa7b6.6164415@news.io.com>
References: <uzoohccrb.fsf@detector.mayfield.hp.com>
Newsgroups: sci.crypt
Lines: 53

On 19 Jun 2000 19:22:32 -0700, in
<uzoohccrb.fsf@detector.mayfield.hp.com>, in sci.crypt d g
<d_g_go@yahoo.com> wrote:

>ritter@io.com (Terry Ritter) writes:
>
>> [...] As I said in a previous posting, the issue here is nothing
>> less than the meaning of "proof" itself: 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.
>
>Could you state what you mean by "provable security"?  As an example,
>see the definition in chapter 5 of Goldreich's "Foundations of
>Cryptography":
>
>http://www.wisdom.weizmann.ac.il/home/oded/public_html/foc-book.html
>
>A preprint of chapter 5 is available online - semantic security is
>defined in : #5.2.1, #5.2.2.  Semantic security as defined by
>Goldreich is essentially probabilistic.  Perhaps you have a different
>model of computation.

I do have a different model, but it is not a model of computation.  My
model is what I perceive as the basis for the entire field of
cryptography:  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.  The general unqualified use of it as a term-of-art is
deceptive to newbies, managers, and managing directors.  It might even
be seen as a marketing term.  

>Do you agree with his construction and analysis of Blum-Goldwasser
>(which is based on the same QR intractability assumption as BBS) in
>section 5.3 in the monograph?

I did finally download the right thing, and it looks to me like a
tremendous contribution.  But, since I'm not a mathematician, I'm
probably the wrong guy to ask about it.  In general, I have no problem
at all with terms being re-defined in a technical context, as long as
that context is maintained.  But the use of an existing term according
to a new technical definition will be deceptive.  Special care must be
taken to avoid the problem simply because the workers in that
sub-field have not been sufficiently creative to find a new phrase for
a new concept.  I suggest "statistically secure."  

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

	<uzoohccrb.fsf@detector.mayfield.hp.com> <394fa7b6.6164415@news.io.com>
Cc: ritter@io.com

Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 08:38:10 GMT
From: pom@imsd.uni-mainz.de (Klaus Pommerening)
Message-ID: <8iputi$o3o$3@bambi.zdv.Uni-Mainz.DE>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 36

In <394fa7b6.6164415@news.io.com> Terry Ritter wrote:
> I do have a different model, but it is not a model of computation.  My
> model is what I perceive as the basis for the entire field of
> cryptography:  The need to find a system which is secure against any
> possible attack.
> 
Not even the OTP is secure against any possible attack
(replay attack, modification of known plaintext).
Real world systems are vulnerable by brute force attacks.

>  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. 
> 
Less than what?

> ...  Special care must be
> taken to avoid the problem simply because the workers in that
> sub-field have not been sufficiently creative to find a new phrase for
> a new concept.  I suggest "statistically secure."  
> 
Good point. And BBS without "bells and whistles" and big enough
module is statistically much more secure than any 128 bit
symmetric cipher, and is statistically as secure as BBS with
"bells and whistles" and a slighly shorter module. (Guess:
2 or 3 bits shorter.)

[Sure, we have no clue how difficult factoring really is.
But we also have no clue, for any symmetric cipher, how
difficult breaking really is.]
-- 
Klaus Pommerening  [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:10:03 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3950f674.5866599@news.io.com>
References: <8iputi$o3o$3@bambi.zdv.Uni-Mainz.DE>
Newsgroups: sci.crypt
Lines: 65

On 21 Jun 2000 08:38:10 GMT, in <8iputi$o3o$3@bambi.zdv.Uni-Mainz.DE>,
in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:

>In <394fa7b6.6164415@news.io.com> Terry Ritter wrote:
>> I do have a different model, but it is not a model of computation.  My
>> model is what I perceive as the basis for the entire field of
>> cryptography:  The need to find a system which is secure against any
>> possible attack.
>> 
>Not even the OTP is secure against any possible attack
>(replay attack, modification of known plaintext).
>Real world systems are vulnerable by brute force attacks.

First of all, I was reciting the goal that every user has in mind.
Presumably, even you.  Goals are not limited by currently-known
reality, and rightly so.  

Next, 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.  

>>  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. 
>> 
>Less than what?

"Less than" a proof that no known weakness exists which we can
eliminate.  

>> ...  Special care must be
>> taken to avoid the problem simply because the workers in that
>> sub-field have not been sufficiently creative to find a new phrase for
>> a new concept.  I suggest "statistically secure."  
>> 
>Good point. And BBS without "bells and whistles" and big enough
>module is statistically much more secure than any 128 bit
>symmetric cipher, and is statistically as secure as BBS with
>"bells and whistles" and a slighly shorter module. (Guess:
>2 or 3 bits shorter.)
>
>[Sure, we have no clue how difficult factoring really is.
>But we also have no clue, for any symmetric cipher, how
>difficult breaking really is.]

I deny that all forms of weakness can be treated as just another type
of keying weakness.  

I dispute that reducing the probability of a weakness is equivalent to
eliminating that weakness.  

And in this particular case, I deny that increasing the keyspace and
so reducing the probability of using a short cycle is the same as
absolutely removing that possibility, since we do have that
alternative.  

---
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, 22 Jun 2000 00:23:50 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FwJ53q.B5J@bath.ac.uk>
References: <3950f674.5866599@news.io.com>
Newsgroups: sci.crypt
Lines: 33

Terry Ritter <ritter@io.com> wrote:
: in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:
:> Terry Ritter <ritter@io.com> wrote:

:>>  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. 
:>> 
:>Less than what?

: "Less than" a proof that no known weakness exists which we can eliminate.

There appears to be no possibility of getting such a proof with BBS,
anyway - regardless of any concerns about the use of short cycles.

It only claims to be as hard to break as factoring the modulus - and
nobody really has any idea how hard that is.

Even if the factoring problem is hard, factoring the modulus is a
significant attack in itself.  We'd be likely to get much better security
from the same key with a big table of hardware-generated, high quality
random numbers - XOR'd with the BBS output for good measure ;-)

This is a "known weakness" which certainly looks like it could be
eliminated - albeit at some expense.

I don't think "a proof that no known weakness exists which we can
eliminate" is on the cards.

Would you settle for a demonstration of no short cycles?
-- 
__________  Lotus Artificial Life  http://alife.co.uk/  tt@cryogen.com
 |im |yler  The Mandala Centre   http://mandala.co.uk/  VIPAR GAMMA GUPPY.

	<uzoohccrb.fsf@detector.mayfield.hp.com> <394fa7b6.6164415@news.io.com> 
	<8iputi$o3o$3@bambi.zdv.Uni-Mainz.DE> <3950f674.5866599@news.io.com>
Cc: ritter@io.com

Subject: Re: small subgroups in Blum Blum Shub
Date: 23 Jun 2000 07:11:32 GMT
From: pom@imsd.uni-mainz.de (Klaus Pommerening)
Message-ID: <8iv2j4$8aq$1@bambi.zdv.Uni-Mainz.DE>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 16

In <3950f674.5866599@news.io.com> Terry Ritter wrote:
> And in this particular case, I deny that increasing the keyspace and
> so reducing the probability of using a short cycle is the same as
> absolutely removing that possibility, since we do have that
> alternative.  
> 
This alternative limits the choice of parameters and seeds,
so reduces the key space significantly. Calculate the
increased probability for a successful attack and compare
this figure with the probability of running into a short cycle
with a less careful parameter choice.
-- 
Klaus Pommerening  [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 22 Jun 2000 00:08:57 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FwJ4Ex.Aw1@bath.ac.uk>
References: <394fa7b6.6164415@news.io.com>
Newsgroups: sci.crypt
Lines: 20

Terry Ritter <ritter@io.com> wrote:
: <d_g_go@yahoo.com> wrote:
:>ritter@io.com (Terry Ritter) writes:

:>> [...] As I said in a previous posting, the issue here is nothing
:>> less than the meaning of "proof" itself: 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.
:>
:>Could you state what you mean by "provable security"?

[snip discussion of what "provable" means - or should mean]

: I suggest "statistically secure."

That's not going to appeal very much to managers or marketing.
-- 
__________  Lotus Artificial Life  http://alife.co.uk/  tt@cryogen.com
 |im |yler  The Mandala Centre   http://mandala.co.uk/  Namaste.

Subject: Re: small subgroups in Blum Blum Shub
Date: 22 Jun 2000 04:00:13 GMT
From: David A Molnar <dmolnar@fas.harvard.edu>
Message-ID: <8is30d$ro8$1@news.fas.harvard.edu>
References: <FwJ4Ex.Aw1@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 18

Tim Tyler <tt@cryogen.com> wrote:

> [snip discussion of what "provable" means - or should mean]

> : I suggest "statistically secure."

> That's not going to appeal very much to managers or marketing.

I saw the flap which IBM PR made over the Ajtai-Dwork cryptosystem
being "provably secure." Other than that, where has this kind of "provable
security" come up in PR or marketing or management decisions?

I do not mean snake oil claims which cannot be backed up, but instead I am
interested in how the academic concept of "provable security" has been
interpreted in practice. 

thanks
-dmolnar

Subject: Re: small subgroups in Blum Blum Shub
Date: 19 Jun 2000 19:28:47 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8imksv$nik$1@blowfish.isaac.cs.berkeley.edu>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 39

In article <394ec029.4137859@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> 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.  

Here's another way to see why we are willing to bend more than you are.

Let me ask you a question.  What length keys do you use?

Let's suppose for the sake of argument that you use 2048-bit RSA keys.
(The argument works for any key length.)  Then we can note that there is
at least a 1/2^2048 chance that the attacker correctly guesses a prime
factor of your RSA modulus.  This can be prevented by moving to a 4096-bit
RSA key, where the chance of a successful result decreases enormously.

This means that 2048-bit RSA has a small but preventable probability of
weakness which is not present in 4096-bit RSA.  So you should be using
4096-bit RSA, not 2048-bit RSA.

But wait!  The same argument says that 4096-bit RSA has a small but
preventable probability of weakness which is not present in 8192-bit RSA,
so you should be using 8192-bit RSA, not 4096-bit RSA.  But 8192-bit
RSA is bad, you should be using 16384-bit RSA.  And so on, ad infinitum.

It's a steep slope, and once you get started down this path, there's
no logical place to stop.  Whatever key length you choose, it's always
illogical to use it.  We're paralyzed.

This is an absurd situation, and it's all a consequence of this premise
that a small but preventable probability of weakness is unacceptable.
I submit that it's the premise that's at fault here, and that if the
probability of weakness is sufficiently small, we can go home happy.

In the computational setting, security is inherently probabilistic.
You don't get absolute security; you just get systems where breaking
it is sufficiently large to prevent compromise.  Similarly, you don't
get guaranteed security; you just get systems where the probability of
compromise is sufficiently small.

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:21:23 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394fa80b.6249857@news.io.com>
References: <8imksv$nik$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 68

On 19 Jun 2000 19:28:47 -0700, in
<8imksv$nik$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:

>Here's another way to see why we are willing to bend more than you are.
>[...]
>It's a steep slope, and once you get started down this path, there's
>no logical place to stop.  Whatever key length you choose, it's always
>illogical to use it.  We're paralyzed.

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.  Because it is inherent, we learn to live with it; we have
no alternative, since key-guessing is not under our control.  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.  

Whatever key length we choose, there is always an additional,
preventable risk if we do not check for short cycles.  As I have said
many times, this is -- as far as I know -- not a practical issue.  But
it is a theoretical issue, and it is a theoretical weakness which can
be avoided.  Avoiding that weakness is the reason for the "useless"
last 2/3 of the BB&S article.  Using the BB&S prescriptions gives us
the ability to say that -- other than keyspace / brute force -- we
know of no weakness that we have not stopped.  

Stopping every known weakness is the essence of cryptographic system
design, and that goes far beyond the cipher per se.  Being willing to
allow a weakness because one *assumes* that it will not be selected is
-- in my view -- a serious flaw in a cryptographic system designer.
For one thing, it means that we cannot claim to have made the system
as secure as it can possibly be made to be.  And it means that if
there were a test for weakness (beyond key-guessing), we could fail
that test and still be "in spec."  

An educated technical person can understand the concepts of key,
keyspace, and key-guessing / brute force fairly quickly.  They can
understand these risks and accept them.  Beyond that understanding,
descriptions of a system with short cycles might be:

|   * almost surely not insecure

|   * secure unless one is very unlucky

But I suspect these descriptions would not be something a customer
would appreciate.  

>[...]
>In the computational setting, security is inherently probabilistic.
>You don't get absolute security; you just get systems where breaking
>it is sufficiently large to prevent compromise.  Similarly, you don't
>get guaranteed security; you just get systems where the probability of
>compromise is sufficiently small.

I agree.  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.  

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

	<8imksv$nik$1@blowfish.isaac.cs.berkeley.edu> <394fa80b.6249857@news.io.com>
Cc: ritter@io.com

Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 08:46:52 GMT
From: pom@imsd.uni-mainz.de (Klaus Pommerening)
Message-ID: <8ipvds$o3o$4@bambi.zdv.Uni-Mainz.DE>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 14

In <394fa80b.6249857@news.io.com> Terry Ritter wrote:
> 
> ...  Using the BB&S prescriptions gives us
> the ability to say that -- other than keyspace / brute force -- we
> know of no weakness that we have not stopped.  
> 
> 
Factoring the modulus is a much stronger attack than brute
force.
-- 
Klaus Pommerening  [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:10:13 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3950f6ee.5988814@news.io.com>
References: <8ipvds$o3o$4@bambi.zdv.Uni-Mainz.DE>
Newsgroups: sci.crypt
Lines: 21

On 21 Jun 2000 08:46:52 GMT, in <8ipvds$o3o$4@bambi.zdv.Uni-Mainz.DE>,
in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:

>In <394fa80b.6249857@news.io.com> Terry Ritter wrote:
>> 
>> ...  Using the BB&S prescriptions gives us
>> the ability to say that -- other than keyspace / brute force -- we
>> know of no weakness that we have not stopped.  
>> 
>> 
>Factoring the modulus is a much stronger attack than brute
>force.

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.

---
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 19:32:58 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8iml4q$nj8$1@blowfish.isaac.cs.berkeley.edu>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 26

In article <394ec029.4137859@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> And you have not been able to describe *your* position at all.  Do you
> imagine that short cycles do or do not exist in BB&S constructions?
> Do you imagine that using such a cycle would be weak or not?  Do you
> imagine that it is actually impossible for a short cycle to be
> selected?

I think it was already clear, but I'll answer your questions.

Yes, short cycles exist in BB&S.  Yes, using such a cycle would be weak.
No, it is not impossible to encounter such a cycle.  Yes, BB&S is provably
secure (under appropriate assumptions and definitions).  There is no
contradiction here.

> Or perhaps you simply missed the many times I have stated
> that -- as far as I know -- this is not a problem in practice.  But it
> is a *theoretical* problem, and as such stands directly in the way of
> any serious claim of "proven security."  

You are making an unnecessary distinction between theory and practice here.
Theory doesn't need to be different from practice just for the sake of being
different!

Under standard theoretical definitions, there is no theoretical problem.
Maybe you prefer non-standard definitions, but I haven't yet heard why
you prefer them.

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:21:39 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394fa816.6261017@news.io.com>
References: <8iml4q$nj8$1@blowfish.isaac.cs.berkeley.edu>
Newsgroups: sci.crypt
Lines: 39

On 19 Jun 2000 19:32:58 -0700, in
<8iml4q$nj8$1@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:

>[...]
>Under standard theoretical definitions, there is no theoretical problem.
>Maybe you prefer non-standard definitions, but I haven't yet heard why
>you prefer them.

The problem is that both "proven" and "secure" are well understood by
an educated person.  Math proofs start after grade school, so
everybody knows what "proof" should mean.  And "security" is the
overall area which contains cryptography, so a sub-field of
cryptography hardly has the right to redefine it.  

By itself, I believe "proven secure" means to most educated people "it
has been proven that insecurity does not exist."  All we have to do is
to look around at the various discussions here on sci.crypt and see
how many times newbies -- and even some oldies -- have embraced the
delusion that there really are systems that are "proven secure" under
the common meaning of that phrase.  I think much of this comes from
seeing the phrase in reputable technical journals where it has the
lesser technical meaning, and is not qualified as a "term of art."
Many confusing "terms of art" exist in many areas, but this one is
particularly deceptive and should be confronted head on when it
occurs.  Deception is not a valid academic mode.  

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.  

---
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 07:26:00 -0400
From: "Trevor L. Jackson, III" <fullmoon@aspi.net>
Message-ID: <394F54C8.49379FC7@aspi.net>
References: <394F1C97.AE49C2F2@t-online.de>
   <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 49

Mok-Kong Shen wrote:

> Terry Ritter wrote:
>
> > Secret Squirrel <squirrel@echelon.alias.net> wrote:
> > >If you cannot
> > >respond with a mathematical argument, you should go away until you can.
> > >You certainly should not be making unsupported technical claims purely
> > >on the basis of what your imagination suggests is the motivation of
> > >other researchers.
> >
> > And you have not been able to describe *your* position at all.  Do you
> > imagine that short cycles do or do not exist in BB&S constructions?
> > Do you imagine that using such a cycle would be weak or not?  Do you
> > imagine that it is actually impossible for a short cycle to be
> > selected?  Or perhaps you simply missed the many times I have stated
> > that -- as far as I know -- this is not a problem in practice.  But it
> > is a *theoretical* problem, and as such stands directly in the way of
> > any serious claim of "proven security."
>
> I am not sure but I have the impression that the presently very heated
> dispute is somewhat analogous to a dispute over OTP. Person A
> gets some hardware generated extremely high quality random bit
> sequences and claims that his encryption is provably secure because
> OTP is proved to be secure, while person B maintains that, because
> the sequences obtained in practice must necessarily have some minute
> deviations from what is assumed in the proof of OTP's security, A's
> system is not provably secure.

Not quite.  One position is similar to that of an OTP user.  The other
position is that of pseudo-OTP user, whose pad is generated by an inferior
process (PRNG).  The OTP user is subject to a Karnak attack.  The other is
subject to both a Karnak attack and cryptanalysis of the PRNG.

The distinction can be seen more clearly when one considers that betting on
long odds say 1:2^256 and betting on an impossibility are the same in practice
-- fruitless.  But they are not the same in theory.  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.

-------------------

(*) I'm not qualified to make the judgment.  The reasoning presented by daw
and mdw appears to be convincing.

Cc: ritter@io.com

Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 14:33:12 GMT
From: pom@imsd.uni-mainz.de (Klaus Pommerening)
Message-ID: <8invb8$9n9$1@bambi.zdv.Uni-Mainz.DE>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 32

In <394ec029.4137859@news.io.com> Terry Ritter wrote:
> The short cycle weakness is a weakness which does not have to exist,
> but which is normally allowed to exist.  The fact that this additional
> weakness possibility is not eliminated is sufficient to show that any
> resulting system cannot be "proven secure."  End of story.   
> 
So what do you think of RSA?
There you also have short cycles, and you can't avoid
them, because they come from the plain text, not from the
key. Remember the iterative attack?

[Assume m = plain text, c = cipher text, E = public encryption function]

If c = E(m), then consider the cycle E(c), E(E(c)), E(E(E(c))),
..., until E^s(c) = c. Now m = E^{s-1}(c).
Hey - we have broken *every* public key encryption.

"The fact that this additional weakness possibility is not
eliminated is sufficient to show" ... that asymmetric encryption
cannot be proven secure.

By the way - finding a key for a symmetric128 bit encryption
by pure guessing has a much higher success probability than
running into a cycle for BBS or RSA with 1024 bit modulus.

Therefore symmetric encryption also cannot be proven secure.
End of story.
-- 
Klaus Pommerening  [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 10:07:42 -0600
From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov>
Message-ID: <394F96CE.B747129B@cic-mail.lanl.gov>
References: <8invb8$9n9$1@bambi.zdv.Uni-Mainz.DE>
Newsgroups: sci.crypt
Lines: 4

I think people are missing the point here. 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.

Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 16:16:13 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8kv66c.lpn.mdw@mull.ncipher.com>
References: <394F96CE.B747129B@cic-mail.lanl.gov>
Newsgroups: sci.crypt
Lines: 11

Tony T. Warnock <u091889@cic-mail.lanl.gov> wrote:
> I think people are missing the point here. 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.

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.

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:31:30 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394faa64.6850970@news.io.com>
References: <slrn8kv66c.lpn.mdw@mull.ncipher.com>
Newsgroups: sci.crypt
Lines: 23

On 20 Jun 2000 16:16:13 GMT, in <slrn8kv66c.lpn.mdw@mull.ncipher.com>,
in sci.crypt mdw@nsict.org (Mark Wooding) wrote:

>Tony T. Warnock <u091889@cic-mail.lanl.gov> wrote:
>> I think people are missing the point here. 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.
>
>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.

I have no idea what that could possibly mean.  If the assumption is
contradicted, surely we cannot say the proof stands.  Unless, of
course, we see "proof" as a mere manipulation of symbols, as opposed
to the correct conclusion.  

---
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: 21 Jun 2000 09:40:07 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8l13bm.pij.mdw@mull.ncipher.com>
References: <394faa64.6850970@news.io.com>
Newsgroups: sci.crypt
Lines: 45

Terry Ritter <ritter@io.com> wrote:

> in sci.crypt mdw@nsict.org (Mark Wooding) wrote:
>
> >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.
> 
> I have no idea what that could possibly mean.  If the assumption is
> contradicted, surely we cannot say the proof stands.  Unless, of
> course, we see "proof" as a mere manipulation of symbols, as opposed
> to the correct conclusion.

It seems perfectly reasonable to me, as an ex-mathematician, to make
statements of the form `X implies Y', and to show, rigorously, why
they're true.  The statement makes no assertions about whether the
hypothesis X is true in any particular circumstance, just that when it
*is* true, Y is necessarily a consequence.

In the particular case under discussion, the assumption X is that our
adversary cannot factor a given BBS modulus, and the consequence is that
the BBS generator with that modulus is unpredictable by that adversary.

There is a technique common in mathematics named `reductio ad
absurdum', or `proof by contradiction', where one assumes the converse
of what is intended to be proven, and deduces a result which contradicts
its hypothesis.

We can apply this technique to the current situation.  Consider a Blum
integer n, and an adversary A who is unable to factor n.  Then A cannot
find a cycle in the output of the BBS generator.  We prove this by
contradiction by demonstrating that, if A finds a cycle, he can factor
n.  Since the base we're working on states that A can't factor n,
something must have gone wrong.  The only thing which might be wrong is
the assumption that A could find a short cycle.  The result follows.

What the foregoing doesn't go into is that finding short cycles might be
a sensible way to go about factoring.  This question is beyond my
abilities as a number theorist to answer, although I'm well aware that
the factoring experts are using a different technique -- the Generalized
Number Field Sieve -- rather than cycle-finding, and I can only conclude
that cycle-finding isn't a realistic factoring method.

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:10:56 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3950f6f7.5997676@news.io.com>
References: <slrn8l13bm.pij.mdw@mull.ncipher.com>
Newsgroups: sci.crypt
Lines: 103

On 21 Jun 2000 09:40:07 GMT, in <slrn8l13bm.pij.mdw@mull.ncipher.com>,
in sci.crypt mdw@nsict.org (Mark Wooding) wrote:

>Terry Ritter <ritter@io.com> wrote:
>
>> in sci.crypt mdw@nsict.org (Mark Wooding) wrote:
>>
>> >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.
>> 
>> I have no idea what that could possibly mean.  If the assumption is
>> contradicted, surely we cannot say the proof stands.  Unless, of
>> course, we see "proof" as a mere manipulation of symbols, as opposed
>> to the correct conclusion.
>
>It seems perfectly reasonable to me, as an ex-mathematician, to make
>statements of the form `X implies Y', and to show, rigorously, why
>they're true.  The statement makes no assertions about whether the
>hypothesis X is true in any particular circumstance, just that when it
>*is* true, Y is necessarily a consequence.
>
>In the particular case under discussion, the assumption X is that our
>adversary cannot factor a given BBS modulus, and the consequence is that
>the BBS generator with that modulus is unpredictable by that adversary.

As a non-specialist, that sounds to me like a very coarse and
broad-stroked approach.  Indeed, the idea of starting out by assuming
our ultimate goal sounds quite dangerous to the forming of correct
logical conclusions.  In fact, it sounds almost circular.  

One problem is that such a proof tends to gloss over nasty facts with
no indication of their existence.  There is no hint that short cycles
exist.  Even though finding a short cycle would violate the
fundamental assumption, there is no sub-assumption which would prevent
one from finding the short cycles which do in fact exist.  So finding
short cycles will happen.  

While "improbable" means "almost never," it also means "must occur
sometime."  As soon as we introduce probability we must allow for
every *possibility* to occur.  So even though it is *improbable* to
select a short cycle, that *must* occur, sometime.  But that allows
factoring N, and for some reason we don't get: "Oh, the assumption
must be false." 

One might well think that the whole point of proofs based on
assumption is that we can develop implications of the assumption, and
then if the implications are shown false, the assumption also must be
false, end of story.  But here we have, "Oh, no, the facts must be
wrong because if the assumption is false the sky will fall."  As a
non-mathematician, it sounds to me like we have stepped outside of
mathematics.  I think we have shown the assumption false, or at least
that it does not hold unconditionally, as stated.  

>There is a technique common in mathematics named `reductio ad
>absurdum', or `proof by contradiction', where one assumes the converse
>of what is intended to be proven, and deduces a result which contradicts
>its hypothesis.
>
>We can apply this technique to the current situation.  Consider a Blum
>integer n, and an adversary A who is unable to factor n.  Then A cannot
>find a cycle in the output of the BBS generator.  We prove this by
>contradiction by demonstrating that, if A finds a cycle, he can factor
>n.  Since the base we're working on states that A can't factor n,
>something must have gone wrong.  The only thing which might be wrong is
>the assumption that A could find a short cycle.  The result follows.

That sounds wrong to me.  You claim to have proven that short cycles
cannot "be found," but I think you have proven that short cycles
cannot exist, which is clearly false.  

If short cycles exist, they will be used, albeit with low probability,
unless that is prevented.  But even a low probability of use is still
use.  Short cycles will be used and when they are that will allow
factoring N.  Since the assumption disallows that, the assumption is
false.  

And since very, very unlikely is *not* the same as impossible, I want
to know where the explicit assumption is that made that so.  Unless an
assumption is explicit, we have no chance to decide whether it is
really something we want to assume.  And I do not.  

>What the foregoing doesn't go into is that finding short cycles might be
>a sensible way to go about factoring.  This question is beyond my
>abilities as a number theorist to answer, although I'm well aware that
>the factoring experts are using a different technique -- the Generalized
>Number Field Sieve -- rather than cycle-finding, and I can only conclude
>that cycle-finding isn't a realistic factoring method.

I agree.  None of this is about practical strength.  But it *is* about
a claim of having "proven security."  

One problem with proofs is that we can prove almost anything.  The
resulting conclusion can have no consequence whatsoever and we still
may have a "proof" of it.   

---
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: 22 Jun 2000 09:50:47 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8l3obm.r8a.mdw@mull.ncipher.com>
References: <3950f6f7.5997676@news.io.com>
Newsgroups: sci.crypt
Lines: 132

Terry Ritter <ritter@io.com> wrote:
> in sci.crypt mdw@nsict.org (Mark Wooding) wrote:
>
> >In the particular case under discussion, the assumption X is that our
> >adversary cannot factor a given BBS modulus, and the consequence is that
> >the BBS generator with that modulus is unpredictable by that adversary.
> 
> As a non-specialist, that sounds to me like a very coarse and
> broad-stroked approach.  Indeed, the idea of starting out by assuming
> our ultimate goal sounds quite dangerous to the forming of correct
> logical conclusions.  In fact, it sounds almost circular.  

Where did I start with the ultimate goal?

The Integer Factoring Problem, and its close relatives the Quadratic
Residuosity Problem and the Square Root Problem, are well known
reference problems in public-key cryptography.  We don't have proofs
that any particular reference problem is actually difficult, but, like
the various Discrete Logarithm Problems, they're about as good as we can
get right now.

The demonstration I alluded to above is that, *given* the difficulty of
IFP (or, actually QRP), we can produce a random number generator whose
output is unpredictable.  Or, more precisely, if n is a Blum integer,
and A is an adversary unable to factor n, then the BBS generator mod n
is unpredictable by A.

The *premise* is the difficulty of our reference problem, i.e., that
factoring is `too hard' for our adversary.  The *goal* is to produce a
random number generator with unpredictable output.

> One problem is that such a proof tends to gloss over nasty facts with
> no indication of their existence.  There is no hint that short cycles
> exist.  Even though finding a short cycle would violate the
> fundamental assumption, there is no sub-assumption which would prevent
> one from finding the short cycles which do in fact exist.  So finding
> short cycles will happen.

That's the point: there doesn't need to be a `sub-assumption'.  See
where I get frustrated enough to blow some dust off my symbolic logic
below... ;-)

> While "improbable" means "almost never," it also means "must occur
> sometime."  As soon as we introduce probability we must allow for
> every *possibility* to occur.  So even though it is *improbable* to
> select a short cycle, that *must* occur, sometime.  But that allows
> factoring N, and for some reason we don't get: "Oh, the assumption
> must be false."

There's a subtle difference between an assumption and a hypothesis.  In
this case, we are hypothesizing the difficulty of the reference Integer
Factoring Problem.  If we then assume that the adversary can find a
short cycle, we find that he can factor, the hypothesis being thereby
contradicted.  The hypothesis stands and the assumption fails; thus, we
conclude that the adversary cannot find short cycles.  We keep our
hypothesis because it's reasonable: we don't actually have a good way of
factoring.

> One might well think that the whole point of proofs based on
> assumption is that we can develop implications of the assumption, and
> then if the implications are shown false, the assumption also must be
> false, end of story.  But here we have, "Oh, no, the facts must be
> wrong because if the assumption is false the sky will fall."  As a
> non-mathematician, it sounds to me like we have stepped outside of
> mathematics.  I think we have shown the assumption false, or at least
> that it does not hold unconditionally, as stated.

OK, I'll try a slightly different approach.  Let F_A(n) be the statement
that A can factor n, and let C_A(n) be the statement that A can find
cycles in the BBS generator mod n.  We have shown that if A can find a
cycle, he can factor.  We can write that as C_A(n) => F_A(n).  This is
equivalent to saying that !F_A(n) => !C_A(n) -- I can trundle through
the formal proof, but it's not very interesting.  Now, our initial
hypothesis is that factoring is hard; i.e., !F_A(n).  You can tell me
the conclusion.

> >There is a technique common in mathematics named `reductio ad
> >absurdum', or `proof by contradiction', where one assumes the converse
> >of what is intended to be proven, and deduces a result which contradicts
> >its hypothesis.
> >
> >We can apply this technique to the current situation.  Consider a Blum
> >integer n, and an adversary A who is unable to factor n.  Then A cannot
> >find a cycle in the output of the BBS generator.  We prove this by
> >contradiction by demonstrating that, if A finds a cycle, he can factor
> >n.  Since the base we're working on states that A can't factor n,
> >something must have gone wrong.  The only thing which might be wrong is
> >the assumption that A could find a short cycle.  The result follows.
> 
> That sounds wrong to me.  You claim to have proven that short cycles
> cannot "be found," but I think you have proven that short cycles
> cannot exist, which is clearly false.

No.  It's obvious that cycles exist, since the quadratic residues mod n
are a finite set and the mapping x |-> x^2 is a permutation.  (I've
proved this fact in a separate article; it would be silly to deny it.)
However, our adversary, who isn't `allowed' to be able to factor the
modulus, can't find any.  (Note that, actually, it's not just short
cycles he's not able to find: it's *any cycle at all*.)

> If short cycles exist, they will be used, albeit with low probability,
> unless that is prevented.  But even a low probability of use is still
> use.  Short cycles will be used and when they are that will allow
> factoring N.  Since the assumption disallows that, the assumption is
> false.

Intriguingly, I think we're actually looking at the BBS generator from
different starting points.  You're looking at it from the standpoint of
a single user who's just generating random bits for some reason.  I'm
looking at it from the angle of the Blum-Goldwasser public-key
cryptosystem, where the modulus is *public*.  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.  But I'm
happy that the security of the system rests on the difficulty of the
QRP.

Of course, when we use the BG system, the starting seed must be chosen
by a user who doesn't know the factors of n, and can't carefully pick
`good' seeds.  This doesn't matter: BG is still strong, except against a
chosen ciphertext attack.

> And since very, very unlikely is *not* the same as impossible, I want
> to know where the explicit assumption is that made that so.  Unless an
> assumption is explicit, we have no chance to decide whether it is
> really something we want to assume.  And I do not.

The explicit assumption, and it really is very explicit, is that the
Integer Factoring Problem, is too difficult for an adversary.  That's
all we need.  We really do have a solid proof that predicting a BBS
generator is as hard as factoring.

-- [mdw]

Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 11:02:20 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8iobjc$ol7$1@blowfish.isaac.cs.berkeley.edu>
References: <394F96CE.B747129B@cic-mail.lanl.gov>
Newsgroups: sci.crypt
Lines: 9

In article <394F96CE.B747129B@cic-mail.lanl.gov>,
Tony T. Warnock <ttw@lanl.gov> wrote:
> I think people are missing the point here. 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.

I think I got the point pretty well.  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.

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:22:02 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394fa82d.6283727@news.io.com>
References: <8invb8$9n9$1@bambi.zdv.Uni-Mainz.DE>
Newsgroups: sci.crypt
Lines: 51

On 20 Jun 2000 14:33:12 GMT, in <8invb8$9n9$1@bambi.zdv.Uni-Mainz.DE>,
in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:

>In <394ec029.4137859@news.io.com> Terry Ritter wrote:
>> The short cycle weakness is a weakness which does not have to exist,
>> but which is normally allowed to exist.  The fact that this additional
>> weakness possibility is not eliminated is sufficient to show that any
>> resulting system cannot be "proven secure."  End of story.   
>> 
>So what do you think of RSA?

I have enough on my plate discussing BB&S.  What do *you* think of the
last 2/3 of the BB&S article?

>There you also have short cycles, and you can't avoid
>them, because they come from the plain text, not from the
>key. Remember the iterative attack?
>
>[Assume m = plain text, c = cipher text, E = public encryption function]
>
>If c = E(m), then consider the cycle E(c), E(E(c)), E(E(E(c))),
>..., until E^s(c) = c. Now m = E^{s-1}(c).
>Hey - we have broken *every* public key encryption.
>
>"The fact that this additional weakness possibility is not
>eliminated is sufficient to show" ... that asymmetric encryption
>cannot be proven secure.
>
>By the way - finding a key for a symmetric128 bit encryption
>by pure guessing has a much higher success probability than
>running into a cycle for BBS or RSA with 1024 bit modulus.
>
>Therefore symmetric encryption also cannot be proven secure.
>End of story.

The concept of a key is the essence of cipher-based cryptography, and
we have no ciphers which are not vulnerable to key guessing.  Changing
that is not under our control, so:  

*  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.

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

	<8invb8$9n9$1@bambi.zdv.Uni-Mainz.DE> <394fa82d.6283727@news.io.com>
Cc: ritter@io.com

Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 08:16:56 GMT
From: pom@imsd.uni-mainz.de (Klaus Pommerening)
Message-ID: <8iptlo$o3o$2@bambi.zdv.Uni-Mainz.DE>
References: <394ec029.4137859@news.io.com>
Newsgroups: sci.crypt
Lines: 12

In <394fa82d.6283727@news.io.com> Terry Ritter wrote:
> *  We *can* build a generator which does not use short cycles.  
> 
BTW the BBS generator outputs the LSB of its internal state
x_i for each step. (x_i = x_{i-1}^2 mod n)
Is there any known result that some choice of parameters in BBS
guarantees that the LSBs don't give short cycles?
-- 
Klaus Pommerening  [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:11:07 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3950f724.6042366@news.io.com>
References: <8iptlo$o3o$2@bambi.zdv.Uni-Mainz.DE>
Newsgroups: sci.crypt
Lines: 20

On 21 Jun 2000 08:16:56 GMT, in <8iptlo$o3o$2@bambi.zdv.Uni-Mainz.DE>,
in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:

>In <394fa82d.6283727@news.io.com> Terry Ritter wrote:
>> *  We *can* build a generator which does not use short cycles.  
>> 
>BTW the BBS generator outputs the LSB of its internal state
>x_i for each step. (x_i = x_{i-1}^2 mod n)
>Is there any known result that some choice of parameters in BBS
>guarantees that the LSBs don't give short cycles?

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.   

---
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, 21 Jun 2000 20:03:57 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <3951038D.2B802AF8@t-online.de>
References: <3950f724.6042366@news.io.com>
Newsgroups: sci.crypt
Lines: 27

Terry Ritter wrote:

> pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:
>
> >In <394fa82d.6283727@news.io.com> Terry Ritter wrote:
> >> *  We *can* build a generator which does not use short cycles.
> >>
> >BTW the BBS generator outputs the LSB of its internal state
> >x_i for each step. (x_i = x_{i-1}^2 mod n)
> >Is there any known result that some choice of parameters in BBS
> >guarantees that the LSBs don't give short cycles?
>
> 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.

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. I seems that my
'assumption' was not fully justified. Could some experts please
clarify the present certainly very essential issue? Thanks.

M. K. Shen

Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 23:56:53 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FwJ3us.Anz@bath.ac.uk>
References: <3950f724.6042366@news.io.com>
Newsgroups: sci.crypt
Lines: 36

Terry Ritter <ritter@io.com> wrote:
: in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:
:>In <394fa82d.6283727@news.io.com> Terry Ritter wrote:

:>> *  We *can* build a generator which does not use short cycles.  
:>
:>BTW the BBS generator outputs the LSB of its internal state
:>x_i for each step. (x_i = x_{i-1}^2 mod n)
:>Is there any known result that some choice of parameters in BBS
:>guarantees that the LSBs don't give short cycles?

: 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.

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.

*If* the cycle were known to be large enough this would be impossible,
though a shortage of such states.  c > S/2 - assuming one bit is output.

If you output more than 1 bit this approach would not work - since you
have some other possible cycle lengths (related to the number of bits
output) to check for.

I don't know if c >= min(p,q) is in some sense "good enough" :-|

Alternatively - if this was admitted to be a possibility - it /might/
still be possible to retain a security proof that eliminated the
possibility of bad seeds by the use of a usually-rapidly-terminating test
that rejected what appear to be all-0 and all-1 streams as potential
problem cases :-/
-- 
__________  Lotus Artificial Life  http://alife.co.uk/  tt@cryogen.com
 |im |yler  The Mandala Centre   http://mandala.co.uk/  Namaste.

Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 22 Jun 2000 09:29:58 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <3951C076.7D9357F9@t-online.de>
References: <FwJ3us.Anz@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 31

Tim Tyler wrote:

> Terry Ritter <ritter@io.com> wrote:
> : in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:
> :>In <394fa82d.6283727@news.io.com> Terry Ritter wrote:
>
> :>> *  We *can* build a generator which does not use short cycles.
> :>
> :>BTW the BBS generator outputs the LSB of its internal state
> :>x_i for each step. (x_i = x_{i-1}^2 mod n)
> :>Is there any known result that some choice of parameters in BBS
> :>guarantees that the LSBs don't give short cycles?
>
> : 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.
>
> 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.

This is not valid. If there is cycle of length c, then the period length of
the lowest bit can never be longer than c. 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.

M. K. Shen

Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 11:02:16 -0700
From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner)
Message-ID: <8iqvv8$pis$1@blowfish.isaac.cs.berkeley.edu>
References: <8iptlo$o3o$2@bambi.zdv.Uni-Mainz.DE>
Newsgroups: sci.crypt
Lines: 12

In article <8iptlo$o3o$2@bambi.zdv.Uni-Mainz.DE>,
Klaus Pommerening <pom@imsd.uni-mainz.de> wrote:
> BTW the BBS generator outputs the LSB of its internal state
> x_i for each step. (x_i = x_{i-1}^2 mod n)
> Is there any known result that some choice of parameters in BBS
> guarantees that the LSBs don't give short cycles?

Guarantees?  No, not that I know of.
But, since the LSBs are indistinguishable from random bits
(assuming factoring is hard), the LSBs have no better chance
of cycling than random bits would.  And, random bits have a
very low chance of cycling...

Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 07:20:09 -0000
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Message-ID: <20000620072009.7245.qmail@nym.alias.net>
References: <d04bc19681191c848535d3c1dbb5d838@anonymous.poster>
Newsgroups: sci.crypt
Lines: 76

David Wagner wrote:
> In article <394ec029.4137859@news.io.com>, Terry Ritter <ritter@io.com> wrote:
> > And you have not been able to describe *your* position at all.  Do you
> > imagine that short cycles do or do not exist in BB&S constructions?
> > Do you imagine that using such a cycle would be weak or not?  Do you
> > imagine that it is actually impossible for a short cycle to be
> > selected?
>
> I think it was already clear, but I'll answer your questions.
>
> Yes, short cycles exist in BB&S.  Yes, using such a cycle would be weak.
> No, it is not impossible to encounter such a cycle.  Yes, BB&S is provably
> secure (under appropriate assumptions and definitions).  There is no
> contradiction here.

To expand on this:

The proof of security says this: if x_0 is chosen at random from among
quadratic residues, the BBS sequence starting from x_0 is as secure as
deciding quadratic reciduosity.  This is the proof of security you get
with the BBS - no more, no less.

It doesn't say that the RNG is secure.  It doesn't say that it can't
be predicted.  What it says is, IF the RNG is insecure, IF it can
be predicted, THEN you can build an algorithm to decide quadratic
reciduosity.  Effectively this is the same as saying that you can factor
RSA moduli of this form.

Your proof of security is essentially that if the RNG can be predicted,
you can factor the modulus.  The informal proofs seen here apply to the
special case where you predict the RNG by finding a cycle.  This is a
simpler case than what BBS consider, and the proof is elementary.

You can turn this proof around and say, if you believe that a given Blum
modulus is safe against factoring, then it follows that it is equally
safe against predicting the BBS sequence.

You get this proven security simply by choosing a Blum modulus and a
random starting point.  That's all the proof requires.

This is why David says that BBS is provably secure, even though cycles
exist.  It is because the proof of security, the equivalence to quadratic
reciduosity, is not affected by the presence of cycles.

Obviously if short cycles exist, you can predict the RNG.  It follows
by the BBS proof, and the short demonstrations posted here, that you
can factor the modulus.

If you think you need to pick a special modulus to avoid short cycles,
that means that you think you need to pick a special modulus to avoid
it being factored.  The two weaknesses are equivalent.

You cannot consistently advise people to choose special moduli for BBS
without advising them to choose those same moduli for RSA.  And then
when you are asked to justify this advice with regard to RSA, there is
nothing you can say.

And your suggestion to choose the seed carefully is completely absurd.
Your opponent can choose his own seeds!  If you have to be careful
picking your seed so that you don't accidentally get one with a short
cycle, the game is already lost.  Your opponent can pick as many seeds
as he likes, and check all of them for cycles.

There is nothing you can do to strengthen your RNG by picking a special
seed, because your opponent is not limited to your choices.  If you
think short cycles are a risk, then he could find a short cycle, factor
the modulus, and you have lost your security.  You gain no benefits
whatsoever by carefully choosing a seed.

Obviously Terry Ritter is not going to be convinced by these arguments.
Years of frustrating debate have established that.  The hope is that other
readers will come to a clearer understanding of exactly what proof of
security is provided by BBS.  They will then see why such authoritative
references as RFC 1750 describe the RNG in its simple form, without
the elaborate additional checks and precautions which Terry Ritter has
claimed are necessary.

Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 17:22:54 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <394fa83e.6300080@news.io.com>
References: <20000620072009.7245.qmail@nym.alias.net>
Newsgroups: sci.crypt
Lines: 51

On 20 Jun 2000 07:20:09 -0000, in
<20000620072009.7245.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster
Remailer <mix@anon.lcs.mit.edu> wrote:

>[...]
>Obviously Terry Ritter is not going to be convinced by these arguments.
>Years of frustrating debate have established that.  

The reason I am not going to be convinced by these arguments is that
they lead to the implication that black is white, and down is up, and
when that happens, the arguments are wrong no matter how crafty they
may be.

Fundamentally here, we have the use of "proven secure" as a "term of
art" while exactly the same phrase describes the long preceding
ultimate goal of cipher-based cryptography.  This one phrase thus has
different meanings depending on context, but the context is rarely
preserved, and that makes the general claim deceptive.  Deceptive
claims are particularly convenient when dealing with those who are not
skilled in the art, such as newbies, managers and managing directors.

A system with known, preventable weakness, no matter how small, is
different than the same system without that weakness.  Using the same
description for both is a travesty and an embarrassment.  

>The hope is that other
>readers will come to a clearer understanding of exactly what proof of
>security is provided by BBS.  They will then see why such authoritative
>references as RFC 1750 describe the RNG in its simple form, without
>the elaborate additional checks and precautions which Terry Ritter has
>claimed are necessary.

Weren't you just saying that *my* arguments weren't scientific?  Since
slurs and deliberate mis-slants are *your* idea of argument, it is no
wonder that my arguments don't seem fair to you.  It is sad, really.

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.

---
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: 20 Jun 2000 21:00:09 -0000
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Message-ID: <20000620210009.17843.qmail@nym.alias.net>
References: <d04bc19681191c848535d3c1dbb5d838@anonymous.poster>
Newsgroups: sci.crypt
Lines: 23

Terry Ritter writes:
> I do have a different model, but it is not a model of computation.  My
> model is what I perceive as the basis for the entire field of
> cryptography:  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.  The general unqualified use of it as a term-of-art is
> deceptive to newbies, managers, and managing directors.  It might even
> be seen as a marketing term.  

You are the main person spreading the misinformation that BBS is "proven
secure" in your bizarre sense if you use special primes and seeds.
Do you honestly think that doing so makes for an RNG which is "secure
against any possible attack" (your words)?  What about factoring?
Isn't that a possible attack?

The fact is, the proof of security with BBS is what is standard in
cryptography.  It is a reduction proof.  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".

Only a fool would make a claim like that.

Terry Ritter, his current address, and his top page.

Last updated: 2001-06-20