Path: illuminati.io.com!uunet!MathWorks.Com!europa.eng.gtefsd.com!howland.reston .ans.net!cs.utexas.edu!not-for-mail From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Re: Random/Pseudo Random Number Generator Date: 18 Jun 1994 14:09:22 -0500 Organization: UTexas Mail-to-News Gateway Lines: 194 Sender: nobody@cs.utexas.edu Message-ID: <199406181908.OAA18085@indial1.io.com> NNTP-Posting-Host: news.cs.utexas.edu Ineachus@spectre.mitre.org (Robert I. Eachus) writes: > AFAIK the only algorithmic RNG that can be considered secure and has >reasonable performance is Blum, Blum, and Shub. Fine. Let's talk about Blum, Blum, and Shub [1]: It is interesting to see a BB&S RNG described by the phrase "reasonable performance," in the light of Section 8 (Lengths of periods (of the sequences produced by the X**2 mod N generator)) of the BB&S paper. The BB&S generator differs from the usual Linear Feedback Shift Register (LFSR) or Linear Congruential designs in that a BB&S system does not create a single major cycle of known length. (A "cycle" is a sequence of RNG states which repeat.) Instead, a BB&S system creates cycles of various lengths, including degenerate (zero-length) cycles and other cycles which are much shorter than one might expect. (I give some examples in my 1991 article [2]). In Section 8 of the BB&S article, N = 23*47 is specifically given as an example of "a special number of the prescribed form." 23*47 = 1081, so this is the number of possible states. Evaluation of this system finds four degenerate cycles, a minimum (non-degenerate) cycle length of 10, a maximum of 110, and an average of 24. In particular, X0 = 46 is degenerate, X0 = 47 is degenerate, X0 = 48 is on a 10-state cycle, and X0 = 24 is on an 11-state cycle. There are two 10-state cycles, four 11-state cycles, and two 110-state cycles. Thus, a BB&S generator cannot be initialized with random state, because this state may happen to be on a short cycle. If this were allowed, the resulting sequence would become "predictable" as soon as the cycle started to repeat. This is prevented in a *real* BB&S design by mathematical proof showing that such a design will have a long cycle of a predictable length (given certain strenuous conditions on N), *and* by using the algorithm in Section 9 (Algorithms for determining length of period and random accessing) to show that an initial state (X0) is on such a cycle. In practice, the initial RNG state or "seed" must be constructed from the cryptographic key, and then checked to see that it is on a cycle of the desired length (it being much faster to check for a particular length than it would be to measure arbitrary length). (In a real system the state will be a very large multi-precision integer.) If the seed is on a cycle of the desired length, it must be changed and checked again. Some substantial effort is required to find a valid seed, especially when compared to designs where this sort of thing is unnecessary. And this effort is required every time a BB&S RNG is re-initialized. Now, one might argue that the really short and dangerous cycles are rare and can be ignored, but, as far as I know, there is no math to support statements about the probability of short cycles in this specific construction. But in any case, the *entire reason* for using the BB&S RNG (which is otherwise rather slow, being an n**2 computation in terms of state-size) is that it has *provable* strength. And if the initial seed is not specially selected, the proof will not hold. It may be possible to save the current RNG state, and then use "random accessing" as a message key, but the system will still be substantially slower in execution than other alternatives. Note that, in the above example, the best we can hope to do is access about 1/10 of the possible states (one long cycle), with an RNG step operation (integer multiply and modulo divide) of n**2 complexity which must support the full state size. We can thus argue that such a generator takes perhaps 100 times the effort that we might expect for the cycle length actually delivered. It appears from my experiments [2:120] that about 3/4 of the BB&S values are "arc states," which join some cycle in a single step. None of these states can occur once the RNG is operating, yet they contribute an overhead to a large value which must be computed. And we have yet to discuss the computational effort required to form N itself: The primary BB&S requirement for N = P * Q is that P and Q each be primes congruent to 3 mod 4. This is exceedingly easy. But to guarantee a particular cycle length (Section 8, Theorem 6), there are two more Conditions [1:378]. Condition 1 defines that a prime is "special" if P = 2*P1 + 1, and P1 = 2*P2 + 1, where P1 and P2 are odd primes. Both P and Q are required to be "special." Finding a valid special primes P and Q is not easy. Condition 2 is somewhat more complex, and only rules out one choice in four, but must be computed anyway if we are to have a real BB&S design. Again, we can choose not to have a guaranteed cycle length, but if so, we do not have a BB&S design, and the result will not be proven to be "unpredictable." In which case, why would we use it? Presumably, the selection of N would be made off-line, but is very expensive nevertheless. >You could probably >build a reasonable RNG out of RSA or Diffe-Helmann but I don't know of >one. Various generators based on DES or digest algorithms are either >too slow, known to be breakable, or on shaky theoretical ground. If firm theoretical results were required for cryptography, we would all be using one-time pads. No other cipher is generally-accepted as provably secure. So why are we not all using one-time pads? Modern stream-cipher RNG's are typically much faster than DES, and are often favorably compared to DES in terms of expected strength. But strength is not necessarily the ultimate requirement: Speed is surprisingly important to the ordinary business use of cryptography, because real cryptography is overhead. If the effort involved in cryptography exceeds real losses, many businesses will ask why it should be used. And very few businesses have the rest of their operations run with security comparable to a serious stream cipher. Ciphers alone cannot guarantee security, and a real cipher need only be substantially more effort to break than the easiest other way to gain the same information. Attacking ciphertext is usually expensive and time-consuming, making it generally the method of last resort. Why not try bribery, wiretaps, bugging, theft, or coercion first? A modern stream-cipher design need not rely as heavily on a strong RNG as older designs, but instead may use reversible nonlinear combiners (of which my own Dynamic Substitution is a major design). The use of nonlinear data combiners also supports multiple levels of combining, something which is almost useless when using linear additive combiners. Nonlinear combiners also provide far more protection for the RNG than additive combiners, which inherently reveal an RNG byte for every known-plaintext pair. This weakness is present in stream ciphers with additive combiners, but is not characteristic of stream ciphers as a class. A fast linear RNG makes a fine cryptographic confusion generator, *provided* that the sequence is isolated and "nonlinearized" before it is used, *and* that the cipher design is inherently resistant to known-plaintext attack. It is not necessary to discard linear designs, provided they are properly used. Frankly, discussion of a need for theoretical strength would make more sense in the context of the "details" which make theoretically- strong systems weak in practice. For example, consider the wide use of PGP, which requires that public keys be *certified* before theoretical strength can be achieved. If we assume both RSA and IDEA to be absolutely secure, key-certification is the remaining limit on the strength of the system, and a very low limit it is. Yet who bothers to validate the keys they use? In light of this, why would we consider "strength" (including theoretical strength) to be a major factor in practical cryptography? Why not set up an informant to distribute spoofed public keys, and then set up the network to re-route e-mail between the desired parties to a nationwide spoofing center? This would be easy, white-collar intelligence, perhaps arguably legal, if the owner of a private system carrying the e-mail "approves" such monitoring. We don't hear much said about the issue of the widespread weak use of PGP. But this is probably because most people will only use cryptography to the extent that it represents easy security. When informed that real security will take some effort, they say "Why bother?" Or, "It can't happen to me!" Or (my favorite) "Since it uses RSA, it must be secure; just study some number theory!" Alas, "easy security" is an oxymoron. References: 1. Blum, L., M. Blum & M. Shub. 1986. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing. 15(2): 364-384. 2. Ritter, T. 1991. The Efficient Generation of Cryptographic Confusion Sequences. Cryptologia. 15(2): 81-139. --- Terry Ritter ritter@io.com