Proof and Strength in the BB&S RNG

Terry Ritter

A Ciphers By Ritter Page

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

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

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

The BB&S RNG

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

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

Security and Proof

The conversation starts with an innocent question about using BB&S as the running-key generator in a one time pad (OTP). The mere mention of BB&S then triggers a massive confrontation apparently just waiting to happen. As in any huge conversation, there are various sub-issues, side comments and snide comments, but much of the discussion is directed at me.

In retrospect, some of the problem seems to develop from a re-definition within mathematical cryptography of both "security" and "proof." Now, the term "security" is well-understood, first because it is part of the universal human condition, and second because there is a vast array of fields associated with "security" outside of cryptography. In particular, it is widely recognized that security is only as strong as the weakest link. Thus, normally, we see "security" as being the mathematical minimum of of the various securities involved, which thus provides a guarantee of some minimum level of security.

Mathematical "proof" is also well-understood, typically resulting from a general math education that begins in high school and often continues through four or more years of college. In most of this education, "proof" is an absolute statement about some condition.

But, in mathematical cryptography, "security" has taken on a statistical meaning, and "proofs" are typically probabilistic. Mathematical cryptography not only does not provide an absolute guarantee of security, it does not even provide a "lower bound" so we can identify the "weakest link." Consequently, even well-educated security experts are prime candidates for being deceived by the "terms of art" used in mathematical cryptography.

In mathematical cryptography, proof of security need not mean that no weakness exists, but may mean merely that if such weakness exists, it is sufficiently rare in large constructions. (And the definition of what size is "large enough" is more controversial than one might think.) Most practitioners of mathematical cryptography seem content to have "proven secure" describe a real system with a known weakness, provided the weakness exists only with low probability (although the actual probability involved is never really mentioned). But normal security work might call that "a hole."

BB&S is a very slow RNG, and the only reason for using it is to achieve the "provably secure" label which is tossed about. Presumably the user is willing to pay for the apparent guarantee of "proven secure." But what they may get is an RNG known to have weak short cycles, any of which might be selected and used, if the user is simply "unlucky." This would be especially ironic if the main reason users seek mathematically-proven security is to avoid depending on luck.

