After a decade of discussion and sci.crypt messages probably numbering in the thousands, we finally have a reasonable way to provably eliminate the (extremely low) possibility of using a short cycle in BB&S. This requires us to go beyond current cryptographic practice and use the special primes construction as described in the original article:
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.Blum, L., M. Blum and M. Shub. 1986. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing. 15: 364-383.
Construct N as the product of two large distinct primes, P and Q.
Both P and Q must be congruent to
The special primes construction apparently assures that we have only "long enough" cycles and degenerate cycles. Then we can choose our seed x0 at random, and check to see that we have not selected a degenerate cycle. See the messages, culminating with a prescription: 2001-06-26 Terry Ritter.
Subject: Seed selection in Blum Blum Shub generators. Date: Tue, 19 Jun 2001 23:04:52 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Message-ID: <20010619230452.A1216@home.com> Newsgroups: sci.crypt Lines: 29 While reading http://www.io.com/~ritter/NEWS2/94061801.HTM I came across the following comment regarding the selection of the initial seed in a BBS generator: "Thus, a BB&S generator cannot be initialized with random state, because this state may happen to be on a short cycle. If this were allowed, the resulting sequence would become "predictable" as soon as the cycle started to repeat." "This is prevented in a *real* BB&S design by mathematical proof showing that such a design will have a long cycle of a predictable length (given certain strenuous conditions on N), *and* by using the algorithm in Section 9 (Algorithms for determining length of period and random accessing) to show that an initial state (X0) is on such a cycle." Immediately above these paragraphs Terry shows a simple example of the short cycles that can result from poor seed selection. Later in the paper he talks about the proper selection of P and Q. The problem is that I don't have a copy of the original paper and don't know how to go about verifying that my initial seed isn't on a short cycle when P and Q are large (> 1024 bits). Generating the large P and Q that satisfy the "special" properties isn't a problem (time isn't an issue for my specific application.) Verifying that the initial seed is good has got me stumped though. Any advice and/or pointers to information I overlooked would be greatly appreciated.
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Wed, 20 Jun 2001 04:52:59 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b302b78.5993797@news.io.com> References: <20010619230452.A1216@home.com> Newsgroups: sci.crypt Lines: 69 On Tue, 19 Jun 2001 23:04:52 -0400, in <20010619230452.A1216@home.com>, in sci.crypt Mixtim <Use-Author-Address-Header@[127.1]> wrote: >While reading http://www.io.com/~ritter/NEWS2/94061801.HTM I came across >the following comment regarding the selection of the initial seed in a >BBS generator: > > "Thus, a BB&S generator cannot be initialized with random state, > because this state may happen to be on a short cycle. If this were > allowed, the resulting sequence would become "predictable" as soon > as the cycle started to repeat." > > "This is prevented in a *real* BB&S design by mathematical proof > showing that such a design will have a long cycle of a predictable > length (given certain strenuous conditions on N), *and* by using the > algorithm in Section 9 (Algorithms for determining length of period > and random accessing) to show that an initial state (X0) is on such > a cycle." > >Immediately above these paragraphs Terry shows a simple example of the >short cycles that can result from poor seed selection. Later in the >paper he talks about the proper selection of P and Q. > >The problem is that I don't have a copy of the original paper and don't >know how to go about verifying that my initial seed isn't on a short >cycle when P and Q are large (> 1024 bits). Generating the large P and Q >that satisfy the "special" properties isn't a problem (time isn't an >issue for my specific application.) Verifying that the initial seed is >good has got me stumped though. > >Any advice and/or pointers to information I overlooked would be greatly >appreciated. First of all, in practice, the short cycle weakness is not usually considered an issue worth defending against. Of course, BB&S is rarely used in practice anyway. My problem in BB&S conversations over many years basically is the use of the moniker "proven secure" for a system which obviously does have a potential weakness (and one which was avoided in the original article). The math crypto guys say this is no contradiction, once we understand what the security proof actually is. Apparently the security guarantee is that no weakness exists which is easier than, say, factoring N. Yet I am reluctant to accept a security proof which includes a *known* possibility of weakness which can be avoided. Almost a decade ago, I had an e-mail conversation with Robert Eachus, who suggested the following: We use the "special primes" construction for P and Q of public-key size, and then check that x is not degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but 23 is not degenerate. Why?) But we don't need much analysis, because finding a degenerate cycle is easy: choose x at random, take a step, record that result, then step again. If the result is the same, start over with a new x. Supposedly the special-primes construction allows us to analyze the other cycles in the system, which are all found to be "long enough" for use. So we just use whatever comes up. That should simplify things considerably, even though special primes are substantially harder to find than ordinary primes. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 22:03:37 +0200 From: "Cristiano" <cristiano.p@mclink.it> Message-ID: <9gtjus$c3u$1@news.mclink.it> References: <3b302b78.5993797@news.io.com> Newsgroups: sci.crypt Lines: 16 "Terry Ritter" <ritter@io.com> wrote: .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, .> who suggested the following: We use the "special primes" construction .> for P and Q of public-key size, and then check that x is not .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but .> 23 is not degenerate. Why?) But we don't need much analysis, because .> finding a degenerate cycle is easy: choose x at random, take a step, .> record that result, then step again. If the result is the same, start .> over with a new x. But if the cycle is long only 3, 4 or 5 is not too short? Cristiano
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 20:39:35 GMT From: Tom St Denis <tomstdenis@yahoo.com> Message-ID: <3B325B91.9190CF2F@yahoo.com> References: <9gtjus$c3u$1@news.mclink.it> Newsgroups: sci.crypt Lines: 19 Cristiano wrote: > > "Terry Ritter" <ritter@io.com> wrote: > .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, > .> who suggested the following: We use the "special primes" construction > .> for P and Q of public-key size, and then check that x is not > .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 > .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but > .> 23 is not degenerate. Why?) But we don't need much analysis, because > .> finding a degenerate cycle is easy: choose x at random, take a step, > .> record that result, then step again. If the result is the same, start > .> over with a new x. > > But if the cycle is long only 3, 4 or 5 is not too short? You're onto it. There is no proof of cycle length, nor any proof of the entropy in the output. Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 23:02:27 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b327bad.3282601@news.io.com> References: <3B325B91.9190CF2F@yahoo.com> Newsgroups: sci.crypt Lines: 34 On Thu, 21 Jun 2001 20:39:35 GMT, in <3B325B91.9190CF2F@yahoo.com>, in sci.crypt Tom St Denis <tomstdenis@yahoo.com> wrote: >Cristiano wrote: >> >> "Terry Ritter" <ritter@io.com> wrote: >> .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, >> .> who suggested the following: We use the "special primes" construction >> .> for P and Q of public-key size, and then check that x is not >> .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 >> .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but >> .> 23 is not degenerate. Why?) But we don't need much analysis, because >> .> finding a degenerate cycle is easy: choose x at random, take a step, >> .> record that result, then step again. If the result is the same, start >> .> over with a new x. >> >> But if the cycle is long only 3, 4 or 5 is not too short? > >You're onto it. There is no proof of cycle length, nor any proof of the >entropy in the output. Apparently, given the special primes construction, the resulting cycle lengths do not occur at random but are instead controlled by the construction itself. Eachus said the cycle lengths *can* be proven to consist only of degenerate cycles and "long enough" cycles (assuming huge special primes). (The "short cycles" *are* "relatively" short, but actually very long.) So, once we eliminate the use of degenerate cycles, whatever we get is fine. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 23:25:38 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <SnvY6.7734$St6.1009632@news3.rdc1.on.home.com> References: <3b327bad.3282601@news.io.com> Newsgroups: sci.crypt Lines: 52 "Terry Ritter" <ritter@io.com> wrote in message news:3b327bad.3282601@news.io.com... > > On Thu, 21 Jun 2001 20:39:35 GMT, in <3B325B91.9190CF2F@yahoo.com>, in > sci.crypt Tom St Denis <tomstdenis@yahoo.com> wrote: > > >Cristiano wrote: > >> > >> "Terry Ritter" <ritter@io.com> wrote: > >> .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, > >> .> who suggested the following: We use the "special primes" construction > >> .> for P and Q of public-key size, and then check that x is not > >> .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 > >> .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but > >> .> 23 is not degenerate. Why?) But we don't need much analysis, because > >> .> finding a degenerate cycle is easy: choose x at random, take a step, > >> .> record that result, then step again. If the result is the same, start > >> .> over with a new x. > >> > >> But if the cycle is long only 3, 4 or 5 is not too short? > > > >You're onto it. There is no proof of cycle length, nor any proof of the > >entropy in the output. > > Apparently, given the special primes construction, the resulting cycle > lengths do not occur at random but are instead controlled by the > construction itself. Eachus said the cycle lengths *can* be proven to > consist only of degenerate cycles and "long enough" cycles (assuming > huge special primes). (The "short cycles" *are* "relatively" short, > but actually very long.) So, once we eliminate the use of degenerate > cycles, whatever we get is fine. Well a degenerate cycle and short cycle are in fact different types of cycles. A => B => B is degenerate. A => B => ...lots more times => A is a "short" cycle [assume 'lots more times' is not an exceedingly large # of times]. We probably can avoid the former but I am certain no method exists to avoid the latter. Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: 22 Jun 2001 14:38:36 GMT From: mdw@nsict.org (Mark Wooding) Message-ID: <slrn9j6m3b.clo.mdw@daryl.nsict.org> References: <SnvY6.7734$St6.1009632@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 51 Tom St Denis <tomstdenis@yahoo.com> wrote: > We probably can avoid the former but I am certain no method exists to avoid > the latter. You're talking rubbish (and not trimming your quotes). The cycle length is related to the order of the starting element (actually, to the order of 2 mod the order of...) I don't think it takes a great deal of imagination to see that, if the maximum cycle length has only large prime factors (and maybe a few tiny ones), it's very easy to check for a cycle which has length product-of-only-tiny- factors and once you've done that, you know that the cycle length must be at least as large as your smallest large prime. Doing this properly-ish... Let n = p q. Let's look at cycle length for x |-> x^2 mod p. (mod q will be completely symmetrical, and then we combine the cycle lengths with lcm if we really care.) A cycle will have the form x, x^2, x^{2^2}, x^{2^3}, ..., x^{2^k} = x. If we write the order of x mod n as ord_n(x), we see that we've found that 2^k = 1 (mod ord_p(x)), i.e., k = ord_{ord_p(x)}(2). We'd like k to be either tiny (so we notice) or enormous (so we're safe). As a first cut, choose p = 2 r + 1 where r is prime. Then ord_p(x) is one of: 1, 2, r, 2 r. ord_p(x) = 1 only happens when x = 1, and ord_p(x) = 2 only happens when x = p - 1, so don't do that. Now we look at the order of 2 mod ord_p(x). It must be a factor of \lambda(ord_p(x)), which (by design) is r - 1. If we choose r = 2 s + 1 where s is also prime. Then we know that the cycle length is either 1, 2 or huge. There are very few primes p of this sort. Finding them is a lot of work. However, if we decide that t is a good minimum cycle length then we can use an approach similar to the Lim-Lee construction: we can choose a pool of primes s_i >= t such that r_i = 2 s_i + 1 is prime, and then choose p, q = 2 \prod_i r_i^{c_i} + 1 for appropriately chosen c_i \in {0, 1}. If we're not too ambitious with t, then finding the s_i isn't a vast amount of work and constructing p and q is fairly easy. Of course, this is all a bit of a waste of effort. p - 1 is unlikely to be particularly smooth, and the order of any element x mod p will probably have a large prime factor r. Similarly, the order of 2 mod ord_x(p) will probably be large (because r - 1 probably has a large prime factor). I'm sure that better number theorists than I can put proper numbers on my handwaving here. -- [mdw]
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Fri, 22 Jun 2001 20:11:38 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <_DNY6.2050$Mf5.741678@news3.rdc1.on.home.com> References: <slrn9j6m3b.clo.mdw@daryl.nsict.org> Newsgroups: sci.crypt Lines: 85 "Mark Wooding" <mdw@nsict.org> wrote in message news:slrn9j6m3b.clo.mdw@daryl.nsict.org... > Tom St Denis <tomstdenis@yahoo.com> wrote: > > > We probably can avoid the former but I am certain no method exists to avoid > > the latter. > > You're talking rubbish (and not trimming your quotes). Rubbish... hehehe > The cycle length is related to the order of the starting element > (actually, to the order of 2 mod the order of...) I don't think it > takes a great deal of imagination to see that, if the maximum cycle > length has only large prime factors (and maybe a few tiny ones), it's > very easy to check for a cycle which has length product-of-only-tiny- > factors and once you've done that, you know that the cycle length must > be at least as large as your smallest large prime. > > Doing this properly-ish... > > Let n = p q. Let's look at cycle length for x |-> x^2 mod p. (mod q > will be completely symmetrical, and then we combine the cycle lengths > with lcm if we really care.) > > A cycle will have the form x, x^2, x^{2^2}, x^{2^3}, ..., x^{2^k} = x. > If we write the order of x mod n as ord_n(x), we see that we've found > that 2^k = 1 (mod ord_p(x)), i.e., k = ord_{ord_p(x)}(2). We'd like k > to be either tiny (so we notice) or enormous (so we're safe). This is nonce. There is no reason to suggest that the cycle won't have a leading edge... try p = 7 q = 11 x = 7 you get 7, [49, 14, 42, 70] Where 7 is never repeated. Not only that but the lsb is biased [P(X=0) = 3/4] > As a first cut, choose p = 2 r + 1 where r is prime. Then ord_p(x) is > one of: 1, 2, r, 2 r. ord_p(x) = 1 only happens when x = 1, and > ord_p(x) = 2 only happens when x = p - 1, so don't do that. <snip> This theory only applies if you are multiplying a base repeatedly... i.e b^1, b^2, b^3, b^4, ... Doing (b^2), b^4, b^8, b^16 with BBS is not guaranteed to be secure since a user will not know if b is a primitive [or at least long perioded] generator. Not only that but just toying around with BBS lends me to think it's none to good. I tried about 13 diff bases for pq = 77, and none of them had a period over 4 elements and some were very degernerate. like 22^2 mod 77 = 22. I would imagine that the cycles are longer as you get up there, but unless you pick a generator as your base the period is not guaranteed at all. Let's say that you have pq = 768 bit number. such that p,q are 384 bits each. Let's suppose both p and q are strong primes. Then some base will have a period of 1, 2, 4, p-1, q-1, 2p - 2, 2q- 2, (q-1)(p-1), 2(q-1)(p-1) or 4(q-1)(p - 1) [I forgot a few but you get the point] Let's say some base G makes a sub-group of order p-1. this is a group with 2^384 elements. In order for the period of G to be maximal in the sub-group, 2 must be a primitive element modulo p-1, which clearly can't be since p-1 is even. We require 2 to be a primitive element since we are doing 2^k mod p-1. Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Fri, 22 Jun 2001 23:59:59 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B33CDEF.607032B7@zetnet.co.uk> References: <_DNY6.2050$Mf5.741678@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 80 -----BEGIN PGP SIGNED MESSAGE----- Tom St Denis wrote: > "Mark Wooding" <mdw@nsict.org> wrote in message > news:slrn9j6m3b.clo.mdw@daryl.nsict.org... > > Doing this properly-ish... > > > > Let n = p q. Let's look at cycle length for x |-> x^2 mod p. (mod q > > will be completely symmetrical, and then we combine the cycle lengths > > with lcm if we really care.) > > > > A cycle will have the form x, x^2, x^{2^2}, x^{2^3}, ..., x^{2^k} = x. > > If we write the order of x mod n as ord_n(x), we see that we've found > > that 2^k = 1 (mod ord_p(x)), i.e., k = ord_{ord_p(x)}(2). We'd like k > > to be either tiny (so we notice) or enormous (so we're safe). > > This is nonce. There is no reason to suggest that the cycle won't have a > leading edge... Think about it more carefully. In the paragraph quoted above, x is an arbitrary element. There's nothing wrong with Mark Wooding's informal proof (although as he says, it isn't really necessary to use this method, since the cycle length is large except with negligable probability anyway). [snip] > Not only that but just toying around with BBS lends me to think it's none to > good. > > I tried about 13 diff bases for pq = 77, and none of them had a period over > 4 elements and some were very degernerate. like 22^2 mod 77 = 22. That isn't surprising, since numbers this size are not difficult to factor. > I would imagine that the cycles are longer as you get up there, but unless > you pick a generator as your base the period is not guaranteed at all. > Let's say that you have pq = 768 bit number. such that p,q are 384 bits > each. Let's suppose both p and q are strong primes. I assume you mean safe primes. > Then some base will > have a period of 1, 2, 4, p-1, q-1, 2p - 2, 2q- 2, (q-1)(p-1), 2(q-1)(p-1) > or 4(q-1)(p - 1) [I forgot a few but you get the point] The possible orders are the factors of the group order lcm(p-1, q-1), i.e. { 1, 2, (p-1)/2, p-1, (q-1)/2, q-1, (p-1)(q-1)/4, (p-1)(q-1)/2 }. > Let's say some base G makes a sub-group of order p-1. this is a group with > 2^384 elements. In order for the period of G to be maximal in the > sub-group, 2 must be a primitive element modulo p-1, which clearly can't be > since p-1 is even. We require 2 to be a primitive element since we are > doing 2^k mod p-1. No, we don't require that, since the order of *any* element of Z*_n must be 1, 2, 4, or >= (min(p, q)-1)/2. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOzPNdzkCAxeYt5gVAQEm3gf/Vbhpyfm4iP5Qfq4h0DbVb72EMwb2E+7w u8zSeHVjS9PSNi7H6f47/6XcfsYCF1YSQPFuP1QOQ2pm7B/yQCWvw8jupqyduO6J 5A4Bqmq7wx7GmomZeU7gd0fsT71lU7gYaYeBk9+Y/cHOuD/ELV3VVfaIXpqeLoB0 O3olkpfKgelZIHNLnlnjQ+X7mrPYK3dX2tBJS6of8mYFaBQ+tEGBxGza1yhL1lqw ORTbQm2SmfLHF5O1nL+OrUJmpYrTXO9q7qHYp9afpKIF+LXvR/xilwjlYZhgEkNw 9FbyWkM4G9s65qbaP3OZywHxiEcjNarbRwEGwlxsPZFSS4WWORs2Ow== =3oOW -----END PGP SIGNATURE-----
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Sat, 23 Jun 2001 16:16:52 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B34B2E4.D993E79C@zetnet.co.uk> References: <sR_Y6.6226$Mf5.2223898@news3.rdc1.on.home.com> <3B33CDEF.607032B7@zetnet.co.uk> Newsgroups: sci.crypt Lines: 86 -----BEGIN PGP SIGNED MESSAGE----- Tom St Denis wrote: > "David Hopwood" <david.hopwood@zetnet.co.uk> wrote in message > news:3B33CDEF.607032B7@zetnet.co.uk... > > [context: let p and q be safe 384-bit primes, and consider the group > > Z*_{pq}.] > > > > The possible orders are the factors of the group order lcm(p-1, q-1), i.e. > > { 1, 2, (p-1)/2, p-1, (q-1)/2, q-1, (p-1)(q-1)/4, (p-1)(q-1)/2 }. > > And any linear combination thereof ... 2q - 2, etc... or is that wrong? That's wrong. A cyclic group G of order k is isomorphic to (Z_k, +). Consider the orders of elements of (Z_k, +); clearly they are the factors of k. > I always though the order of any element can be any linear combination of > the factors of phi(p) or lcm(p-1,q-1)? No. Also, I think you're still confusing phi and lambda; if p and q are prime, then phi(pq) = (p-1)(q-1) lambda(pq) = lcm(p-1, q-1). > > > Let's say some base G makes a sub-group of order p-1. this is a group > > > with 2^384 elements. In order for the period of G to be maximal in the > > > sub-group, 2 must be a primitive element modulo p-1, which clearly can't > > > be since p-1 is even. We require 2 to be a primitive element since we > > > are doing 2^k mod p-1. > > > > No, we don't require that, since the order of *any* element of Z*_n must > > be 1, 2, 4, or >= (min(p, q)-1)/2. I meant 1, 2, or >= (min(p, q)-1)/2; it can't be 4. I was sure I'd corrected that before posting, but obviously not. However, you're right in pointing out that I had also missed out another essential part of the argument; see below. > This is not true. You are not doing > > g^x mod n > > You are doing > > g^(2^k) mod n = g^(2^k mod phi(g)) mod p > > So the order of 2 modulo the order of the sub-group that g generates modulo > p is important. Yes, but Mark Wooding already took that into account: # Now we look at the order of 2 mod ord_p(x). It must be a factor of # \lambda(ord_p(x)), So, since in the example ord_p(x) is a factor of 2((p-1)/2)((q-1)/2), and (p-1)/2 and (q-1)/2 are prime, we have that the order of 2 mod ord_p(x) is a factor of lcm((p-1)/2 - 1, (q-1)/2 - 1). Mark had set p = 2r + 1 and r = 2s + 1. If we similarly set q = 2r' + 1 and r' = 2s' + 1, then the cycle length is a factor of lcm(2s, 2s') = 2 lcm(s, s'). So if s and s' have no small factors (except 1), then the cycle length is either 1, 2, or large. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOzSynjkCAxeYt5gVAQEgLwf/by/RIlf7kXruwEhSH1TtZdyZ1PVOuxJO BGuN9NBqRrqp71HI0ZMIbPjzQu2iqMiq0kexj9MDfYF8GpweTpC+ivZXE5KoIKHS iCGeygmq3OtqgZkwF532Znp+pha4aKLVaIYoM8GvlYjImIf3iGJyC963SZNm7OAQ rxxnB+lVqPGhbODChobZ98zNxRAwChfflzS+K41DB2ofoC0RI1LC9goh2WwPQi3+ bB1HTGPgawtkjCwAzMuYix3pGlWOO4HL4f81exFz+J40foRWBkenyhOwAMtXOUvp MNFQyqkXIJP5lCV6YMVtCyb+YejFkXwiAl13C++hx4E7GI2SuIYysg== =uESN -----END PGP SIGNATURE-----
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Sat, 23 Jun 2001 20:20:52 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <ES6Z6.11217$Mf5.3040393@news3.rdc1.on.home.com> References: <3B34B2E4.D993E79C@zetnet.co.uk> Newsgroups: sci.crypt Lines: 16 "David Hopwood" <david.hopwood@zetnet.co.uk> wrote in message news:3B34B2E4.D993E79C@zetnet.co.uk... > -----BEGIN PGP SIGNED MESSAGE----- <snip> Yeah I see the faulty of my math. I agree that your cycle lengths are correct. Mind if I ask what is the signficant difference between phi and lamda? Isn't lamda a factor of phi? [more precisely isn't phi a multiple of lamda?] Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Tue, 26 Jun 2001 04:12:12 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b380b71.4332015@news.io.com> References: <3B34B2E4.D993E79C@zetnet.co.uk> Newsgroups: sci.crypt Lines: 28 On Sat, 23 Jun 2001 16:16:52 +0100, in <3B34B2E4.D993E79C@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >[...] >Mark had set p = 2r + 1 and >r = 2s + 1. If we similarly set q = 2r' + 1 and r' = 2s' + 1, then the cycle >length is a factor of lcm(2s, 2s') = 2 lcm(s, s'). > >So if s and s' have no small factors (except 1), then the cycle length is >either 1, 2, or large. In my experience traversing the states and cycles of tiny BB&S constructions (see http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2 ), I have never found a cycle of length 2 in a "special primes" construction. Do you have or can you construct an example of special primes BB&S construction with a length 2 cycle? --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Tue, 26 Jun 2001 17:01:15 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B38B1CB.D2C7F37D@zetnet.co.uk> References: <3b380b71.4332015@news.io.com> Newsgroups: sci.crypt Lines: 53 -----BEGIN PGP SIGNED MESSAGE----- Terry Ritter wrote: > David Hopwood <david.hopwood@zetnet.co.uk> wrote: > >[...] > >Mark had set p = 2r + 1 and > >r = 2s + 1. If we similarly set q = 2r' + 1 and r' = 2s' + 1, then the cycle > >length is a factor of lcm(2s, 2s') = 2 lcm(s, s'). > > > >So if s and s' have no small factors (except 1), then the cycle length is > >either 1, 2, or large. More precisely, it can be proven by this argument that the cycle length is 1, 2 or large (but in fact 2 is ruled out for a different reason; see below). > In my experience traversing the states and cycles of tiny BB&S > constructions (see > > http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2 > > ), I have never found a cycle of length 2 in a "special primes" > construction. > > Do you have or can you construct an example of special primes BB&S > construction with a length 2 cycle? That would require the element 2 to be of order 2 in Z*_{lambda(N)}. If lambda(N) > 4 then this obviously can't occur, and lambda(N) must be > 4 since p, q >= 7. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOzixsDkCAxeYt5gVAQH0hggAxQFSkdyr+RaORERSeS6FJMaaXd9Qgppi I4jm0Mb3nDVgycl4ySrz2j9f/buFEHvi9eq3QGYNL82eOLmhM2Qq4DRSbUwpemCj QoMWZae7ka91cNQkuwq/zlPVzFMP9OOTKygIfSr+D/HRWKpjCmc/aKvOZDkcRqtv VjlheZxtTQrKRzYUCygXpimye34DF0gcUXS0zsBKBLGA3MUWUTBj5qrA3mFdnHmL ygrpF2XbirOZIJ3oKdMWAML1aQCXQjvIUHzku88oSUyS10hCfy90irV8CrMFSDun QKkQ8uyBo6tsLILFfKJxvd4573md6D9F4qLXtdcxIyry5ZMlYMuA0g== =GdfS -----END PGP SIGNATURE-----
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Tue, 26 Jun 2001 19:13:46 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b38de9b.1115567@news.io.com> References: <3B38B1CB.D2C7F37D@zetnet.co.uk> Newsgroups: sci.crypt Lines: 34 On Tue, 26 Jun 2001 17:01:15 +0100, in <3B38B1CB.D2C7F37D@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >>[...] >> Do you have or can you construct an example of special primes BB&S >> construction with a length 2 cycle? > >That would require the element 2 to be of order 2 in Z*_{lambda(N)}. >If lambda(N) > 4 then this obviously can't occur, and lambda(N) must >be > 4 since p, q >= 7. So one way to provably eliminate the use of dangerously short cycles in a practical BB&S is: 1. Use two *special* primes of public-key size. 2. Select the initial state x[0] at random. 3. Take a step (skip any lead-in), save x[1], take another step, then compare the current state x[2] with saved state x[1]; if they are the same, go to 2. (Note that the comparison can terminate as soon as a single bit difference is found; almost always, only one word comparison need execute.) This eliminates the use of degenerate cycles. And -- due to the special primes construction -- all of the remaining cycles, even the relatively "short" ones, are "long enough" for use. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Wed, 27 Jun 2001 14:40:22 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010627144022.A5184@home.com> References: <3B38B1CB.D2C7F37D@zetnet.co.uk> Newsgroups: sci.crypt Lines: 22 On Tue, Jun 26, 2001 at 07:13:46PM +0000, Terry Ritter wrote: > So one way to provably eliminate the use of dangerously short cycles > in a practical BB&S is: [snip] One simple program I wrote to generate the BBS primes produced the following output: $ time bbsgen /dev/urandom 128 attempt number 1031 attempt number 4875 p = 5e67ef2826ec916de1279b65eec9367 q = 12205916de2de95df58e176388ea6988f n = 6af3ca948c41280993fe97724864cb7e7346dfa9c8af116deb7c4ee34757e89 real 0m18.372s user 0m18.290s sys 0m0.280s Do those times seem too long to anyone? Anyone have anything significantly quicker?
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 11:24:57 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010623112457.A45240@home.com> References: <3B38B1CB.D2C7F37D@zetnet.co.uk> Newsgroups: sci.crypt Lines: 21 On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > So as long as you use double-safe primes the order of any element is huge > (assuming p' is about 384 bits the period will be around 2^383). > Now the good question: How likely is it to find such a doubly safe prime? I don't know how likely it is but the procedure isn't hard, just time consuming. Simply: 1. Pick a really big prime -- however many bits you want. 2. Multiply the prime by 2 and add 1. 3. Check that the number obtained in step 2 is a prime. If not then start over at step 1. 4. Multiply the new prime by 2 and add 1. 5. Check that the number obtained in step 4 is a prime. If not then start over at step 1. You now have one of the numbers you need (as any prime times 2 plus 1 is congruent to 3 mod 4). Yes it takes a while, but if you are writing an application for which this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 18:22:04 +0100 From: "Mike Scott" <mscott@indigo.ie> Message-ID: <%f4Z6.10494$Fk7.94018@news.indigo.ie> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 34 You could speed this process up substantially by using trial division on all three numbers that need to be prime, to quickly eliminate the majority of "non-double-safe-primes". Only if all three pass this test will expensive primality testing be required Mike Scott "Mixtim" <Use-Author-Address-Header@[127.1]> wrote in message news:20010623112457.A45240@home.com... > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 20:12:30 +0200 From: "Cristiano" <cristiano.p@mclink.it> Message-ID: <9h2mbs$m11$1@news.mclink.it> References: <q12Z6.7939$Mf5.2479512@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 52 "Tom St Denis" <tomstdenis@yahoo.com> wrote: > Now the good question: How likely is it to find such a doubly safe prime? The code proposed by Mixtim works but it is terribly slow. I wrote code to find p1=p2*2+1 and p=p1*2+1 (p, p1 and p2 primes; do you have read the paper by Thierry Moreau?). I suggest to initialize to one 3 vectors of size n, 2*n and 4*n (n depend on platform and on size of p). Then set to zero the numbers wich are divisible for small primes (also this limit depend on platform). Now we can check with Miller-Rabin test the numbers with flag to 1. MR test should be done with primes bases and random numbers bases. I hope the following c++ code will be a little bit more explanatory (xi is the starting point, T is the numbers of iterations for MR test): void FIND_BBS(Big &xi,const int T) { const unsigned SS=10000,SSb=SS*32; ULONG *const b1=new ULONG[SS],*const b2=new ULONG[2*SS],*const b3=new ULONG[4*SS]; while(1) { memset(b1,255,SS*4); memset(b2,255,2*SS*4); memset(b3,255,4*SS*4); for(unsigned i=0;i<mip->npri;i++) { const unsigned p=mip->PRIMES[i]; unsigned r=xi%p; if(r) r=p-r; while(r<SSb) { set_bit(r,0,b1); r+=p; } r=(xi*2+1)%p; if(r) r=p-r; while(r<2*SSb) { set_bit(r,0,b2); r+=p; } r=(xi*4+3)%p; if(r) r=p-r; while(r<4*SSb) { set_bit(r,0,b3); r+=p; } } for(int i=0;i<SSb;i++) { if(get_bit(i,b1)) if(get_bit(i*2,b2)) if(get_bit(i*4,b3)) { if(MR(xi,2)) if(MR(xi*2+1,2)) if(MR(xi*4+3,T)) if(MR(xi,T)) if(MR(xi*2+1,T)) { delete[] b1; delete[] b2; delete[] b3; return; } } ++xi; } } } If SS and mip->npri will have regulated well, we will get the fastest code that I know. Cristiano
Subject: Re: BBS and safe primes Date: Sun, 24 Jun 2001 01:56:14 +0300 From: Fat Phil <fatphil_without_this_suffix@altavista.com> Message-ID: <3B351E8E.5A7DC67B@altavista.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 50 Mixtim wrote: > > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok. There is a program, initially called "PrimeForm", now called "PFGW", which can find numbers that satisfy these conditions trivially. www.primeform.net should get you to a site where it can be downloaded. Look up "ABC2" file formats in the documentation, and start with something like the following: <<< ABC2: (2^768+2*$a+1) & (2^769+4*$a+3) & (2^770+8*$a+7) a in 1 to 1000000 >>> Run it with -f and it will trial factor first (which makes a lot of sense as most of the above will have small factors. It then does an incredibly fast SPRP (strong probable primality test). I used it to find the my 1800-digit 'illegal prime'. It found the PRP in only a few minutes (though the formal Elliptic Curve Primality Proof took several weeks). For tiny primes (such as 384 bits) an individual PRP should take bugger all time, but finding the combination of three primes will be substantially harder (about 1 in 10million tests?). Presieving and using an "ABC file" rather than an "ABC2 file" is another possibility. Phil
Subject: BBS Standalone Code Date: Sat, 30 Jun 2001 20:50:15 GMT From: Flip@safebunch.com Message-ID: <bYq%6.2921$Kf3.27493@www.newsranger.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 14 Hi All, does anyone know where I can get a copy of the Blum-Blum-Shaub (I may have the last name wrong ... sorry), otherwise known as BBS PRNG code. It would be nice to have standalone C code if it is available. I tried on the net, but to no avail. Any help is appreciated. By the way, does BBS have good crypto-PRNG properties (like entropy)? Thank you ... Wilson
Subject: Re: BBS Standalone Code Date: Sat, 30 Jun 2001 17:49:13 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010630174913.A36797@home.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 32 On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > have the last name wrong ... sorry), otherwise known as BBS code. If you go to http://www.swox.com/gmp/ you can get a library for arbitrary precision arithmetic. The BBS algorithm is simply one gmp library call over and over: mpz_powm_ui(x, x, 2, n); After each call you use one (or more) bits from x. The hard part is generating the two special primes p and q to get n. I have a program that generates these special primes if you want it. $ time ./bbsprime 128 2c89599636259a1d586e3db8a25ecfc7 real 0m0.624s user 0m0.619s sys 0m0.001s $ time ./bbsprime 128 9157b3e960da3ea5f4cb433ff98c6647 real 0m5.440s user 0m5.396s sys 0m0.008s It can take a few seconds to get just a 128 bit special prime. Generating 512 bit special primes can take much longer. I'm sure other programs exist that find them more quickly. But once you have them then BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Wed, 04 Jul 2001 15:59:01 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B439FB5.9501AFD8@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 39 Do the special primes guarantee that the generator will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Wed, 04 Jul 2001 23:01:17 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <1fN07.93093$Mf5.26695719@news3.rdc1.on.home.com> References: <3B439FB5.9501AFD8@postoffice.pacbell.net> Newsgroups: sci.crypt Lines: 12 <subnet2@postoffice.pacbell.net> wrote in message news:3B439FB5.9501AFD8@postoffice.pacbell.net... > Do the special primes guarantee that the generator will not have short > cycles? Yes doubly safe primes will ensure that any non-trivial base will have a long period. Tom
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 03:48:15 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b43e36c.737664@news.io.com> References: <3B439FB5.9501AFD8@postoffice.pacbell.net> Newsgroups: sci.crypt Lines: 18 On Wed, 04 Jul 2001 15:59:01 -0700, in <3B439FB5.9501AFD8@postoffice.pacbell.net>, in sci.crypt subnet2@postoffice.pacbell.net wrote: >Do the special primes guarantee that the generator will not have short >cycles? Not completely. The special primes construction guarantees that *if* we avoid selecting a degenerate cycle (and that is easy enough to check), all the remaining cycles are "long enough" for use. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 22:19:12 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B454A50.CD546325@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 38 Do the special primes guarantee that the BBS will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 22:19:29 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B454A61.2FD3AD73@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 38 Do the special primes guarantee that the BBS will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 22:18:49 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B454A39.FBD8D86F@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 38 Do the special primes guarantee that the BBS will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Fri, 06 Jul 2001 06:33:45 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b455ba0.3515922@news.io.com> References: <3B454A39.FBD8D86F@postoffice.pacbell.net> Newsgroups: sci.crypt Lines: 21 On Thu, 05 Jul 2001 22:18:49 -0700, in <3B454A39.FBD8D86F@postoffice.pacbell.net>, in sci.crypt subnet2@postoffice.pacbell.net wrote: >Do the special primes guarantee that the BBS will not have short cycles? No. No, no, no. With public-key size special primes, the "short" cycles will either be "long enough" to use, or degenerate (i.e., single-cycle loops). To eliminate the possibility of using a degenerate cycle in practice, we choose x[0] at random, take a step (thus skipping any lead-in), save x[1], step again, and compare x[2] with x[1]. If x[2] == x[1] (which almost never happens in practice, so we need to force that to check the code), we choose another x[0] and start over. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS Standalone Code Date: Fri, 06 Jul 2001 08:08:39 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B45D476.4D020774@postoffice.pacbell.net> References: <3b455ba0.3515922@news.io.com> Newsgroups: sci.crypt Lines: 26 Thanks. I did not undertand this. Terry Ritter wrote: > On Thu, 05 Jul 2001 22:18:49 -0700, in > <3B454A39.FBD8D86F@postoffice.pacbell.net>, in sci.crypt > subnet2@postoffice.pacbell.net wrote: > > >Do the special primes guarantee that the BBS will not have short cycles? > > No. No, no, no. > > With public-key size special primes, the "short" cycles will either be > "long enough" to use, or degenerate (i.e., single-cycle loops). To > eliminate the possibility of using a degenerate cycle in practice, we > choose x[0] at random, take a step (thus skipping any lead-in), save > x[1], step again, and compare x[2] with x[1]. If x[2] == x[1] (which > almost never happens in practice, so we need to force that to check > the code), we choose another x[0] and start over. > > --- > Terry Ritter ritter@io.com http://www.io.com/~ritter/ > Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 11:24:57 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 21 On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > So as long as you use double-safe primes the order of any element is huge > (assuming p' is about 384 bits the period will be around 2^383). > Now the good question: How likely is it to find such a doubly safe prime? I don't know how likely it is but the procedure isn't hard, just time consuming. Simply: 1. Pick a really big prime -- however many bits you want. 2. Multiply the prime by 2 and add 1. 3. Check that the number obtained in step 2 is a prime. If not then start over at step 1. 4. Multiply the new prime by 2 and add 1. 5. Check that the number obtained in step 4 is a prime. If not then start over at step 1. You now have one of the numbers you need (as any prime times 2 plus 1 is congruent to 3 mod 4). Yes it takes a while, but if you are writing an application for which this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 18:22:04 +0100 From: "Mike Scott" <mscott@indigo.ie> Message-ID: <%f4Z6.10494$Fk7.94018@news.indigo.ie> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 34 You could speed this process up substantially by using trial division on all three numbers that need to be prime, to quickly eliminate the majority of "non-double-safe-primes". Only if all three pass this test will expensive primality testing be required Mike Scott "Mixtim" <Use-Author-Address-Header@[127.1]> wrote in message news:20010623112457.A45240@home.com... > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 20:12:30 +0200 From: "Cristiano" <cristiano.p@mclink.it> Message-ID: <9h2mbs$m11$1@news.mclink.it> References: <q12Z6.7939$Mf5.2479512@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 52 "Tom St Denis" <tomstdenis@yahoo.com> wrote: > Now the good question: How likely is it to find such a doubly safe prime? The code proposed by Mixtim works but it is terribly slow. I wrote code to find p1=p2*2+1 and p=p1*2+1 (p, p1 and p2 primes; do you have read the paper by Thierry Moreau?). I suggest to initialize to one 3 vectors of size n, 2*n and 4*n (n depend on platform and on size of p). Then set to zero the numbers wich are divisible for small primes (also this limit depend on platform). Now we can check with Miller-Rabin test the numbers with flag to 1. MR test should be done with primes bases and random numbers bases. I hope the following c++ code will be a little bit more explanatory (xi is the starting point, T is the numbers of iterations for MR test): void FIND_BBS(Big &xi,const int T) { const unsigned SS=10000,SSb=SS*32; ULONG *const b1=new ULONG[SS],*const b2=new ULONG[2*SS],*const b3=new ULONG[4*SS]; while(1) { memset(b1,255,SS*4); memset(b2,255,2*SS*4); memset(b3,255,4*SS*4); for(unsigned i=0;i<mip->npri;i++) { const unsigned p=mip->PRIMES[i]; unsigned r=xi%p; if(r) r=p-r; while(r<SSb) { set_bit(r,0,b1); r+=p; } r=(xi*2+1)%p; if(r) r=p-r; while(r<2*SSb) { set_bit(r,0,b2); r+=p; } r=(xi*4+3)%p; if(r) r=p-r; while(r<4*SSb) { set_bit(r,0,b3); r+=p; } } for(int i=0;i<SSb;i++) { if(get_bit(i,b1)) if(get_bit(i*2,b2)) if(get_bit(i*4,b3)) { if(MR(xi,2)) if(MR(xi*2+1,2)) if(MR(xi*4+3,T)) if(MR(xi,T)) if(MR(xi*2+1,T)) { delete[] b1; delete[] b2; delete[] b3; return; } } ++xi; } } } If SS and mip->npri will have regulated well, we will get the fastest code that I know. Cristiano
Subject: Re: BBS and safe primes Date: Sun, 24 Jun 2001 01:56:14 +0300 From: Fat Phil <fatphil_without_this_suffix@altavista.com> Message-ID: <3B351E8E.5A7DC67B@altavista.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 50 Mixtim wrote: > > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok. There is a program, initially called "PrimeForm", now called "PFGW", which can find numbers that satisfy these conditions trivially. www.primeform.net should get you to a site where it can be downloaded. Look up "ABC2" file formats in the documentation, and start with something like the following: <<< ABC2: (2^768+2*$a+1) & (2^769+4*$a+3) & (2^770+8*$a+7) a in 1 to 1000000 >>> Run it with -f and it will trial factor first (which makes a lot of sense as most of the above will have small factors. It then does an incredibly fast SPRP (strong probable primality test). I used it to find the my 1800-digit 'illegal prime'. It found the PRP in only a few minutes (though the formal Elliptic Curve Primality Proof took several weeks). For tiny primes (such as 384 bits) an individual PRP should take bugger all time, but finding the combination of three primes will be substantially harder (about 1 in 10million tests?). Presieving and using an "ABC file" rather than an "ABC2 file" is another possibility. Phil
Subject: Re: Q: Internet banking Date: 9 Jul 2001 00:40:03 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> Message-ID: <20010709004003.22385.qmail@nym.alias.net> References: <3B48A275.DDA62121@arcormail.de> Newsgroups: sci.crypt Lines: 31 Mixtim writes: > On Sun, Jul 08, 2001 at 07:00:05PM -0000, lcs Mixmaster Remailer wrote: > > (And by the way, the reductions and proofs make no assumptions about > > special primes, they are for ordinary RSA primes. Choosing special primes > > does not increase the proven security of BBS at all. If someone wishes > > to deny this, let them give the specific formula for the greater security > > that is obtained with special primes. How many additional calls to the > > BBS oracle are necessary to achieve a specific factoring or QR attack? > > How much additional work? Let them quantify the difference. They can't > > do it, because it can't be done. The claim that special primes are > > needed or helpful is nothing but handwaving and hot air.) > > You are only speaking of academic weaknesses. In practice, BBS > is quite strong. If you'd care to demonstrate a weakness then > feel free to try the following data. N is a product of two > "special" primes p and q. It is represented here as a base 16 > number. The uuencoded data following N is the first 1020 bytes > from a BBS using N and a random starting X that was 640 bits long. > What are the next 4 bytes of the sequence? Of course the sequence is not predictable. The point is, why did you use "special" primes? They are not necessary. They do not add any security to your system. All of the BBS proofs which give us reason to trust it are based on ordinary primes, not special ones. There is no reason to use special primes. It's not that special primes weaken it, as you seemed to be reading the comment; it's that they fail to strengthen BBS, hence they are not necessary. Those who spread the misinformation that BBS requires special primes make people think it's a lot more complicated than it is.
Subject: Re: Q: Internet banking Date: Mon, 09 Jul 2001 04:30:23 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b49334b.4281079@news.io.com> References: <20010709004003.22385.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 69 On 9 Jul 2001 00:40:03 -0000, in <20010709004003.22385.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: >Mixtim writes: >> On Sun, Jul 08, 2001 at 07:00:05PM -0000, lcs Mixmaster Remailer wrote: >> > (And by the way, the reductions and proofs make no assumptions about >> > special primes, they are for ordinary RSA primes. Choosing special primes >> > does not increase the proven security of BBS at all. If someone wishes >> > to deny this, let them give the specific formula for the greater security >> > that is obtained with special primes. How many additional calls to the >> > BBS oracle are necessary to achieve a specific factoring or QR attack? >> > How much additional work? Let them quantify the difference. They can't >> > do it, because it can't be done. The claim that special primes are >> > needed or helpful is nothing but handwaving and hot air.) >> >> You are only speaking of academic weaknesses. In practice, BBS >> is quite strong. If you'd care to demonstrate a weakness then >> feel free to try the following data. N is a product of two >> "special" primes p and q. It is represented here as a base 16 >> number. The uuencoded data following N is the first 1020 bytes >> from a BBS using N and a random starting X that was 640 bits long. >> What are the next 4 bytes of the sequence? > >Of course the sequence is not predictable. > >The point is, why did you use "special" primes? They are not necessary. >They do not add any security to your system. All of the BBS proofs which >give us reason to trust it are based on ordinary primes, not special ones. >There is no reason to use special primes. > >It's not that special primes weaken it, as you seemed to be reading >the comment; it's that they fail to strengthen BBS, hence they are >not necessary. Those who spread the misinformation that BBS requires >special primes make people think it's a lot more complicated than it is. There is a very good reason to use the special primes construction as given in the original BB&S article: Failing to use the special primes construction creates a -- admittedly tiny -- possibility that usefully short cycles may exist and may be selected at random. And if that should happen, the proven secure generator is not secure. Yet the whole point of using BB&S is to end up with a secure generator. By using the special primes construction, the only possible "short" cycles are shown to be either degenerate or "long enough." It is easy to check that any seed we select at random is not on a degenerate cycle, and that is cheap and easy proof that we are not enabling that particular weakness. Yes, the probability of selecting a short cycle is very, very low. But short cycles are the "weak keystreams" of BB&S. And it is not entirely unknown for crypto implementors to explicitly avoid weak keys, even if a mathematician might think such keys would "never" be encountered. Never is a very long time. I claim that avoiding weak keys does in fact "strengthen" BB&S by avoiding the possibility that a weak key might be used. Furthermore, since that is raw fact, the only possible debate is over how useful that strengthening really is. And since the issue may include both confidence for the user and professional pride for the designer, I doubt mathematics can resolve it. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: 9 Jul 2001 20:20:44 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> Message-ID: <20010709202044.1740.qmail@nym.alias.net> References: <3b49334b.4281079@news.io.com> Newsgroups: sci.crypt Lines: 34 Terry Ritter writes: > I claim that avoiding weak keys does in fact "strengthen" BB&S by > avoiding the possibility that a weak key might be used. Furthermore, > since that is raw fact, the only possible debate is over how useful > that strengthening really is. And since the issue may include both > confidence for the user and professional pride for the designer, I > doubt mathematics can resolve it. But if it does strengthen BBS, then you should be able to quantify the degree of strengthening. We can, after all, quantify the strength of BBS, at least in principle. We can show how many calls to the BBS prediction oracle are necessary to have a given chance of factoring N. This is the basis for our belief in the strength of BBS. There is no reason for debate. It is not a subjective issue where user confidence and professional pride enter into it. This is mathematics. Either you can strengthen BBS or not. We can calculate numerically how strong BBS is, in terms of numbers of oracle calls to break the modulus. If your method strengthens it, it should lead to a larger numerical estimate of that strength. You need to tell us what that number is, for people to judge whether the additional expense of generating special primes is worth it. Imagine a bridge made of steel. We have calculated its strength numerically. Now a magician proposes to put a magic spell on it to make it stronger. The designer is skeptical and asks him to calculate how many more tonnes of traffic it can hold. The magician claims this will increase user confidence and add professional pride, but that mathematics cannot resolve it. Who is more convincing, the one who relies on mathematics, or the one who says that the strength of a construction (cryptographic or mechanical) cannot be resolved mathematically?
Subject: Re: Q: Internet banking Date: Mon, 9 Jul 2001 22:07:59 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9id9vv$1bog$2@agate.berkeley.edu> References: <20010709202044.1740.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 29 lcs Mixmaster Remailer wrote: >But if it does strengthen BBS, then you should be able to quantify >the degree of strengthening. I would say something that is just a little less strong. Namely: The whole point of BBS is to get something that is provably strong. If you don't care about provably strong, we've got constructions that are far better than BBS. However, my understanding about why Ritter likes BBS is because he is not willing to accept anything less than a proof as evidence of security. Therefore, if he is considering some extension to BBS (such as "only use strong primes") that adds no provable strength---i.e., where we don't have any proof that it adds strength---I see no point to add it. In the absence of a proof that the extension adds strength, you might as well omit it, if all you care about is what can be proven. If you're worried that the version without the extension might be insecure, then maybe you should be just as worried that the version with the extension is insecure, too: after all, we have no proof that the extended version is any better than the unextended version. Now if what you want is heuristic security, possibly because you want to use the darn thing in practice and you want to minimize the likelihood that it gets broken as much as possible, then you might be willing to combine both techniques that have some proven properties and techniques with no proven properties. However, I *believe* Ritter's position is that we have no good reason to trust things without proven properties, so this doesn't apply. I hope he'll correct me if I'm mis-stating his position.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 05:10:36 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4a8e48.8894712@news.io.com> References: <9id9vv$1bog$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 155 On Mon, 9 Jul 2001 22:07:59 +0000 (UTC), in <9id9vv$1bog$2@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >lcs Mixmaster Remailer wrote: >>But if it does strengthen BBS, then you should be able to quantify >>the degree of strengthening. > >I would say something that is just a little less strong. > >Namely: The whole point of BBS is to get something that is provably >strong. That is what the designer and user care about, yes. There would seem to be no other point to use awkward and slow BB&S. >If you don't care about provably strong, we've got constructions >that are far better than BBS. However, my understanding about why Ritter >likes BBS is because he is not willing to accept anything less than a >proof as evidence of security. Actually, I am just not willing to have mathematicians claim "proven secure" to designers and users without extensive caveats. And if designers and users do buy into the "proven secure" we have (again, there being no other reason for using BB&S), then the actual design should reflect a real attempt to eliminate all known weakness, as users expect a mathematical proof to do automatically. As far as I know, the sole known *weakness* of BB&S is the existence and possible use of short cycles, especially in the ordinary construction. This flaw was eliminated in the original BB&S article with modest front-end cost, but high per-use cost. It now turns out that we can do the same thing at negligible per-use cost. Merely by using the special primes construction from the BB&S article, all "short" cycles are known to be "long enough" for use except degenerate cycles, which we can easily test with just a couple of steppings. The usual mathematical spin on this is that the security improvement thus gained is so modest as to be lost in the asymptotic results. However, we have actual experience with what users expect perfection to mean: The original Intel Pentium design also had a flaw. Very rarely, it would produce incorrect arithmetic results. It was such an unlikely flaw that it hardly every occurred. (Already we see the correspondence with BB&S short cycles which are hardly ever selected.) Intel argued that such a very unlikely flaw was no flaw at all. (Just as mathematical cryptographers now argue that choosing short cycles is so unlikely that it can be ignored.) Intel thus concluded that there was no need to replace the faulty Pentiums. Alas, their customers felt differently. Large technical companies like IBM and various accounting firms also felt differently. Eventually, Intel changed their position. As Intel learned, the issue was not actual wrong answers, but instead lack of confidence. Just as it is in BB&S. >Therefore, if he is considering some >extension to BBS (such as "only use strong primes") that adds no provable >strength---i.e., where we don't have any proof that it adds strength---I >see no point to add it. If you do not see that avoiding the use of short cycles improves (statistical) strength, you have your sums wrong. The improvement is indisputable. The only issue is whether the amount of improvement is useful, and the interpretation of "useful" depends upon the cost of the improvement, and the outlook of the designer and user. We have just covered that. >In the absence of a proof that the extension adds strength, There is no such absence. >you might >as well omit it, if all you care about is what can be proven. That is what users want, but not what they get. >If you're >worried that the version without the extension might be insecure, then >maybe you should be just as worried that the version with the extension >is insecure, too: after all, we have no proof that the extended version >is any better than the unextended version. I guess it's "turtles all the way down," again, which does not apply to my position this time any more than it did the last. Proof of strength in practice is not available, so I could hardly demand it, now could I? If and when that changes we will have a brave new world. For now, we are constrained to follow the same path that the entire previous history of cryptography has followed before us. Which is to say: no such proof. Nevertheless, the existence of new mathematical "security proofs" has reached the ears of the user. They are impressed. Eventually this may have negative repercussions, as users are informed that they are not getting what they expected, but for now some want proofs. That is the reason for using BB&S. And an implementation which achieves what the original BB&S article describes is more trustworthy and deserves more confidence than the simplified modern version even if that is asymptotically just as secure. >Now if what you want is heuristic security, possibly because you want >to use the darn thing in practice and you want to minimize the likelihood >that it gets broken as much as possible, then you might be willing to >combine both techniques that have some proven properties and techniques >with no proven properties. I think that would be a different issue than we discuss here. >However, I *believe* Ritter's position is that >we have no good reason to trust things without proven properties, Taken alone, that is a correct statement of one position. I'm not sure how that relates to BB&S, however. I think all of cryptography needs to address the implications of the absence of the feedback which is normal in all other areas of design and manufacture. Absent proof and absent feedback (since the opponents do not tell us what successes they have), we can have no idea whether or not our ciphers accomplish what we want them to do. Our situation is not necessarily hopeless: I think steps *can* be taken to improve things. In particular we can introduce the common use of multi-ciphering with independent keys, and selection from among different ciphers on a message-by-message basis, both of which are inspired by Shannon. The intent is not to provide the missing proof, but instead to protect against particular kinds of potential fault. But none of that will occur until there is a general realization that we have a design problem created by a lack of real feedback. >so this >doesn't apply. Having looked at the OTP and found it wanting, and having looked at BB&S and found that wanting, I don't expect cryptographic "proven strength" to apply in practice, no. >I hope he'll correct me if I'm mis-stating his position. I do try. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 06:14:07 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ie6ff$27bs$1@agate.berkeley.edu> References: <3b4a8e48.8894712@news.io.com> Newsgroups: sci.crypt Lines: 34 Terry Ritter wrote: >As far as I know, the sole known *weakness* of BB&S is the existence >and possible use of short cycles, especially in the ordinary >construction. As others have observed, this is only a weakness if factoring is easy, and we have to assume that factoring is hard anyway if we want to use BB&S. Since this has been discussed at length before, I'll leave it at that. >The usual mathematical spin on this is that the security improvement >thus gained is so modest as to be lost [...] >The original Intel Pentium design also had a flaw. Very rarely, it >would produce incorrect arithmetic results. It was such an unlikely >flaw that it hardly every occurred. (Already we see the >correspondence with BB&S short cycles which are hardly ever selected.) The analogy is flawed. For floating point arithmetic, we can build algorithms whose answers are guaranteed 100% correct (of course implementation can introduce flaws, but the algorithms themselves have zero chance of an error). In cryptography, we cannot. There is always an epsilon chance that a single lucky guess at the key will succeed, breaking the system. This is a fundamental and unavoidable property of computational-based cryptography. Therefore, it is unreasonable to ask for zero chance of being broken---such a request would be impossible to satisfy. I agree that this is the natural first thing to think of asking for, but when you realize that this is unattainable, then you have to set your sights a little bit lower. Fortunately, what is attainable appears to be quite satisfactory for all practical purposes. Therefore, it is reasonable to ask Intel to use floating point algorithms that have a zero chance of error, but it is not reasonable to ask crypto manufacturers to provide crypto algorithms that have a zero chance of being broken.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 06:36:27 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4aa25a.14033453@news.io.com> References: <9ie6ff$27bs$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 74 On Tue, 10 Jul 2001 06:14:07 +0000 (UTC), in <9ie6ff$27bs$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>As far as I know, the sole known *weakness* of BB&S is the existence >>and possible use of short cycles, especially in the ordinary >>construction. > >As others have observed, this is only a weakness if factoring is easy, >and we have to assume that factoring is hard anyway if we want to use BB&S. If a short cycle happens to be selected, that allows factoring. What the proof means to me is that, asymptotically, it is at least as hard to find a short cycle as it is to factor N. But "finding a short cycle" is not and has never been the issue. Short cycles do exist and *may* be selected. This is equivalent to accidentally using a weak key, and is a preventable weakness. Checking for and not using weak keys is hardly unknown. We do *not* have to believe the math or assume factoring is hard to address the use of short cycles. Instead, we can actually prevent that use, and at reasonable cost. >Since this has been discussed at length before, I'll leave it at that. > >>The usual mathematical spin on this is that the security improvement >>thus gained is so modest as to be lost [...] >>The original Intel Pentium design also had a flaw. Very rarely, it >>would produce incorrect arithmetic results. It was such an unlikely >>flaw that it hardly every occurred. (Already we see the >>correspondence with BB&S short cycles which are hardly ever selected.) > >The analogy is flawed. For floating point arithmetic, we can build >algorithms whose answers are guaranteed 100% correct (of course >implementation can introduce flaws, but the algorithms themselves have >zero chance of an error). In cryptography, we cannot. There is always >an epsilon chance that a single lucky guess at the key will succeed, >breaking the system. This is a fundamental and unavoidable property of >computational-based cryptography. Therefore, it is unreasonable to ask >for zero chance of being broken---such a request would be impossible >to satisfy. I agree that this is the natural first thing to think of >asking for, but when you realize that this is unattainable, then you have >to set your sights a little bit lower. Fortunately, what is attainable >appears to be quite satisfactory for all practical purposes. > >Therefore, it is reasonable to ask Intel to use floating point algorithms >that have a zero chance of error, but it is not reasonable to ask crypto >manufacturers to provide crypto algorithms that have a zero chance of >being broken. The analogy stands. Intel does not claim (in more than a marketing sense) that no error exists in their chips. I believe the arithmetic logic has been checked, but even that could be wrong. No, the issue was never that Intel should make a provably error-free chip. The issue was that an error was found, and that Intel dismissed the known flaw as meaningless because it was very rare. That is the same issue as BB&S. In practice, it is unreasonable to expect a zero chance of fault. But we can hope that no *known* fault will be allowed to exist. The existence and possible use of short cycles in BB&S is a known fault which fortunately can be eliminated at minimal cost -- or not. Allowing that fault to exist is exactly the issue Intel encountered. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 07:55:01 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ieccl$2cts$1@agate.berkeley.edu> References: <3b4aa25a.14033453@news.io.com> Newsgroups: sci.crypt Lines: 28 Terry Ritter wrote: >But "finding a short cycle" is not and has never been the issue. >Short cycles do exist and *may* be selected. This is equivalent to >accidentally using a weak key, and is a preventable weakness. >Checking for and not using weak keys is hardly unknown. Right. But using the prime 1208923250890892301 is a possibility and it may be selected; when it is selected, the adversary will be able to break our system. This means that any RSA modulus that has this as a factor is a weak key. Therefore, we should add a special tweak to our implementation to double-check that we're not using one of these weak keys, i.e., we're not using this prime as a factor of our RSA modulus. Checking for and not using weak keys is hardly unknown. We do *not* have to believe the math or assume factoring is hard to address the use of this class of weak keys. Instead, we can actually address that use, and at reasonable cost. The logic seems indisputable. We'd better fix all implementations to check for this prime, and post haste! Surely you must agree. Right? (P.S. Ok, ok, most likely the number I gave isn't actually prime. I didn't bother checking. Don't complain to me if it isn't! Just humor me and pretend this is an example of some randomly chosen prime. I'm too lazy to generate a real prime of the right length.)
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 18:44:05 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4b4cce.8097446@news.io.com> References: <9ieccl$2cts$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 54 On Tue, 10 Jul 2001 07:55:01 +0000 (UTC), in <9ieccl$2cts$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>But "finding a short cycle" is not and has never been the issue. >>Short cycles do exist and *may* be selected. This is equivalent to >>accidentally using a weak key, and is a preventable weakness. >>Checking for and not using weak keys is hardly unknown. > >Right. But using the prime 1208923250890892301 is a possibility >and it may be selected; when it is selected, the adversary will be >able to break our system. This means that any RSA modulus that has >this as a factor is a weak key. Therefore, we should add a special >tweak to our implementation to double-check that we're not using one >of these weak keys, i.e., we're not using this prime as a factor of >our RSA modulus. Checking for and not using weak keys is hardly >unknown. We do *not* have to believe the math or assume factoring >is hard to address the use of this class of weak keys. Instead, we >can actually address that use, and at reasonable cost. > >The logic seems indisputable. We'd better fix all implementations >to check for this prime, and post haste! Surely you must agree. >Right? No. You describe a brute force break: finding the key (in this case a factor) by "luck," at random. That cannot be avoided in any system which uses a key. In contrast, short cycles are weakness *in* *addition* to the chance of finding the right key. Short cycles thus make the system weaker than brute force. This may be a tiny additional weakness, but it can be avoided, and at reasonable cost. There is nothing wrong with a desire to provably reduce weakness; it is certainly not worthy of ridicule. Deciding whether designers and users should pay what it costs to remove a weakness is not a mathematical issue. That is a designer and user decision based on their goals and costs. >(P.S. Ok, ok, most likely the number I gave isn't actually prime. >I didn't bother checking. Don't complain to me if it isn't! Just >humor me and pretend this is an example of some randomly chosen prime. >I'm too lazy to generate a real prime of the right length.) --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM Organisation: The Clue Factory
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 05:34:47 GMT From: Paul Crowley <paul@JUNKCATCHER.cluefactory.org.uk> Message-ID: <874rsju6sx.fsf@saltationism.subnet.hedonism.cluefactory.org.uk> References: <3b4b4cce.8097446@news.io.com> Newsgroups: sci.crypt Lines: 14 ritter@io.com (Terry Ritter) writes: > You describe a brute force break: finding the key (in this case a > factor) by "luck," at random. That cannot be avoided in any system > which uses a key. No, he isn't. He's describing an attack based on testing for the specific prime that he named. The prime is named in advance; it's possible for the BBS implementation to test for that specific prime and avoid using it. -- __ Paul Crowley \/ o\ sig@paul.cluefactory.org.uk /\__/ http://www.cluefactory.org.uk/paul/ "Conservation of angular momentum makes the world go around" - John Clark
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 21:37:15 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4e186c.2192247@news.io.com> References: <874rsju6sx.fsf@saltationism.subnet.hedonism.cluefactory.org.uk> Newsgroups: sci.crypt Lines: 46 On Thu, 12 Jul 2001 05:34:47 GMT, in <874rsju6sx.fsf@saltationism.subnet.hedonism.cluefactory.org.uk>, in sci.crypt Paul Crowley <paul@JUNKCATCHER.cluefactory.org.uk> wrote: >ritter@io.com (Terry Ritter) writes: >> You describe a brute force break: finding the key (in this case a >> factor) by "luck," at random. That cannot be avoided in any system >> which uses a key. > >No, he isn't. He's describing an attack based on testing for the >specific prime that he named. The prime is named in advance; it's >possible for the BBS implementation to test for that specific prime >and avoid using it. And yet you did not retain the issue in your quote so we could all see it and come to a conclusion. Why is that? Referring back, I see that my comment was charitably on target. The primes and the "seed" are the key in a BB&S system. In any system where we have a key, the opponent may guess the key. Guessing the key *is* brute force, even if one just waits for the key to come up. (And it may not, since N is often retained and re-used.) There must always be a key, but short cycles need *not* be available for selection or use. Short cycles thus represent *additional* weakness, beyond the simple existence of a key. And we can act to eliminate this added weakness at modest or even trivial cost. This is not rocket science: * Weak short cycles do exist in BB&S. * Weak cycles can be completely avoided by using the special primes construction and then checking that we have not selected a degenerate cycle. * In any system which seeks *guaranteed* strength, the existence of known uncorrected faults is disturbing. So the modest cost of avoiding weak keys is hardly an unreasonable design. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 11:13:22 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B4F2C32.F4F48949@sandia.gov> References: <3b4e186c.2192247@news.io.com> Newsgroups: sci.crypt Lines: 36 Terry Ritter wrote: <snip> > This is not rocket science: > > * Weak short cycles do exist in BB&S. Ok. > * Weak cycles can be completely avoided by using the special primes > construction and then checking that we have not selected a degenerate > cycle. Ok. > * In any system which seeks *guaranteed* strength, the existence of > known uncorrected faults is disturbing. So the modest cost of > avoiding weak keys is hardly an unreasonable design. It seems unreasonable to me unless and until one provides a reason to believe that the improvement stands a chance of being worth the cost. I think it is central to this debate that the nature of the strength "guarantee" is clear. It is certainly not true that BB&S is guaranteed not to be breakable, period. Instead, we have that breaking (a given) BB&S has a certain probability. Using the special primes construction will change the probability by some amount. Neither you nor those who have disagreed with you have shown an actual computation of the improvement in probability. Thus, an implementor is left with choosing whose faith to believe. It's not "is the improvement non-zero?", but "how much is it worth?" Even a "modest" cost can sometimes be too much. JM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 19:39:40 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4F325C.19F4C1BC@t-online.de> References: <3B4F2C32.F4F48949@sandia.gov> Newsgroups: sci.crypt Lines: 36 John Myre wrote: > > Terry Ritter wrote: > > * In any system which seeks *guaranteed* strength, the existence of > > known uncorrected faults is disturbing. So the modest cost of > > avoiding weak keys is hardly an unreasonable design. > > It seems unreasonable to me unless and until one provides > a reason to believe that the improvement stands a chance of > being worth the cost. > > I think it is central to this debate that the nature of the > strength "guarantee" is clear. It is certainly not true that > BB&S is guaranteed not to be breakable, period. Instead, we > have that breaking (a given) BB&S has a certain probability. > Using the special primes construction will change the > probability by some amount. > > Neither you nor those who have disagreed with you have shown > an actual computation of the improvement in probability. Thus, > an implementor is left with choosing whose faith to believe. > It's not "is the improvement non-zero?", but "how much is it > worth?" Even a "modest" cost can sometimes be too much. If one wants to rely on the extremely small probability of encountering degenerate cycles, then I believe one has to know that these are sufficiently 'randomly' distributed, i.e. not clustered in some zones which a user with bad luck might step into. I asked about the question of distribution, but haven't yet got an answer. M. K. Shen
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 19:27:21 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4f4ae4.7581659@news.io.com> References: <3B4F2C32.F4F48949@sandia.gov> Newsgroups: sci.crypt Lines: 104 On Fri, 13 Jul 2001 11:13:22 -0600, in <3B4F2C32.F4F48949@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >Terry Ritter wrote: ><snip> >> This is not rocket science: >> >> * Weak short cycles do exist in BB&S. > >Ok. > >> * Weak cycles can be completely avoided by using the special primes >> construction and then checking that we have not selected a degenerate >> cycle. > >Ok. > >> * In any system which seeks *guaranteed* strength, the existence of >> known uncorrected faults is disturbing. So the modest cost of >> avoiding weak keys is hardly an unreasonable design. > >It seems unreasonable to me unless and until one provides >a reason to believe that the improvement stands a chance of >being worth the cost. All this isn't about *you*: It isn't up to you to decide for everybody else. I consider the tradeoff to be beyond "reasonable" to "necessary." >I think it is central to this debate that the nature of the >strength "guarantee" is clear. It is certainly not true that >BB&S is guaranteed not to be breakable, period. Sadly, correct. >Instead, we >have that breaking (a given) BB&S has a certain probability. I'm not sure we really do have that probability, per se. Perhaps if we had such an expression we could begin to see the numerical security consequences of the expected wild variations in cycle structure in the casual construction. In my view, it is not useful to simply have a mean value; indeed, the worst case (e.g., the shortest non-degenerate cycle) is usually most appropriate to cryptography. And, in a sense, the longer a "short cycle" is, the more trouble it is (the more likely it is to be selected at random), until the cycle length becomes "long enough" and it is no longer a threat. >Using the special primes construction will change the >probability by some amount. The special primes construction was the construction in the original BB&S article. Do you have a problem with that? >Neither you nor those who have disagreed with you have shown >an actual computation of the improvement in probability. *Of* *course* I have shown "an actual computational improvement in probability." There is some probability of fault in the special primes construction. That probability includes short cycle faults. I take away the short cycle faults. The resulting probability of fault is less. QED. Unfortunately, the proof is disturbingly silent about the actual probability of flaws, and about the types of flaws that remain in either construction. As long as the math is silent on the details, we are left with "whatever weak cycles might have existed in the casual construction have been eliminated," instead of "the probability of weakness is z." >Thus, >an implementor is left with choosing whose faith to believe. Such is always the case when the conventional wisdom is wrong. >It's not "is the improvement non-zero?", but "how much is it >worth?" Even a "modest" cost can sometimes be too much. Again, that comparison is not up to you. It is common and widely accepted in practice that in many things it is necessary to pay more the closer to perfection one comes. Since one cannot really hope for a "proven secure" cryptosystem to be actually "guaranteed fault free" in practice, the best one can do is to take the "proven secure" cryptosystem and eliminate the faults one can do something about. That may be the closest to perfection one can get, and there is usually an escalating cost to perfection. Those interested in perfection are often more than willing to pay. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 14:59:56 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B4F614C.97307C55@sandia.gov> References: <3b4f4ae4.7581659@news.io.com> Newsgroups: sci.crypt Lines: 160 Terry Ritter wrote: <snip> > >> * In any system which seeks *guaranteed* strength, the existence of > >> known uncorrected faults is disturbing. So the modest cost of > >> avoiding weak keys is hardly an unreasonable design. I replied: > >It seems unreasonable to me unless and until one provides > >a reason to believe that the improvement stands a chance of > >being worth the cost. And Terry riposted: > All this isn't about *you*: It isn't up to you to decide for > everybody else. That sure *reads* like an insult. What's your point? > I consider the tradeoff to be beyond "reasonable" to > "necessary." You are certainly entitled to your opinion, as am I. > >I think it is central to this debate that the nature of the > >strength "guarantee" is clear. It is certainly not true that > >BB&S is guaranteed not to be breakable, period. > > Sadly, correct. > > >Instead, we > >have that breaking (a given) BB&S has a certain probability. > > I'm not sure we really do have that probability, per se. I don't mean we know the probability, I mean that we know that the security is probabalistic. The enemy has some definite chance (not zero) of breaking the scheme. > Perhaps if we had such an expression we could begin to see the > numerical security consequences of the expected wild variations in > cycle structure in the casual construction. Indeed. > In my view, it is not > useful to simply have a mean value; indeed, the worst case (e.g., the > shortest non-degenerate cycle) is usually most appropriate to > cryptography. And, in a sense, the longer a "short cycle" is, the > more trouble it is (the more likely it is to be selected at random), > until the cycle length becomes "long enough" and it is no longer a > threat. Quite so. It would also be helpful to know the probabilities of the various cycle lengths. To be concrete, suppose for the sake of argument that we knew, for the modulus size we have chosen, that a short cycle would occur one time in 2^400. I would argue that the chance of a short cycle occurring is therefore so small that the chance of a bug in the cycle-length-checking code introducing a fatal insecurity is greater, and we would thus be fools to include such code. Of course, the problem is, as you say, that such concrete facts are not abundant. > >Using the special primes construction will change the > >probability by some amount. > > The special primes construction was the construction in the original > BB&S article. Do you have a problem with that? A problem with what? Should I be using different terminology? > >Neither you nor those who have disagreed with you have shown > >an actual computation of the improvement in probability. > > *Of* *course* I have shown "an actual computational improvement in > probability." I mean, no one (to my knowledge) has computed what the difference in probability is. (You might compare what I said with what you put in quotes.) > There is some probability of fault in the special primes construction. > That probability includes short cycle faults. I take away the short > cycle faults. The resulting probability of fault is less. QED. Clearly one cannot disagree with that. > Unfortunately, the proof is disturbingly silent about the actual > probability of flaws, and about the types of flaws that remain in > either construction. As long as the math is silent on the details, we > are left with "whatever weak cycles might have existed in the casual > construction have been eliminated," instead of "the probability of > weakness is z." Exactly. > >Thus, > >an implementor is left with choosing whose faith to believe. > > Such is always the case when the conventional wisdom is wrong. Please. The reason for the problem is not who's wrong, but the lack of concrete, numerical values on which to base a judgement. > >It's not "is the improvement non-zero?", but "how much is it > >worth?" Even a "modest" cost can sometimes be too much. > > Again, that comparison is not up to you. It's up to somebody, in each case. Whoever that is, would like to know what the actual cost and actual benefit of using the special primes construction is. All you have ever said is that the benefit is positive, not zero. Almost no one has ever disagreed with that. The "conventional wisdom" is that the actual improvement in security with the inclusion of the special primes construction, as opposed to without, is small enough to be ignored. Your position, as I understand it, is that the improvement can be reasonably expected to be large enough not to be ignored. I have seen no particular reason to choose one over the other. > It is common and widely accepted in practice that in many things it is > necessary to pay more the closer to perfection one comes. > > Since one cannot really hope for a "proven secure" cryptosystem to be > actually "guaranteed fault free" in practice, the best one can do is > to take the "proven secure" cryptosystem and eliminate the faults one > can do something about. (Including faults introduced by adding extra features.) > That may be the closest to perfection one can > get, and there is usually an escalating cost to perfection. Those > interested in perfection are often more than willing to pay. My only problem with this is that, if someone is interested in perfection, they had better not mess with BB&S, in any configuration. You can eliminate short cycles, but that won't give you a system with perfect security. For that matter, the proof that BB&S is breakable only if we can factor (well, OK, decide quadratic reciduousity) was made *without* requiring the special primes construction. Which means that including the special primes construction does not add to the proven strength. What it does, is add some unknown amount of security. It may be worth the cost, in some or even all situations, to include the special primes construction. I just can't see that there's any way for a bystander to judge, except by appeal to authority (yours or others). JM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 23:15:09 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4F64DD.AAB53A3B@t-online.de> References: <3B4F614C.97307C55@sandia.gov> Newsgroups: sci.crypt Lines: 47 John Myre wrote: > > Terry Ritter wrote: > <snip> > I replied: > > >It seems unreasonable to me unless and until one provides > > >a reason to believe that the improvement stands a chance of > > >being worth the cost. > > And Terry riposted: > > All this isn't about *you*: It isn't up to you to decide for > > everybody else. > > That sure *reads* like an insult. What's your point? As a third person, I would say that Terry Ritter didn't have an insult in mind. He meant that the cost issue is to be decided in each concrete case by the user of the application (and not us, who are only discussing in this group), I believe. [snip] > My only problem with this is that, if someone is interested > in perfection, they had better not mess with BB&S, in any > configuration. You can eliminate short cycles, but that won't > give you a system with perfect security. > > For that matter, the proof that BB&S is breakable only if > we can factor (well, OK, decide quadratic reciduousity) was > made *without* requiring the special primes construction. > Which means that including the special primes construction > does not add to the proven strength. What it does, is add > some unknown amount of security. > > It may be worth the cost, in some or even all situations, to > include the special primes construction. I just can't see > that there's any way for a bystander to judge, except by > appeal to authority (yours or others). I may be wrong, since my memory about the BBS paper is no longer good. Isn't it that the special primes construction is in the paper? M. K. Shen
Subject: Re: Q: Internet banking Date: Sun, 15 Jul 2001 07:20:32 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b51443d.7325968@news.io.com> References: <3B4F614C.97307C55@sandia.gov> Newsgroups: sci.crypt Lines: 187 On Fri, 13 Jul 2001 14:59:56 -0600, in <3B4F614C.97307C55@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >Terry Ritter wrote: [...] >> >I think it is central to this debate that the nature of the >> >strength "guarantee" is clear. It is certainly not true that >> >BB&S is guaranteed not to be breakable, period. >> >> Sadly, correct. >> >> >Instead, we >> >have that breaking (a given) BB&S has a certain probability. The BB&S security proof is probabilistic. Weak degenerate cycles do always exist in BB&S constructions, so the proof clearly does not represent the worst case. Yet in practice we can and do judge cryptosystems by the worst known flaw. And if we do that here, the system strength is always almost zero unless we eliminate degenerate cycles and short cycles. >> I'm not sure we really do have that probability, per se. > >I don't mean we know the probability, I mean that we know >that the security is probabalistic. The enemy has some >definite chance (not zero) of breaking the scheme. So it's just OK to leave known flaws in the design when we can fix those flaws at minimal expense? I don't think so. BB&S is a slow huge-integer system, and is already vastly more costly than, say, the huge and nonlinearized RNG's I build (and which have no strength proof). Since there is already a huge cost involved, why would anyone not spend a little more to eliminate some *known* worst-case faults? >[...] >It would also be helpful to know the probabilities of the >various cycle lengths. To be concrete, suppose for the sake >of argument that we knew, for the modulus size we have chosen, >that a short cycle would occur one time in 2^400. As I understand it, the determining factor for cycle structure is not really modulus size per se, but rather the specific relationship between the primes. I expect the cycle structure to vary wildly even with a fixed modulus, unless both primes are special. Again, one might get some mean value for probability here, but what we want to know is worst-case weakness, not average strength. >I would >argue that the chance of a short cycle occurring is therefore >so small that the chance of a bug in the cycle-length-checking >code introducing a fatal insecurity is greater, and we would >thus be fools to include such code. It's not like we can avoid using computer code. Nor is it like we can improve system strength by using the simplest possible RNG (e.g., a counter). Some amount of complexity is necessary for good cryptography. Simply choosing BB&S also means complex huge-integer math code and the ability to check and select primes. This is vastly more machinery than needed for "simple" Additive RNG's. Are they thus "better"? I have seen no claim that we should not use BB&S at all because we cannot guarantee the implementation. No, the claim is instead that we should not fix *known* faults in BB&S because that *might* induce other faults that we don't know. But we have to deal with possibility of faults throughout the implementation, and not just in fixing the math. Even if the repairs don't work, we are probably no worse off than if we had not tried to fix the system at all. >[...] >> >Thus, >> >an implementor is left with choosing whose faith to believe. >> >> Such is always the case when the conventional wisdom is wrong. > >Please. The reason for the problem is not who's wrong, but >the lack of concrete, numerical values on which to base a >judgement. The issue is not who is wrong, or even whose faith to believe, but instead one of gathering the facts, making one's own judgment, then trusting those conclusions in the face of the expected outrage of conventional wisdom. It seems to me that the minimum strengths in BB&S systems are quite likely to be short cycles. Eliminating those problems raises the cryptosystem strength to whatever the next step would be. The issue is not the *probability* of choosing a short cycle, but rather the mere existence of a short cycle which *could* be selected, since that sets the cryptographic strength of the system. >> >It's not "is the improvement non-zero?", but "how much is it >> >worth?" Even a "modest" cost can sometimes be too much. >> >> Again, that comparison is not up to you. > >It's up to somebody, in each case. Whoever that is, would >like to know what the actual cost and actual benefit of using >the special primes construction is. All you have ever said >is that the benefit is positive, not zero. Almost no one has >ever disagreed with that. I think the math exists to work out cycle lengths, but my impression is that it requires individual analysis. For example, I have a preprint of: Brennan, J. and B. Geist. 1998. Analysis of Iterated Modular Exponentiation: The Orbits of x**a mod N. Designs, Codes and Cryptography 13. 229-245. It is pretty rough going for me. >The "conventional wisdom" is that the actual improvement >in security with the inclusion of the special primes >construction, as opposed to without, is small enough to >be ignored. Your position, as I understand it, is that >the improvement can be reasonably expected to be large >enough not to be ignored. Ultimately, that depends upon what we define as "improvement." How about this: * First of all, deliberately leaving fixable flaws in cryptosystems is something we just do not do. Among other things, this is a matter of pride and expertise. * Next, the appropriate measure of the strength of a cryptosystem is not the average of all possibilities as seems acceptable to theoretical cryptography, but instead the minimum strength over all preventable possibilities. (The minimum strength of any keyed cipher is zero if the opponent guesses the key, but that is already handled by having a "large enough" key.) Normally we cannot compute such a value, but in this case, when short cycles are allowed for use, we know it is almost zero. >[...] >(Including faults introduced by adding extra features.) We have to find primes anyway, and it seems unlikely to me that finding special primes will be more error-prone. Perhaps the worst that could happen is that the special primes will be just ordinary primes, in which case we are back to the casual construction anyway. The computer program does have to work correctly, yes. Nothing about that is new. >> That may be the closest to perfection one can >> get, and there is usually an escalating cost to perfection. Those >> interested in perfection are often more than willing to pay. > >My only problem with this is that, if someone is interested >in perfection, they had better not mess with BB&S, in any >configuration. You can eliminate short cycles, but that won't >give you a system with perfect security. Eliminating short cycles will improve the system, and may improve the worst-case strength. If and when some other known flaw is exposed, we can fix that. Saying that we know of no such flaw, and so cannot fix it, so it may remain in the system, hardly seems a valid argument for doing nothing. Maybe there is no such other flaw. >[...] >It may be worth the cost, in some or even all situations, to >include the special primes construction. I just can't see >that there's any way for a bystander to judge, except by >appeal to authority (yours or others). A bystander in this discussion will just have to understand the issues and make and trust their own decision. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 23:03:24 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4F621C.42A8F29C@t-online.de> References: <3b4f4ae4.7581659@news.io.com> Newsgroups: sci.crypt Lines: 30 Terry Ritter wrote: > > John Myre <jmyre@sandia.gov> wrote: [snip] > >It's not "is the improvement non-zero?", but "how much is it > >worth?" Even a "modest" cost can sometimes be too much. > > Again, that comparison is not up to you. > > It is common and widely accepted in practice that in many things it is > necessary to pay more the closer to perfection one comes. > > Since one cannot really hope for a "proven secure" cryptosystem to be > actually "guaranteed fault free" in practice, the best one can do is > to take the "proven secure" cryptosystem and eliminate the faults one > can do something about. That may be the closest to perfection one can > get, and there is usually an escalating cost to perfection. Those > interested in perfection are often more than willing to pay. I believe that a decision in crypto is not 'inherently' different from one in engineering, where both money and risks are involved. One has somehow (not entirely objectively) to determine how much money to spend and get the most of that money. Note also in this connection that after certain expense the law of diminishing return sets in. M. K. Shen
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 07:55:57 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ieced$2cts$2@agate.berkeley.edu> References: <3b4aa25a.14033453@news.io.com> Newsgroups: sci.crypt Lines: 7 Terry Ritter wrote: >In practice, it is unreasonable to expect a zero chance of fault. But >we can hope that no *known* fault will be allowed to exist. No, unfortunately, we can't. In computational-based cryptography, there is always the possibility that someone guesses our private key. This is an example of a known fault that cannot be avoided.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 18:44:20 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4b4cf8.8138896@news.io.com> References: <9ieced$2cts$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 20 On Tue, 10 Jul 2001 07:55:57 +0000 (UTC), in <9ieced$2cts$2@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>In practice, it is unreasonable to expect a zero chance of fault. But >>we can hope that no *known* fault will be allowed to exist. > >No, unfortunately, we can't. In computational-based cryptography, >there is always the possibility that someone guesses our private key. >This is an example of a known fault that cannot be avoided. Yes, and short cycles are an example of a known fault which *can* be avoided. One might have thought the distinction was obvious. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 10:05:30 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4AB74A.A1C41D3C@t-online.de> References: <3b4aa25a.14033453@news.io.com> Newsgroups: sci.crypt Lines: 38 Terry Ritter wrote: > > If a short cycle happens to be selected, that allows factoring. > > What the proof means to me is that, asymptotically, it is at least as > hard to find a short cycle as it is to factor N. > > But "finding a short cycle" is not and has never been the issue. > Short cycles do exist and *may* be selected. This is equivalent to > accidentally using a weak key, and is a preventable weakness. > Checking for and not using weak keys is hardly unknown. > > We do *not* have to believe the math or assume factoring is hard to > address the use of short cycles. Instead, we can actually prevent > that use, and at reasonable cost. I know too little about BBS but would like to ask whether the argument of finding a short cycle is hard is based simply on the fact that the percentage of short cycles asymptotically goes to zero. If that were the case, then I suppose that one should in any case additionally assure that short cycles do not occur in 'special' locations but are 'randomly' distributed. For otherwise there could be a disaster, if, for some reason, the user happens to be habituated to operate in the region where the short cycles have a higher frequency to occur. M. K. Shen ----------------------------- P.S. It is a pleasure and honour for me to see that, evidently as a consequence of a chance error, experts come to discuss within the thread initiated by me on internet banking. I am taking the liberty to remark, though, that my original question about the status (in countries other than Germany) of home banking computer interfaces yet remains open.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 18:45:53 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4b4d52.8228944@news.io.com> References: <3B4AB74A.A1C41D3C@t-online.de> Newsgroups: sci.crypt Lines: 65 On Tue, 10 Jul 2001 10:05:30 +0200, in <3B4AB74A.A1C41D3C@t-online.de>, in sci.crypt Mok-Kong Shen <mok-kong.shen@t-online.de> wrote: >Terry Ritter wrote: >> >> If a short cycle happens to be selected, that allows factoring. >> >> What the proof means to me is that, asymptotically, it is at least as >> hard to find a short cycle as it is to factor N. >> >> But "finding a short cycle" is not and has never been the issue. >> Short cycles do exist and *may* be selected. This is equivalent to >> accidentally using a weak key, and is a preventable weakness. >> Checking for and not using weak keys is hardly unknown. >> >> We do *not* have to believe the math or assume factoring is hard to >> address the use of short cycles. Instead, we can actually prevent >> that use, and at reasonable cost. > >I know too little about BBS but would like to ask whether >the argument of finding a short cycle is hard is based >simply on the fact that the percentage of short cycles >asymptotically goes to zero. That's the only argument I've heard. >If that were the case, then >I suppose that one should in any case additionally assure >that short cycles do not occur in 'special' locations but >are 'randomly' distributed. For otherwise there could >be a disaster, if, for some reason, the user happens to >be habituated to operate in the region where the short >cycles have a higher frequency to occur. But if we use the special primes construction, and then check that we are not using degenerate cycles (this just takes two RNG steps), we *eliminate* the problem completely. We *guarantee* that we do not use a degenerate cycle. We *guarantee* that all remaining "short" cycles are "long enough" to use, so we just use whatever we get. In contrast, if the special primes construction is not used, there is no control over the cycle structure of the system. We expect many more cycles, with many more states in cycles which may be dangerously short and yet not degenerate, and so are more difficult to eliminate. (There are approaches one could take, but they would be substantially more expensive.) >M. K. Shen >----------------------------- >P.S. It is a pleasure and honour for me to see that, >evidently as a consequence of a chance error, experts come >to discuss within the thread initiated by me on internet >banking. I am taking the liberty to remark, though, that >my original question about the status (in countries other >than Germany) of home banking computer interfaces yet >remains open. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: 12 Jul 2001 06:32:48 -0700 From: Simon.Johnson6@btinternet.com (Simon Johnson) Message-ID: <c0879d5f.0107120532.35ebfad4@posting.google.com> References: <3b4b4d52.8228944@news.io.com> Newsgroups: sci.crypt Lines: 47 ritter@io.com (Terry Ritter) wrote in message news:<3b4b4d52.8228944@news.io.com>... > On Tue, 10 Jul 2001 10:05:30 +0200, in > <3B4AB74A.A1C41D3C@t-online.de>, in sci.crypt Mok-Kong Shen > <mok-kong.shen@t-online.de> wrote: > > >Terry Ritter wrote: > >> > >> If a short cycle happens to be selected, that allows factoring. > >> > >> What the proof means to me is that, asymptotically, it is at least as > >> hard to find a short cycle as it is to factor N. > >> > >> But "finding a short cycle" is not and has never been the issue. > >> Short cycles do exist and *may* be selected. This is equivalent to > >> accidentally using a weak key, and is a preventable weakness. > >> Checking for and not using weak keys is hardly unknown. > >> > >> We do *not* have to believe the math or assume factoring is hard to > >> address the use of short cycles. Instead, we can actually prevent > >> that use, and at reasonable cost. > > > >I know too little about BBS but would like to ask whether > >the argument of finding a short cycle is hard is based > >simply on the fact that the percentage of short cycles > >asymptotically goes to zero. > > That's the only argument I've heard. > > > >If that were the case, then > >I suppose that one should in any case additionally assure > >that short cycles do not occur in 'special' locations but > >are 'randomly' distributed. For otherwise there could > >be a disaster, if, for some reason, the user happens to > >be habituated to operate in the region where the short > >cycles have a higher frequency to occur. > > But if we use the special primes construction, and then check that we > are not using degenerate cycles (this just takes two RNG steps), we > *eliminate* the problem completely. We *guarantee* that we do not use > a degenerate cycle. We *guarantee* that all remaining "short" cycles > are "long enough" to use, so we just use whatever we get. There are still weak keys... Try 0 & 1. I presume that you meant to include these to. Simon.
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 21:38:04 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4e1890.2228793@news.io.com> References: <c0879d5f.0107120532.35ebfad4@posting.google.com> Newsgroups: sci.crypt Lines: 34 On 12 Jul 2001 06:32:48 -0700, in <c0879d5f.0107120532.35ebfad4@posting.google.com>, in sci.crypt Simon.Johnson6@btinternet.com (Simon Johnson) wrote: >ritter@io.com (Terry Ritter) wrote in message news:<3b4b4d52.8228944@news.io.com>... >>[...] >> But if we use the special primes construction, and then check that we >> are not using degenerate cycles (this just takes two RNG steps), we >> *eliminate* the problem completely. We *guarantee* that we do not use >> a degenerate cycle. We *guarantee* that all remaining "short" cycles >> are "long enough" to use, so we just use whatever we get. > >There are still weak keys... Try 0 & 1. I presume that you meant to >include these to. OK. 0: 0**2 (mod N) == 0. Looks like a degenerate cycle to me. 1: 1**2 (mod N) == 1. Looks like a degenerate cycle to me. "Degenerate" cycles are just "single state" cycles. I distinguish them from ordinary cycles, because there does not seem to be much "cycling" going on -- the result is just a constant value. Degenerate cycles are easy to find by saving the current x, taking a step, then seeing if the result has changed. In practice, we want to take one step before saving x for comparison, as the structure of BB&S includes "lead-in" steps. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 09:35:14 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4AB032.219C69F1@t-online.de> References: <9ie6ff$27bs$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 24 David Wagner wrote: > > Therefore, it is reasonable to ask Intel to use floating point algorithms > that have a zero chance of error, but it is not reasonable to ask crypto > manufacturers to provide crypto algorithms that have a zero chance of > being broken. It is a sad and astonishing (to the public) fact that, after decades of research and development (incurring very substantial costs) in verification of chip logics, errors like those of Intel recur. (There are special programming languages and systems of logic destined to prove that something really does what it should do.) On the other hand, I am convinced that no real design engineer ever has the illusion that his chip can be absolutely perfect. In fact, no engineer in any other fields of engineering ever does so, unless he has an substantial psychological problem. Yet mathematics demands perfection and with mathematical crypto one seems to have naturally 'inherited' that demand. M. K. Shen
Subject: Re: Q: Internet banking Date: Sun, 15 Jul 2001 01:08:45 GMT From: jsavard@ecn.ab.SBLOK.ca.nowhere (John Savard) Message-ID: <3b50ecc0.509046@news.powersurfr.com> References: <9id9vv$1bog$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 12 On Mon, 9 Jul 2001 22:07:59 +0000 (UTC), daw@mozart.cs.berkeley.edu (David Wagner) wrote, in part: >In the absence of a proof that the extension adds strength, you might >as well omit it, if all you care about is what can be proven. But since it is _known_ that short cycles may result from the use of other primes, and since short cycles are not secure, I find it hard to believe that using the strong primes is inappropriate. John Savard http://home.ecn.ab.ca/~jsavard/index.html
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 05:10:28 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4a8e35.8875939@news.io.com> References: <20010709202044.1740.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 180 On 9 Jul 2001 20:20:44 -0000, in <20010709202044.1740.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: >Terry Ritter writes: > >> I claim that avoiding weak keys does in fact "strengthen" BB&S by >> avoiding the possibility that a weak key might be used. Furthermore, >> since that is raw fact, the only possible debate is over how useful >> that strengthening really is. And since the issue may include both >> confidence for the user and professional pride for the designer, I >> doubt mathematics can resolve it. > >But if it does strengthen BBS, then you should be able to quantify >the degree of strengthening. That is an obvious non sequitur: Avoiding weak keys obviously increases strength; whether or not I personally can quantify that is something else again. Science is not about winning arguments by using the techniques of propaganda. >We can, after all, quantify the strength >of BBS, at least in principle. That would of course be "academic strength." >We can show how many calls to the BBS >prediction oracle are necessary to have a given chance of factoring N. >This is the basis for our belief in the strength of BBS. Quantification is *not* the basis for belief in strength. In fact, it is usually deceptive: It is not at all unusual for newbies to talk about how long it would take to break their cipher which uses a huge key. But ciphers are rarely broken the way the designer intends, and quantification on that basis is amusingly false. Real strength in practice is what occurs when our ciphertext contacts the opponents. But we do not know those opponents, nor even what they can do, because they do not tell us. We thus cannot know the real strength of our systems, and any attempt quantify real strength is academic delusion. >There is no reason for debate. The issue of increased strength when we are prevented from using weak short cycles we might otherwise have used is of course indisputable. >It is not a subjective issue where user >confidence and professional pride enter into it. Actually, strength in practice is inherently subjective: we have no idea what the real strength of our ciphers might be, because we do not know what our opponents know. Strength is also contextual, because it depends upon what any particular group of opponents knows. Even negligably-rare possibilities are significant in real systems. For example, the original Intel Pentium chip had an arithmetic fault which "almost never" occurred in practice. Intel argued that this was really no fault at all, and so they would not replace such chips. But their customers saw things differently. If our cryptosystem is intended to support even as much confidence as people want from arithmetic computation, we must fix all known faults, even very rare ones. That of course does not mean that no other faults exist. It does mean we do all we can. >This is mathematics. Mathematics is only an approximate model of reality, and captures only part of the story. In particular, it does not model the feelings of a user who has been assured of the mathematically proven strength of his system, only to find that extremely rare faults are known and were not treated seriously. People get fired for that. >Either you can strengthen BBS or not. Well, I can certainly strengthen your false BB&S construction which does not follow the BB&S article. Normally, we expect a name to mean something. The BB&S article gives a prescription which includes the special primes construction. When your construction does not use special primes, you are not following the prescription of the BB&S article, but instead doing something else. You are taking a particular published description and doing something else while using that respected name. Frankly, that is a "no, no." >We can calculate numerically how >strong BBS is, in terms of numbers of oracle calls to break the modulus. >If your method strengthens it, it should lead to a larger numerical >estimate of that strength. Again, any such computation is not about real strength, but instead some form of academic strength. BB&S academic strength estimates are typically asymptotic. A small increase in strength need not show up in such computations. But it would be logically false to say that such a result implies that no strength increase has occurred. Any such computation made to sufficient precision must show an increase in strength from not using short weak cycles. >You need to tell us what that number is, >for people to judge whether the additional expense of generating special >primes is worth it. Do you really imagine that cryptographic tradeoffs are made on the basis of quantified strength vs. expense? Do you really imagine that open mathematics has the ability to quantify cryptographic strength? If so, you seriously deluded: Unless we know what the opponents know, we have no basis on which to analyze what they can do. And we do not. A realistic approach is a rational recognition of a real possibility of weakness, with a resolve to pay a reasonable cost to avoid such weakness. In this case, once the front-end cost is paid for finding special primes, the per-use cost of avoiding degenerate cycles is only a small part of generating any sequence of reasonable length. >Imagine a bridge made of steel. We have calculated its strength >numerically. Now a magician proposes to put a magic spell on it to make >it stronger. The designer is skeptical and asks him to calculate how >many more tonnes of traffic it can hold. The magician claims this will >increase user confidence and add professional pride, but that mathematics >cannot resolve it. The facts are pretty much self-evident and conclusive: 1. Nobody doubts that BB&S systems are not "maximal length" RNG's, and that multiple cycles do exist, including degenerate "cycles." 2. Nobody can doubt that if one uses a degenerate cycle, the resulting sequence is weak (it is in fact a constant). 3. Nobody can doubt that if one simply chooses starting values at random, it is possible to select a degenerate cycle. 4. Nobody can doubt that if the possibility of choosing a weak sequence exists -- AT ANY LEVEL OF PROBABILITY -- and we prevent that, academic strength has thus increased. There is nothing disputable about this. In fact, the false BB&S construction produces a system which can vary wildly in the resulting cycle structure, so that few general statements can be made about it. This inability to analyze the general system is *not* a mathematical advantage. In contrast, real BB&S uses the special primes construction and the cycle structure *can* be analyzed and understood. That *is* an advantage, and it is a *mathematical* advantage of the special primes construction itself. >Who is more convincing, the one who relies on mathematics, or the one who >says that the strength of a construction (cryptographic or mechanical) >cannot be resolved mathematically? I am not here to "convince" the reader. My role is to call it as I see it, and lay out the argument as clearly as I can, so that anyone who cares to can come to their own decision. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 06:18:53 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ie6od$27bs$2@agate.berkeley.edu> References: <3b4a8e35.8875939@news.io.com> Newsgroups: sci.crypt Lines: 13 Terry Ritter wrote: >BB&S academic strength estimates are typically asymptotic. This is just a historical accident. There is nothing fundamental about asymptotics. At the time, asymptotics were considered sufficient. If the BB&S paper had been written today, there is a much greater chance it would include concrete security estimates. You can extract a concrete security result from all those asymptotic proofs, once you understand them sufficiently. Indeed, Dan Bernstein posted here a concrete security version of a classic asymptotic result.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 06:45:34 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4aa47c.14580221@news.io.com> References: <9ie6od$27bs$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 32 On Tue, 10 Jul 2001 06:18:53 +0000 (UTC), in <9ie6od$27bs$2@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>BB&S academic strength estimates are typically asymptotic. > >This is just a historical accident. There is nothing fundamental about >asymptotics. > >At the time, asymptotics were considered sufficient. If the BB&S paper >had been written today, there is a much greater chance it would include >concrete security estimates. > >You can extract a concrete security result from all those asymptotic >proofs, once you understand them sufficiently. Indeed, Dan Bernstein >posted here a concrete security version of a classic asymptotic result. Then I suggest that you or Dan follow that up. The necessary results, however, are not in dispute: Eliminating the use of short cycles which might otherwise be used means there are fewer cases in which weakness can occur. If the numbers do not reflect that, the computation must be wrong, biased, of insufficient precision, or just not sufficiently comprehensive to reflect this reality. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 08:01:40 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9iecp4$2cts$3@agate.berkeley.edu> References: <3b4aa47c.14580221@news.io.com> Newsgroups: sci.crypt Lines: 12 Terry Ritter wrote: >Then I suggest that you or Dan follow that up. Why would I want to? You're the one claiming that the conventional wisdom is wrong. You're claiming that checking for short cycles makes a non-negligible difference to security. The burden is on you to convince us. You could convince us by giving us a proof. Feel free to do so. However, I'm not going to do your work for you, especially when I (and pretty much everyone else who has weighed in on this topic) find it pretty clear that the result is not going to support your position.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 18:48:19 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4b4dab.8318114@news.io.com> References: <9iecp4$2cts$3@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 55 On Tue, 10 Jul 2001 08:01:40 +0000 (UTC), in <9iecp4$2cts$3@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>Then I suggest that you or Dan follow that up. > >Why would I want to? You're the one claiming that the conventional >wisdom is wrong. Here you are close to committing the logical fallacy of "appeal to authority." Entrenched belief does not argue, and therefore does not weigh either side. But if you see that the conventional wisdom may be wrong, you may have a responsibility to try and put it right. >You're claiming that checking for short cycles makes >a non-negligible difference to security. No. It is you who somehow feels empowered to decide what "negligible" means. And that is *not* your call. That is for the designer and user to decide in concert with *their* goals and *their* costs. The role of a scientist is to display the facts, and not to decide unilaterally how those facts should be used. >The burden is on you to >convince us. No. My burden is limited to presenting the argument. It is necessary for each reader to convince themselves, or not. This is Science, not Marketing. >You could convince us by giving us a proof. Feel free to do so. However, >I'm not going to do your work for you, especially when I (and pretty >much everyone else who has weighed in on this topic) find it pretty >clear that the result is not going to support your position. The proof is obvious: It is OBVIOUS that eliminating short cycles does reduce the weakness in the system. No more proof is needed. If the math does not give these results, the math is wrong. The only possible dispute is whether the amount of improvement is worth the cost, and that is not an issue for math. If math thinks otherwise, it oversteps. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: 11 Jul 2001 04:26:42 -0700 From: Simon.Johnson6@btinternet.com (Simon Johnson) Message-ID: <c0879d5f.0107110326.5c1bd3f6@posting.google.com> References: <3b4b4dab.8318114@news.io.com> Newsgroups: sci.crypt Lines: 57 ritter@io.com (Terry Ritter) wrote in message news:<3b4b4dab.8318114@news.io.com>... > On Tue, 10 Jul 2001 08:01:40 +0000 (UTC), in > <9iecp4$2cts$3@agate.berkeley.edu>, in sci.crypt > daw@mozart.cs.berkeley.edu (David Wagner) wrote: > > >Terry Ritter wrote: > >>Then I suggest that you or Dan follow that up. > > > >Why would I want to? You're the one claiming that the conventional > >wisdom is wrong. > > Here you are close to committing the logical fallacy of "appeal to > authority." Entrenched belief does not argue, and therefore does not > weigh either side. > > But if you see that the conventional wisdom may be wrong, you may have > a responsibility to try and put it right. > > > >You're claiming that checking for short cycles makes > >a non-negligible difference to security. > > No. It is you who somehow feels empowered to decide what "negligible" > means. And that is *not* your call. That is for the designer and > user to decide in concert with *their* goals and *their* costs. > > The role of a scientist is to display the facts, and not to decide > unilaterally how those facts should be used. > > > >The burden is on you to > >convince us. > > No. My burden is limited to presenting the argument. It is necessary > for each reader to convince themselves, or not. This is Science, not > Marketing. > > > >You could convince us by giving us a proof. Feel free to do so. However, > >I'm not going to do your work for you, especially when I (and pretty > >much everyone else who has weighed in on this topic) find it pretty > >clear that the result is not going to support your position. > > The proof is obvious: It is OBVIOUS that eliminating short cycles > does reduce the weakness in the system. No more proof is needed. If > the math does not give these results, the math is wrong. > > The only possible dispute is whether the amount of improvement is > worth the cost, and that is not an issue for math. If math thinks > otherwise, it oversteps. What is useless is asking math - "What cycle length is acceptable?".. Math cannot ever answer questions like this as you point out. A better question, and one i've not seen answered, is "What is the Average cycle length for a given seed?" Simon.
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 21:36:38 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4e1848.2156470@news.io.com> References: <c0879d5f.0107110326.5c1bd3f6@posting.google.com> Newsgroups: sci.crypt Lines: 95 On 11 Jul 2001 04:26:42 -0700, in <c0879d5f.0107110326.5c1bd3f6@posting.google.com>, in sci.crypt Simon.Johnson6@btinternet.com (Simon Johnson) wrote: >ritter@io.com (Terry Ritter) wrote in message news:<3b4b4dab.8318114@news.io.com>... >> On Tue, 10 Jul 2001 08:01:40 +0000 (UTC), in >> <9iecp4$2cts$3@agate.berkeley.edu>, in sci.crypt >> daw@mozart.cs.berkeley.edu (David Wagner) wrote: >> >> >Terry Ritter wrote: >> >>Then I suggest that you or Dan follow that up. >> > >> >Why would I want to? You're the one claiming that the conventional >> >wisdom is wrong. >> >> Here you are close to committing the logical fallacy of "appeal to >> authority." Entrenched belief does not argue, and therefore does not >> weigh either side. >> >> But if you see that the conventional wisdom may be wrong, you may have >> a responsibility to try and put it right. >> >> >> >You're claiming that checking for short cycles makes >> >a non-negligible difference to security. >> >> No. It is you who somehow feels empowered to decide what "negligible" >> means. And that is *not* your call. That is for the designer and >> user to decide in concert with *their* goals and *their* costs. >> >> The role of a scientist is to display the facts, and not to decide >> unilaterally how those facts should be used. >> >> >> >The burden is on you to >> >convince us. >> >> No. My burden is limited to presenting the argument. It is necessary >> for each reader to convince themselves, or not. This is Science, not >> Marketing. >> >> >> >You could convince us by giving us a proof. Feel free to do so. However, >> >I'm not going to do your work for you, especially when I (and pretty >> >much everyone else who has weighed in on this topic) find it pretty >> >clear that the result is not going to support your position. >> >> The proof is obvious: It is OBVIOUS that eliminating short cycles >> does reduce the weakness in the system. No more proof is needed. If >> the math does not give these results, the math is wrong. >> >> The only possible dispute is whether the amount of improvement is >> worth the cost, and that is not an issue for math. If math thinks >> otherwise, it oversteps. > >What is useless is asking math - "What cycle length is acceptable?".. >Math cannot ever answer questions like this as you point out. A better >question, and one i've not seen answered, is "What is the Average >cycle length for a given seed?" With the casual construction any such answer will be complex. The advantage of the special primes construction is to place the cycle structure under control. Then it *can* be analyzed so things can be said about what that structure is, and how that can be optimally used. But until the cycle structure is under control, the possibilities are extremely general. The casual construction actually includes the special primes construction as a tiny proper subset, so it is clearly not always worse. But the cycle structure is so varied that it is difficult to capture in a few simple statements. Degenerate cycles do always exist, but in practice we can easily avoid those. Whether cycles exist which are short enough to be a practical danger depends upon the form of the modulus. Then we might talk about the probability of having such a modulus, but unless we can avoid such a modulus, that really has not solved the problem. Even if dangerous cycles do exist in a selected modulus, we expect the number states leading to and within those cycles to be such a tiny fraction of N as to be very unlikely to be selected at random. But "unlikely" is not "impossible." That is a known weakness; an unfixed flaw. The possibility exists that one might guarantee a lack of dangerous cycles by using a modulus of a simpler special form without going all the way to the special primes construction. That would be nice, but the special primes construction is all we have now, and we ought to be thankful we have that. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: 11 Jul 2001 14:44:21 GMT From: mdw@nsict.org (Mark Wooding) Message-ID: <slrn9kopi5.qfl.mdw@daryl.nsict.org> References: <3b4b4dab.8318114@news.io.com> Newsgroups: sci.crypt Lines: 23 Terry Ritter <ritter@io.com> wrote: > >You're claiming that checking for short cycles makes > >a non-negligible difference to security. > > No. It is you who somehow feels empowered to decide what "negligible" > means. And that is *not* your call. That is for the designer and > user to decide in concert with *their* goals and *their* costs. Wrong. The word `negligible' has a technical meaning in provable- security cryptography. A function f(k) is `negligible in k' if f(k) < 1/c(k) for all polynomial functions c(k) and sufficiently large k. Usually, k is a `security parameter', e.g., the size of the BBS modulus. We make the assumption that factoring is `hard' -- i.e., a probabilistic algorithm constrained to run in time polynomial in k has negligible probability of successfully factoring a randomly chosen k-bit number. The reduction from BBS prediction to factoring shows that the probability of finding a cycle, short or not, must be negligible under our assumption. (The proof of this statement, by contradiction, is obvious.) -- [mdw]
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 21:39:33 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4e18be.2274911@news.io.com> References: <slrn9kopi5.qfl.mdw@daryl.nsict.org> Newsgroups: sci.crypt Lines: 52 On 11 Jul 2001 14:44:21 GMT, in <slrn9kopi5.qfl.mdw@daryl.nsict.org>, in sci.crypt mdw@nsict.org (Mark Wooding) wrote: >Terry Ritter <ritter@io.com> wrote: > >> >You're claiming that checking for short cycles makes >> >a non-negligible difference to security. >> >> No. It is you who somehow feels empowered to decide what "negligible" >> means. And that is *not* your call. That is for the designer and >> user to decide in concert with *their* goals and *their* costs. > >Wrong. The word `negligible' has a technical meaning in provable- >security cryptography. A function f(k) is `negligible in k' if f(k) < >1/c(k) for all polynomial functions c(k) and sufficiently large k. >Usually, k is a `security parameter', e.g., the size of the BBS modulus. > >We make the assumption that factoring is `hard' -- i.e., a probabilistic >algorithm constrained to run in time polynomial in k has negligible >probability of successfully factoring a randomly chosen k-bit number. >The reduction from BBS prediction to factoring shows that the >probability of finding a cycle, short or not, must be negligible under >our assumption. (The proof of this statement, by contradiction, is >obvious.) While not wrong, your response is both beside the point and deceptive. Simply because something is "negligible" within the context of a proof does not necessarily make it also "negligible" to designers and users who have different criteria. Math is not the sole owner of the word "negligible." It is quite clear that math guys who accept the proof also are willing to accept the tiny *additional* probability of exposure that short cycles bring. And they have been willing to accept this added risk despite the fact that the original BB&S article shows how it may be avoided. Accepting additional risk is just fine -- as long as only your own data are involved. But it may not be quite so fine for cipher designers and users, who may have their own view of "negligible." No matter how unlikely they may be, short cycles do represent an additional risk which can be eliminated at modest or trivial cost. They are the "weak keys" of BB&S, and what to do about them is a design issue, not a math issue. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 16:48:20 -0400 From: Shai Halevi <shaih@watson.ibm.com> Message-ID: <3B4B6A14.F0D3CA9A@watson.ibm.com> References: <3b49334b.4281079@news.io.com> Newsgroups: sci.crypt Lines: 42 Terry Ritter wrote: > There is a very good reason to use the special primes construction as > given in the original BB&S article: > > Failing to use the special primes construction creates a -- admittedly > tiny -- possibility that usefully short cycles may exist and may be > selected at random. And if that should happen, the proven secure > generator is not secure. Yet the whole point of using BB&S is to end > up with a secure generator. [...] > --- > Terry Ritter ritter@io.com http://www.io.com/~ritter/ > Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM I don't think that this is the reason for these special primes. Terry's argument seems to assume that a product of random "special primes" is less likely to be factorized than a product of just random primes. That assumption is widely believed to be false. The only other explanation that I've heard for these special primes, is the so-called "1st party attack": I generate my modulus in such a way to ensure that it has some known weakness (e.g., only small cycles), and then use that weakness to repudiate transactions that I did using that modulus. (That is, I go to court and complain that someone broke my public key, since it has that specific weakness.) To me, that scenario sounds quite dubious. After all, I might as well complain that someone was lucky enough to guess my secret key. (From a mathematical point of view, both complaints are more or less equally likely.) The only plausible justification that I can think of is a psychological one: The court may dismiss out-of-hand the latter complaint, since it sounds so absurd, while the former complaint may sound more "mathematically involved", and the court may not know enough to immediately discard it. -- Shai p.s. As far as I can tell, the "1st party attack" does not apply to pseudorandom generators. Maybe the reason that people suggest to use it there, is that they just got use to think that "special primes are better."
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 22:15:35 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4b7e4b.20768076@news.io.com> References: <3B4B6A14.F0D3CA9A@watson.ibm.com> Newsgroups: sci.crypt Lines: 99 On Tue, 10 Jul 2001 16:48:20 -0400, in <3B4B6A14.F0D3CA9A@watson.ibm.com>, in sci.crypt Shai Halevi <shaih@watson.ibm.com> wrote: >Terry Ritter wrote: > >> There is a very good reason to use the special primes construction as >> given in the original BB&S article: >> >> Failing to use the special primes construction creates a -- admittedly >> tiny -- possibility that usefully short cycles may exist and may be >> selected at random. And if that should happen, the proven secure >> generator is not secure. Yet the whole point of using BB&S is to end >> up with a secure generator. [...] >> --- >> Terry Ritter ritter@io.com http://www.io.com/~ritter/ >> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM > >I don't think that this is the reason for these special primes. Terry's argument >seems to assume that a product of random "special primes" is less likely to be >factorized than a product of just random primes. But I do not so assume. I think you have misunderstood, so I have somehow failed to communicate. Let me make my position plain: First of all, any BB&S construction defines a system with multiple cycles of varying length; BB&S is not a "maximal length" RNG design. Abstractly, the possibility exists that the construction will have "weak" cycles short enough to actually repeat in use, and if we select a seed at random, we may select such a cycle. If that happens, when the cycle starts to repeat the sequence has become absolutely predictable with no strength at all, independent of all proof guarantees. Presumably we can also use the repeating cycle length to help factor N, which links the situation to the proof. I believe the special primes construction defines a system with a simplified cycle structure. That structure includes a few degenerate cycles, and a few "short" cycles. But if we use primes of public-key size, even the so-called "short" cycles are long enough for practical use. That means we can absolutely eliminate the possibility of selecting and using a weak cycle merely by avoiding degenerate cycles, and we can do that in just a couple of RNG steps. In contrast, the more casual construction which is now used does not control the cycle structure of the resulting system. Not only do we have the degenerate cycles, but we may also well have weak cycles which are *not* degenerate. In this case, simply avoiding degenerate cycles is not sufficient to avoid selecting and using weak cycles. I do not imply that randomly choosing a "too short" cycle is likely in practice, even with the casual construction. Nor is this an attackable weakness, but is instead somewhat comparable to using a weak key in a cipher which has weak keys. In such a situation, sometimes the decision is made to simply choose keys at random anyway, because the possibility of weakness is not deemed worth checking. Nevertheless, sometimes implementations *do* check for and eliminate weak keys without great consternation and derision from other cryptographers. Any decision to avoid weak keys is a user and designer decision, and not fundamentally a math decision. Furthermore, BB&S is sort of a special case. Even an extremely tiny possibility of known weakness does represent an odd a risk in a system specifically designed for *proven* strength. If the known weakness can be absolutely avoided at minimal cost, I claim that doing so can be a rational decision for a cipher designer. That's it. >That assumption is widely >believed to be false. > >The only other explanation that I've heard for these special primes, is the >so-called "1st party attack": I generate my modulus in such a way to ensure that >it has some known weakness (e.g., only small cycles), and then use that weakness >to repudiate transactions that I did using that modulus. (That is, I go to court >and complain that someone broke my public key, since it has that specific >weakness.) > >To me, that scenario sounds quite dubious. After all, I might as well complain >that someone was lucky enough to guess my secret key. (From a mathematical point >of view, both complaints are more or less equally likely.) > >The only plausible justification that I can think of is a psychological one: The >court may dismiss out-of-hand the latter complaint, since it sounds so absurd, >while the former complaint may sound more "mathematically involved", and the court >may not know enough to immediately discard it. > >-- Shai > >p.s. As far as I can tell, the "1st party attack" does not apply to pseudorandom >generators. Maybe the reason that people suggest to use it there, is that they >just got use to think that "special primes are better." --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: BBS and false analogies Date: Tue, 10 Jul 2001 22:19:10 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B4B714E.417F83EB@zetnet.co.uk> References: <3b4a8e48.8894712@news.io.com> Newsgroups: sci.crypt Lines: 64 -----BEGIN PGP SIGNED MESSAGE----- Terry Ritter wrote: > As far as I know, the sole known *weakness* of BB&S is the existence > and possible use of short cycles, especially in the ordinary > construction. This flaw was eliminated in the original BB&S article > with modest front-end cost, but high per-use cost. It now turns out > that we can do the same thing at negligible per-use cost. Merely by > using the special primes construction from the BB&S article, all > "short" cycles are known to be "long enough" for use except degenerate > cycles, which we can easily test with just a couple of steppings. > > The usual mathematical spin on this is that the security improvement > thus gained is so modest as to be lost in the asymptotic results. > However, we have actual experience with what users expect perfection > to mean: > > The original Intel Pentium design also had a flaw. Very rarely, it > would produce incorrect arithmetic results. It was such an unlikely > flaw that it hardly every occurred. No, this is a false analogy. The Pentium FDIV bug was *not* unlikely in the same sense as short cycles in BBS; in fact it was perfectly reproducible, and for some (useful) programs, it would happen with probability 1. Intel's PR department were disingenuous in ever claiming otherwise. (Actually, the claim that the bug is "unlikely" to occur doesn't even make sense, since the inputs to FDIV, unlike BBS moduli, are not chosen randomly.) > As Intel learned, the issue was not actual wrong answers, but instead > lack of confidence. The issue was very much actual wrong answers: there are many applications for which the consequences of an incorrect floating point computation can be very serious. That's why operating systems and some C runtime libraries still contain code to detect the faulty chips and provide a correct emulation of FDIV. There was *also* the issue of the arrogant way in which Intel dismissed public criticism, but it would be a mistake to assume that the bug itself wasn't serious. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBO0tsejkCAxeYt5gVAQGRewf8DrIcnay59qJ7HuuBd0SgHpN2UxGsc51E drfxiFU4WMZZGp/IniuVKj8wdW3DMsT4hJMASE7e97GdRvs3NINhPATYdM3bhvsV yZRJRayur9UA2umXhu+Ab1Ae3AHAn2iBWqY+WzmkkgDqRqjg99cwFRFu1fBae5ku WTOMGhhwWEXtfaBoOy5ynOXblIvhnV8nxVIrKEYhlqMFzUJLhuWZKitPZQWFDsZy 9nDVbfkOWj7ykMAvIWMUvx+tJWxuCYIL97W44hgutDnBj7AbRvrjy94kUdOJfc4k 0aKY6lhxRu7AAJOaILql01UQYhMzxFXtMauCXSC8tE7Jq4BTgrIVVw== =2ZYi -----END PGP SIGNATURE-----
Subject: Re: BBS and false analogies Date: Wed, 11 Jul 2001 04:08:11 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4bd102.3106546@news.io.com> References: <3B4B714E.417F83EB@zetnet.co.uk> Newsgroups: sci.crypt Lines: 89 On Tue, 10 Jul 2001 22:19:10 +0100, in <3B4B714E.417F83EB@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >-----BEGIN PGP SIGNED MESSAGE----- > >Terry Ritter wrote: >> As far as I know, the sole known *weakness* of BB&S is the existence >> and possible use of short cycles, especially in the ordinary >> construction. This flaw was eliminated in the original BB&S article >> with modest front-end cost, but high per-use cost. It now turns out >> that we can do the same thing at negligible per-use cost. Merely by >> using the special primes construction from the BB&S article, all >> "short" cycles are known to be "long enough" for use except degenerate >> cycles, which we can easily test with just a couple of steppings. >> >> The usual mathematical spin on this is that the security improvement >> thus gained is so modest as to be lost in the asymptotic results. >> However, we have actual experience with what users expect perfection >> to mean: >> >> The original Intel Pentium design also had a flaw. Very rarely, it >> would produce incorrect arithmetic results. It was such an unlikely >> flaw that it hardly every occurred. > >No, this is a false analogy. The Pentium FDIV bug was *not* unlikely >in the same sense as short cycles in BBS; in fact it was perfectly >reproducible, and for some (useful) programs, it would happen with >probability 1. Intel's PR department were disingenuous in ever claiming >otherwise. (Actually, the claim that the bug is "unlikely" to occur >doesn't even make sense, since the inputs to FDIV, unlike BBS moduli, >are not chosen randomly.) Yes, the analogy is valid: The BB&S short cycle flaw is just as reproducible as the FDIV bug, as long as the modulus is not changed, and that is a common case. Often, the modulus is computed once and kept for repeated use, with only the seed x0 selected at random on a per-use basis. But even if the modulus did change, the flaw *potential* would remain. The casual construction just does not have cycle-structure guarantees whether the modulus is changed or not. So the possibility of short cycles would still be there, and such cycles might be selected and used at any seed init time. In the same way, users imagined that an FDIV error might occur in any computation. This is the same issue. >> As Intel learned, the issue was not actual wrong answers, but instead >> lack of confidence. > >The issue was very much actual wrong answers: there are many applications >for which the consequences of an incorrect floating point computation >can be very serious. That's why operating systems and some C runtime >libraries still contain code to detect the faulty chips and provide a >correct emulation of FDIV. Clearly, with BB&S, "there are many applications for which the consequences" of selecting a short cycle "can be very serious." A short cycle is insecure the moment it begins to repeat. That is unquestionable weakness from a "proven secure" generator. We do not have to live with that, since we can avoid it at minimal cost. >There was *also* the issue of the arrogant way in which Intel dismissed >public criticism, but it would be a mistake to assume that the bug itself >wasn't serious. The FDIV bug produced wrong results, but few such results were actually seen. The hubbub was more about *the* *possibility* of wrong answers, rather than wrong answers themselves. That is lack of confidence. The worry about BB&S is also lack of confidence: we have extremely rare faults which are accepted and tolerated instead of being eliminated. With BB&S the math guys seem to say: "Yeah, it's a weakness. But who cares, it's so rare you'll never see it." And that corresponds very well to the Intel response to their FDIV bug. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS and false analogies Date: 11 Jul 2001 08:01:17 -0700 From: Simon.Johnson6@btinternet.com (Simon Johnson) Message-ID: <c0879d5f.0107110701.242b8ff6@posting.google.com> References: <3b4bd102.3106546@news.io.com> Newsgroups: sci.crypt Lines: 97 ritter@io.com (Terry Ritter) wrote in message news:<3b4bd102.3106546@news.io.com>... > On Tue, 10 Jul 2001 22:19:10 +0100, in > <3B4B714E.417F83EB@zetnet.co.uk>, in sci.crypt David Hopwood > <david.hopwood@zetnet.co.uk> wrote: > > >-----BEGIN PGP SIGNED MESSAGE----- > > > >Terry Ritter wrote: > >> As far as I know, the sole known *weakness* of BB&S is the existence > >> and possible use of short cycles, especially in the ordinary > >> construction. This flaw was eliminated in the original BB&S article > >> with modest front-end cost, but high per-use cost. It now turns out > >> that we can do the same thing at negligible per-use cost. Merely by > >> using the special primes construction from the BB&S article, all > >> "short" cycles are known to be "long enough" for use except degenerate > >> cycles, which we can easily test with just a couple of steppings. > >> > >> The usual mathematical spin on this is that the security improvement > >> thus gained is so modest as to be lost in the asymptotic results. > >> However, we have actual experience with what users expect perfection > >> to mean: > >> > >> The original Intel Pentium design also had a flaw. Very rarely, it > >> would produce incorrect arithmetic results. It was such an unlikely > >> flaw that it hardly every occurred. > > > >No, this is a false analogy. The Pentium FDIV bug was *not* unlikely > >in the same sense as short cycles in BBS; in fact it was perfectly > >reproducible, and for some (useful) programs, it would happen with > >probability 1. Intel's PR department were disingenuous in ever claiming > >otherwise. (Actually, the claim that the bug is "unlikely" to occur > >doesn't even make sense, since the inputs to FDIV, unlike BBS moduli, > >are not chosen randomly.) > > Yes, the analogy is valid: > > The BB&S short cycle flaw is just as reproducible as the FDIV bug, as > long as the modulus is not changed, and that is a common case. Often, > the modulus is computed once and kept for repeated use, with only the > seed x0 selected at random on a per-use basis. > > But even if the modulus did change, the flaw *potential* would remain. > The casual construction just does not have cycle-structure guarantees > whether the modulus is changed or not. So the possibility of short > cycles would still be there, and such cycles might be selected and > used at any seed init time. In the same way, users imagined that an > FDIV error might occur in any computation. > > This is the same issue. > > > >> As Intel learned, the issue was not actual wrong answers, but instead > >> lack of confidence. > > > >The issue was very much actual wrong answers: there are many applications > >for which the consequences of an incorrect floating point computation > >can be very serious. That's why operating systems and some C runtime > >libraries still contain code to detect the faulty chips and provide a > >correct emulation of FDIV. > > Clearly, with BB&S, "there are many applications for which the > consequences" of selecting a short cycle "can be very serious." > > A short cycle is insecure the moment it begins to repeat. That is > unquestionable weakness from a "proven secure" generator. We do not > have to live with that, since we can avoid it at minimal cost. > > > >There was *also* the issue of the arrogant way in which Intel dismissed > >public criticism, but it would be a mistake to assume that the bug itself > >wasn't serious. > > The FDIV bug produced wrong results, but few such results were > actually seen. The hubbub was more about *the* *possibility* of wrong > answers, rather than wrong answers themselves. That is lack of > confidence. > > The worry about BB&S is also lack of confidence: we have extremely > rare faults which are accepted and tolerated instead of being > eliminated. > > With BB&S the math guys seem to say: "Yeah, it's a weakness. But who > cares, it's so rare you'll never see it." And that corresponds very > well to the Intel response to their FDIV bug. I suppose the question is how rare though? If i had an exceptional spell of luck i could guess the factors to 'n'.. rare? yes. Impossible? no. It'd be nice to know, given the factors of 'n', how many cycles there are below a certain length. Simon. > --- > Terry Ritter ritter@io.com http://www.io.com/~ritter/ > Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: BBS seeds Date: Thu, 12 Jul 2001 20:03:11 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B4DF46F.E3A11C77@zetnet.co.uk> References: <c0879d5f.0107120532.35ebfad4@posting.google.com> Newsgroups: sci.crypt Lines: 40 -----BEGIN PGP SIGNED MESSAGE----- Simon Johnson wrote: > ritter@io.com (Terry Ritter) wrote: > > But if we use the special primes construction, and then check that we > > are not using degenerate cycles (this just takes two RNG steps), we > > *eliminate* the problem completely. We *guarantee* that we do not use > > a degenerate cycle. We *guarantee* that all remaining "short" cycles > > are "long enough" to use, so we just use whatever we get. > > There are still weak keys... Try 0 & 1. I presume that you meant to > include these to. 0 and 1 are not weak seeds: 0 cannot occur because it is not in Z*_N (equivalently, the value x_{-1} that is squared to give the seed cannot be 0), and 1 gives a degenerate cycle which is detected by the check mentioned above. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBO030SzkCAxeYt5gVAQEeswf9HkfOcnSDnIPA0hH3M5qdCXgvQ4ZVee+k WNE66H2e4g+aR/tNibF92OoivUBhxGqEeCJoUZoTtBORUg4JOLgXZndgOxvwtTc2 RqlcfvJCu+z/rqFzgyiTnoOeXtFMVunHs8y6ZsTf/8lYBCJ2J8S8u9kHEWhIkeZC eO9oZnCbKyl3tuPmqnRx6Kt3F7bk4BnEwnJ4dpDsU+injfZKxsRMpvpV+YabO6zY zQOAbOI8G/fVibJDlJYPKt8slbHdgQpjF776NJw8bMCpBsdjhSXmIppPPCWds7Rg 6WMEfMuHwbTBLbITWQMp4vy0WIxggH8uhnURtB7l4/MXQ89gzxejxw== =CE24 -----END PGP SIGNATURE-----
Subject: Re: BBS seeds Date: Fri, 13 Jul 2001 18:10:55 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4f38ff.2999124@news.io.com> References: <3B4DF46F.E3A11C77@zetnet.co.uk> Newsgroups: sci.crypt Lines: 37 On Thu, 12 Jul 2001 20:03:11 +0100, in <3B4DF46F.E3A11C77@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >-----BEGIN PGP SIGNED MESSAGE----- > >Simon Johnson wrote: >> ritter@io.com (Terry Ritter) wrote: >> > But if we use the special primes construction, and then check that we >> > are not using degenerate cycles (this just takes two RNG steps), we >> > *eliminate* the problem completely. We *guarantee* that we do not use >> > a degenerate cycle. We *guarantee* that all remaining "short" cycles >> > are "long enough" to use, so we just use whatever we get. >> >> There are still weak keys... Try 0 & 1. I presume that you meant to >> include these to. > >0 and 1 are not weak seeds: 0 cannot occur because it is not in Z*_N >(equivalently, the value x_{-1} that is squared to give the seed cannot >be 0), and 1 gives a degenerate cycle which is detected by the check >mentioned above. Of course zero can occur -- if, as usual, the seed selection is made at random. Presumably what you mean by this is that zero should not be allowed to occur, which of course, is my point as well. One part of this is exactly how one should prevent such a thing. Zero and one are weak seeds: weak seeds which are detected and eliminated "by the [degenerate cycle] check mentioned above." --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Definition of "negligable" Date: Thu, 12 Jul 2001 20:04:31 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B4DF4BF.F1F06FB5@zetnet.co.uk> References: <slrn9kopi5.qfl.mdw@daryl.nsict.org> Newsgroups: sci.crypt Lines: 83 -----BEGIN PGP SIGNED MESSAGE----- Mark Wooding wrote: > Terry Ritter <ritter@io.com> wrote: > > David Wagner wrote: > > > You're claiming that checking for short cycles makes > > > a non-negligible difference to security. > > > > No. It is you who somehow feels empowered to decide what "negligible= " > > means. And that is *not* your call. That is for the designer and > > user to decide in concert with *their* goals and *their* costs. > = > Wrong. The word `negligible' has a technical meaning in provable- > security cryptography. A function f(k) is `negligible in k' if f(k) < > 1/c(k) for all polynomial functions c(k) and sufficiently large k. That is the technical definition of negligable for asymptotic proofs. It was intended to capture the literal English meaning of negligable: "that which can be neglected", i.e. an event that is either insignificant= enough, or (as in this case) improbable enough that it is neither necessa= ry nor useful to take specific steps to prevent it. As is now generally agre= ed, I think (but was not when the BBS paper was written), the asymptotic definition is not entirely satisfactory, and it is preferable to use concrete security definitions instead. In "concrete provable security," designers and/or users do decide what constitutes a negligable advantage (usually implicitly by choosing parame= ter sizes for which they believe that the scheme is secure, using the proof as guidance). By advocating checking for short cycles, Terry Ritter (acting in the role of a designer [*1]) is clearly saying that he thinks they should not be neglected, i.e. that they make a non-negligible difference to security, as David Wagner said. The conventional wisdom is that in that case the security parameters (here the modulus size) should be made large enough that the probability of weakness becomes negligable. If Ritter doesn't accept that that can be done, then he is rejecting the whole basis of the "provable security" subfield of cryptography [*2], not just making a technical point about BBS. [*1] as is everyone posting in this thread, effectively. [*2] or the hardness of IFP, but I assume that in this thread we are accepting for the sake of argument that IFP is hard (that is, that the probability of factoring by a computationally-bounded adversary can be made extremely small), for sizes of modulus that can be estimated and are not too long to be used in practice. - -- = David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has b= een seized under the Regulation of Investigatory Powers Act; see www.fipr.org= /rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBO03pwTkCAxeYt5gVAQGfFggAs9UfM/IRZDnZ72nh47xIDTu0sc9TsmCb UWCQySs/SOTMlJAaAyG0Tmsxjy/0hh+7RCdf20TR3nHWeY6GDOC2BkK7wJJN5qdT fRKHwvEgZAL0kxkGJf6WkSIAiNPQcSmA1TtpV3rYxh4hbg+8TAlUKe3/UrlYcYwe uMcvx3Qq/+m0pOHv//YgwZu9pp+eI3QSPjcj4qPrLH5w25ao9EZ+LF3RpfcOn8l4 QQgs3H5Mips++Zdo6+9nIraxoffJ53FraR7qVzOjHlTCQwzFFuvAoSvxVfyPRGs7 J6FeGC2h3h9ATkCeqZlOS+wJo5Ysz48+kn/VFJqLzxHS8J5K7sPMng=3D=3D =3DSYGv -----END PGP SIGNATURE-----
Subject: Re: Definition of "negligable" Date: Fri, 13 Jul 2001 08:42:44 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4E9864.3EFB8B40@t-online.de> References: <3B4DF4BF.F1F06FB5@zetnet.co.uk> Newsgroups: sci.crypt Lines: 33 David Hopwood wrote: > [snip] > In "concrete provable security," designers and/or users do decide what > constitutes a negligable advantage (usually implicitly by choosing parameter > sizes for which they believe that the scheme is secure, using the proof > as guidance). By advocating checking for short cycles, Terry Ritter (acting > in the rôle of a designer [*1]) is clearly saying that he thinks they should > not be neglected, i.e. that they make a non-negligible difference to > security, as David Wagner said. The conventional wisdom is that in that case > the security parameters (here the modulus size) should be made large enough > that the probability of weakness becomes negligable. If Ritter doesn't > accept that that can be done, then he is rejecting the whole basis of the > "provable security" subfield of cryptography [*2], not just making a > technical point about BBS. Sorry for a dumb question: In another post you said that the 1 that leads to degenerate cycle is detectable by check. Of course that's also known, because the case is evident/trivial. But doesn't that mean that one should check, since there could be other cases than the 1 that one could easily step into, if one isn't careful engough? I mean, suppose there are degenerate cases that are 'concentrated' in a certain zone which the user might with bad luck go in and hence would have a much higher chance of encountering the degenerate cycles than in the case where the degenerate cases are sort of randomly distributed. Are there any studies of the 'distribution' of the degenerate cases? Thanks. M. K. Shen
Subject: Re: Definition of "negligable" Date: Fri, 13 Jul 2001 18:14:04 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4f3a27.3295249@news.io.com> References: <3B4DF4BF.F1F06FB5@zetnet.co.uk> Newsgroups: sci.crypt Lines: 89 On Thu, 12 Jul 2001 20:04:31 +0100, in <3B4DF4BF.F1F06FB5@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >-----BEGIN PGP SIGNED MESSAGE----- > >Mark Wooding wrote: >> Terry Ritter <ritter@io.com> wrote: >> > David Wagner wrote: >> > > You're claiming that checking for short cycles makes >> > > a non-negligible difference to security. >> > >> > No. It is you who somehow feels empowered to decide what "negligible= >" >> > means. And that is *not* your call. That is for the designer and >> > user to decide in concert with *their* goals and *their* costs. >> = > >> Wrong. The word `negligible' has a technical meaning in provable- >> security cryptography. A function f(k) is `negligible in k' if f(k) < >> 1/c(k) for all polynomial functions c(k) and sufficiently large k. > >That is the technical definition of negligable for asymptotic proofs. >It was intended to capture the literal English meaning of negligable: >"that which can be neglected", i.e. an event that is either insignificant= > >enough, or (as in this case) improbable enough that it is neither necessa= >ry >nor useful to take specific steps to prevent it. As is now generally agre= >ed, >I think (but was not when the BBS paper was written), the asymptotic >definition is not entirely satisfactory, and it is preferable to use >concrete security definitions instead. > >In "concrete provable security," designers and/or users do decide what >constitutes a negligable advantage (usually implicitly by choosing parame= >ter >sizes for which they believe that the scheme is secure, using the proof >as guidance). By advocating checking for short cycles, Terry Ritter (acti= >ng >in the r=F4le of a designer [*1]) is clearly saying that he thinks they s= >hould >not be neglected, i.e. that they make a non-negligible difference to >security, as David Wagner said. The conventional wisdom is that in that c= >ase >the security parameters (here the modulus size) should be made large enou= >gh >that the probability of weakness becomes negligable. If Ritter doesn't >accept that that can be done, then he is rejecting the whole basis of the= > >"provable security" subfield of cryptography [*2], not just making a >technical point about BBS. Certainly I reject the idea that it is just fine to encourage the production of systems with known flaws which can be avoided at reasonable cost. Short cycle flaws are *NOT* in the same category as guessing a key, which of course can be made a negligible possibility by increasing the size of the system. The short cycle flaw is always *in* *addition* to other flaws *AND* is preventable. We don't need to make the system bigger to hide the problem, we need to fix the problem. A designer who selects BB&S does so because of security proofs. He expects to get a system which has no flaws, which is of course a delusion in itself. Nevertheless, the deliberate inclusion of preventable known flaws with the claim "they will never happen" is a direct slap in the face. A flaw is certainly not negligible if it affects confidence in the system. If the "provable security" subfield of cryptography thinks otherwise, then, fine, I reject it, as, indeed, anyone should. It is time to distinguish between unavoidable flaws, and flaws which can be eliminated. It is also time for math to document all flaws clearly, instead of trying to hide them away so nobody will notice. >[*1] as is everyone posting in this thread, effectively. >[*2] or the hardness of IFP, but I assume that in this thread we are > accepting for the sake of argument that IFP is hard (that is, that > the probability of factoring by a computationally-bounded adversary > can be made extremely small), for sizes of modulus that can be > estimated and are not too long to be used in practice. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Definition of "negligable" Date: Fri, 13 Jul 2001 19:55:09 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9injmt$2jjm$2@agate.berkeley.edu> References: <3b4f3a27.3295249@news.io.com> Newsgroups: sci.crypt Lines: 6 Terry Ritter wrote: >The short cycle flaw is always *in* *addition* to >other flaws *AND* is preventable. The "use of the prime 1208923250890892301" flaw is always in addition to other flaws and is preventable, too.
Subject: Re: Definition of "negligable" Date: Fri, 13 Jul 2001 23:03:30 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4F6222.71AEA8E0@t-online.de> References: <9injmt$2jjm$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 15 David Wagner wrote: > > Terry Ritter wrote: > >The short cycle flaw is always *in* *addition* to > >other flaws *AND* is preventable. > > The "use of the prime 1208923250890892301" flaw is always in > addition to other flaws and is preventable, too. Sorry for my sheer ignorance. What type of flaw is that? Thanks. M. K. Shen
Subject: Re: Definition of "negligable" Date: Fri, 13 Jul 2001 22:24:28 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <wyK37.173351$Mf5.46603177@news3.rdc1.on.home.com> References: <3B4F6222.71AEA8E0@t-online.de> Newsgroups: sci.crypt Lines: 22 "Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message news:3B4F6222.71AEA8E0@t-online.de... > > > David Wagner wrote: > > > > Terry Ritter wrote: > > >The short cycle flaw is always *in* *addition* to > > >other flaws *AND* is preventable. > > > > The "use of the prime 1208923250890892301" flaw is always in > > addition to other flaws and is preventable, too. > > Sorry for my sheer ignorance. What type of flaw is that? > Thanks. Known factor I presume. Tom
Subject: Re: Definition of "negligable" Date: Sat, 14 Jul 2001 05:14:46 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4fd491.7471241@news.io.com> References: <9injmt$2jjm$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 30 On Fri, 13 Jul 2001 19:55:09 +0000 (UTC), in <9injmt$2jjm$2@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>The short cycle flaw is always *in* *addition* to >>other flaws *AND* is preventable. > >The "use of the prime 1208923250890892301" flaw is always in >addition to other flaws and is preventable, too. Please. SOME primes must always be used. When the opponent selects a particular prime to check, we cannot know that, and so cannot avoid it. It is not in the realm of preventable flaws. We can only "prevent" our use of that prime by supernatural knowledge of what the dangerous prime is. In contrast, when we select a short cycle, we give the opponent a weak system to confront. But we can avoid short cycles, so the use of a short cycle is a true preventable flaw. It is also in addition to any particular prime the opponent may check. These ideas are quite distinct. The analogy is invalid. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Definition of "negligable" Date: Sat, 14 Jul 2001 08:40:51 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ip0ij$tas$1@agate.berkeley.edu> References: <3b4fd491.7471241@news.io.com> Newsgroups: sci.crypt Lines: 18 Terry Ritter wrote: >daw@mozart.cs.berkeley.edu (David Wagner) wrote: >>The "use of the prime 1208923250890892301" flaw is always in >>addition to other flaws and is preventable, too. > >[...] It is not in the realm of preventable flaws. [...] Sure it is. I betcha a nickel I can write a BBS implementation that prevents the occurrence of this particular flaw. This particular flaw---the one where you use specifically the prime 1208923250890892301---is clearly preventable. You just check for use of this prime and throw away the key if it has this form. Now if you want to talk about using other primes, and whether they are flaws or whether they are preventable, well, we could discuss it, but that's a different discussion, and maybe we'd better settle this one first.
Subject: Re: Definition of "negligable" Date: Sun, 15 Jul 2001 07:20:40 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b514444.7332629@news.io.com> References: <9ip0ij$tas$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 54 On Sat, 14 Jul 2001 08:40:51 +0000 (UTC), in <9ip0ij$tas$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>daw@mozart.cs.berkeley.edu (David Wagner) wrote: >>>The "use of the prime 1208923250890892301" flaw is always in >>>addition to other flaws and is preventable, too. >> >>[...] It is not in the realm of preventable flaws. [...] > >Sure it is. I betcha a nickel I can write a BBS implementation >that prevents the occurrence of this particular flaw. > >This particular flaw---the one where you use specifically the prime >1208923250890892301---is clearly preventable. You just check for use >of this prime and throw away the key if it has this form. Well, the designer / user can indeed check and throw away, but against what value do they check? Only the opponent knows what value the opponents are waiting for, so the designer / user cannot check against that value. Code cannot be written to check against a particular value which is not and will not be known. The designer / user of the BB&S system can indeed avoid any particular known prime. But primes are the keys, so *some* primes must be used. Guessing the correct key is always a possibility in any keyed system. That is a weakness, but it is not a *preventable* weakness unless the opponents have previously published the keys they will check. >Now if you want to talk about using other primes, and whether they >are flaws or whether they are preventable, well, we could discuss it, >but that's a different discussion, and maybe we'd better settle this >one first. Unless you have some meaning for 1208923250890892301 other than being some arbitrary prime, I see nothing to settle. Given public-key-size primes, the special primes construction forces all "short" cycles to be "long enough," except for degenerate cycles, which can be detected and avoided and thus not used. In any "BB&S" construction we are guaranteed to have degenerate cycles. These are correctable flaws because they can be detected and avoided. And, when that is done, the system no longer has a known preventable weakness. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Definition of "negligable" Date: Mon, 16 Jul 2001 08:59:56 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B5290EC.507CF7C2@t-online.de> References: <3b514444.7332629@news.io.com> Newsgroups: sci.crypt Lines: 37 Terry Ritter wrote: > > daw@mozart.cs.berkeley.edu (David Wagner) wrote: > >Now if you want to talk about using other primes, and whether they > >are flaws or whether they are preventable, well, we could discuss it, > >but that's a different discussion, and maybe we'd better settle this > >one first. > > Unless you have some meaning for 1208923250890892301 other than being > some arbitrary prime, I see nothing to settle. I am also interested to know the 'type' of flaw in using BBS examplified by that number. > Given public-key-size primes, the special primes construction forces > all "short" cycles to be "long enough," except for degenerate cycles, > which can be detected and avoided and thus not used. > > In any "BB&S" construction we are guaranteed to have degenerate > cycles. These are correctable flaws because they can be detected and > avoided. And, when that is done, the system no longer has a known > preventable weakness. I think that one point to be noticed is the cost/return issue. If that is neligibly low, then all those who are economically (practically) oriented would consider it favourable (at least reasonable) to include the additional processing step. The practice of encryption is at the end governed by economic factors, not by pure theory of the scientists (at least not before the scientists could demostrate that 'absolutely' perfect security is realizable in this world). M. K. Shen
Subject: Re: Definition of "negligable" Date: Tue, 17 Jul 2001 03:41:04 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b53b3cd.931226@news.io.com> References: <3B5290EC.507CF7C2@t-online.de> Newsgroups: sci.crypt Lines: 38 On Mon, 16 Jul 2001 08:59:56 +0200, in <3B5290EC.507CF7C2@t-online.de>, in sci.crypt Mok-Kong Shen <mok-kong.shen@t-online.de> wrote: >[...] >I think that one point to be noticed is the cost/return >issue. The appropriate measure may be incremental cost. Any form of BB&S is going to be slow, and we assume that decision is already made. Now how much does it cost to remove the known defects? The incremental cost of the special primes construction consists first of finding special primes. That will take longer than ordinary primes, but the results can be re-used, and is probably not a per-use cost. The incremental cost next consists of checking for degenerate cycles. That consumes exactly two RNG steps. Since using the RNG may involve thousands of steps or more, the degenerate cycle check is negligible by comparison. >If that is neligibly low, then all those who are >economically (practically) oriented would consider it >favourable (at least reasonable) to include the >additional processing step. The practice of encryption >is at the end governed by economic factors, not by pure >theory of the scientists (at least not before the >scientists could demostrate that 'absolutely' perfect >security is realizable in this world). --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Terry Ritter, his current address, and his top page.
Last updated: 2001-07-20