SecureRandom policies and mechanisms

IMPORTANT: anyone writing a security provider that implements a SecureRandom algorithm should read this section in full.

The organisation of this section is somewhat different from other categories of algorithms defined by SCAN. Many of the algorithms in other categories are deterministic, and even those that are not, have a specification that allows comparison with fixed test vectors (for example, a probabilistic signature algorithm still produces a deterministic result from signature verification, and the signatures must be generated according to an algorithm that ensures that they verify correctly).

Random number generators, on the other hand, are always non-deterministic. In fact, since the application should not rely on the output of a SecureRandom object being reproducible, it is not strictly necessary for a SecureRandom name to map to a specific algorithm.

With this in mind, there are two ways to approach naming of RNGs:

  1. Define names that correspond to particular applications or requirements for a random source. For example, "KeyGeneration" could specify a high-grade, conservatively designed source of random bytes suitable for generating long-term private keys. A provider can map the name "KeyGeneration" to any RNG that is believed to satisfy this requirement.
  2. Define names that correspond to ways of implementing a random source. For example, "URandom" could specify that the output is taken from the underlying operating system's /dev/urandom device, if present. In this case it would be incorrect to implement "URandom" in any other way, even if the alternative is believed to be at least as secure, and to perform at least as well as /dev/urandom in all respects.
Approach 1 (the "Policy" approach), has the advantage that the mechanism to be used can be tailored to the available resources. If a security flaw is found, it can be updated by changing how the policy is implemented, without disturbing or requiring any changes to applications. The flip side of this is that it may be more difficult to analyse whether an application that chooses some policy actually achieves the required randomness properties, because the policy may be implemented differently depending on the JVM, OS, and/or hardware platform, which security providers are installed (and in which order), or the mappings in various provider configuration files.

[[most of the "policy" entries have not been filled in yet.]]

Approach 2 (the "Mechanism" approach), has the advantage that an application writer knows precisely which algorithm will be used. Also, if a security flaw is found in a mechanism, it is known precisely which applications the flaw affects. However, if a security flaw is found in an algorithm, any applications will have to change which algorithm they use, rather than simply changing to a later version of a security provider.

Note that the policy approach does not have to be as loosely defined as suggested above. For example, a policy could be "use mechanism X if available, and mechanism Y otherwise, unless this is changed in a future version of SCAN". This provides most of the flexibility of an approach based purely on requirements, and allows "security fixes" if necessary, while avoiding most of the problems of attempting to analyse an unknown or moving target.

The names we define below include both policies and mechanisms. One way of implementing a mapping between them is to have each policy name as an alias for a mechanism.

Some excellent general papers on cryptanalysis of RNGs are:


[[the following Java-specific discussion should go somewhere else]]

For the Java mapping of SCAN, there is a "default" SecureRandom algorithm, which an application can obtain by instantiating the SecureRandom class directly (i.e. as "new SecureRandom()"). In JDK 1.2 and 1.3, there is a serious design flaw in the way this is mapped to a SecureRandom implementation: the providers are searched in preference order, and for the first that implements one or more SecureRandom algorithms, one of those algorithms is picked effectively at random, and used as the default. (In fact the "first" key starting with "SecureRandom." is used, but because of the way provider properties are stored using a hashtable, this does not necessarily correspond to the first property that was listed in a .properties file or added using the Provider.put method.)

In order to work around this design bug, I recommend the following:

If a provider implements a SecureRandom algorithm and does not use the above workaround, it MUST use some other method of avoiding this bug.

In any case, it is recommended that new applications instantiate a SecureRandom by name.


Default SecureRandom Policy
Description:
This name should be given to the default SecureRandom policy of a given provider (if any), in addition to specifying it as the value of the "SecureRandom" property.

Although there is no way to enforce this constraint, choices for default SecureRandom algorithms should be believed to be at least as conservative as "SHA1PRNG", which was the default algorithm in JDK 1.1.



! BBS SecureRandom Mechanism
Designers:
L. Blum, Manuel Blum, M. Shub
Alias:
"Blum-Blum-Shub"
Missing information:
Need to say how to derive x, and how updating of the seed is handled.
References:
Parameters:
Security comment:
The security of this PRNG depends on the complexity of factoring the parameter n.


DevRandom SecureRandom Mechanism
Designers:
(of /dev/random) Theodore Ts'o, Phil Karn, Colin Plumb, Dale Worley
Description:
This algorithm obtains bytes from the device driver /dev/random originally designed for Linux, or the direct equivalent in other operating systems. /dev/urandom obtains entropy from various hardware events accessible to the OS kernel. It does not block when more bytes are requested than are directly obtainable from the hardware; instead, the available entropy is processed through a cryptographic PRNG, which in the case of the Linux implementation is constructed from a hash function.

If the operating system does not provide a suitable device, or if it cannot be opened, the provider MUST throw NoSuchAlgorithmException from the algorithm class constructor.

References:
Comments:


URandom SecureRandom Mechanism
Designers:
(of /dev/random) Theodore Ts'o, Phil Karn, Colin Plumb, Dale Worley
Description:
This algorithm obtains bytes from the device driver /dev/urandom originally designed for Linux, or the direct equivalent in other operating systems. /dev/urandom obtains entropy from various hardware events accessible to the OS kernel. It does not block when more bytes are requested than are directly obtainable from the hardware; instead, the available entropy is processed through a cryptographic PRNG, which in the case of the Linux implementation is constructed from a hash function.

If the operating system does not provide a suitable device, or if it cannot be opened, the provider MUST throw NoSuchAlgorithmException from the algorithm class constructor.

References:
[see references for DevRandom]
Comments:
Security comment:
At the time of writing, /dev/urandom does not ensure that a minimum amount of entropy has been collected before starting to produce output. To work around this, it is strongly recommended that implementations read 32 bytes from /dev/random, blocking as necessary and discarding the result, before reading from /dev/urandom. This need only be done once (for example in a static initialiser).
[[REMIND: check that this is actually sufficient.]]


WiderWake4+1 SecureRandom Mechanism
Description:
A fast RNG based on the stream cipher WiderWake4+1. The byte order may be whatever is convenient.

This is intended to be a fast PRNG that produces uniformly distributed output.

Reseeding is achieved by hashing the input seed with SHA-1, and XORing the result into the feedback variables (using whatever byte order is convenient).

Alias:
"WiderWake41" (use for identifiers)
Security comment:
WiderWake has not received a great deal of analysis, and therefore it might not be a good choice for a conservative RNG. However, it is very fast in software.


! SHA1PRNG SecureRandom Mechanism
Description:
This is the algorithm that was implemented by the SecureRandom class in JDK 1.1. It is similar (but not identical) to the random number generator suggested in Annex D of IEEE Std 1363-2000.
Missing information:
Need full description.
References:

Valid HTML 4.0 Valid CSS Copyright and trademarks