2000-08- 3 Grant Anderson: "I know there has been much discussion about (supposed) OTP ciphers and how most of them generally don't fulfil the OTP requirements. What I don't understand is why the use of the blum-blum-shub generator as the pad isn't acceptable?"
2000-08- 3 Mack: "The basic problem with the BBS is that it is very slow."
2000-08- 3 lordcow77: "Practically everyone accepts that choosing the factors of the modulus to be congruent to 3 mod 4 and picking a random starting point are enough to ensure that the resulting BBS sequence will be secure . . . ."
2000-08- 3 Mark Wooding: "Can you provide a reference?"
2000-08- 3 lordcow77: "A proof would be a surprise to me as well :-)"
2000-08- 3 Mok-Kong Shen: "For one that does not have expert knowledge in BBS, like me, it seems unfortunately to be difficult to know from the materials of past discussions in the group alone whether one party is absolutly right and the other absulutely wrong."
2000-08- 4 Bryan Olson: "So look it up. Surely anyone can recognize the utter slyness of the claims that the reason the major current references don't include the long-cycle test in their description of the generator is that the authors have simply not read the whole paper."
2000-08- 4 Mok-Kong Shen: "If only the simpler form is described in a book and nothing else, how can a reader recognize laziness/carelessness of its author or its opposite, excepting through reading the original article of BBS?"
2000-08- 8 Bryan Olson: "I suppose you are right that one will not be able to tell . . . ."
2000-08- 8 Mok-Kong Shen: "The real problem is that those, who are able to fully understand the original paper of BBS, probably wouldn't stay long with this thread and watch the heated debate . . . ."
2000-08- 3 Terry Ritter: "Using a short cycle is unarguably insecure. And, unless we specifically prevent it, using a short cycle is an unarguable possibility."
2000-08- 3 Paul Pires: "Well said. I wish that I could be that generous in defending against nonsensical attacks."
2000-08- 3 Joseph Ashwood: ". . . while Mr Ritter and I have been on differing sides of discussions before, I agree with him completely in this case."
2000-08- 4 Mack: "I agree with Terry Ritter also."
2000-08- 5 David Hopwood: "The probability of weakness is not changed significantly by applying the constraints that Ritter thinks are necessary . . . ."
2000-08- 6 Mok-Kong Shen: "Thus if, in analogy, we equate OTP to infinity, then BBS is a very large (but finite) number."
2000-08- 7 Terry Ritter: "Here is the summary again:
* It is INDISPUTABLE that short cycles do exist in BB&S.
* If the start value is selected purely at random, it is INDISPUTABLE that a short cycle might be selected.
* It is INDISPUTABLE that when a random number generator (RNG) cycle has been traversed, we can predict future values from the ones produced in the past."
2000-08- 8 Bryan Olson: "So once more you refuse to address what people are saying. You bleat yet again that if a short cycle happens it's weak, as if the post to which you respond had said otherwise."
2000-08- 8 Terry Ritter: "The post to which I responded implied that weakness could not exist, and did so in a slightly offensive manner. It was false, because there is weakness. It just happens rarely."
2000-08- 8 Bryan Olson: "I take a different view: I think showing the failure happens with negligible probability is a perfectly valid way to address the weakness."
2000-08- 8 Terry Ritter: "If Bryan wants to see it as a debating trick, he can do that just as long as he likes."
2000-08-10 Bryan Olson: "I thought we might actually make progress last time."
2000-08- 9 Benjamin Goldberg: "Weak keys have low probability, but when they occur, the system is wide open."
2000-08-10 lcs Mixmaster Remailer: ". . . if any of these things happen, the rsa modulus is easy to factor, with a proper program. But the chances of any of them happening are infinitisimal."
2000-08-12 Benjamin Goldberg: "No, BBS is not quite the same as RSA."
2000-08-10 David Hopwood: "A practical example is IDEA: this has a set of weak keys that occur with probability about 2^-96. As it happens I haven't written any applications for end-users that use IDEA, but if I did, I wouldn't consider it necessary to check for weak keys."
2000-08-12 lcs Mixmaster Remailer: "In general, if you can find short cycles, you can factor. Hence if you believe factoring is hard, you believe that short cycles can't be found."
2000-08-14 Benjamin Goldberg: "But the attacker never sees 1035, only it's least significant bit . . . ."
2000-08-15 lcs Mixmaster Remailer: "The point is, if you can find a cycle of "X" values, you can factor. Terry Ritter's advice to choose X values which aren't on a cycle is useless, because it implies worrying that your modulus can be factored by mere guessing."
2000-08-15 Terry Ritter: ". . . to the extent that someone practices BB&S on the basis of the proof, with the goal being absolute confidence in having an unbreakable cipher, a practical issue does exist." "A BB&S system can be weak in many ways without damaging math as we know it."
2000-08-15 Mok-Kong Shen: "Excuse me for posing some presumably very dumb questions."
2000-08-15 Mark Wooding: "The proof of unpredictability is a two-step thing:"
2000-08-15 Mok-Kong Shen: "So it means that you only need to prove the unpredictability and the statistical perfectness 'automatically' follows."
2000-08-15 Mark Wooding: "We know that finding cycles *of the LSB* is no easier than factoring!" "Terry doesn't agree, but doesn't have any analysis of LSB period to back him up."
2000-08-15 Terry Ritter: "I would say that I do have such an analysis, and it does back me up: If we use the BB&S construction, we are *guaranteed* not to use a short cycle. If we don't, then we are just very, very *unlikely* to use a short cycle."
2000-08-15 Mok-Kong Shen: "Please correct me if I am wrong. I guess that you have investigated the cycle lengths of the direct output of the congruence relation but not the cycle lengths of the LSB, which could be comparatively much shorter."
2000-08-16 Terry Ritter: "No correction is needed, since you are right. I have no special information on the LSB question."
2000-08-16 Mok-Kong Shen: "Thank you for the answer. This means that the situation is much WORSE than what an quasi-observer of this thread like me up till now imagines."
2000-08-16 Mark Wooding: "Note that the period length of the parity sequence must be a factor of the period length of the sequence."
2000-08-16 Mok-Kong Shen: "So why not persuing it a bit further?"
2000-08-15 Mok-Kong Shen: "I conjecture that one has to be able to say something definite about the distribution of cycle lengths of LSB, if one can prove that finding cycles of the LSB is no easier than factoring."
2000-08-16 Mark Wooding: "The proof is much more general than that. It shows that *any* method of predicting the generator's output allows you to factor."
2000-08-16 Mok-Kong Shen: ". . . we can't simply through hand waving ignore the potential possibility that such patterns could also occur for LSB of moduli that are difficult to factor."
2000-08-15 Terry Ritter: "The construction as described in BB&S first guarantees that cycles of a given length must exist, and then shows how to check that x0 is on such a cycle. The check is thus absolute proof that a short cycle has not been selected."
2000-08-15 Mark Wooding: "No, it only shows the cycle length for the sequence , not the sequence of parity bits."
2000-08-15 Mok-Kong Shen: "Sorry, I am really confused. 'Parity bits' or 'LSB'?"
2000-08-16 Terry Ritter: "The "parity" property to which BB&S refers is "odd vs. even," which is also the least-significant-bit (LSB) in binary representation."
2000-08-16 David Hopwood: "Either (they are equally secure)."
2000-08-16 Mark Wooding: "That's interesting to know."
2000-08-17 David Hopwood: "Oops, no they aren't (or at least this is not proven)."
2000-08-16 Mok-Kong Shen: "Is there any concrete relation between the quadratic residuacity assumption and the assumption of hardness of factoring N?"
2000-08-17 Mok-Kong Shen: ". . . I don't see where the argument 'finding short cycles is equivalent to factoring' . . . ."
2000-08-17 Mark Wooding: "Finding cycles permits prediction, and *all* prediction methods reduce to solving QRP, so there's no problem here."
2000-08-17 Mok-Kong Shen: "Unpredictablility to the right seems to be actually more useful, isn't it?"
2000-08-17 Mark Wooding: "I think that both are useful."
2000-08-17 Mok-Kong Shen: "If the main theorem does not involve cycle length and has firmly established the security issue, why does one (in particular BBS) has to bother to consider subsequently the cycle length question at all?"
2000-08-18 Mark Wooding: "Some people keep on bringing the subject up without any particularly good reason. The security proof, such as it is, applies regardless of any considerations about cycle lengths."
2000-08-18 David Hopwood: "OTOH, I don't think that the cycle length issue is a good motivation for choosing factors of special form (either the method using Lim-Lee primes, or the "special primes" defined in the BBS paper)."
2000-08-18 Mok-Kong Shen: "If the main theorem does not involve cycle length and has firmly established the security issue, why does one (in particular BBS) have to bother to consider subsequently the cycle length question at all?"
2000-08-17 Terry Ritter: "To allow short cycles is to let them be our minimum guaranteed strength."
2000-08-18 David Hopwood: "Moreover, "always unpredictable" is not necessary and was never claimed."
2000-08-20 D. J. Bernstein: "If you want to apply the theorems, you need _much_ larger values of N."
2000-08-21 Mok-Kong Shen: "Thank you very much for the valuable information."
2000-08-21 Mark Wooding: "Oh, do you have a pointer to Alexi-Chor-Goldreich-Schnorr?"
2000-08-24 Tim Tyler: "FWIW: two /possible/ papers at:"
2000-08-16 John Savard: "Since the BBS modulus can't be a power of two, I don't think you have to worry about that."
2000-08-16 Mok-Kong Shen: "Do I understand correctly that you claim that the cycle length of equals the cycle length of the parity bits . . . ?"
2000-08-16 John Savard: ". . . if the cycle length for the generator as a whole is pq . . . it IS clear that no other cycle length for the parity bit less than pq is possible."
2000-08-16 Mark Wooding: "Yes, but it isn't: it's a factor of \lambda(\lambda(n))." "Indeed, the difficulty of prediction implies the lack of bias as a trivial corollary."
2000-08-16 Mok-Kong Shen: "There are two points. First is the terminology."
2000-08-19 Tim Tyler: "I for one don't see how the nature of the BBS modulus might help prevent cycles in the low bits."
2000-08-20 Mok-Kong Shen: "BBS states only that the cycle length of LSB must divide the first mentioned cycle length but leaves the exact relationship between the two to be an open question."
2000-08-21 Mark Wooding: "You missed the bit where I explained exactly how the nature of the BBS modulus can prevent short cycles in the parity bit."
2000-08-22 Tim Tyler: "Yes, I definitely did."
2000-08-22 Mark Wooding: "I can't expect that everyone here reads every message I post. I can't even be bothered to read most of them, so I can't see why anyone else should, really. ;-)"
2000-08-16 Terry Ritter: "I got carried away on the old issue. Sorry."
2000-08-15 Mok-Kong Shen: "Does the phrase 'cycles of a given length' refer to cycles of the direct output of the congruence relation or does it refer to cycles of LSB."
2000-08-16 Terry Ritter: "My mistake, I was answering the old question."
2000-08- 8 Mok-Kong Shen: "The cycle length of LSB of the output definitely cannot be longer but can very probably be much shorter than the cycle length of the output itself."
2000-08- 9 Terry Ritter: "The LSB of the x^2 mod N result *is* the output of BB&S." "To the extent that there is a proof of BB&S, that proof must cover this situation, because this *is* BB&S."
2000-08- 9 Mok-Kong Shen: "I should very much appreciate it, if some expert would confirm that the issue is indeed well taken care of in the article of BBS . . . ."
2000-08- 9 lcs Mixmaster Remailer: "This is correct. It is frustrating that you have come so close here to understanding the position of those who have been arguing against you for so many years."
2000-08-10 Trevor L. Jackson, III: ". . . the system without a short cycle check does not promise the same theoretical security as a system with the check."
2000-08-10 Mark Wooding: "If finding X by trying very hard is impractically difficult, then finding X by accidentally tripping over it must be at least as difficult."
2000-08-10 Doug Kuhlman: "I want that X..."
2000-08-10 Mark Wooding: "It already runs on millions of Unix boxes..."
2000-08-10 Terry Ritter: "This is not about an algorithm for an attack. It is about leaving weakness in the signal we send. Just as it would not be acceptable to leave plaintext between our impossible-to-break ciphertext, it is also not acceptable to every once in a while have a breakable result that we can prevent. Calling that "proven secure" is just adding insult to the injury."
2000-08-10 Trevor L. Jackson, III: "Two conterclaims:"
2000-08-11 Mark Wooding: "I'm confused by your terminology."
2000-08-11 Trevor L. Jackson, III: ". . . I'll let this one die."
2000-08-11 David Hopwood: ". . . the impracticality of finding one on purpose *implies* that there is negligable probability of selecting one by accident . . . ."
2000-08-10 Terry Ritter: "That logic is wrong. If there is a possibility of choosing a short cycle, that *will* happen, sooner or later. Then the attacker *can* factor N, which contradicts the assumption."
2000-08-10 Doug Kuhlman: "You consistently confuse possibility with probability and claim that one is the other."
2000-08-10 Terry Ritter: "Possibility and probability are statistical terms. If something is *possible* under random selection, it eventually *will* *happen*."
2000-08-15 Doug Kuhlman: "The possibility of landing on a short cycle is the least of my concerns (about BBS)."
2000-08-15 Trevor L. Jackson, III: "Can you provide some number/formulae that describe the incidence of short cycles for a typical BBS generator?"
2000-08-16 Terry Ritter: "One of the advantages of analysis is to address things which are too infrequent to be detected reliably from experiment." "Any system which allows use of short cycles cannot be guaranteed to have any more strength than a short cycle, no matter what other theoretical advances may occur."
2000-08-10 Terry Ritter: "I DO NOT ACCEPT that a cryptosystem which has a known potential weakness can legitimately be called "proven secure.""
2000-08-10 Mok-Kong Shen: "With n=209, a cycle of length 4 (which I fould on my second trial) gives the LSB of 0000! Now this is certainly a toy example. But it is on the other hand definitely a warning . . . ."
2000-08-10 Guy Macon: "Hmmm. Those very rare chances again."
2000-08-10 Mok-Kong Shen: "I got the suspicion from David Molnar's information that for non-BBS moduli, i.e. not of the form 3 mod 4, he [often] got 01010101.... . Now it seems to me to be very reasonable to think that for BBS moduli, the same could happen through maybe not so often."
2000-08-10 Terry Ritter: "For the purposes of discussion we are willing to assume that factoring is difficult. Yet even *with* that assumption, the reduced BB&S without short-cycle checks will be weak occasionally."
2000-08-10 Mok-Kong Shen: ". . . in GENERAL one should replace in crypto discussions the term 'provably secure' with the long phrase I proposed, in order to prevent 'general' mis-interpretations."
2000-08-10 Terry Ritter: ". . . even if we do that we can't "guarantee" a secure system, and if not, then why use BB&S at all?"
2000-08-11 Mok-Kong Shen: ". . . one could say that the decision to use the full version of BBS corresponds to checking weak keys in block ciphers and hence a user who opts for checking weak keys should use the full version of BBS, if he behaves consistently."
2000-08-11 Bryan Olson: ". . . even if one does filter out short state cycles, one still has not proven a long output cycle." Ed note: This is presumably in the context of the LSB's question. The BB&S paper does prove a long known cycle length via the special primes construction.
2000-08-11 Mok-Kong Shen: "If we KNEW the output cycle of LSB to be long! But it is unfortunate that we don't yet know."
2000-08-13 Bryan Olson: "We do not know if factoring is hard in most cases, and a short cycle in the bit output is one of arbitrarily many defects that might happen (in the sense that we have not proven it can't) if factoring the modulus turns out to be easy."
2000-08-11 David Hopwood: "Proofs in this area of cryptology are generally probabilistic, but they are *not* statistical . . . ."
2000-08-11 Terry Ritter: "A distribution of values (here weakness) is a statistical entity." "When x0 values are selected at random they are random variables, which are definitely statistical entities" "The effect of random sampling from a distribution is inherently statistical in nature."
2000-08-11 Mok-Kong Shen: ". . . 'security proved under certain assumptions' is better in my view."
2000-08-10 Mark Wooding: "The proof not statistical. It states that the output of a BBS generator cannot be distibguished from random data by any polynomial-time test by an adversary who cannot decide quadratic residuosity."
2000-08-10 Mok-Kong Shen: "Would a LSB sequence of 000000..... or 010101..... be indistinguishable from random data or distinguishable?"
2000-08-10 Terry Ritter: "What we have here is a construction which leaks the solution, unless explicitly prevented. So the failure does *not* impact math theories. Which also implies that those same theories cannot be depended upon for reasoning about strength in this and similar situations."
2000-08-11 Mark Wooding: "But the proof doesn't say that BBS is *secure*. It's says that it's *as secure as factoring*."
2000-08-10 Trevor L. Jackson, III: "Is it your position that there are repeating decimals that have cycles so long that they are are indistinguishable from irrationals?"
2000-08-11 Bryan Olson: "For those who spent a lot of effort trying to convince Mr. Ritter that the cycle-length test didn't change the nature of the theorem, I expect that's as close to a concession as we're going to get." "Will he ever understand the rest?"
2000-08-11 David Hopwood: "OK, in that case you must not accept that BBS is proven secure at all, under any assumptions, and with or without the cycle checks."
2000-08-11 Terry Ritter: "I don't really have a view about whether BB&S is secure." "On the other hand, I *know* that any random number generator is insecure when it has traversed a cycle, and I *know* that short cycles do exist in BB&S. Thus, I *know* that failing to prevent the use of a short cycle is a risk." "But I also *know* the prescription in BB&S will prevent the use of short cycles, which makes the short cycle problem an unnecessary and preventable risk. So I *know* that "real" BB&S is arguably "strong*er*" than the "reduced" or "simplified" BB&S which does not check for short cycles."
2000-08-10 Tony T. Warnock: "The question is not whether it's infeasible to find a short cycle, it's whether it's feasible to find a long one."
2000-08-10 David Hopwood: "If it is infeasible to find a short cycle, then there is negligable probability that one will be picked at random. Therefore we don't need to specifically find a guaranteed long cycle; we can just pick a seed at random . . . ."
2000-08-10 lcs Mixmaster Remailer: "First, thanks to the reference to Vazirani&Vazirani. We can dispense with the awkward claim that BBS reduces to quadratic reciduosity, and simply say that it reduces to factoring. If you think you need to check for short cycles, then you think your opponent can factor your modulus by guessing cycles."
2000-08-10 Terry Ritter: "It is not true that factoring is unconditionally hard. Factoring is easy when a factor is leaked. That is what the reduced BB&S does when it uses a short cycle. So if we want to depend upon factoring being hard, we had better arrange to not use a short cycle."
2000-08-10 John Myre: "If an event has sufficiently low probability, then it is perfectly sane and reasonable to design a system assuming it will never happen."
2000-08-10 Terry Ritter: "The issue is "proof," and to understand that we need to know what happens in *every* case, not just a handwave representing the majority of cases. Claiming that reduced BB&S is secure in every x0 selection is obviously just plain wrong. Knowing that, we can see that the most the proof can possibly mean is that in *other* cases, BB&S is strong." "In practice, the whole reason for using BB&S is to get a proof of strength; most people probably think means that there simply are no weaknesses. Yet here we have a case -- and there is no reason to think that short cycles are the only case -- where the system *is* *unarguably* *insecure*, and that case is known but not even checked for. In this situation, a claim of "proven secure" would be inappropriate." "I suggest "proven almost never weak."
2000-08-10 John Myre: "Since short cycles can exist, the BBS strength claim cannot be interpreted as a guarantee that the opponent can never break any particular sequence. There is a way to eliminate some "weak" cases (by selecting the BBS parameters in the careful way defined in the BBS paper). In doing so, however, we do not get any better guarantee of strength, in the sense of the proofs in the BBS paper. It might in fact be better, but the guarantee isn't any better."
2000-08-11 Terry Ritter: "There really is no math involved. The issue is what is being claimed. If you think that what is claimed is security in every case, then the claim is wrong with the reduced system. If you think that what is being claimed is a probability of strength -- "almost always" security -- then the claim is probably right."
2000-08-14 Benjamin Goldberg: ". . . in your short cycle example (PQ=1081, and the cycle length 11, I believe), how do we learn the factors of PQ from the LSBs of that cycle?"
2000-08-14 Terry Ritter: "As I have stated many times, I think shot cycles are not a weakness in practice. Instead, I am most concerned with the meaning of cryptographic proof. For, if we have an example where weakness can occur, then, clearly, cryptographic proof has failed to prevent that weakness. Given one such example, we have to ask if more exist. If then the answer is "No, because that would break math," we have to ask how the original problem could possibly exist in the first place. I think we are now coming to a consensus position in which cryptographic proof has far less practical import than most of us previously thought." "After thinking about these issues for the last day or so, I think that part of our problem ultimately stems from a language ambiguity in the word "assumption." In reality there is not just one but many necessary assumptions."
2000-08-11 lcs Mixmaster Remailer: "Since we've already established that no such checking is necessary for the second RSA system, it follows that no such checking is necessary for BBS."
2000-08-11 Trevor L. Jackson, III: "Up to this point I follow your argument, but at this point there's a gap."
2000-08-12 Trevor L. Jackson, III: "If I understand this correctly it amounts to a claim that a rational attacker will not test for short cycles because the effort expended, when discounted by the odds of success, does not get him any closer to cracking the system than an equivalent amount of effort invested in a QR search."
2000-08-12 Mok-Kong Shen: "Is the science of crypto entirely separated from psychology?"
2000-08-14 David Hopwood: ". . . an attacker that uses an inefficient method of factoring will not have any greater success probability (for a given amount of work) than one that uses a more efficient method."
2000-08-14 Tim Tyler: "What if the attacker has a dedicated, parallel, short-cycle testing machine - built for some other purpose - but only a general purpose serial computer for use in factoring?"
2000-08-14 Trevor L. Jackson, III: "So we should ignore the irrational ones who will cover all bases and thus crack messages by finding short cycles we've overlooked. I'd rather not over look them."
2000-08-14 Tony T. Warnock: "If a long stretch of zeros (length to be determined later) occured in a OTP, I would assume the generator was broken."
2000-08-14 Trevor L. Jackson, III: "The point seems to be that finding a short cycle in a BBS generator is not the product of a broken mechanism, but a predictable consequence of the underlying math. Since those consequences can be contained (described and rendered negligible mathematically) in a way that broken RNGs cannot, they can be ignored while the threat of a broken RNG cannot ever be ignored."
2000-08-14 Mok-Kong Shen: "I tend to partake your view."
2000-08-12 lcs Mixmaster Remailer: "All this worry about seeds "leaking" the factors is absurd, which the present analysis is intended to show."
2000-08-15 lcs Mixmaster Remailer: "BBS prediction reduces to factoring difficulty. But what does it mean that factoring is hard? It certaily doesn't mean that no numbers can be factored, ever." "And of course if anyone were ever so foolish as to follow Terry Ritter's advice in implementing BBS, they would appear equally amateurish."
2000-08-15 Terry Ritter: ". . . if we want our "proof" of strength to cover even the extremely rare event of using a short cycle, then we must have an additional assumption such that we will not use or traverse a short cycle. Of course, if we are willing to accept short cycles and resulting loss of data as an extremely rare event, then we will not be interested in the more comprehensive "proof."" "Real BB&S uses the techniques in the BB&S article to prevent short cycles. That is the definition of BB&S. Everything else is what other people claim BB&S should have been, in which case they should write their own paper, and get that different system named after them. Using the different and lesser system and calling it by the name of its better is deceptive."
2000-08- 7 Joseph Ashwood: "You act as if there is no question of the security of those systems."
2000-08- 4 Mark Wooding: "This is excellent work, thoroughly worth reading."
2000-08- 6 Benjamin Goldberg: "Makeing the factors congruent to 3 mod 4 isn't a specific prevention of short cycles?"
2000-08- 7 Terry Ritter: "Short cycles appear to be inherent in the construction."
2000-08- 8 Benjamin Goldberg: "Perhaps there is some relationship between P and Q we can test for which will avoid short cycles, which isn't part of the current parameter choosing process."
2000-08- 8 David Hopwood: "The factors of the modulus must be congruent to 3 mod 4 in order for the proofs in the BBS paper to apply. Note that this is entirely independent of the issue of short cycles."
2000-08- 7 Mark Wooding: "Short cycles will exist. In particular, the values 0, 1, p, and q lead to cycles of period 1."
2000-08- 8 David A Molnar: "A long time ago I built a BBS generator in Scheme. I found that there were varying cycle lengths when using a modulus n = p q with p and q congruent to 3 mod 4. When p or q were congruent to 1 mod 4, or not actually prime, then I ended up with an alternating 0-1-0-1-0-1 output."
2000-08- 9 Mok-Kong Shen: "Would the LSB of BBS, i.e. with p and q of the form 3 mod 4, have, on the other hand, very good statistical quality?"
2000-08- 9 Mok-Kong Shen: "I have just do an example with p=11, q=19, n=209. There is a cycle of length 4: (38, 190, 152, 114). Taking the LSB, we have all 0's."
2000-08-10 Tim Tyler: "A potentially useful observation."
2000-08-12 Benjamin Goldberg: "Your q isn't a Blum Integer, I don't think."
2000-08-12 Mok-Kong Shen: "p=11=2*4+3; q=19=4*4+3; are both Blum integers. But my example was no good. Here a (large) cycle of length 12:"
2000-08- 3 Tim Tyler: "Being hard to predict is a different thing to being /impossible/ to predict - which is what an ideal OTP ought to be." "For example an attacker can guess a BBS seed. If they get it right, reams of plausible plaintext will spew out - while if they don't it is /extremely/ unlikely to. This attack is impossible with a real OTP."
2000-08- 4 Grant Anderson: "Therefore, a CSPRNG which passes all the random tests and is indistinguishable from a "real" random source should be suitable . . . ." [Ed. Note: I think the point was that no deterministic RNG could possibly replace an OTP generator.]
2000-08- 3 Mack: "The basic answer to your question is that yes BBS is secure." "It isn't generally used because it is slow."
2000-08- 3 Mark Wooding: "Breaking the BBS is as hard as deciding quadratic residuosity. That's certainly no harder than factoring, because you can use factoring to decide quadratic residuosity . . . ."
2000-08- 3 Terry Ritter: "But being "no harder than factoring" is meaningless when an approach *allows* factoring." "The BB&S structure inherently includes both long and short cycles. If an opponent encounters a short cycle and identifies a repetition, they know the cycle length and can proceed to factor. Thus, use of a short cycle can expose the system to factoring."
2000-08- 3 Mark Wooding: "The security warranty works regardless, as long as the modulus is a Blum integer."
2000-08- 3 Terry Ritter: "When factoring is easy, "breaking" BB&S is easy. And factoring *is* easy when someone uses a short cycle." "The "security warranty" is that BB&S is secure... AS LONG AS FACTORING IS HARD. But factoring is NOT always hard. For example, Factoring is not hard if we give away one of the factors. And that is exactly what we do when we use a short cycle."
2000-08- 3 Tim Tyler: "There are other ways to improve the security of this system, besides weeding out short cycles."
2000-08- 7 Terry Ritter: "The theoretical strength guarantees certainly do not prevent us from choosing or using a weak short cycle. At best, they just say that such an event is "unlikely." And they say that whether we have checked for short cycles or not. The theory is thus unresponsive to both the presence of a real risk, and its elimination. That means the theory cannot be relied upon as an indication of security."
2000-08- 7 Mok-Kong Shen: "Not infrequently proofs are based on yet unproved number theoretical conjectures."
2000-08-10 Tim Tyler: "Even /after/ any surgery to remove short cycles, the BBS is never going to become "absolutely secure" - and we will still be able to make it stronger by "our own action"."
2000-08-10 Mok-Kong Shen: "See my follow-up . . . ."
2000-08-10 Terry Ritter: "It is *not* sufficient that the assumptions be true: Even when the assumptions *are* true, BB&S *still* is weak every now and then."
2000-08-13 Bryan Olson: "When you allow the defect might appear, you allow that factoring might be easy and have contradicted the premise."
2000-08-13 Terry Ritter: "Since "pretend" BB&S does *not* check for short cycle operation, it allows the defect to occur. By not checking, it does not help assure that the assumption ("factoring is hard") holds, which means that "pretend" BB&S has the potential weakness of using a short cycle *in* *addition* to any other weaknesses it may have."
2000-08-13 Bryan Olson: "The BBS security assumption is that the attacker cannot factor the modulus when given the modulus. (Though in practice we would not give him the modulus.) Giving him generator output, starting from a random point, cannot increase the chance he could violate the assumption, since he can start generators at all the random points he wants."
2000-08-14 Terry Ritter: "Many people have assumed that short cycles simply could not exist in BB&S because factoring was assumed hard, and if short cycles existed, factoring could be easy. But whether factoring is hard or not, short cycles do exist anyway." "So we *can* *assume* that factoring is hard, but if we then happen to select, use and traverse a short cycle, our assumption has become demonstrably false. In other words, a mere assumption is insufficient to protect us from the real defect of selecting and using a short cycle."
2000-08-15 Bryan Olson: "I don't know what people you are talking about; of course they exist. The proof shows that they must be sufficiently unlikely that they do not increase the chance for an attacker to factor a given modulus."
2000-08-19 Tim Tyler: "As I understand it, we know that attempts to factor the modulus are a better attack on BBS than brute force seed search - so the system already falls short of what is possible in terms of security."
2000-08-19 Mok-Kong Shen: "Most instances of the so-called 'provable security' involve assumptions."
2000-08-14 Mok-Kong Shen: ". . . Since some large numbers are evidently easy to factor, what does an assumption of hardness of factoring (without further qualifications) imply?"
2000-08-14 Mark Wooding: "Depends who you talk to. Some will waffle on about `strong primes' and suchlike; others will tell you just to generate random primes. I think that the random primes people are right."
2000-08-14 Mok-Kong Shen: "Could you conceive of any possibility of ever formally characterizing the 'most difficult sort of composite numbers'?"
2000-08-14 lordcow77: ". . . the products of two random primes of the same length."
2000-08-15 Mark Wooding: "Our understanding of what numbers are particularly hard to factor will change as we get better at factoring, and it will change in an unpredictable way."
2000-08- 4 Bryan Olson: "The scheme without the long cycle test is secure in the same sense as the scheme with the test."
2000-08- 7 Terry Ritter: "There is [. . .] a distinct difference between using a short cycle and using a long one, yet both are treated in the same way in the security proofs. What is the meaning of a proof of strength when the system it describes is not secure?"
2000-08- 7 Mok-Kong Shen: "I have the impression that, excepting OTP, most cases of 'proven strength' seem to be just that."
2000-08- 7 Joseph Ashwood: When a proper proof of security is performed, there are a set of assumptions that are made, either explicitly or implicitly. When these assumptions are met, or they are assumed to be true [. . .], then one can rely on the security proof."
2000-08- 7 Bryan Olson: "The OTP theorem doesn't say that encrypting with a particular key will maintain secrecy. It says choosing a one-time key uniformly at random and exposing the resulting ciphertext does not increase the chance of the attacker determining the plaintext."
2000-08- 8 Mok-Kong Shen: "You can point out the false logic here."
2000-08- 8 Bryan Olson: ". . . cryptographic security properties apply to the system with its key space, not to particular choices of key. Even if we obtain proof of the conjectures, that factoring is hard in general would not imply that every large number will be unfactorable."
2000-08-14 Tim Tyler: "This case still seems totally different from the case of using BBS with short cycles."
2000-08-14 Terry Ritter: "This whole discussion is theoretical, generally addressing the meaning of cryptographic proof. I'm unaware of any controversy about the idea that cycles theoretically could be detected easily."
2000-08-15 John Savard: "Since there is a 'mathematical proof' that the output of a BBS generator is "hard" to predict, in the same sense that breaking some public-key ciphers is known to be "hard" [...], I would, however, have to conclude that it is also a proof that a BBS generator cannot produce only a short cycle . . . ."
2000-08-16 David Hopwood: "There is no potential lead in."
2000-08-16 Terry Ritter: "Right."
2000-08-15 Bryan Olson: "The issue that secrecy comes from the keyspace and not the key applies to all secrecy systems."
2000-08-15 John Savard: "How can we take the undeniable truths of mathematics, and the practical facts of common-sense, and show that they don't really contradict each other?"
2000-08-15 Mok-Kong Shen: "I think that one has at this point remember that (an ideal) OTP is only a theoretical model and that in practice we adopt practical means that we (with more or less subjectivity) consider to be appropriate."
2000-08-17 Tim Tyler: "Imagine a rare spy, who - after landing in enemy territory - opens up his OTP and prepares to report that his espionage mission began successfully. Scanning the pages, he finds all the symbols are zeros. Imagine his dismay ;-)"
2000-08-17 Mok-Kong Shen: "Why? If the spy knows that his agency has given him a true OTP and he also happens to be a crypto theoretician, he will not hesitate a micro-second before applying the pad!"
2000-08-18 Trevor L. Jackson, III: "Is the message as secure if he does not calculate the ciphertext produced by the null pad and simply sends the plaintext?"
2000-08-19 Mok-Kong Shen: ". . . the spy, having FULL belief on the impeacability of the theory, should do his routine encryption processing with the pad and send the message."
2000-08-19 Trevor L. Jackson, III: "In principle, one can rely upon the source to produce the output it is designed to produce. But when one encouters an artifact, even an expected one, the urge to apply quality control to the output becomes intense."
2000-08-20 Mok-Kong Shen: "If we let the source generate a large amount of such sequences, we can see whether the distribution of these values sufficiently well correspond to that of an ideal random source. If we do the same for all statistical tests available, we can have indeed a quite good feeling of the quality of the source in my humble view."
2000-08-19 Douglas A. Gwyn: ". . . it is not the *data* that might be random, but the *process* that generates it. It is thus better to consider the property of "randomness" as meaning agreement with a specific source model."
2000-08-20 Mok-Kong Shen: "Right."
2000-08-20 Douglas A. Gwyn: ". . . for many people it might be *easier* to implement the algorithm and run some standard tests (e.g. Diehard), but that doesn't make it the best way to gain confidence in the patternlessness of the output from the algorithm."
2000-08-20 Mok-Kong Shen: ". . . a theory almost without exception is based on assumptions which are simplifications/approximations of the real world . . . ."
2000-08-21 Bryan Olson: "How could that ever hold?"
2000-08-21 Mok-Kong Shen: ". . . there be no practical means of knowing that a given source indeed produces an ideal OTP, as far as I am aware."
2000-08-21 Bryan Olson: "The question is how could it be zero."
2000-08-21 Mok-Kong Shen: ". . . before the timepoint where his huge neuronal network starts to compose the message, even the spy himself doesn't know what that message is. So I think that justifies to ascribe a probability 0.
2000-08-21 Bryan Olson: "That justifies "small" or even "negligible"." "Zero is wrong."
2000-08-21 Mok-Kong Shen: "Then kindly give me an example of yours that can serve to illustrate a probability of measure zero so that we could have a compararison."
2000-08-22 Bryan Olson: "Uh, O.K: Let m be any message space, and s the sum of the probabilities of all messages in m. Consider the probability that s does not equal one."
2000-08-22 Mok-Kong Shen: "First of all I don't yet see how you were answering to my question . . . ."
2000-08-21 Bryan Olson: ". . . claiming it's secure in the case when one chooses the zero key is wrong. It is not the individual cases that are secure - secrecy is only provable for the set of cases with their probabilities."
2000-08-17 Tim Tyler: " Another issue might be that rejecting short cycles appears to decrease the size of the keyspace. Has anyone yet proposed that rejecting these seeds is a cause of loss of strength? ;-)"
2000-08-16 Paul Pires: ". . . if you conceed that the occurance is exceedingly rare it does not seem as if it could be a meaningful reduction. A theoretical weakness without practical repercussions?"
2000-08-17 Mok-Kong Shen: "So it appears that in the proof of security of OTP one needs an additional assumption:"
2000-08-21 Bryan Olson: "The proof holds for the keyspace, so the assumption is the worst case and any violation can only hurt the attacker."
2000-08-18 David Hopwood: "I thought about that, and concluded that it doesn't."
2000-08-18 David Hopwood: "... except that the distribution of moduli is different, of course."
2000-08- 7 Bryan Olson: "The proof - without the long cycle test - deals with _all_ algorithmic methods of predicting the generator."
2000-08- 8 Mok-Kong Shen: "As someone has pointed out . . . , the term 'provable security' is misleading in almost all applied instances."
2000-08- 3 Mack: "BBS uses one squaring. RSA uses one squaring and one multiplication."
2000-08- 4 Tim Tyler: "It looks like you're both right ;-)"
2000-08- 3 Mark Wooding: "It *is* acceptable. The Blum-Goldwasser probabiliistic encryption algorithm is based on this very same idea."
2000-08- 3 Scott Nelson: ". . . a pad derived from BBS is just another stream cipher, and it shouldn't be called a one time pad."
2000-08- 3 Joseph Ashwood: "For a OTP the requirements are very strict, and generally unachievable. The most important one for this discussion is that each bit of the key stream must have an entropy content of 1 bit."

