org.hd.d.efs
Class EntropyPool

java.lang.Object
  extended by java.util.Random
      extended by java.security.SecureRandom
          extended by org.hd.d.efs.EntropyPool
All Implemented Interfaces:
java.io.Serializable

public final class EntropyPool
extends java.security.SecureRandom

Manages a pool of truly random bits, hopefully cryptographically secure. This can be directly used as a SecureRandom number generator as well as managing the underlying pool of bits, and should be at least as good (ie cryptographically safe, spectrally-pure, etc) a source of bits as its `guarantor' SecureRandom generator, since every setSeed() passes its values to both the pool and the underlying generator, and every output (which ultimately comes from nextBytes()) is XORed byte-for-byte with nextBytes() output from the guarantor generator. (A little of the input to addEntropy() is used to prod the guarantor from time to time, but no bits marked as carrying entropy are themselves fed to the guarantor generator, in case it leaks bits to the outside world.)

This pool is designed to be chaotic so that a single bit difference in the seed injected into two pool instances, even if the environment, system clock, etc, is identical for those instances, should change on average half the output bits of every subsequent byte drawn from the pool.

Full internal seeding is deferred until first needed, and calling setSeed() before extracting bits from the pool will not have EntropyPool avoid loading its own seed bits anyway.

This class follows the general contract of SecureRandom in that adding a seed can only increase the ``randomness'' in the generator, not reset its state.

This relies to some extent on the default SecureRandom implementation to try to guarantee a minimum level of entropy at start-up. If you provide good external entropy, however, the significance of that dependency rapidly diminishes. If you supply a guarantor, its seed-bit (ie entropy) generator is used too.

You should be very cautious of using the EntropyPool with:

since without one or all of these its state potentially becomes guessable.

This uses the supplied SecureRandom instance as a backup guarantor that we provide a reasonably secure bit-stream; bits on the way out are XORed with bytes from the guarantor generator (so both would have to be compromised for the output to be so), and seeds are fed into the guarantor generator too.

This class makes some slight effort to hide its entropy bits from any casual inspection of a core dump of the JVM or the operating system's swap space or of physical memory, as well as by trying to inject known plaintext or extract unlimited bits from the pool.

This class cannot be serialised, but a disguised random portion of the entropy held inside can be extracted as a seed to assist with fast start-up of a new generator, making the initial state of the pool difficult for a remote adversary to guess.

This routine is thread-safe with methods synchronized to protect use of internal variables.

When adding data to the pool we may attempt to compress it first (and cap any estimated entropy appropriately) to eliminate gross redundancy and to improve performance.

This class is final for security.

This implementation attempts to abide by as many of the rules at the end of http://www.cryptoengines.com/~peter/06_random.pdf as possible. (In particular, self test is not yet implemented.)

This implementation is designed to work with JDK 1.6 or newer.

The inspiration for this code is from prngd 0.9 by Lutz Jaenicke and he was also happy for me to reuse his code and many good bits were accordingly ``borrowed''!

See Also:
Serialized Form

Field Summary
static int DEFAULT_MIN_INITIAL_ENTROPY_BITS_BASE
          Minimum (default) initial base starting bits of entropy in the pool; strictly positive.
static int DEFAULT_POOL_CAPACITY_BASE
          Default (maximum) entropy pool base size in bits; strictly positive.
static java.lang.String EXTERNAL_ENTROPY_SOURCE_COMMON_URL
          Suggested URL for emergency entropy source as String.
static int EXTERNAL_ENTROPY_SOURCE_READ_SIZE
          Size of chunk that we expect to read from the externalEntropySource; strictly positive.
static float MAX_COMPRESSIBILITY
          If a block of supposedly-random output can be compressed smaller than this, we have a problem.
static int MIN_LENGTH_CHECKABLE
          Minimum length of data we can usefully check.
 
Constructor Summary
EntropyPool()
          Make default-size pool with some real entropy added c/o SecureRandom.
EntropyPool(java.security.SecureRandom _guarantor, int poolSizeBits, int _initialEntropyBits, boolean _injectEmergencyBitsIfPoolEmpty)
          Initialise the pool with some bits and a minimum amount of entropy.
EntropyPool(java.security.SecureRandom _guarantor, int poolSizeBits, int _initialEntropyBits, boolean _injectEmergencyBitsIfPoolEmpty, java.net.URL externalEntroptySourceURL)
          Initialise the pool with some bits and a minimum amount of entropy.
EntropyPool(java.net.URL externalEntroptySourceURL)
          Make default-size pool with external entropy source and SecureRandom guarantor.
 
Method Summary
 int addEntropy(byte[] data, int newEntropyBits)
          Add entropy-bearing bits with an estimated total entropy in bits.
static void checkGeneratedBits(byte[] bits, boolean doFullTests)
          Simple and fast check on generated bits; throws an Error if the generator may be broken.
static void cleanArray(byte[] data)
          Cleans a byte array by overwriting it; leaves it all zeros as if newly created.
 void destroy()
          Destroy the pool contents.
protected  void finalize()
          Help discard sensitive information when we are GCed.
 byte[] generateSeed()
          Extract a seed value to save for a restart later.
 byte[] generateSeed(int numBytes)
          Returns seed bytes which should be entropy-laden.
 int getCurrentPoolLevelBits()
          Get current pool size in bits; non-negative and no more than the maximum size specified.
 boolean getInjectEmergencyBitsIfPoolEmpty()
          If true, emergency entropy is injected when bits are extracted from an empty pool.
 int getMaxPoolSizeBits()
          Returns (maximum) size of entropy pool (bits).
 boolean needsMoreEntropy()
          Returns true if the pool is short of entropy and needs more added.
 void nextBytes(byte[] result)
          Get unlimited random bytes (a la Linux's /dev/urandom).
 byte[] nextBytesLimited(int byteCount)
          Get random bytes limited by the amount of entropy in the system.
 long nextLong()
          Returns the next pseudo-random, uniformly distributed long value.
 void setSeed(byte[] data)
          Add seed (after creating an instance).
 void setSeed(long value)
          Set a seed in a manner compatible with java.util.Random.
 java.lang.String toString()
          Return a simple description of the state of the pool.
 
Methods inherited from class java.security.SecureRandom
getAlgorithm, getInstance, getInstance, getInstance, getProvider, getSeed, next
 
Methods inherited from class java.util.Random
nextBoolean, nextDouble, nextFloat, nextGaussian, nextInt, nextInt
 
Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

DEFAULT_POOL_CAPACITY_BASE

public static final int DEFAULT_POOL_CAPACITY_BASE
Default (maximum) entropy pool base size in bits; strictly positive. We use this expanded automatically with (class construction) time to reflect safety margin required to keep up with improvement in available computing power to typical adversary every year. This helps to support generation of bigger keys, less guessable sequences, etc.

See Also:
Constant Field Values

DEFAULT_MIN_INITIAL_ENTROPY_BITS_BASE

public static final int DEFAULT_MIN_INITIAL_ENTROPY_BITS_BASE
Minimum (default) initial base starting bits of entropy in the pool; strictly positive. Should make guessing the initial state hard; hard enough for it to be safe to start extracting bits immediately.

We use this expanded automatically with (class construction) time.

When at least 64 and getInjectEmergencyBitsIfPoolEmpty() returns true, then any of the nextXXX() calls to get a primitive, such as nextLong() or nextDouble() or nextInt(), should always return a fully random value provided that the SecureRandom and guarantor seed-bit generator results are fully and truly random.

If getInjectEmergencyBitsIfPoolEmpty() is false we may chose not to inject any initial entropy into the pool to allow faster start-up.

See Also:
Constant Field Values

EXTERNAL_ENTROPY_SOURCE_READ_SIZE

public static final int EXTERNAL_ENTROPY_SOURCE_READ_SIZE
Size of chunk that we expect to read from the externalEntropySource; strictly positive. This is much greater than 1 for efficiency.

If the externalEntropySource is not an indefinite stream, eg is coming from a random.hd.org-like source, this can be used to parameterise the URL to have the right number of bytes generated in the response, either this or a multiple. The pool will open a new connection once the old one is "exhausted" if need be.

This is pitched to be the minimum pool size; hopefully big enough to get enough entropy into the pool to satisfy several typical requests.

See Also:
Constant Field Values

EXTERNAL_ENTROPY_SOURCE_COMMON_URL

public static final java.lang.String EXTERNAL_ENTROPY_SOURCE_COMMON_URL
Suggested URL for emergency entropy source as String. Not guaranteed to work on all systems, but should work with many modern *NIXes and other OSes as a source of kernel-gathered entropy.

See Also:
Constant Field Values

MAX_COMPRESSIBILITY

public static final float MAX_COMPRESSIBILITY
If a block of supposedly-random output can be compressed smaller than this, we have a problem. This needs to be used thoughtfully, and at best allows a heuristic check.

See Also:
Constant Field Values

MIN_LENGTH_CHECKABLE

public static final int MIN_LENGTH_CHECKABLE
Minimum length of data we can usefully check.

See Also:
Constant Field Values
Constructor Detail

EntropyPool

public EntropyPool(java.net.URL externalEntroptySourceURL)
Make default-size pool with external entropy source and SecureRandom guarantor. Just like the default constructor except that the externalEntroptySourceURL is supplied.

This defaults to forcing some (somewhat expensive) emergency entropy injection if a request is made for more bits than are actually in the pool.

Parameters:
externalEntroptySourceURL - if non-null, the EntropyPool will try extracting emergency entropy from the given URL before or in combination with its (very slow) internal source if the pool runs empty; such a source had better be (a) a good source of truly random and entropy-laden bits, and (b) secure, ie with the data fetched by the pool not observable

EntropyPool

public EntropyPool()
Make default-size pool with some real entropy added c/o SecureRandom. This may take a little while to create but by default should start in a reasonably unpredictable state.

This uses an instance of the default SecureRandom implementation as the guarantor of `secureness'.

