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.

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: Xi+1 := Xi2 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.


Contents


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