Subject: OTP using BBS generator?
Date: Thu, 03 Aug 2000 15:48:42 +1200
From: Grant Anderson <grant_anderson@supreme-overlord.com>
Message-ID: <3988EB99.29597754@supreme-overlord.com>
Newsgroups: sci.crypt
Lines: 28

I know there has been much discussion about (supposed) OTP ciphers and
how
most of them generally don't fulfil the OTP requirements. What I don't
understand is why the use of the blum-blum-shub generator as the  pad
isn't acceptable? I have read a great deal about the characteristics of
the BBS generator and it *seems* secure as "random-number" generators
go.

Assuming that each individual has a private key pair (two large primes)
p
and q and a public key n such that p x q = n, then the BBS generator
creates bits by:

x(i)=x^2 mod n for each i

Now obviously you can't use the same pad twice, so you would need to do
something like having a central repository (the keyserver for example)
which remembers the last "i" value for each user. So when you want to
encrypt for user A, you contact the keyserver and obtain their  public
key
(n) and the initialisation value i and start generating from i+1....

What is wrong with this solution?

Cheers,
Grant Anderson.

Subject: Re: OTP using BBS generator?
Date: 03 Aug 2000 05:18:06 GMT
From: macckone@aol.comnjunk123 (Mack)
Message-ID: <20000803011806.18934.00000762@ng-cl1.aol.com>
References: <3988EC4E.9555D120@supreme-overlord.com>
Newsgroups: sci.crypt
Lines: 6

