random.c

cryptlib安全工具包

/****************************************************************************
*																			*
*					cryptlib Randomness Management Routines					*
*						Copyright Peter Gutmann 1995-2007					*
*																			*
****************************************************************************/

/* The random pool handling code in this module and the other modules in the
   /random subdirectory represent the cryptlib continuously seeded
   pseudorandom number generator (CSPRNG) as described in my 1998 Usenix
   Security Symposium paper "The generation of practically strong random
   numbers".

   The CSPRNG code is copyright Peter Gutmann (and various others) 1995-2004
   all rights reserved.  Redistribution of the CSPRNG modules and use in
   source and binary forms, with or without modification, are permitted
   provided that the following BSD-style license conditions are met:

   1. Redistributions of source code must retain the above copyright notice
	  and this permission notice in its entirety.

   2. Redistributions in binary form must reproduce the copyright notice in
	  the documentation and/or other materials provided with the distribution.

   3. A copy of any bugfixes or enhancements made must be provided to the
	  author, <[e-mail]> to allow them to be added to the
	  baseline version of the code.

   ALTERNATIVELY, the code may be distributed under the terms of the GNU
   General Public License, version 2 or any later version published by the
   Free Software Foundation, in which case the provisions of the GNU GPL are
   required INSTEAD OF the above restrictions.

   ALTERNATIVELY ALTERNATIVELY, the code may be distributed under the terms 
   of the GNU Library/Lesser General Public License, version 2 or any later 
   version published by the Free Software Foundation, in which case the 
   provisions of the GNU LGPL are required INSTEAD OF the above restrictions.

   Although not required under the terms of the GPL or LGPL, it would still 
   be nice if you could make any changes available to the author to allow a
   consistent code base to be maintained */

#if defined( INC_ALL )
  #include "crypt.h"
  #ifdef CONFIG_RANDSEED
	#include "stream.h"
  #endif /* CONFIG_RANDSEED */
  #include "random_int.h"
#else
  #include "crypt.h"
  #ifdef CONFIG_RANDSEED
	#include "io/stream.h"
  #endif /* CONFIG_RANDSEED */
  #include "random/random_int.h"
#endif /* Compiler-specific includes */

/* If we don't have a defined randomness interface, complain */

#if !( defined( __BEOS__ ) || defined( __IBM4758__ ) || \
	   defined( __MAC__ ) || defined( __MSDOS__ ) || defined( __MVS__ ) || \
	   defined( __OS2__ ) || defined( __PALMOS__ ) || \
	   defined( __TANDEM_NSK__ ) || defined( __TANDEM_OSS__ ) || \
	   defined( __UNIX__ ) || defined( __VMCMS__ ) || \
	   defined( __WIN16__ ) || defined( __WIN32__ ) || \
	   defined( __WINCE__ ) || defined( __XMK__ ) )
  #error You need to create OS-specific randomness-gathering functions in random/<os-name>.c
#endif /* Various OS-specific defines */

/* If we're using stored seed data, make sure that the seed quality setting
   is in order */

#ifdef CONFIG_RANDSEED
  #ifndef CONFIG_RANDSEED_QUALITY
	/* If the user hasn't provided a quality estimate, default to 80 */
	#define CONFIG_RANDSEED_QUALITY		80
  #endif /* !CONFIG_RANDSEED_QUALITY */
  #if ( CONFIG_RANDSEED_QUALITY < 10 ) || ( CONFIG_RANDSEED_QUALITY > 100 )
	#error CONFIG_RANDSEED_QUALITY must be between 10 and 100
  #endif /* CONFIG_RANDSEED_QUALITY check */
#endif /* CONFIG_RANDSEED */

/* A custom form of REQUIRES()/ENSURES() that takes care of unlocking the
   randomness mutex on the way out */

#define REQUIRES_MUTEX( x )	\
		if( !( x ) ) { krnlExitMutex( MUTEX_RANDOM ); retIntError(); }
#define ENSURES_MUTEX	REQUIRES_MUTEX

/****************************************************************************
*																			*
*						Randomness Interface Definitions					*
*																			*
****************************************************************************/

/* In order to avoid the pool startup problem (where initial pool data may
   consist of minimally-mixed entropy samples) we require that the pool be
   mixed at least the following number of times before we can draw data from
   it.  This usually happens automatically because a slow poll adds enough
   data to cause many mixing iterations, however if this doesn't happen we
   manually mix it the appropriate number of times to get it up to the
   correct level */

#define RANDOMPOOL_MIXES		10

/****************************************************************************
*																			*
*								Utility Functions							*
*																			*
****************************************************************************/

/* Sanity-check the randomness state */

CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1 ) ) \
static BOOLEAN sanityCheck( const RANDOM_INFO *randomInfo )
	{
	assert( isReadPtr( randomInfo, sizeof( RANDOM_INFO ) ) );

	/* Make sure that the pool index information is within bounds.  The pool
	   index can briefly become the same as RANDOMPOOL_SIZE if we've filled
	   the pool and we've about to mix it */
	if( randomInfo->randomPoolPos < 0 || \
		randomInfo->randomPoolPos > RANDOMPOOL_SIZE )
		return( FALSE );

	/* Make sure that the pool accounting information is within bounds */
	if( randomInfo->randomQuality < 0 || randomInfo->randomQuality > 100 )
		return( FALSE );
	if( randomInfo->randomPoolMixes < 0 || \
		randomInfo->randomPoolMixes > RANDOMPOOL_MIXES )
		return( FALSE );

	return( TRUE );
	}

/****************************************************************************
*																			*
*						Random Pool Management Routines						*
*																			*
****************************************************************************/

/* Initialise and shut down the random pool */

STDC_NONNULL_ARG( ( 1 ) ) \
void initRandomPool( INOUT RANDOM_INFO *randomInfo )
	{
	assert( isWritePtr( randomInfo, sizeof( RANDOM_INFO ) ) );

	memset( randomInfo, 0, sizeof( RANDOM_INFO ) );
	}

STDC_NONNULL_ARG( ( 1 ) ) \
void endRandomPool( INOUT RANDOM_INFO *randomInfo )
	{
	assert( isWritePtr( randomInfo, sizeof( RANDOM_INFO ) ) );

	zeroise( randomInfo, sizeof( RANDOM_INFO ) );
	}

/* Stir up the data in the random pool.  Given a circular buffer of length n
   bytes, a buffer position p, and a hash output size of h bytes, we hash
   bytes from p - h...p - 1 (to provide chaining across previous hashes) and
   p...p + 64 (to have as much surrounding data as possible affect the
   current data).  Then we move on to the next h bytes until all n bytes have
   been mixed.  See "Cryptographic Security Architecture Design and 
   Implementation" for the full details of the PRNG design */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int mixRandomPool( INOUT RANDOM_INFO *randomInfo )
	{
	HASHFUNCTION_ATOMIC hashFunctionAtomic;
	BYTE dataBuffer[ CRYPT_MAX_HASHSIZE + 64 + 8 ];
	int hashSize, hashIndex;
	ORIGINAL_INT_VAR( randomPoolMixes, randomInfo->randomPoolMixes );

	assert( isWritePtr( randomInfo, sizeof( RANDOM_INFO ) ) );

	REQUIRES( sanityCheck( randomInfo ) );

	getHashAtomicParameters( CRYPT_ALGO_SHA1, &hashFunctionAtomic, &hashSize );

	/* Stir up the entire pool.  We can't check the return value of the
	   hashing call because there isn't one, however the hashing code has 
	   gone through a self-test when the randomness subsystem was 
	   initialised */
	for( hashIndex = 0; hashIndex < RANDOMPOOL_SIZE; hashIndex += hashSize )
		{
		int dataBufIndex, poolIndex;

		/* Precondition: We're processing hashSize bytes at a time */
		REQUIRES( hashIndex % hashSize == 0 );

		/* If we're at the start of the pool then the first block that we hash
		   is at the end of the pool, otherwise it's the block immediately
		   preceding the current one */
		poolIndex = ( hashIndex >= hashSize ) ? \
					hashIndex - hashSize : RANDOMPOOL_SIZE - hashSize;
		ENSURES( poolIndex >= 0 && poolIndex <= RANDOMPOOL_SIZE - hashSize );

		/* Copy hashSize bytes from position p - hashSize... p + 64 in the
		   circular pool into the hash data buffer:

				poolIndex
					| hashIndex
					v	v
			--------+---+-----------------------+---------
					| 20|			64			|			Pool
			--------+---+-----------------------+---------
					|							|
					+---------------------------+
					|							|			Buffer
					+---------------------------+
					 \							/
					  \	Hash  ------------------	
					   \	 /
			------------+---+-----------------------------
						| 20|								Pool'
			------------+---+----------------------------- 
					^	^						^
					|	|						|
				   p-h	p					  p+64 */
		for( dataBufIndex = 0; dataBufIndex < hashSize + 64; dataBufIndex++ )
			{
			dataBuffer[ dataBufIndex ] = randomInfo->randomPool[ poolIndex ];
			poolIndex = ( poolIndex + 1 ) % RANDOMPOOL_SIZE;
			}

		/* Postconditions for the state data copy: We got hashSize + 64 bytes 
		   surrounding the current pool position */
		ENSURES( dataBufIndex == hashSize + 64 );

		/* Hash the data in the circular pool, depositing the result at position 
		   p...p + hashSize */
		hashFunctionAtomic( randomInfo->randomPool + hashIndex,
							RANDOMPOOL_ALLOCSIZE - hashIndex, 
							dataBuffer, dataBufIndex );
		}
	zeroise( dataBuffer, CRYPT_MAX_HASHSIZE + 64 );

	/* Postconditions for the pool mixing: The entire pool was mixed and
	   temporary storage was cleared */
	ENSURES( hashIndex >= RANDOMPOOL_SIZE );
	FORALL( i, 0, CRYPT_MAX_HASHSIZE + 64,
			dataBuffer[ i ] == 0 );

	/* Increment the mix count and move the write position back to the start
	   of the pool */
	if( randomInfo->randomPoolMixes < RANDOMPOOL_MIXES )
		randomInfo->randomPoolMixes++;
	randomInfo->randomPoolPos = 0;

	/* Postconditions for the status update: We mixed the pool at least
	   once, and we're back at the start of the pool */
	POST( randomInfo->randomPoolMixes == RANDOMPOOL_MIXES || \
		  randomInfo->randomPoolMixes == \
							ORIGINAL_VALUE( randomPoolMixes ) + 1 );
	ENSURES( randomInfo->randomPoolPos == 0 );

	ENSURES( sanityCheck( randomInfo ) );

	return( CRYPT_OK );
	}

