# Proof and Strength in the BB&S RNG

## 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: Xi+1 := Xi2 mod N, (or X[i+1] := X[i]**2 mod N). This defines a mathematical system which always has multiple cycles, some of which will be shorter than the longest cycles, while others will be degenerate cycles with constant values. Choosing an initial X[0] thus chooses a particular cycle within the RNG (including, with very low probability, short and degenerate cycles) and thus a sequence of X values. The value reported out of the RNG is the least-significant bit (LSb) of X. Typically BB&S would be the RNG part of a conventional stream cipher. Any stream cipher confusion sequence which repeats in practice is appallingly weak, because -- after the first pass through the cycle -- it is absolutely predictable.

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

### Contents

• 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>
<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/

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/

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),
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: <3988EC4E.9555D120@supreme-overlord.com>
Newsgroups: sci.crypt
Lines: 49

The difference lies in the requirements for a OTP. 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.

Take your favorite keyed pRNG, with a key of size k. Now let's startg the
examination under the best assumptions for the generator. Obviously for the
first bit the generator is good, after all there are k bits of entropy and
only 1 bit of pad generated. For each bit n generated, it also must consume
1 bit of entropy from the pool, so the total entropy used by getting to that
bit is n. When n=k, we have reached the limit of the key, and by encrypting
just 1 more bit we violate the rule for OTP that I gave above. That is why a
pRNG can't be used for a OTP, it's entropy pool is not infinite, so n > k is
unavoidable. Now the requirements for a stream cipher are different, and BBS
may be usable for that.
Joe

"Grant Anderson" <grant_anderson@supreme-overlord.com> wrote in message
news:3988EC4E.9555D120@supreme-overlord.com...
> 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.
>
>



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

Last updated: 2001-06-12