The basic problem with the BBS
is that it is very slow.

Mack
Remove njunk123 from name to reply by e-mail

Bytes: 1216

Subject: Re: OTP using BBS generator?
Date: Thu, 03 Aug 2000 07:01:49 -0700
From: lordcow77 <london222NOloSPAM@netzero.com.invalid>
Message-ID: <0ebe7ce0.c2ca4460@usw-ex0105-040.remarq.com>
References: <39891A4E.110D7318@t-online.de>
   <398912AD.1A01F46C@supreme-overlord.com>
   <20000803011806.18934.00000762@ng-cl1.aol.com>
Newsgroups: sci.crypt
Lines: 27

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>BBS has been a recurring topic in this group. I have little
>knowledge in that but I have the impression that discussions
>about it never led to unanimously accepted results. You
>may try to look into old postings of this group.
>

Wrong. Practically everyone accepts that choosing the factors of
the modulus to be congruent to 3 mod 4 and picking a random
starting point are enough to ensure that the resulting BBS
sequence will be secure, based on the computational equivalence
of predicting BBS and deciding quadratic residuosity (and
therefore factoring). Terry Ritter is the only proponent of the
position that one must take elaborate steps to ensure that one
falls into a guaranteed long cycle on the basis of a
misunderstanding of the security proof given by Blum, Blum, and
Shub and a desire to assert that no cipher can be proven to be
secure under reasonable assumptions, such that he can promote
his own products that "stack" multiple patented algorithms
together.

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

Got questions?  Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com

Subject: Re: OTP using BBS generator?
Date: 3 Aug 2000 16:51:50 GMT
From: mdw@nsict.org (Mark Wooding)
Message-ID: <slrn8oj8p6.26s.mdw@mull.ncipher.com>
References: <0ebe7ce0.c2ca4460@usw-ex0105-040.remarq.com>
Newsgroups: sci.crypt
Lines: 10

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

> based on the computational equivalence of predicting BBS and deciding
> quadratic residuosity (and therefore factoring).

I don't mean to detract from your main point, with which I agree, but I
wasn't aware that it was proven that factoring can polytime reduce to
QRP.  Can you provide a reference?

-- [mdw]

Subject: Re: OTP using BBS generator?
Date: Thu, 03 Aug 2000 10:27:22 -0700
From: lordcow77 <london222NOloSPAM@netzero.com.invalid>
Message-ID: <29f3bf00.9eba152b@usw-ex0103-018.remarq.com>
References: <slrn8oj8p6.26s.mdw@mull.ncipher.com>
Newsgroups: sci.crypt
Lines: 20

mdw@nsict.org (Mark Wooding) wrote:
>lordcow77 <london222NOloSPAM@netzero.com.invalid> wrote:
>
>I don't mean to detract from your main point, with which I
agree, but I
>wasn't aware that it was proven that factoring can polytime
reduce to
>QRP.  Can you provide a reference?
>

A proof would be a surprise to me as well :-) QRP polytime
reduces to IFP, although I haven't seen anything proven on a
polytime reduction from IFP to QRP.

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

Got questions?  Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com

Subject: Re: OTP using BBS generator?
Date: Thu, 03 Aug 2000 18:52:29 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <3989A34D.A55FAC70@t-online.de>
References: <0ebe7ce0.c2ca4460@usw-ex0105-040.remarq.com>
Newsgroups: sci.crypt
Lines: 36

lordcow77 wrote:
> 
> Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
> >BBS has been a recurring topic in this group. I have little
> >knowledge in that but I have the impression that discussions
> >about it never led to unanimously accepted results. You
> >may try to look into old postings of this group.
> >
> 
> Wrong. Practically everyone accepts that choosing the factors of
> the modulus to be congruent to 3 mod 4 and picking a random
> starting point are enough to ensure that the resulting BBS
> sequence will be secure, based on the computational equivalence
> of predicting BBS and deciding quadratic residuosity (and
> therefore factoring). Terry Ritter is the only proponent of the
> position that one must take elaborate steps to ensure that one
> falls into a guaranteed long cycle on the basis of a
> misunderstanding of the security proof given by Blum, Blum, and
> Shub and a desire to assert that no cipher can be proven to be
> secure under reasonable assumptions, such that he can promote
> his own products that "stack" multiple patented algorithms
> together.

For one that does not have expert knowledge in BBS, like me,
it seems unfortunately to be difficult to know from the materials 
of past discussions in the group alone whether one party is 
absolutly right and the other absulutely wrong. Perhaps this is 
a consequence of the fact that crypto is a subtle art. (BTW, 
multiple encryption is not an invention of Terry Ritter but is 
well-known since earlier times of cryptography. Shannon also 
treated a series of three ciphers in one of his papers. There 
seems to be no reason why one should neglect that potential 
device of cryptography in my humble view.)

M. K. Shen

Subject: Re: OTP using BBS generator?
Date: Fri, 04 Aug 2000 05:42:07 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8mdl3f$3ah$1@nnrp1.deja.com>
References: <3989A34D.A55FAC70@t-online.de>
Newsgroups: sci.crypt
Lines: 26

Mok-Kong Shen
> For one that does not have expert knowledge in BBS, like me,
> it seems unfortunately to be difficult to know from the materials
> of past discussions in the group alone whether one party is
> absolutly right and the other absulutely wrong.

So look it up.  Surely anyone can recognize the utter
slyness of the claims that the reason the major current
references don't include the long-cycle test in their
description of the generator is that the authors have simply
not read the whole paper.  One could study the math and
understand why, for example HAC, describes the simpler form
of the generator; but only modest skill should enable one to
recognize that the author are not lazy nor careless, they do
understand the material, and that there's no evidence that
these allegations are other than fabrications.

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

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

Subject: Re: OTP using BBS generator?
Date: Fri, 04 Aug 2000 11:49:35 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <398A91AF.51504A25@t-online.de>
References: <8mdl3f$3ah$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 31

Bryan Olson wrote:
> 
> Mok-Kong Shen wrote:
> > For one that does not have expert knowledge in BBS, like me,
> > it seems unfortunately to be difficult to know from the materials
> > of past discussions in the group alone whether one party is
> > absolutly right and the other absulutely wrong.
> 
> So look it up.  Surely anyone can recognize the utter
> slyness of the claims that the reason the major current
> references don't include the long-cycle test in their
> description of the generator is that the authors have simply
> not read the whole paper.  One could study the math and
> understand why, for example HAC, describes the simpler form
> of the generator; but only modest skill should enable one to
> recognize that the author are not lazy nor careless, they do
> understand the material, and that there's no evidence that
> these allegations are other than fabrications.

I am afraid either the phrase 'but only modest skill should 
enable one to recognize that the author are not lazy nor 
careless' is not objective or you are demanding a skill that 
you condider to be modest but actually is not for the average
people. If only the simpler form is described in a book and
nothing else, how can a reader recognize laziness/carelessness
of its author or its opposite, excepting through reading the 
original article of BBS?

M. K. Shen

Subject: Re: OTP using BBS generator?
Date: Tue, 08 Aug 2000 04:19:51 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8mo1p4$8a9$1@nnrp1.deja.com>
References: <398A91AF.51504A25@t-online.de>
Newsgroups: sci.crypt
Lines: 22

Mok-Kong Shen wrote:
> Bryan Olson wrote:
> I am afraid either the phrase 'but only modest skill should
> enable one to recognize that the author are not lazy nor
> careless' is not objective or you are demanding a skill that
> you condider to be modest but actually is not for the average
> people.

I suppose you are right that one will not be able to tell,
given that he is both unwilling to deeply study the material
for himself, and cannot trust the consensus of experts if
there is one claim, even completely unsubstantiated, against
them.

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

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

Subject: Re: OTP using BBS generator?
Date: Tue, 08 Aug 2000 08:25:20 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <398FA7D0.A06E656A@t-online.de>
References: <8mo1p4$8a9$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 43

Bryan Olson wrote:
> 
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > I am afraid either the phrase 'but only modest skill should
> > enable one to recognize that the author are not lazy nor
> > careless' is not objective or you are demanding a skill that
> > you condider to be modest but actually is not for the average
> > people.
> 
> I suppose you are right that one will not be able to tell,
> given that he is both unwilling to deeply study the material
> for himself, and cannot trust the consensus of experts if
> there is one claim, even completely unsubstantiated, against
> them.