This defaults to forcing some (somewhat expensive) emergency entropy injection if a request is made for more bits than are actually in the pool.


EntropyPool

public EntropyPool(java.security.SecureRandom _guarantor,
                   int poolSizeBits,
                   int _initialEntropyBits,
                   boolean _injectEmergencyBitsIfPoolEmpty)
Initialise the pool with some bits and a minimum amount of entropy. Any attempt to start with no initial entropy will be ignored and the default value will be used.

Even after getting some entropy from SecureRandom we don't count it. We should add external entropy as soon as possible. We do throw in some cheap entropy from the system.

We add in data such as system property names and values, and could add the system IP address and other values portably available, that while unchanging are not necessarily readily accessible or fully guessable to adversaries/users without access to the host machine.

We defer the most expensive initialisation until actually needed, so that constructing EntropyPool instances that may never be used is relatively lightweight. Postponing some of the initialisation may also allow us to gather from a wider variety of sources that have had longer to accumulate noise.

In passing, we check that our injectCheapEntropyTimeAndCount() routine generates different values at least on successive calls as a quick self-check. This test has a very small possibility of failure even if the injectCheapEntropyTimeAndCount() routine is operating correctly, but should be vanishingly small if the system is usable.

This sets up a null URL for the external emergency entropy source.

This constructor exists partly for backwards compatibility with versions 0.1.13 and earlier.

