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
In
eachus@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