The real problem is that those, who are able to fully 
understand the original paper of BBS, probably wouldn't 
stay long with this thread and watch the heated debate 
and those, who are not, can (by definition) get nothing 
definite from a deep study, no matter how deeply they 
try. As to trusting experts, there is the problem of 
knowing who are the genuine experts and one risks being
involved in a 'religious' issue. (Indeed, there exists 
at least one person on earth who by definition can't 
err. But unfortunately he is not in our group.) If 
there are two persons who have opposite opinions and 
both claim to have expert knowledge, whom should one 
trust??

BTW, BBS has been recurring many times in our group.
I sincerely hope that this time the experts discussing 
here will conduct their disputes to a 'bitter end', 
giving a CLEAR result for the observing non-experts 
(with one party explictly conceding to be defeated),
such that, if anyone later once more posts questions 
about BBS in the group, a simply pointer could be made 
to that result. It's no longer fun reading the same
dispute stuff for the fifth or more times.

M. K. Shen

Subject: Re: OTP using BBS generator?
Date: Thu, 03 Aug 2000 19:06:19 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <3989c299.4078028@news.io.com>
References: <0ebe7ce0.c2ca4460@usw-ex0105-040.remarq.com>
Newsgroups: sci.crypt
Lines: 74

On Thu, 03 Aug 2000 07:01:49 -0700, in
<0ebe7ce0.c2ca4460@usw-ex0105-040.remarq.com>, in sci.crypt lordcow77
<london222NOloSPAM@netzero.com.invalid> wrote:

>Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>>BBS has been a recurring topic in this group. I have little
>>knowledge in that but I have the impression that discussions
>>about it never led to unanimously accepted results. You
>>may try to look into old postings of this group.
>>
>
>Wrong. Practically everyone accepts that choosing the factors of
>the modulus to be congruent to 3 mod 4 and picking a random
>starting point are enough to ensure that the resulting BBS
>sequence will be secure, based on the computational equivalence
>of predicting BBS and deciding quadratic residuosity (and
>therefore factoring). 

That is false on its face.  You can accept if you want, however.

It is true that using a short cycle would be extremely unlikely.  But
*when* that event occurs, all the math proofs you have will not save
you, since the resulting system is insecure.  

Using a short cycle is unarguably insecure.  And, unless we
specifically prevent it, using a short cycle is an unarguable
possibility.  

The only valid argument here is that using a short cycle would be
extremely unlikely, and that is no conflict, because I agree.  

>Terry Ritter is the only proponent of the
>position that one must take elaborate steps to ensure that one
>falls into a guaranteed long cycle on the basis of a
>misunderstanding of the security proof given by Blum, Blum, and
>Shub and a desire to assert that no cipher can be proven to be
>secure under reasonable assumptions, such that he can promote
>his own products that "stack" multiple patented algorithms
>together.

Alas for the attempt at a personal attack, I have no current
"products" in that sense.  I do hold current patents which represent
fundamentally new cryptographic technology.  You can like that or you
can hate it, but I own the technology anyway.  

Does the fact that I might make money out of improving technology
somehow make me suspect for pointing out the problems in other
approaches?  Finding the problems is why I have better approaches.
But I may be one of the few authors and designers who actively seeks
negative comments and then publishes those on my pages, as readers can
attest.  

My stuff is not intended to replace BB&S or PK, but if they have
problems that I see, I'm going to say so, independent of whether I can
profit from that or not.  

I have been doing this for the better part of a decade, and I don't
need to have my motives questioned.  By pointing out problems, others
can make their own informed choices about how to solve those problems
or perhaps use something else.  My patented technology provides
alternatives which others may weigh against the price of its use.  

For free, I offer a 400K Crypto Glossary, plus a free Introduction to
Cryptography, Literature Surveys also free, plus lots of other stuff.
You don't have to buy a book to read my stuff, but if you want to read
it in a library, you can do that too, on any Web terminal.  

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

Subject: Re: OTP using BBS generator?
Date: Thu, 3 Aug 2000 12:44:56 -0700
From: "Paul Pires" <diodude@got.net>
Message-ID: <5%ji5.14708$GS1.250965@news-west.usenetserver.com>
References: <3989c299.4078028@news.io.com>
Newsgroups: sci.crypt
Lines: 88

Terry Ritter <ritter@io.com> wrote in message
news:3989c299.4078028@news.io.com...
>
> On Thu, 03 Aug 2000 07:01:49 -0700, in
> <0ebe7ce0.c2ca4460@usw-ex0105-040.remarq.com>, in sci.crypt lordcow77
> <london222NOloSPAM@netzero.com.invalid> wrote:
>
> >Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
> >>BBS has been a recurring topic in this group. I have little
> >>knowledge in that but I have the impression that discussions
> >>about it never led to unanimously accepted results. You
> >>may try to look into old postings of this group.
> >>
> >
> >Wrong. Practically everyone accepts that choosing the factors of
> >the modulus to be congruent to 3 mod 4 and picking a random
> >starting point are enough to ensure that the resulting BBS
> >sequence will be secure, based on the computational equivalence
> >of predicting BBS and deciding quadratic residuosity (and
> >therefore factoring).
>
> That is false on its face.  You can accept if you want, however.
>
> It is true that using a short cycle would be extremely unlikely.  But
> *when* that event occurs, all the math proofs you have will not save
> you, since the resulting system is insecure.
>
> Using a short cycle is unarguably insecure.  And, unless we
> specifically prevent it, using a short cycle is an unarguable
> possibility.
>
> The only valid argument here is that using a short cycle would be
> extremely unlikely, and that is no conflict, because I agree.
>
>
> >Terry Ritter is the only proponent of the
> >position that one must take elaborate steps to ensure that one
> >falls into a guaranteed long cycle on the basis of a
> >misunderstanding of the security proof given by Blum, Blum, and
> >Shub and a desire to assert that no cipher can be proven to be
> >secure under reasonable assumptions, such that he can promote
> >his own products that "stack" multiple patented algorithms
> >together.
>
> Alas for the attempt at a personal attack, I have no current
> "products" in that sense.  I do hold current patents which represent
> fundamentally new cryptographic technology.  You can like that or you
> can hate it, but I own the technology anyway.
>
> Does the fact that I might make money out of improving technology
> somehow make me suspect for pointing out the problems in other
> approaches?  Finding the problems is why I have better approaches.
> But I may be one of the few authors and designers who actively seeks
> negative comments and then publishes those on my pages, as readers can
> attest.
>
> My stuff is not intended to replace BB&S or PK, but if they have
> problems that I see, I'm going to say so, independent of whether I can
> profit from that or not.
>
> I have been doing this for the better part of a decade, and I don't
> need to have my motives questioned.  By pointing out problems, others
> can make their own informed choices about how to solve those problems
> or perhaps use something else.  My patented technology provides
> alternatives which others may weigh against the price of its use.
>
> For free, I offer a 400K Crypto Glossary, plus a free Introduction to
> Cryptography, Literature Surveys also free, plus lots of other stuff.
> You don't have to buy a book to read my stuff, but if you want to read
> it in a library, you can do that too, on any Web terminal.

Well said. I wish that I could be that generous in defending against
nonsensical attacks. The problem with taking the high ground in an argument
is that you must scale it first. I'll keep climbing.

Thanks for the example.

Paul

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

Subject: Re: OTP using BBS generator?
Date: Thu, 3 Aug 2000 14:12:01 -0700
From: "Joseph Ashwood" <ashwood@msn.com>
Message-ID: <O#qg39Y$$GA.585@cpmsnbbsa08>
References: <3989c299.4078028@news.io.com>
Newsgroups: sci.crypt
Lines: 19

I know I'm arriving rather late to the party but, while Mr Ritter and I have
been on differing sides of discussions before, I agree with him completely
in this case. What he has suggested is to verify the lack of a short cycle,
through a relatively cheap mechanism (certainly cheaper than the compromised
security that could result is that check would have been failed). I find
this to be solid reasoning, and something that should be done by anyone
making use of BBS in this fashion.

On a more personal note, I've noticed that this conversation has drifted
towards being personal insults, please try to remember that Mr Ritter has
been a long standing member of this group, and has build a quite solid,
respected position, all you are doing is harming your credibiltity, as can
be rather easily seen by looking at Mr Ritter's response, which was to the
best of my knowledge completely factual, and dealt more with the issue at
hand than his attacker.
                Joe

Subject: Re: OTP using BBS generator?
Date: 04 Aug 2000 00:43:36 GMT
From: macckone@aol.comnjunk123 (Mack)
Message-ID: <20000803204336.05175.00000707@ng-fe1.aol.com>
References: <O#qg39Y$$GA.585@cpmsnbbsa08>
Newsgroups: sci.crypt
Lines: 36

>I know I'm arriving rather late to the party but, while Mr Ritter and I have
>been on differing sides of discussions before, I agree with him completely
>in this case. What he has suggested is to verify the lack of a short cycle,
>through a relatively cheap mechanism (certainly cheaper than the compromised
>security that could result is that check would have been failed). I find
>this to be solid reasoning, and something that should be done by anyone
>making use of BBS in this fashion.
>
>On a more personal note, I've noticed that this conversation has drifted
>towards being personal insults, please try to remember that Mr Ritter has
>been a long standing member of this group, and has build a quite solid,
>respected position, all you are doing is harming your credibiltity, as can
>be rather easily seen by looking at Mr Ritter's response, which was to the
>best of my knowledge completely factual, and dealt more with the issue at
>hand than his attacker.
>                Joe
>
>

I agree with Terry Ritter also.  There are several types of cycles
possible with the BBS generator.  It is important that the
primes used be "special".  In that case the cycle will be two or
we have found a multiple of a factor of N for a short cycle.  It is
easy to check for both of these conditions.

Using a single bit from each X increases the chance of the cycle
of the output being two by a great deal, does anyone have an
analysis of how often this occurs?

Mack
Remove njunk123 from name to reply by e-mail

Subject: Re: OTP using BBS generator?
Date: Sat, 05 Aug 2000 18:38:36 +0100
From: David Hopwood <hopwood@zetnet.co.uk>
Message-ID: <398C511C.77C8210D@zetnet.co.uk>
References: <O#qg39Y$$GA.585@cpmsnbbsa08>
Newsgroups: sci.crypt
Lines: 48

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

Joseph Ashwood wrote:
> I know I'm arriving rather late to the party but, while Mr Ritter and I have
> been on differing sides of discussions before, I agree with him completely
> in this case. What he has suggested is to verify the lack of a short cycle,
> through a relatively cheap mechanism (certainly cheaper than the compromised
> security that could result is that check would have been failed).

It's not particularly cheap in terms of the speed of parameter generation,
and it has been proven that short cycles happen with negligable probability,
if the parameter sizes are such that factoring is hard.

The probability of weakness is not changed significantly by applying the
constraints that Ritter thinks are necessary; as has been pointed out
repeatedly, his arguments are based on a misunderstanding of the BBS
security proofs.

> I find this to be solid reasoning, and something that should be done by
> anyone making use of BBS in this fashion.

It really doesn't provide any significant advantage - if checking for short
cycles were actually needed for BBS, that would cast doubt on the security
of every IFP-based cryptosystem, including RSA, Rabin, etc.

- -- 
David Hopwood <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

iQEVAwUBOYxQ5jkCAxeYt5gVAQGerAgAr0jXT3fyZFVkFZVdCoXu2AR4Ur+BdIzt
0F1gYbwODTSpFjeovdJTKwT18blRYwiHZyZL+z6H8ob/XYJS0OH67szO8IJbWzBL
Ulchhw60m5wExA617AQ6JOwheKTkfxJsUErhY62b3ojFWOmviI/Z6M2HpQ3gz0bP
yTb1IOoGNuikKcqt6xCqG51vswGtp5FX+Lpv34fW8AApD/Um+GR4jrbYAyHUgB8z
18g0Dg67TlLMDdQsxqy50VBzgWF/tJEyz4YoWj142Dzeh8GQhoZd/Aoygar4cJ2x
an3agDB4WQUFjGQCSJ0xBAuONP7U6x7mdAMZqBnY1EOEcynmypUDwg==
=AqMi
-----END PGP SIGNATURE-----

Subject: Re: OTP using BBS generator?
Date: Sun, 06 Aug 2000 19:51:57 +0200
From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Message-ID: <398DA5BD.73A73CE@t-online.de>
References: <398C511C.77C8210D@zetnet.co.uk>
Newsgroups: sci.crypt
Lines: 33

