privately, an adversary who can observe either of the public keys and
knows the modulus being used need only search through the space of
the other secret key in order to be able to calculate the shared
secret [D-H]. So, conservatively, it would be best to consider
public Diffie-Hellman to produce a quantity whose guessability
corresponds to the worse of the two inputs. Because of this and the
fact that Diffie-Hellman is computationally intensive, its use as a
mixing function is not recommended.
5.5. Using a Mixing Function to Stretch Random Bits
Although it is not necessary for a mixing function to produce the
same or fewer output bits than its inputs, mixing bits cannot
"stretch" the amount of random unpredictability present in the
inputs. Thus, four inputs of 32 bits each, in which there are 12
bits worth of unpredictability (such as 4,096 equally probable
values) in each input, cannot produce more than 48 bits worth of
unpredictable output. The output can be expanded to hundreds or
thousands of bits by, for example, mixing with successive integers,
but the clever adversary’s search space is still 2^48 possibilities.
Furthermore, mixing to fewer bits than are input will tend to
strengthen the randomness of the output.
The last table in Section 5.1 shows that mixing a random bit with a
constant bit with Exclusive Or will produce a random bit. While this
is true, it does not provide a way to "stretch" one random bit into
more than one. If, for example, a random bit is mixed with a 0 and
then with a 1, this produces a two bit sequence but it will always be
either 01 or 10. Since there are only two possible values, there is
still only the one bit of original randomness.
5.6. Other Factors in Choosing a Mixing Function
For local use, AES has the advantages that it has been widely tested
for flaws, is reasonably efficient in software, and is widely
documented and implemented with hardware and software implementations
available all over the world including open source code. The SHA*
family have had a little less study and tend to require more CPU
cycles than AES but there is no reason to believe they are flawed.
Both SHA* and MD5 were derived from the earlier MD4 algorithm. They
all have source code available [SHA*, MD4, MD5]. Some signs of
weakness have been found in MD4 and MD5. In particular, MD4 has only
three rounds and there are several independent breaks of the first
two or last two rounds. And some collisions have been found in MD5
output.
AES was selected by a robust, public, and international process. It
and SHA* have been vouched for by the US National Security Agency
(NSA) on the basis of criteria that mostly remain secret, as was DES.
While this has been the cause of much speculation and doubt,
investigation of DES over the years has indicated that NSA
involvement in modifications to its design, which originated with
IBM, was primarily to strengthen it. There has been no announcement
of a concealed or special weakness being found in DES. It is likely
that the NSA modifications to MD4 to produce the SHA algorithms
similarly strengthened these algorithms, possibly against threats not
yet known in the public cryptographic community.
Where input lengths are unpredictable, hash algorithms are more
convenient to use than block encryption algorithms since they are
generally designed to accept variable length inputs. Block
encryption algorithms generally require an additional padding
algorithm to accommodate inputs that are not an even multiple of the
block size.
As of the time of this document, the authors know of no patent claims
to the basic AES, DES, SHA*, MD4, and MD5 algorithms other than
patents for which an irrevocable royalty free license has been
granted to the world. There may, of course, be essential patents of
which the authors are unaware or patents on implementations or uses
or other relevant patents issued or to be issued.
6. Pseudo-random Number Generators
When a seed has sufficient entropy, from input as described in
Section 3 and possibly de-skewed and mixed as described in Sections 4
and 5, one can algorithmically extend that seed to produce a large
number of cryptographically-strong random quantities. Such
algorithms are platform independent and can operate in the same
fashion on any computer. For the algorithms to be secure, their
input and internal workings must be protected from adversarial
observation.
The design of such pseudo-random number generation algorithms, like
the design of symmetric encryption algorithms, is not a task for
amateurs. Section 6.1 below lists a number of bad ideas that failed
algorithms have used. To learn what works, skip Section 6.1 and just
read the remainder of this section and Section 7, which describes and
references some standard pseudo random number generation algorithms.
See Section 7 and Part 3 of [X9.82].
6.1. Some Bad Ideas
The subsections below describe a number of ideas that might seem
reasonable but that lead to insecure pseudo-random number generation.
6.1.1. The Fallacy of Complex Manipulation
One approach that may give a misleading appearance of
unpredictability is to take a very complex algorithm (or an excellent
traditional pseudo-random number generator with good statistical
properties) and to calculate a cryptographic key by starting with
limited data such as the computer system clock value as the seed.
Adversaries who knew roughly when the generator was started would
have a relatively small number of seed values to test, as they would
know likely values of the system clock. Large numbers of pseudo-
random bits could be generated, but the search space that an
adversary would need to check could be quite small.
Thus, very strong or complex manipulation of data will not help if
the adversary can learn what the manipulation is and if there is not
enough entropy in the starting seed value. They can usually use the
limited number of results stemming from a limited number of seed
values to defeat security.
Another serious strategic error is to assume that a very complex
pseudo-random number generation algorithm will produce strong random
numbers, when there has been no theory behind or analysis of the
algorithm. There is a excellent example of this fallacy near the
beginning of Chapter 3 in [KNUTH], where the author describes a
complex algorithm. It was intended that the machine language program
corresponding to the algorithm would be so complicated that a person
trying to read the code without comments wouldn’t know what the
program was doing. Unfortunately, actual use of this algorithm
showed that it almost immediately converged to a single repeated
value in one case and a small cycle of values in another case.
Not only does complex manipulation not help you if you have a limited
range of seeds, but blindly-chosen complex manipulation can destroy
the entropy in a good seed!
6.1.2. The Fallacy of Selection from a Large Database
Another approach that can give a misleading appearance of
unpredictability is to randomly select a quantity from a database and
to assume that its strength is related to the total number of bits in
the database. For example, typical USENET servers process many
megabytes of information per day [USENET_1, USENET_2]. Assume that a
random quantity was selected by fetching 32 bytes of data from a
random starting point in this data. This does not yield 32*8 = 256
bits worth of unguessability. Even if much of the data is human
language that contains no more than 2 or 3 bits of information per
byte, it doesn’t yield 32*2 = 64 bits of unguessability. For an
adversary with access to the same Usenet database, the unguessability
rests only on the starting point of the selection. That is perhaps a
little over a couple of dozen bits of unguessability.
The same argument applies to selecting sequences from the data on a
publicly available CD/DVD recording or any other large public
database. If the adversary has access to the same database, this
"selection from a large volume of data" step buys little. However,
if a selection can be made from data to which the adversary has no
access, such as system buffers on an active multi-user system, it may
be of help.
6.1.3. Traditional Pseudo-random Sequences
This section talks about traditional sources of deterministic or
"pseudo-random" numbers. These typically start with a "seed"
quantity and use simple numeric or logical operations to produce a
sequence of values. Note that none of the techniques discussed in
this section is suitable for cryptographic use. They are presented
for general information.
[KNUTH] has a classic exposition on pseudo-random numbers.
Applications he mentions are simulations of natural phenomena,
sampling, numerical analysis, testing computer programs, decision
making, and games. None of these have the same characteristics as
the sorts of security uses we are talking about. Only in the last
two could there be an adversary trying to find the random quantity.
However, in these cases, the adversary normally has only a single
chance to use a guessed value. In guessing passwords or attempting
to break an encryption scheme, the adversary normally has many,
perhaps unlimited, chances at guessing the correct value. Sometimes
the adversary can store the message to be broken and repeatedly
attack it. Adversaries are also be assumed to be aided by a
computer.
For testing the "randomness" of numbers, Knuth suggests a variety of
measures, including statistical and spectral. These tests check
things like autocorrelation between different parts of a "random"
sequence or distribution of its values. But these tests could be met
by a constant stored random sequence, such as the "random" sequence
printed in the CRC Standard Mathematical Tables [CRC]. Despite
meeting all the tests suggested by Knuth, that sequence is unsuitable
for cryptographic us, as adversaries must be assumed to have copies
of all commonly published "random" sequences and to be able to spot
the source and predict future values.
A typical pseudo-random number generation technique is the linear
congruence pseudo-random number generator. This technique uses
modular arithmetic, where the value numbered N+1 is calculated from
the value numbered N by
V = ( V * a + b )(Mod c)
N+1 N
The above technique has a strong relationship to linear shift
register pseudo-random number generators, which are well understood
cryptographically [SHIFT*]. In such generators, bits are introduced
at one end of a shift register as the Exclusive Or (binary sum
without carry) of bits from selected fixed taps into the register.
For example, consider the following:
+----+ +----+ +----+ +----+
| B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+
| 0 | | 1 | | 2 | | n | |
+----+ +----+ +----+ +----+ |
| | | |
| | V +-----+
| V +----------------> | |
V +-----------------------------> | XOR |
+---------------------------------------------------> | |
+-----+
V = ( ( V * 2 ) + B XOR B ... )(Mod 2^n)
N+1 N 0 2
The quality of traditional pseudo-random number generator algorithms
is measured by statistical tests on such sequences. Carefully-chosen
values a, b, c, and initial V or carefully-chosen placement of the
shift register tap in the above simple process can produce excellent
statistics.
These sequences may be adequate in simulations (Monte Carlo
experiments) as long as the sequence is orthogonal to the structure
of the space being explored. Even there, subtle patterns may cause
problems. However, such sequences are clearly bad for use in
security applications. They are fully predictable if the initial
state is known. Depending on the form of the pseudo-random number
generator, the sequence may be determinable from observation of a
short portion of the sequence [SCHNEIER, STERN]. For example, with
the generators above, one can determine V(n+1) given knowledge of
V(n). In fact, it has been shown that with these techniques, even if
only one bit of the pseudo-random values are released, the seed can
be determined from short sequences.
Not only have linear congruent generators been broken, but techniques
are now known for breaking all polynomial congruent generators
[KRAWCZYK].
6.2. Cryptographically Strong Sequences
In cases where a series of random quantities must be generated, an
adversary may learn some values in the sequence. In general,
adversaries should not be able to predict other values from the ones
that they know.
The correct technique is to start with a strong random seed, to take
cryptographically strong steps from that seed [FERGUSON, SCHNEIER],
and not to reveal the complete state of the generator in the sequence
elements. If each value in the sequence can be calculated in a fixed
way from the previous value, then when any value is compromised, all
future values can be determined. This would be the case, for
example, if each value were a constant function of the previously
used values, even if the function were a very strong, non-invertible
message digest function.
(Note that if a technique for generating a sequence of key values is
fast enough, it can trivially be used as the basis for a
confidentiality system. If two parties use the same sequence
generation technique and start with the same seed material, they will
generate identical sequences. These could, for example, be XOR’ed at
one end with data being sent to encrypt it, and XOR’ed with this data
as received to decrypt it, due to the reversible properties of the
XOR operation. This is commonly referred to as a simple stream
cipher.)
6.2.1. OFB and CTR Sequences
One way to produce a strong sequence is to take a seed value and hash
the quantities produced by concatenating the seed with successive
integers, or the like, and then to mask the values obtained so as to
limit the amount of generator state available to the adversary.
It may also be possible to use an "encryption" algorithm with a
random key and seed value to encrypt successive integers, as in
counter (CTR) mode encryption. Alternatively, one can feedback all
of the output value from encryption into the value to be encrypted
for the next iteration. This is a particular example of output
feedback mode (OFB) [MODES].
An example is shown below in which shifting and masking are used to
combine part of the output feedback with part of the old input. This
type of partial feedback should be avoided for reasons described
below.
+---------------+
| V |
| | n |--+
+--+------------+ |
| | +---------+
shift| +---> | | +-----+
+--+ | Encrypt | <--- | Key |
| +-------- | | +-----+
| | +---------+
V V
+------------+--+
| V | |
| n+1 |
+---------------+
Note that if a shift of one is used, this is the same as the shift
register technique described in Section 6.1.3, but with the all-
important difference that the feedback is determined by a complex
non-linear function of all bits rather than by a simple linear or
polynomial combination of output from a few bit position taps.
Donald W. Davies showed that this sort of shifted partial output
feedback significantly weakens an algorithm, compared to feeding all
the output bits back as input. In particular, for DES, repeatedly
encrypting a full 64-bit quantity will give an expected repeat in
about 2^63 iterations. Feeding back anything less than 64 (and more
than 0) bits will give an expected repeat in between 2^31 and 2^32
iterations!
To predict values of a sequence from others when the sequence was
generated by these techniques is equivalent to breaking the
cryptosystem or to inverting the "non-invertible" hashing with only
partial information available. The less information revealed in each
iteration, the harder it will be for an adversary to predict the
sequence. Thus it is best to use only one bit from each value. It
has been shown that in some cases this makes it impossible to break a
system even when the cryptographic system is invertible and could be
broken if all of each generated value were revealed.
6.2.2. The Blum Blum Shub Sequence Generator
Currently the generator which has the strongest public proof of
strength is called the Blum Blum Shub generator, named after its
inventors [BBS]. It is also very simple and is based on quadratic
residues. Its only disadvantage is that it is computationally
intensive compared to the traditional techniques given in Section
6.1.3. This is not a major drawback if it is used for moderately-
infrequent purposes, such as generating session keys.
Simply choose two large prime numbers (say, p and q) that each gives
a remainder of 3 when divided by 4. Let n = p * q. Then choose a
random number, x, that is relatively prime to n. The initial seed
for the generator and the method for calculating subsequent values
are then:
2
s = ( x )(Mod n)
0
2
s = ( s )(Mod n)
i+1 i
Be careful to use only a few bits from the bottom of each s. It is
always safe to use only the lowest-order bit. If one uses no more
than the:
log ( log ( s ) )
2 2 i
low-order bits, then predicting any additional bits from a sequence
generated in this manner is provably as hard as factoring n. As long
as the initial x is secret, n can be made public if desired.
An interesting characteristic of this generator is that any of the s
values can be directly calculated. In particular,
( (2^i) (Mod ((p-1)*(q-1)) ) )
s = ( s )(Mod n)
i 0
This means that in applications where many keys are generated in this
fashion, it is not necessary to save them all. Each key can be
effectively indexed and recovered from that small index and the
initial s and n.
6.3. Entropy Pool Techniques
Many modern pseudo-random number sources, such as those described in
Sections 7.1.2 and 7.1.3 utilize the technique of maintaining a
"pool" of bits and providing operations for strongly mixing input
with some randomness into the pool and extracting pseudo-random bits
from the pool. This is illustrated in the figure below.
+--------+ +------+ +---------+
--->| Mix In |--->| POOL |--->| Extract |--->
| Bits | | | | Bits |
+--------+ +------+ +---------+
^ V
| |
+-----------+
Bits to be fed into the pool can come from any of the various
hardware, environmental, or user input sources discussed above. It
is also common to save the state of the pool on system shutdown and
to restore it on re-starting, when stable storage is available.
Care must be taken that enough entropy has been added to the pool to
support particular output uses desired. See [RSA_BULL1] for similar
suggestions.
7. Randomness Generation Examples and Standards
Several public standards and widely deployed examples are now in
place for the generation of keys or other cryptographically random
quantities. Some, in section 7.1, include an entropy source.
Others, described in section 7.2, provide the pseudo-random number
strong-sequence generator but assume the input of a random seed or
input from a source of entropy.
7.1. Complete Randomness Generators
Three standards are described below. The two older standards use
DES, with its 64-bit block and key size limit, but any equally strong
or stronger mixing function could be substituted [DES]. The third is
a more modern and stronger standard based on SHA-1 [SHA*]. Lastly,
the widely deployed modern UNIX and Windows random number generators
are described.
7.1.1. US DoD Recommendations for Password Generation
The United States Department of Defense has specific recommendations
for password generation [DoD]. It suggests using the US Data
Encryption Standard [DES] in Output Feedback Mode [MODES] as follows:
Use an initialization vector determined from
the system clock,
system ID,
user ID, and
date and time;
use a key determined from
system interrupt registers,
system status registers, and
system counters; and,
as plain text, use an external randomly generated 64-bit
quantity such as the ASCII bytes for 8 characters typed
in by a system administrator.
The password can then be calculated from the 64 bit "cipher text"
generated by DES in 64-bit Output Feedback Mode. As many bits as are
needed can be taken from these 64 bits and expanded into a
pronounceable word, phrase, or other format if a human being needs to
remember the password.
7.1.2. The /dev/random Device
Several versions of the UNIX operating system provide a kernel-
resident random number generator. Some of these generators use
events captured by the Kernel during normal system operation.