/****************************************************************************
*																			*
*								Get Random Data								*
*																			*
****************************************************************************/

/* Get a block of random data from the randomness pool in such a way that
   compromise of the data doesn't compromise the pool and vice versa.  This 
   is done by performing the (one-way) pool mixing operation on the pool and
   on a transformed version of the pool that becomes the key.  This 
   corresponds to the Barak-Halevi construction:

	r || s' = next( s );
	s' = refresh( s ^ new_state );

   where 'r' is the generator output and 's' is the generator state (the RNG
   design here predates Barak-Halevi by about 10 years but the principle is
   the same).
   
   The transformed version of the pool from which the key data will be drawn 
   is then further processed by running each 64-bit block through the X9.17
   generator.  As an additional precaution the key data is folded in half to
   ensure that not even a hashed or encrypted form of the previous contents
   is available.  No pool data ever leaves the pool.

   This function performs a more paranoid version of the FIPS 140 continuous
   tests on both the main pool contents and the X9.17 generator output to
   detect stuck-at faults and short cycles in the output.  In addition the
   higher-level message handler applies FIPS 140-like statistical tests to
   the output and will retry the fetch if the output fails the tests.  This
   additional step is performed at a higher level because it's then applied
   to all randomness sources used by cryptlib and not just the built-in one.

   Because the pool output is folded to mask the PRNG output, the output from 
   each round of mixing is only half the pool size, as defined below */

#define RANDOM_OUTPUTSIZE	( RANDOMPOOL_SIZE / 2 )

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int tryGetRandomOutput( INOUT RANDOM_INFO *randomInfo,
							   INOUT RANDOM_INFO *exportedRandomInfo )
	{
	const BYTE *samplePtr = randomInfo->randomPool;
	const BYTE *x917SamplePtr = exportedRandomInfo->randomPool;
	unsigned long sample;
	int i, status;

	assert( isWritePtr( randomInfo, sizeof( RANDOM_INFO ) ) );
	assert( isWritePtr( exportedRandomInfo, sizeof( RANDOM_INFO ) ) );

	/* Precondition: The pool is ready to go.  This check isn't so much to
	   confirm that this really is the case (it's already been checked
	   elsewhere) but to ensure that the two pool parameters haven't been
	   reversed.  The use of generic pools for all types of random output is
	   useful in terms of providing a nice abstraction, but less useful for
	   type safety */
	REQUIRES( sanityCheck( randomInfo ) );
	REQUIRES( randomInfo->randomQuality >= 100 && \
			  randomInfo->randomPoolMixes >= RANDOMPOOL_MIXES && \
			  randomInfo->x917Inited == TRUE );
	REQUIRES( exportedRandomInfo->randomQuality == 0 && \
			  exportedRandomInfo->randomPoolMixes == 0 && \
			  exportedRandomInfo->x917Inited == FALSE );

	/* Copy the contents of the main pool across to the export pool,
	   transforming it as we go by flipping all of the bits */
	for( i = 0; i < RANDOMPOOL_ALLOCSIZE; i++ )
		exportedRandomInfo->randomPool[ i ] = randomInfo->randomPool[ i ] ^ 0xFF;