David Hopwood wrote:
> 
> Joseph Ashwood wrote:
> > I know I'm arriving rather late to the party but, while Mr Ritter and I have
> > been on differing sides of discussions before, I agree with him completely
> > in this case. What he has suggested is to verify the lack of a short cycle,
> > through a relatively cheap mechanism (certainly cheaper than the compromised
> > security that could result is that check would have been failed).
> 
> It's not particularly cheap in terms of the speed of parameter generation,
> and it has been proven that short cycles happen with negligable probability,
> if the parameter sizes are such that factoring is hard.
> 
> The probability of weakness is not changed significantly by applying the
> constraints that Ritter thinks are necessary; as has been pointed out
> repeatedly, his arguments are based on a misunderstanding of the BBS
> security proofs.

Scott Nelson said in his follow-up:

    One Time Pad is more a theoretical than practical encryption.
    To be theoretically perfect, it requires perfect random
    numbers for the pad.  BBS is at best pseudo random,
    therefore can, at best, offer pseudo security.

Thus if, in analogy, we equate OTP to infinity, then BBS is
a very large (but finite) number. Subtracting a small number from 
a very large number gives still a very large (but finite) number. 
Does this analogy capture the essence of what you said? Thanks.

M. K. Shen

Subject: Re: OTP using BBS generator?
Date: Mon, 07 Aug 2000 04:50:14 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <398e3fa2.1683088@news.io.com>
References: <398C511C.77C8210D@zetnet.co.uk>
Newsgroups: sci.crypt
Lines: 84

On Sat, 05 Aug 2000 18:38:36 +0100, in
<398C511C.77C8210D@zetnet.co.uk>, in sci.crypt David Hopwood
<hopwood@zetnet.co.uk> wrote:

>-----BEGIN PGP SIGNED MESSAGE-----
>
>Joseph Ashwood wrote:
>> I know I'm arriving rather late to the party but, while Mr Ritter and I have
>> been on differing sides of discussions before, I agree with him completely
>> in this case. What he has suggested is to verify the lack of a short cycle,
>> through a relatively cheap mechanism (certainly cheaper than the compromised
>> security that could result is that check would have been failed).
>
>It's not particularly cheap in terms of the speed of parameter generation,
>and it has been proven that short cycles happen with negligable probability,
>if the parameter sizes are such that factoring is hard.

BB&S short cycles are unlikely to be a *practical* weakness.  

But this *is* a practical *issue*, since the whole point of using slow
BB&S in practice is to gain proven strength.  If the proof does not
hold for every cycle we may select, then BB&S may be weak in normal
use, which means there is no point in using BB&S.  

Here is the summary again:  

*  It is INDISPUTABLE that short cycles do exist in BB&S.  

*  If the start value is selected purely at random, it is INDISPUTABLE
that a short cycle might be selected.  

*  It is INDISPUTABLE that when a random number generator (RNG) cycle
has been traversed, we can predict future values from the ones
produced in the past.  

Every deterministic RNG must repeat eventually, and when it does, it
becomes insecure no matter how many security proofs it has.  If a
system is designed such that a short cycle may be selected, it can
have no guarantee of security.  

>The probability of weakness is not changed significantly by applying the
>constraints that Ritter thinks are necessary; as has been pointed out
>repeatedly, his arguments are based on a misunderstanding of the BBS
>security proofs.

