From: (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
Message-ID: <>

 In (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

      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

 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.


 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