Parameters:
poolSizeBits - is the requested minimum entropy pool size in bits (must not be negative); the system will increase this if necessary
_initialEntropyBits - is the initial entropy in bits (must not be negative) to inject into the pool from a SecureRandom seed-bit source (the guarantor's or the default SecureRandom source as appropriate); the system will increase this if necessary to a safe minimum value if _injectEmergencyBitsIfPoolEmpty is true but in no case actually counts this as real entropy as returned by getCurrentPoolLevelBits()
_guarantor - if non-null, all seeds are fed to this as well as to the pool, and all output is XORed with this, to guarantee a minimum level of spectral purity and cryptographic security; if null the this pool does not use a guarantor, will be faster, and will use the default SecureRandom seed-bit source to seed itself
_injectEmergencyBitsIfPoolEmpty - if true and we empty the pool, we inject some emergency (and expensive) entropy from our own source on every call to nextBytes(), nextLong(), nextInt(), etc, to ensure that there is at least some new and unguessable entropy in each computed value
Throws:
java.lang.Error - if its initial set-up or self-tests fail

EntropyPool

public EntropyPool(java.security.SecureRandom _guarantor,
                   int poolSizeBits,
                   int _initialEntropyBits,
                   boolean _injectEmergencyBitsIfPoolEmpty,
                   java.net.URL externalEntroptySourceURL)
Initialise the pool with some bits and a minimum amount of entropy. Any attempt to start with no initial entropy will be ignored and the default value will be used.

Even after getting some entropy from SecureRandom we don't count it. We should add external entropy as soon as possible. We do throw in some cheap entropy from the system.

We add in data such as system property names and values, and could add the system IP address and other values portably available, that while unchanging are not necessarily readily accessible or fully guessable to adversaries/users without access to the host machine.

We defer the most expensive initialisation until actually needed, so that constructing EntropyPool instances that may never be used is relatively lightweight. Postponing some of the initialisation may also allow us to gather from a wider variety of sources that have had longer to accumulate noise.

In passing, we check that our injectCheapEntropyTimeAndCount() routine generates different values at least on successive calls as a quick self-check. This test has a very small possibility of failure even if the injectCheapEntropyTimeAndCount() routine is operating correctly, but should be vanishingly small if the system is usable.

Parameters:
poolSizeBits - is the requested minimum entropy pool size in bits (must not be negative); the system will increase this if necessary
_initialEntropyBits - is the initial entropy in bits (must not be negative) to inject into the pool from a SecureRandom seed-bit source (the guarantor's or the default SecureRandom source as appropriate); the system will increase this if necessary to a safe minimum value if _injectEmergencyBitsIfPoolEmpty is true but in no case actually counts this as real entropy as returned by getCurrentPoolLevelBits()
_guarantor - if non-null, all seeds are fed to this as well as to the pool, and all output is XORed with this, to guarantee a miminum level of spectural purity and cryptographic security; if null the this pool does not use a guarantor, will be faster, and will use the default SecureRandom seed-bit source to seed itself
_injectEmergencyBitsIfPoolEmpty - if true and we empty the pool, we inject some emergency (and expensive) entropy from our own source on every call to nextBytes(), nextLong(), nextInt(), etc, to ensure that there is at least some new and unguessable entropy in each computed value; does not make much sense to have the externalENtropySourceURL non-null if this is false
externalEntroptySourceURL - if non-null, the EntropyPool will try extracting emergency entropy from the given URL before or in combination with its (very slow) internal source if the pool runs empty and _injectEmergencyBitsIfPoolEmpty is true; such a source had better be (a) a good source of truly random and entropy-laden bits, and (b) secure, ie with the data fetched by the pool not observable
Throws:
java.lang.Error - if its initial set-up or self-tests fail
Method Detail

getCurrentPoolLevelBits

public int getCurrentPoolLevelBits()
Get current pool size in bits; non-negative and no more than the maximum size specified.


needsMoreEntropy

public boolean needsMoreEntropy()
Returns true if the pool is short of entropy and needs more added.


getMaxPoolSizeBits

public int getMaxPoolSizeBits()
Returns (maximum) size of entropy pool (bits). Need not be synchronized because maxPoolSizeBits is constant after construction.


getInjectEmergencyBitsIfPoolEmpty

public boolean getInjectEmergencyBitsIfPoolEmpty()
If true, emergency entropy is injected when bits are extracted from an empty pool. If the pool does not contain enough entropy to satisfy a request to nextBytes() or one of the other methods such as nextDouble(), extra entropy is injected from a number of internal sources including our internal seed bit generator (and/or that of any guarantor).

If true, this should ensure that all values extracted from the pool contain at least some true entropy.

An EntropyPool being used as a source of cryptographically-secure numbers should probably have this true so as to try to ensure non-predictability even if external entropy cannot be injected fast enough to keep pace with demand.

Note that there is only enough entropy injected to make the entire value extracted probably unguessable, and there may well be less entropy than requested, through the value should still have good spectral and statistical properties and be secure because of the good hashing function used to generate output.


setSeed

public void setSeed(byte[] data)
Add seed (after creating an instance). This is treated like any other entropy data except that it is not counted as adding any entropy to the pool.

It is possibly a good idea to replace or destroy a seed file after using it, depending on your environment.

A seed file might initially be made by concatenating together a few files such as recent (unembarrassing) emails, some system stats output, some hex data from HotBits, etc.

We clone the input array to avoid destroying it.

We reseed the guarantor generator too with this data.

Overrides:
setSeed in class java.security.SecureRandom

setSeed

public void setSeed(long value)
Set a seed in a manner compatible with java.util.Random. This is treated like any other entropy data except that it is not counted as adding any entropy to the pool.

Since this will get called back indirectly by SecureRandom's constructor (with value 0 as it happens) before we are fully initialised, we return immediately where the passed value is zero..

We reseed the guarantor generator too with this data.

Overrides:
setSeed in class java.security.SecureRandom

addEntropy

public final int addEntropy(byte[] data,
                            int newEntropyBits)
                     throws java.lang.IllegalArgumentException
Add entropy-bearing bits with an estimated total entropy in bits. The estimated total entropy must be no more than the actual number of bits supplied; we may attempt to compress the data to try to remove redundancy and silently cap the estimated entropy further. Indeed we try hard to avoid letting lots of bogus claimed entropy into the system that way, in particular completely ignoring an entirely empty array (one still full of zeros) that we might have forgotten to fill with real-world data!

Returns the estimated number of bits added.

The estimated entropy can be zero to churn the pool and possibly help it but not notionally increase the stored entropy.

The entropy estimate must not be negative.

Do not alter the input array while the routine is running...

The input array is erased by this routine after use.

A null or zero-length or all-zeros input array is interpreted as a request to churn the pool a little, and, for example, to implicitly note the timing/count of an external event. This operation is reasonably cheap with a null or zero-length array.

Throws:
java.lang.IllegalArgumentException

generateSeed

public byte[] generateSeed(int numBytes)
Returns seed bytes which should be entropy-laden. Returns the given number of seed bytes, computed using the seed generation algorithm that this class uses to seed itself. This call may be used to seed other random number generators.

This is very CPU-intensive.

This does not consume entropy from the pool.

We use our internal entropy source whitened by the guarantor's seed-generator if set or SecureRandom's if there is no guarantor.

We don't believe that the any SecureRandom.generateSeed() routine returns new entropy up to at least JDK 1.4.

We don't need to synchronize this because all the underlying generateSeed() calls that we make should be thread-safe.

Overrides:
generateSeed in class java.security.SecureRandom
Parameters:
numBytes - the number of seed bytes to generate.
Returns:
the seed bytes.

generateSeed

public byte[] generateSeed()
Extract a seed value to save for a restart later. The seed generated is of a suitable size to seed another EntropyPool of about the same size and characteristics as this one.

This seed reduces the entropy level in the pool just like any other way of extracting entropy from the pool.

The generated seed should probably be used to overwrite any extant seed file in situ, and should be protected from casual inspection.

A seed should probably be saved when the system is shutting down, and could also be done immediately after the previous seed file is read to discard any initial data bits, and maybe also periodically (infrequently and only when the pool is full) to ensure that a newish seed file is available even if the system was shut down abruptly (eg by a crash) and could not save a seed normally.

We generate a set of bits about one quarter the pool size.

We may (expensively) inject a little extra entropy while extracting this seed value.

It should not be possible to discover the previous state or the new state of the pool from the seed. We try to make it hard even to know exactly how large or how full the pool was from looking at the saved seed, though we do not try to draw out of the pool more entropy than was present since that might be very slow.


nextLong

public long nextLong()
Returns the next pseudo-random, uniformly distributed long value. Identical behaviour to java.util.Random.nextLong(), but more efficient since we extract all the random bits in one go rather than in two calls as would otherwise be the case.

Overrides:
nextLong in class java.util.Random
Returns:
the next pseudo-random, uniformly distributed long value from this random number generator's sequence.

nextBytesLimited

public byte[] nextBytesLimited(int byteCount)
Get random bytes limited by the amount of entropy in the system. This routine returns with the minimum of the requested number of bytes and the number of whole bytes of entropy the pool is believed to contain (and that entropy is then marked as removed from the pool).

This may, for example, return zero bytes if insufficient entropy has been injected into the pool.

This routine may be especially useful for extracting really random bits for secret-key generation.

Parameters:
byteCount - maximum number of bytes desired subject to available entropy in the pool; must be non-negative

checkGeneratedBits

public static void checkGeneratedBits(byte[] bits,
                                      boolean doFullTests)
                               throws java.lang.Error
Simple and fast check on generated bits; throws an Error if the generator may be broken. This does a very simple check that some set of `random' bits that we have generated does appear to be reasonably random.

This does not alter its input array or copy it anywhere and is designed to be fast.

This will ignore very short arrays where its has no reasonable chance of detecting faulty output. Our threshold is about 8 bytes.

The possible indicators of faulty generation looked for are:

This needs to be used thoughtfully...

Parameters:
doFullTests - if true we may test the bits more extensively, eg for excess compressibility; this should not be done on real random bits handed to users since the compression (etc) routines might leak the sensitive data somehow
Throws:
java.lang.Error - if it looks like the generator may be grossly faulty.

nextBytes

public void nextBytes(byte[] result)
Get unlimited random bytes (a la Linux's /dev/urandom). Get real entropy if possible, but if that fails, generate cryptographically-secure pseudo-random bits from the pool.

Decrement the pool entropy measure appropriately, down to zero if we remove all the entropy.

We mix before and after giving out the entropy to try to ensure that no useful state relating to the bits we are about to give out was, or will be, in memory for long.

Output is XORed with the underlying guarantor generator (if supplied) to guarantee good spectral and security behaviour.

If we actually empty the pool we attempt to inject some extra entropy on the fly from internal sources and possibly the SecureRandom/guarantor sources while generating the output. This may be expensive, but as a result it should prove relatively unlikely that any extracted bytes should contain no real entropy at all.

Overrides:
nextBytes in class java.security.SecureRandom

cleanArray

public static void cleanArray(byte[] data)
Cleans a byte array by overwriting it; leaves it all zeros as if newly created. We do the overwrite several times with alternating bit patterns to try very hard not to leave too many traces of sensitive bits around.

This can be used to try to hide any sensitive data.


toString

public java.lang.String toString()
Return a simple description of the state of the pool. Don't leak any very critical data, especially not pool contents.

Overrides:
toString in class java.lang.Object

destroy

public void destroy()
Destroy the pool contents. This will force the pool to be cleared.

The pool is usable after this if need be.


finalize

protected void finalize()
                 throws java.lang.Throwable
Help discard sensitive information when we are GCed. Not guaranteed to be called, but if it is called will explicitly destroy some potentially sensitive information that might otherwise be left in the JVM's memory image.

We do this in a way that does not hold any locks, and so cannot cause a deadlock during GC.

Overrides:
finalize in class java.lang.Object
Throws:
java.lang.Throwable - the Exception raised by this method