To the contrary, I would say that it is you and the others who
seriously overestimate cryptographic proof in general, and have a
significant misunderstanding of random number generators (RNG's) in
particular.  

This argument has progressed to the point that my issues are virtually
unassailable: they are easily understood and obviously correct,
independent of any claim you may make.  If you really have a result
which conflicts with these points, it is time to re-think your math.

You may have other issues, and I may or may not dispute them, but
saying that I misunderstand is strange.  Clearly you don't let a mere
lack of context stop you from presenting your preconceptions.

Because these issues are in simple form, most people reading here can
understand that they are true, whether math guys agree with that or
not.  Presumably, those on the other side will find some semantic
argument to claim they were right all along -- despite disputing my
points time and time again.  And that will demonstrate just how much
we can trust what math guys say about crypto security.  

>> I find this to be solid reasoning, and something that should be done by
>> anyone making use of BBS in this fashion.
>
>It really doesn't provide any significant advantage - if checking for short
>cycles were actually needed for BBS, that would cast doubt on the security
>of every IFP-based cryptosystem, including RSA, Rabin, etc.

You have misstated the weakness at issue.  See above.

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

Subject: Re: OTP using BBS generator?
Date: Tue, 08 Aug 2000 05:26:14 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8mo5lk$apa$1@nnrp1.deja.com>
References: <398e3fa2.1683088@news.io.com>
Newsgroups: sci.crypt
Lines: 40

Terry Ritter wrote:
> David Hopwood

> This argument has progressed to the point that my issues are virtually
> unassailable: they are easily understood and obviously correct,
> independent of any claim you may make.  If you really have a result
> which conflicts with these points, it is time to re-think your math.

So once more you refuse to address what people are
saying.  You bleat yet again that if a short
cycle happens it's weak, as if the post to which
you respond had said otherwise.

Care to try?  Where is the proof that if one _does_ reject
short cycles one must, with probability one, get a
particular instance that is not predictable by an attacker
(given that general factoring is intractable)?  We know that
such an attack cannot be based on a short cycle of the
generator state; you need not point that out again.

> You may have other issues, and I may or may not dispute them, but
> saying that I misunderstand is strange.  Clearly you don't let a mere
> lack of context stop you from presenting your preconceptions.

There's no question that you misunderstood the BB&S
proof.  Check out:

    http://x64.deja.com/getdoc.xp?AN=637286423

where you state what you assumed the proofs guaranteed.

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

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

Subject: Re: OTP using BBS generator?
Date: Tue, 08 Aug 2000 16:29:13 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <399034e8.4865622@news.io.com>
References: <8mo5lk$apa$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 143

On Tue, 08 Aug 2000 05:26:14 GMT, in <8mo5lk$apa$1@nnrp1.deja.com>, in
sci.crypt Bryan Olson <bryanolson@my-deja.com> wrote:

>Terry Ritter wrote:
>> David Hopwood
>
>> This argument has progressed to the point that my issues are virtually
>> unassailable: they are easily understood and obviously correct,
>> independent of any claim you may make.  If you really have a result
>> which conflicts with these points, it is time to re-think your math.
>
>So once more you refuse to address what people are
>saying.  You bleat yet again that if a short
>cycle happens it's weak, as if the post to which
>you respond had said otherwise.

The post to which I responded implied that weakness could not exist,
and did so in a slightly offensive manner.  It was false, because
there is weakness.  It just happens rarely.  

There is a remarkable lack of desire to address this known weakness,
even though we know how to do that.  This means the math guys are
perfectly happy to leave a preventable weakness in a cryptosystem,
something which I think none of us should accept as reasonable.  

But what *really* happens is that every time I assume Bryan might be
capable of reasoned discourse, he proves me wrong.  

>Care to try?  Where is the proof that if one _does_ reject
>short cycles one must, with probability one, get a
>particular instance that is not predictable by an attacker
>(given that general factoring is intractable)?  

That would be more your proof than mine.  I do not champion the use of
BB&S.  Instead, I expose the fact that "proven strength" is a
mathematical term-of-art which implies things which are not at all
what a non-mathematician might expect.  

Basically, a large portion of the crypto and non-crypto population is
being deceived by the use of technical terms about proof and strength
which do not really mean what a lesser being might think.  

Moreover, the theory itself has a real problem:  Any state-based
Random Number Generator (RNG) of whatever design has some cycle
length.  Whenever that cycle length is exceeded, the sequence becomes
predictable.  But nowhere in the proof -- as far as I know -- is a
limit proposed for generator use.  So, sort-cycle or long-cycle,
eventually the cycle *will* be traversed (in theory), and the system
*will* become insecure.  As proven, the system is always *in*secure,
except for one cycle traversal at the start.  The only thing that
prevents this in practice is the size of the values and so the size of
the cycles, but even huge values will have some limit, and the theory
does not take that into account.  I would say that the theory is
insufficient as it stands.  

>We know that
>such an attack cannot be based on a short cycle of the
>generator state; you need not point that out again.

Since short cycles are weak and preventing short cycles is possible
yet not done, the situation obviously needs to be pointed out as
frequently as possible.  I can't spend as much time on line as I used
to; perhaps someone else will help take up the cause.  

>> You may have other issues, and I may or may not dispute them, but
>> saying that I misunderstand is strange.  Clearly you don't let a mere
>> lack of context stop you from presenting your preconceptions.
>
>There's no question that you misunderstood the BB&S
>proof.  Check out:
>
>
>http://x64.deja.com/getdoc.xp?AN=637286423

And here it is!

|On 21 Jun 2000 08:16:56 GMT, in <8iptlo$o3o$2@bambi.zdv.Uni-Mainz.DE>, 
| in sci.crypt pom@imsd.uni-mainz.de (Klaus Pommerening) wrote:
|  
| >In <394fa82d.6283727@news.io.com> Terry Ritter wrote:
| >> *  We *can* build a generator which does not use short cycles.  
| >> 
| >BTW the BBS generator outputs the LSB of its internal state
| >x_i for each step. (x_i = x_{i-1}^2 mod n)
| >Is there any known result that some choice of parameters in BBS
| >guarantees that the LSBs don't give short cycles?
|  
|Not that I know of.  I never even thought of investigating such a 
|thing on my small models.  I guess I assumed that sort of thing 
|was exactly what the proofs guaranteed.  

>
>where you state what you assumed the proofs guaranteed.

This is exactly the reason that I have in the past stopped conversing
with Bryan, and now will do so again.  It is not because he has found
an error in my reasoning, or a change in my position, or a hypocrisy
in my comments.  It is because he is unwilling or unable to accept
comments in their appropriate context.  There are a lot of people who
respond, a lot of points made, and a lot of words flying around; it is
easy to find something which might be taken out of context.  I note
that as usual he does not actually include the quote; personally, I
think he just expects that most people won't look it up.  This sort of
thing happens repeatedly, and simply is not acceptable behavior.  

With respect my comment about what the proofs guarantee, it was a
specific response to the last question, which is about
Least-Significant-Bits (LSB's) in particular, not short cycles in
general.  I never investigated whether the LSB's form short cycles,
even though I have investigated short cycles in the BB&S system.  My
response was that this sort of peculiar special case is exactly what
should be covered by a proof, and in his recent message, Bryan seemed
to indicate just that:

>The proof - without the long
>cycle test - deals with _all_ algorithmic methods of
>predicting the generator.  

I take that to mean that predicting bits -- in particular LSB's -- is
also thought to be hard.  Which is what I expect from the proof.
Which is consistent with what I have said and will say on this
subject.  

I am not a BB&S proof expert.  I do not promote the use of BB&S.  But
if one is to use BB&S, one should at least know what one is getting.
The failure to exclude short cycles means that a "proven secure"
system has a preventable weakness which is not being excluded.  Sure,
it almost never happens, but almost never is not never.  

Suppose a new cipher were invented which could prevent the weakness of
an opponent choosing the correct key -- it would absolutely prevent
brute force attacks on the key.  That would close a weakness of
similar probability to the BB&S short cycles, and I think it would be
widely acclaimed.  In BB&S we have a weakness of similar import, yet
the math guys want us to ignore it.  I find that odd.

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

Subject: Re: OTP using BBS generator?
Date: Tue, 08 Aug 2000 20:28:43 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8mpqhn$fca$1@nnrp1.deja.com>
References: <399034e8.4865622@news.io.com>
Newsgroups: sci.crypt
Lines: 201

Terry Ritter wrote:
> Bryan Olson wrote:

> >So once more you refuse to address what people are
> >saying[...]

> The post to which I responded implied that weakness could not exist,
> and did so in a slightly offensive manner.  It was false, because
> there is weakness.  It just happens rarely.

No, in that post David Hopwood got it right:

| it has been proven that short cycles happen with negligible
| probability, if the parameter sizes are such that factoring
| is hard

> There is a remarkable lack of desire to address this known weakness,
> even though we know how to do that.

I take a different view: I think showing the failure happens
with negligible probability is a perfectly valid way to
address the weakness.

[...]
> But what *really* happens is that every time I assume Bryan might be
> capable of reasoned discourse, he proves me wrong.
>
> >Care to try?  Where is the proof that if one _does_ reject
> >short cycles one must, with probability one, get a
> >particular instance that is not predictable by an attacker
> >(given that general factoring is intractable)?
>
> That would be more your proof than mine.  I do not champion the use of
> BB&S.

(Nor do I incidentally.)

> Instead, I expose the fact that "proven strength" is a
> mathematical term-of-art which implies things which are not at all
> what a non-mathematician might expect.

Could this be progress?  I've been saying that the scheme
without the long cycle test is secure in the same sense as
the scheme with the test. In neither case are individual
choices of parameters proven strong. Are you now agreeing?

> Basically, a large portion of the crypto and non-crypto population is
> being deceived by the use of technical terms about proof and strength
> which do not really mean what a lesser being might think.

What population of the community understands probabilistic
arguments I cannot say.  But to those who do really
understand them, they're persuasive.  For a particular
choice of parameters, and I must use a particular choice
when the time comes to encrypt, I don't know that the
parameters cannot be broken, or even that the chance that
they'll be broken is negligible.  So I work from what I do
know: if I choose the parameters from the probability space
and encrypt, then the chance of the system falling is
negligible.  Strength is in the keyspace, not the key.

Dependence on probability appears throughout science and
engineering.  Where cryptology specifically falls short is
in theorems premised on open conjectures.

> Moreover, the theory itself has a real problem:  Any state-based
> Random Number Generator (RNG) of whatever design has some cycle
> length.  Whenever that cycle length is exceeded, the sequence becomes
> predictable.  But nowhere in the proof -- as far as I know -- is a
> limit proposed for generator use.  So, sort-cycle or long-cycle,
> eventually the cycle *will* be traversed (in theory), and the system
> *will* become insecure.  As proven, the system is always *in*secure,
> except for one cycle traversal at the start.  The only thing that
> prevents this in practice is the size of the values and so the size of
> the cycles, but even huge values will have some limit, and the theory
> does not take that into account.  I would say that the theory is
> insufficient as it stands.

The theory assumes that the parameters are chosen to be
large enough that factoring is intractable.  Given that we
cannot do enough computation to factor with non-negligible
probability, we also cannot do enough to get through the
cycle with non-negligible probability.

> >There's no question that you misunderstood the BB&S
> >proof.  Check out:
> >
> >
> >http://x64.deja.com/getdoc.xp?AN=637286423
>
> And here it is!
>

[Klaus Pommerening]:
> | >BTW the BBS generator outputs the LSB of its internal state
> | >x_i for each step. (x_i = x_{i-1}^2 mod n)
> | >Is there any known result that some choice of parameters in BBS
> | >guarantees that the LSBs don't give short cycles?
[Ritter:]
> |Not that I know of.  I never even thought of investigating such a
> |thing on my small models.  I guess I assumed that sort of thing
> |was exactly what the proofs guaranteed.

Yes, exactly the kind of thing I've pointed out both before
and after that post: the long cycle filter doesn't imply
there's no case in which particular parameters fail (though I
don't know if this kind of failure is possible).  But why,
after reading the paper, citing the paper, and accusing
everyone else of not reading the whole paper, were you still
_assuming_ what the proofs guaranteed?

> This is exactly the reason that I have in the past stopped conversing
> with Bryan, and now will do so again.

No, what you've done is a debating trick where you alternate
between claiming that you don't respond to my posts and
responding to them.

> It is not because he has found
> an error in my reasoning, or a change in my position, or a hypocrisy
> in my comments.  It is because he is unwilling or unable to accept
> comments in their appropriate context.

Has your position changed?  Do I understand correctly that
the significant issue to you is that proof of strength ought
to imply strength against all crypt-analytic attacks for
every choice of key?  I've been saying that with or without
the cycle length test, the generator is only strong in the
probabilistic sense, as a property of the key space and not
a particular key (and subject to the open assumption).  Do
we now have agreement?

> There are a lot of people who
> respond, a lot of points made, and a lot of words flying around; it is
> easy to find something which might be taken out of context. I note
> that as usual he does not actually include the quote; personally, I
> think he just expects that most people won't look it up.  This sort of
> thing happens repeatedly, and simply is not acceptable behavior.

You object to the link?  I particularly did not want to take
anything out of context, so I provided a link to the whole
post which further links to the threaded history.

[...]
> With respect my comment about what the proofs guarantee, it was a
> specific response to the last question, which is about
> Least-Significant-Bits (LSB's) in particular, not short cycles in
> general.  I never investigated whether the LSB's form short cycles,
> even though I have investigated short cycles in the BB&S system.  My
> response was that this sort of peculiar special case is exactly what
> should be covered by a proof, and in his recent message, Bryan seemed
> to indicate just that:
>
> >The proof - without the long
> >cycle test - deals with _all_ algorithmic methods of
> >predicting the generator.

True, and a good example of out-of-context quoting.  The
sentence that immediately follows in the same paragraph:

| The proof is a reduction from QR
| (and later factoring) and thus it only shows the generator
| hard to predict in the sense and in the cases in which
| factoring is hard.

You keep saying how deceptive people are to call these
things proofs of security.  Then when I carefully explain
the cases and sense in which the proof applies, you chop
that off, making it into the kind you call
deceptive.

But since this is still a technical group, I'll get back to
the point of that entire paragraph: the BBS generator proof
of security against all algorithmic attacks is a result
about the key space and not any particular key.  BB&S added
that keys can be chosen to bring the chance of one
particular form of failure from negligible to zero. The
crypto community has judged the general argument much more
interesting and important than the extra resistance to one
particular attack.

The major flaw in the BBS proof remains the reliance on
an open conjecture.

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

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

Subject: Re: OTP using BBS generator?
Date: Tue, 08 Aug 2000 21:37:01 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <39907b79.3479797@news.io.com>
References: <8mpqhn$fca$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 26

On Tue, 08 Aug 2000 20:28:43 GMT, in <8mpqhn$fca$1@nnrp1.deja.com>, in
sci.crypt Bryan Olson <bryanolson@my-deja.com> wrote:

>Terry Ritter wrote:
>[...]
>> This is exactly the reason that I have in the past stopped conversing
>> with Bryan, and now will do so again.
>
>No, what you've done is a debating trick where you alternate
>between claiming that you don't respond to my posts and
>responding to them.

I guess when one tries to give a guy another chance in the ridiculous
hope that he has changed his spots, one deserves just that sort of
response!  

If Bryan wants to see it as a debating trick, he can do that just as
long as he likes.  As far as I am concerned, he is interested in
"winning"; not participating in a discussion of reality.  That can
look like discussion, but is not really, and neither is this.

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

Subject: Re: OTP using BBS generator?
Date: Thu, 10 Aug 2000 03:01:29 GMT
From: Bryan Olson <bryanolson@my-deja.com>
Message-ID: <8mt5u9$oek$1@nnrp1.deja.com>
References: <39907b79.3479797@news.io.com>
Newsgroups: sci.crypt
Lines: 56

Terry Ritter wrote:
> Bryan Olson wrote:
> >Terry Ritter wrote:
> >> This is exactly the reason that I have in the past
> >> stopped conversing
> >> with Bryan, and now will do so again.
> >
> >No, what you've done is a debating trick where you alternate
> >between claiming that you don't respond to my posts and
> >responding to them.
>
> I guess when one tries to give a guy another chance in the ridiculous
> hope that he has changed his spots, one deserves just that sort of
> response!
>
> If Bryan wants to see it as a debating trick, he can do that just as
> long as he likes.

Well, I was confused as to what to make of it.  The first
time I heard of it was in January, when you wrote in a
response to someone else that you no longer debate with me.
The next day you followed up one of my posts, quoting my
points and making yours.  And the day after that, I read
that you no longer participate in discussions with me.

> As far as I am concerned, he is interested in
> "winning"; not participating in a discussion of reality.  That can
> look like discussion, but is not really, and neither is this.

If you don't think this issue of whether you converse with
me belongs in the discussion, *you* didn't have to bring it
up.  Why not respond instead to my entirely technical post

    http://www.deja.com/getdoc.xp?AN=655556392

or to any of the technical points from this strand?

I thought we might actually make progress last time.  Can we
agree that BBS generator with or without the cycle length
filter does not ensure (even if factoring is usually hard)
that each individual key will induce unpredictable output?
If so we can move on to whether proofs that apply to the key
proofs of security, (as I argued they can and I gather you
hold they cannot).

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

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

Subject: Re: OTP using BBS generator?
Date: Wed, 09 Aug 2000 19:49:44 GMT
From: Benjamin Goldberg <goldbb2@earthlink.net>
Message-ID: <3990A233.8D403CF3@earthlink.net>
References: <8mpqhn$fca$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 64

Bryan Olson wrote:
[snip]
> No, in that post David Hopwood got it right:
> 
> | it has been proven that short cycles happen with negligible
> | probability, if the parameter sizes are such that factoring
> | is hard
> 
> > There is a remarkable lack of desire to address this known weakness,
> > even though we know how to do that.
> 
> I take a different view: I think showing the failure happens
> with negligible probability is a perfectly valid way to
> address the weakness.

Suppose we have a block cipher with big keys.  Further suppose that a
small number of those keys give the identity transformation, and all
other keys are VERY secure.  Also, suppose that there's no known way to
find those weak keys without doing a trial encryption, but a trial
encryption is trivial.  Weak keys have low probability, but when they
occur, the system is wide open.

With BBS, short cycles occur with low probability, and the system is
very secure when we don't have a short cycle.  There's no known way to
detect weather short cycles will occur without explicit testing, but
explicit testing is trivial.  If a short cycle does occur, the system is
wide open.

Does anyone see a similarity?  Would anyone use the described block
cipher without testing for the identity transformation?  Assume that the
identity transformation occurs as often as short BBS cycles.

Personally, I think there exists some kind of futher restriction on the
parameters to BBS which will eliminate short cycles entirely, but we
haven't found it yet.  That would be better than explicit testing for
short cycles.

[snip]
> [Klaus Pommerening]:
> > | >BTW the BBS generator outputs the LSB of its internal state
> > | >x_i for each step. (x_i = x_{i-1}^2 mod n)
> > | >Is there any known result that some choice of parameters in BBS
> > | >guarantees that the LSBs don't give short cycles?
> [Ritter:]
> > |Not that I know of.  I never even thought of investigating such a
> > |thing on my small models.  I guess I assumed that sort of thing
> > |was exactly what the proofs guaranteed.
> 
> Yes, exactly the kind of thing I've pointed out both before
> and after that post: the long cycle filter doesn't imply
> there's no case in which particular parameters fail (though I
> don't know if this kind of failure is possible).  But why,
> after reading the paper, citing the paper, and accusing
> everyone else of not reading the whole paper, were you still
> _assuming_ what the proofs guaranteed?

What it seems that Ritter is saying is that he's assuming that if there
are no short cycles in the state then there will be short cycles in the
LSB of the state.

You're response to that seems confused.  Or else my understanding of
your response is confused.

Subject: Re: OTP using BBS generator?
Date: 10 Aug 2000 01:40:16 -0000
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Message-ID: <20000810014016.17567.qmail@nym.alias.net>
References: <3990A233.8D403CF3@earthlink.net>
Newsgroups: sci.crypt
Lines: 22

Benjamin Goldberg writes:
> With BBS, short cycles occur with low probability, and the system is
> very secure when we don't have a short cycle.  There's no known way to
> detect weather short cycles will occur without explicit testing, but
> explicit testing is trivial.  If a short cycle does occur, the system is
> wide open.

The same reasoning applies to accidentally choosing easy-to-guess primes.
What if you are so unlucky as to choose a prime which exactly matches
the ASCII representation of a Shakespeare sonnet?  Or what if it turns
out to be one more than a power of two?  Or what if p/q happens to be
very close to a simple rational fraction?

The point is, if any of these things happen, the rsa modulus is easy to
factor, with a proper program.  But the chances of any of them happening
are infinitisimal.  And the same is true with choosing a seed that leads
to a short cycle.

Don't forget: if *you* could find a short-cycle seed, so could someone
else.  And if he can, he can break your RSA modulus, and all bets are off.
If you truly think short cycles are a problem, you should conclude that
RSA is not safe.

Subject: Re: OTP using BBS generator?
Date: Sat, 12 Aug 2000 03:54:43 GMT
From: Benjamin Goldberg <goldbb2@earthlink.net>
Message-ID: <39935C9B.F0590173@earthlink.net>
References: <20000810014016.17567.qmail@nym.alias.net>
Newsgroups: sci.crypt
Lines: 76

lcs Mixmaster Remailer wrote:
> 
> Benjamin Goldberg writes:
> > With BBS, short cycles occur with low probability, and the system is
> > very secure when we don't have a short cycle.  There's no known way
> > to detect weather short cycles will occur without explicit testing,
> > but explicit testing is trivial.  If a short cycle does occur, the
> > system is wide open.
> 
> The same reasoning applies to accidentally choosing easy-to-guess
> primes.  What if you are so unlucky as to choose a prime which exactly
> matches the ASCII representation of a Shakespeare sonnet?  Or what if
> it turns out to be one more than a power of two?  Or what if p/q
> happens to be very close to a simple rational fraction?

That's entirely different.  What your describing is like saying "Suppose
I search for my primes by testing each N bit number up to sqrt(pq), in
random order, for being one of the primes, and BY RANDOM CHANCE, I
happen to get it as my guess".  If PQ has some property such as you
describe, it would be non-trivial [*very* difficult] to discover that it
is so.

I'm saying, you've picked some PQ, and some X[0].  The X[i] values go
through a short cycle and repeat.  Perhaps the cycle length is 1, and
the keystream is then either all 0's or all 1's.  If this has occured,
there is 100% chance of it being noticable.

> The point is, if any of these things happen, the rsa modulus is easy
> to factor, with a proper program.  But the chances of any of them
> happening are infinitisimal.  And the same is true with choosing a
> seed that leads to a short cycle.

Erm.  "What if you are so unlucky as to choose a prime which exactly
matches the ASCII representation of a Shakespeare sonnet?"  Sure, I
suppose that it would be easy to find a program that tests for that
specific modulus, and that program would of course already have the
factors.  It's a bit like saying, I've generated X many private
key/public key pairs, and I want to try factor person Z's public key by
testing if it's in my list.  "Or what if it turns out to be one more
than a power of two?"  Supposing PQ is N bits long, you've the same
likelyhood of P or Q happening to be 2^N+1, as you have of finding PQ on
a list of N known products of pairs of big primes.  "Or what if p/q
happens to be very close to a simple rational fraction?"  I don't see
how this would help us factor PQ.

> Don't forget: if *you* could find a short-cycle seed, so could someone
> else.  And if he can, he can break your RSA modulus, and all bets are
> off. If you truly think short cycles are a problem, you should
> conclude that RSA is not safe.

Bzzt! No, BBS is not quite the same as RSA.

Here's a BBS example of a short cycle: P is 23, Q is 47, X[0] is 46. 
X[i+1]=X[i]^2%PQ  The short cycle that occurs is that for X[1] onward,
the value is 1035.  This means [assuming we use the lowest bit] that the
keystream is all 1's, and the plaintext message can be seen by XORing 1
with every bit.  HE'S FOUND THE MESSAGE!

Now suppose we're using RSA, with some P and Q and message M and
encryption exponent E with the same properties as the BBS example:  that
means X[0]=M, X[i+1]=X[i]^E%(PQ) and we've somehow got a message that
degenerates into a short cycle: all X[i] where i>=1 are the same as
X[1].  We've encrypted M, which mean's we've got (and sent) X[1].  Our
opponent might learn that X[2] and X[3] and X[4], etc happen to all be
the same as X[1], but that tells him nothing about X[0].  HE DOESN'T
HAVE THE MESSAGE!

See the difference?  Opponent has message vs. opponent doesn't have
message.  Simple.

--
Galibrath's Law of Human Nature: "Faced with the choice between changing 
one's mind and proving that there is no need to do so, almost everybody
gets busy on the proof."-Vejita/Joel on #afd

Subject: Re: OTP using BBS generator?
Date: Thu, 10 Aug 2000 17:15:22 +0100
From: David Hopwood <hopwood@zetnet.co.uk>
Message-ID: <3992D519.825F2C13@zetnet.co.uk>
References: <3990A233.8D403CF3@earthlink.net>
Newsgroups: sci.crypt
Lines: 152

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

Benjamin Goldberg wrote:
> Bryan Olson wrote:
> [snip]
> > No, in that post David Hopwood got it right:
> >
> > | it has been proven that short cycles happen with negligible
> > | probability, if the parameter sizes are such that factoring
> > | is hard
> >
> > > There is a remarkable lack of desire to address this known weakness,
> > > even though we know how to do that.
> >
> > I take a different view: I think showing the failure happens
> > with negligible probability is a perfectly valid way to
> > address the weakness.
> 
> Suppose we have a block cipher with big keys.  Further suppose that a
> small number of those keys give the identity transformation, and all
> other keys are VERY secure.  Also, suppose that there's no known way to
> find those weak keys without doing a trial encryption, but a trial
> encryption is trivial. Weak keys have low probability, but when they
> occur, the system is wide open.

To be as generous as possible to your argument, let's assume that there
is a proof, under assumptions that are as reasonable as the intractability
of factoring, that there are no other significant weaknesses in the cipher
(if there is no such proof, then this example is clearly not comparable to
BBS).

If the probability of a weak key is low enough to be considered
negligable (the decision as to what is negligable is up to whoever is
applying the security proof), then such a system would be considered
secure in most probabilistic models of security, under the assumption
that keys are selected at random. The system is also secure in practice,
if keys are selected by a good RNG.

So, the conclusions derived from the security model match what we need
in the real world, as well as they can be expected to (and modulo the
possibility of attacks that fall outside most formal security models,
e.g. power analysis, fault analysis, etc.)

There is the issue that keys might not in practice be selected at random,
but that is something that in most cases can be analysed independently of
the cipher.

However, note that some constructions for hashes, etc. based on block
ciphers (e.g. Davies-Meyer), are secure only if very strong assumptions
are made about a cipher's key scheduling; they are insecure when used
with ciphers that have even fairly minor key scheduling weaknesses.
I tend to avoid these constructions entirely - I just don't trust that
the assumptions will be satisfied.

Another important caveat is that if you are put in the position of selecting
a cipher that will be used for a very large range of applications (AES is
an extreme example of this), then it would be a bad idea to select an
algorithm that had weak keys, however unlikely. This is because there's
no way to be sure that the random-key assumption will hold for all
applications that use the cipher.

> With BBS, short cycles occur with low probability, and the system is
> very secure when we don't have a short cycle.  There's no known way to
> detect weather short cycles will occur without explicit testing, but
> explicit testing is trivial.  If a short cycle does occur, the system is
> wide open.
> 
> Does anyone see a similarity?

Yes, of course; they are quite similar cases (with the caveats mentioned
above, and the one below about the cost of testing for weakness).

> Would anyone use the described block cipher without testing for the
> identity transformation? Assume that the identity transformation occurs
> as often as short BBS cycles.

I would, if I was confident that the weak keys weren't a symptom of some
other hidden weakness. If I wasn't confident of that, I probably wouldn't
use the cipher at all.

A practical example is IDEA: this has a set of weak keys that occur with
probability about 2^-96. As it happens I haven't written any applications
for end-users that use IDEA, but if I did, I wouldn't consider it
necessary to check for weak keys.

OTOH, note that testing for an identity permutation is much cheaper and
less complex than testing for short BBS cycles, so it would also be a
reasonable and consistent position to argue for testing in that case, but
against testing cycle length in BBS.

> Personally, I think there exists some kind of further restriction on the
> parameters to BBS which will [provably] eliminate short cycles entirely,
> but we haven't found it yet.

I think that's unlikely, because I can't see any approach to proving the
open question mentioned below. Given that it's 18 years since the BBS
paper was published, probably one of the following is true:

 - not many people have looked at this question (which I doubt given the
   amount of research into bit-security of IFP-based cryptosystems),
 - there is a published proof that I'm not aware of,
 - it is difficult to prove,
 - it is false.

[snip]
> > [Klaus Pommerening]:
> > > | >Is there any known result that some choice of parameters in BBS
> > > | >guarantees that the LSBs don't give short cycles?
> > [Ritter:]
> > > |Not that I know of.  I never even thought of investigating such a
> > > |thing on my small models.  I guess I assumed that sort of thing
> > > |was exactly what the proofs guaranteed.
> >
> > Yes, exactly the kind of thing I've pointed out both before
> > and after that post: the long cycle filter doesn't imply
> > there's no case in which particular parameters fail (though I
> > don't know if this kind of failure is possible).  But why,
> > after reading the paper, citing the paper, and accusing
> > everyone else of not reading the whole paper, were you still
> > _assuming_ what the proofs guaranteed?
> 
> What it seems that Ritter is saying is that he's assuming that if there
> are no short cycles in the state then there will be [no??] short cycles
> in the LSB of the state.

Well, the BBS paper is quite clear about what the state of public knowledge
on this was in 1982 - it's posed as an open question just after Theorem 10
(and AFAIK it is still an open question).

- -- 
David Hopwood <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

iQEVAwUBOZLTZTkCAxeYt5gVAQGxJAgAuLCoUTitQOxGAJzK76iBt03jqUI7XLN1
iyDwV2zgLDSBZ97cgHo4R/lR9vGi6FhvLx5olkixYRg9s1JHt/dJOG38yzHdiOc7
0R4IMOcFZXpENtevDBoJEUTm3+9stGK30ablyeXRj8IuSFeGO0goAXK6FqKlt4jK
MYDfiJ/KY59yq8vCLe9wMTv5erP6fA3KWUcCX2no7O5DwUeL25YbaTzqpzzoYKLo
aF1P+h6ak7Ve6DB/69awjMTTx9dGr78Mi5T9oB6udgGyFfDFdCAotJ9qgbG3oac1
CX6cj4kuurIPzJMLzYCvOIIs0vejPVCWf+gkqLqH39G6+FmFV+kPcA==
=cVB+
-----END PGP SIGNATURE-----

Subject: Re: OTP using BBS generator?
Date: 12 Aug 2000 07:20:02 -0000
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Message-ID: <20000812072002.17618.qmail@nym.alias.net>
References: <3990A233.8D403CF3@earthlink.net>
Newsgroups: sci.crypt
Lines: 28

Benjamin Goldberg writes:
> Here's a BBS example of a short cycle: P is 23, Q is 47, X[0] is 46. 
> X[i+1]=X[i]^2%PQ  The short cycle that occurs is that for X[1] onward,
> the value is 1035.  This means [assuming we use the lowest bit] that the
> keystream is all 1's, and the plaintext message can be seen by XORing 1
> with every bit.  HE'S FOUND THE MESSAGE!
>
> Now suppose we're using RSA, with some P and Q and message M and
> encryption exponent E with the same properties as the BBS example:  that
> means X[0]=M, X[i+1]=X[i]^E%(PQ) and we've somehow got a message that
> degenerates into a short cycle: all X[i] where i>=1 are the same as
> X[1].  We've encrypted M, which mean's we've got (and sent) X[1].  Our
> opponent might learn that X[2] and X[3] and X[4], etc happen to all be
> the same as X[1], but that tells him nothing about X[0].  HE DOESN'T
> HAVE THE MESSAGE!

If you can find short cycles, you can factor the value.  You have
x^2 = y^2 mod n, so (x^2 - y^2) = 0 mod n, so (x-y)(x+y) is a multiple
of n, and if you take the gcd of x-y and/or x+y with n you have a good
chance of finding a factor.

In your example, you have that 46*46 = 1035*1035 = 1035, mod 1081.
Now we can do the gcd of the modulus with 1035-46.  gcd(1081,989) = 23,
which is one of the factors!  We've factored the modulus.

In general, if you can find short cycles, you can factor.  Hence if you
believe factoring is hard, you believe that short cycles can't be found.
That's the bottom line.

Subject: Re: OTP using BBS generator?
Date: Mon, 14 Aug 2000 21:18:59 GMT
From: Benjamin Goldberg <goldbb2@earthlink.net>
Message-ID: <39986246.48CD65C0@earthlink.net>
References: <20000812072002.17618.qmail@nym.alias.net>
Newsgroups: sci.crypt
Lines: 34

lcs Mixmaster Remailer wrote:
> 
[snip]
> 
> If you can find short cycles, you can factor the value.  You have
> x^2 = y^2 mod n, so (x^2 - y^2) = 0 mod n, so (x-y)(x+y) is a multiple
> of n, and if you take the gcd of x-y and/or x+y with n you have a good
> chance of finding a factor.
> 
> In your example, you have that 46*46 = 1035*1035 = 103

Proof and Strength in the BB&S RNG

Terry Ritter

A Ciphers By Ritter Page

The BB&S RNG

Security and Proof

Contents