src/include/ipxe/entropy.h

#ifndef _IPXE_ENTROPY_H
#define _IPXE_ENTROPY_H

/** @file
 *
 * Entropy source
 *
 */

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
FILE_SECBOOT ( PERMITTED );

#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <ipxe/hash_df.h>
#include <ipxe/sha256.h>
#include <ipxe/tables.h>
#include <config/entropy.h>

/** A noise sample */
typedef uint8_t noise_sample_t;

/** An entropy sample */
typedef uint8_t entropy_sample_t;

/** An amount of min-entropy
 *
 * Expressed as a fixed-point quantity in order to avoid floating
 * point calculations.
 */
typedef unsigned int min_entropy_t;

/** Fixed-point scale for min-entropy amounts */
#define MIN_ENTROPY_SCALE ( 1 << 16 )

/**
 * Construct a min-entropy fixed-point value
 *
 * @v bits		min-entropy in bits
 * @ret min_entropy	min-entropy as a fixed-point value
 */
#define MIN_ENTROPY( bits ) \
	( ( min_entropy_t ) ( (bits) * MIN_ENTROPY_SCALE ) )

/**
 * Repetition count test state
 *
 * This is the state for the repetition Count Test defined in ANS
 * X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
 */
struct entropy_repetition_count_test {
	/**
	 * A = the most recently seen sample value
	 */
	noise_sample_t most_recent_sample;
	/**
	 * B = the number of times that value A has been seen in a row
	 */
	unsigned int repetition_count;
	/**
	 * C = the cutoff value above which the repetition test should fail
	 *
	 * Filled in by entropy_init().
	 */
	unsigned int cutoff;
};

/**
 * Adaptive proportion test state
 *
 * This is the state for the Adaptive Proportion Test for the Most
 * Common Value defined in ANS X9.82 Part 2 (October 2011 Draft)
 * Section 8.5.2.1.3.
 */
struct entropy_adaptive_proportion_test {
	/**
	 * A = the sample value currently being counted
	 */
	noise_sample_t current_counted_sample;
	/**
	 * S = the number of samples examined in this run of the test so far
	 */
	unsigned int sample_count;
	/**
	 * B = the current number of times that S (sic) has been seen
	 *     in the W (sic) samples examined so far
	 */
	unsigned int repetition_count;
	/**
	 * C = the cutoff value above which the repetition test should fail
	 *
	 * Filled in by entropy_init().
	 */
	unsigned int cutoff;
};

/**
 * Startup test state
 *
 * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
 * that at least one full cycle of the continuous tests must be
 * performed at start-up.
 */
struct entropy_startup_test {
	/** Number of startup tests performed */
	unsigned int tested;
	/**
	 * Number of startup tests required for one full cycle
	 *
	 * Filled in by entropy_init().
	 */
	unsigned int count;
};

/** An entropy source */
struct entropy_source {
	/** Name */
	const char *name;
	/**
	 * min-entropy per sample
	 *
	 * min-entropy is defined in ANS X9.82 Part 1-2006 Section 8.3 and in
	 * NIST SP 800-90 Appendix C.3 as
	 *
	 *    H_min = -log2 ( p_max )
	 *
	 * where p_max is the probability of the most likely sample value.
	 *
	 * Filled in by entropy_init().
	 */
	min_entropy_t min_entropy_per_sample;
	/** Repetition count test state */
	struct entropy_repetition_count_test repetition_count_test;
	/** Adaptive proportion test state */
	struct entropy_adaptive_proportion_test adaptive_proportion_test;
	/** Startup test state */
	struct entropy_startup_test startup_test;
	/**
	 * Failure status (if any)
	 *
	 * Any failure of an entropy source is regarded as permanent.
	 */
	int rc;

	/**
	 * Enable entropy gathering
	 *
	 * @ret rc		Return status code
	 */
	int ( * enable ) ( void );
	/**
	 * Disable entropy gathering
	 *
	 */
	void ( * disable ) ( void );
	/**
	 * Get noise sample
	 *
	 * @ret noise		Noise sample
	 * @ret rc		Return status code
	 *
	 * This is the GetNoise function defined in ANS X9.82 Part 2
	 * (October 2011 Draft) Section 6.5.2.
	 */
	int ( * get_noise ) ( noise_sample_t *noise );
};

/** Entropy source table */
#define ENTROPY_SOURCES __table ( struct entropy_source, "entropy_sources" )

/** Declare an entropy source */
#define __entropy_source( order ) __table_entry ( ENTROPY_SOURCES, order )

/** @defgroup entropy_source_order Entropy source order
 *
 * @{
 */

#define ENTROPY_PREFERRED	01	/**< Preferred entropy source */
#define ENTROPY_NORMAL		02	/**< Normal entropy source */
#define ENTROPY_FALLBACK	03	/**< Fallback entropy source */

/** @} */

extern int get_entropy_input_tmp ( min_entropy_t min_entropy, uint8_t *tmp,
				   size_t tmp_len );

/** Use SHA-256 as the underlying hash algorithm for Hash_df
 *
 * Hash_df using SHA-256 is an Approved algorithm in ANS X9.82.
 */
#define entropy_hash_df_algorithm sha256_algorithm

/** Underlying hash algorithm output length (in bytes) */
#define ENTROPY_HASH_DF_OUTLEN_BYTES SHA256_DIGEST_SIZE

/**
 * Get noise sample
 *
 * @v source		Entropy source
 * @ret noise		Noise sample
 * @ret rc		Return status code
 *
 * This is the GetNoise function defined in ANS X9.82 Part 2
 * (October 2011 Draft) Section 6.5.2.
 */
static inline __attribute__ (( always_inline )) int
get_noise ( struct entropy_source *source, noise_sample_t *noise ) {

	return source->get_noise ( noise );
}

/**
 * Obtain entropy input
 *
 * @v min_entropy_bits	Minimum amount of entropy, in bits
 * @v data		Data buffer
 * @v min_len		Minimum length of entropy input, in bytes
 * @v max_len		Maximum length of entropy input, in bytes
 * @ret len		Length of entropy input, in bytes, or negative error
 *
 * This is the implementation of the Get_entropy_input function (using
 * an entropy source as the source of entropy input and condensing
 * each entropy source output after each GetEntropy call) as defined
 * in ANS X9.82 Part 4 (April 2011 Draft) Section 13.3.4.2.
 *
 * This function is inlined since the entropy amount and length inputs
 * are always compile-time constants.
 */
static inline __attribute__ (( always_inline )) int
get_entropy_input ( unsigned int min_entropy_bits, void *data, size_t min_len,
		    size_t max_len ) {
	size_t tmp_len = ( ( ( min_entropy_bits * 2 ) + 7 ) / 8 );
	uint8_t tmp_buf[ tmp_len ];
	uint8_t *tmp = ( ( tmp_len > max_len ) ? tmp_buf : data );
	unsigned int n;
	int rc;

	/* Sanity check */
	build_assert ( min_entropy_bits <= ( 8 * max_len ) );

	/* Round up minimum entropy to an integral number of bytes */
	min_entropy_bits = ( ( min_entropy_bits + 7 ) & ~7 );

	/* (Unnumbered).  The output length of the hash function shall
	 * meet or exceed the security strength indicated by the
	 * min_entropy parameter.
	 */
	build_assert ( ( 8 * ENTROPY_HASH_DF_OUTLEN_BYTES ) >=
		       min_entropy_bits );

	/* 1.  If ( min_length > max_length ), then return ( FAILURE, Null ) */
	build_assert ( min_len <= max_len );

	/* 2.  n = 2 * min_entropy */
	n = ( 2 * min_entropy_bits );

	/* 3.  entropy_total = 0
	 * 4.  tmp = a fixed n-bit value, such as 0^n
	 * 5.  While ( entropy_total < min_entropy )
	 *     5.1.  ( status, entropy_bitstring, assessed_entropy )
	 *           = GetEntropy()
	 *     5.2.  If status indicates an error, return ( status, Null )
	 *     5.3.  nonce = MakeNextNonce()
	 *     5.4.  tmp = tmp XOR df ( ( nonce || entropy_bitstring ), n )
	 *     5.5.  entropy_total = entropy_total + assessed_entropy
	 *
	 * (The implementation of these steps is inside the function
	 * get_entropy_input_tmp().)
	 */
	build_assert ( __builtin_constant_p ( tmp_len ) );
	build_assert ( n == ( 8 * tmp_len ) );
	if ( ( rc = get_entropy_input_tmp ( MIN_ENTROPY ( min_entropy_bits ),
					    tmp, tmp_len ) ) != 0 ) {
		return rc;
	}

	/* 6.  If ( n < min_length ), then tmp = tmp || 0^(min_length-n)
	 * 7.  If ( n > max_length ), then tmp = df ( tmp, max_length )
	 * 8.  Return ( SUCCESS, tmp )
	 */
	if ( tmp_len < min_len ) {
		/* (Data is already in-place.) */
		build_assert ( data == tmp );
		memset ( ( data + tmp_len ), 0, ( min_len - tmp_len ) );
		return min_len;
	} else if ( tmp_len > max_len ) {
		build_assert ( tmp == tmp_buf );
		hash_df ( &entropy_hash_df_algorithm, tmp, tmp_len,
			  data, max_len );
		return max_len;
	} else {
		/* (Data is already in-place.) */
		build_assert ( data == tmp );
		return tmp_len;
	}
}

/**
 * Calculate cutoff value for the repetition count test
 *
 * @v min_entropy_per_sample	Min-entropy per sample
 * @ret cutoff			Cutoff value
 *
 * This is the cutoff value for the Repetition Count Test defined in
 * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
 */
static inline __attribute__ (( always_inline )) unsigned int
entropy_repetition_count_cutoff ( min_entropy_t min_entropy_per_sample ) {
	double max_repetitions;
	unsigned int cutoff;

	/* The cutoff formula for the repetition test is:
	 *
	 *   C = ( 1 + ( -log2(W) / H_min ) )
	 *
	 * where W is set at 2^(-30) (in ANS X9.82 Part 2 (October
	 * 2011 Draft) Section 8.5.2.1.3.1).
	 */
	max_repetitions = ( 1 + ( MIN_ENTROPY ( 30 ) /
				  min_entropy_per_sample ) );

	/* Round up to a whole number of repetitions.  We don't have
	 * the ceil() function available, so do the rounding by hand.
	 */
	cutoff = max_repetitions;
	if ( cutoff < max_repetitions )
		cutoff++;
	build_assert ( cutoff >= max_repetitions );

	/* Floating-point operations are not allowed in iPXE since we
	 * never set up a suitable environment.  Abort the build
	 * unless the calculated number of repetitions is a
	 * compile-time constant.
	 */
	build_assert ( __builtin_constant_p ( cutoff ) );

	return cutoff;
}

/**
 * Window size for the adaptive proportion test
 *
 * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.1 allows
 * five possible window sizes: 16, 64, 256, 4096 and 65536.
 *
 * We expect to generate relatively few (<256) entropy samples during
 * a typical iPXE run; the use of a large window size would mean that
 * the test would never complete a single cycle.  We use a window size
 * of 64, which is the smallest window size that permits values of
 * H_min down to one bit per sample.
 */
#define ADAPTIVE_PROPORTION_WINDOW_SIZE 64

/**
 * Combine adaptive proportion test window size and min-entropy
 *
 * @v n			N (window size)
 * @v h			H (min-entropy)
 * @ret n_h		(N,H) combined value
 */
#define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) )

/**
 * Define a row of the adaptive proportion cutoff table
 *
 * @v h			H (min-entropy)
 * @v c16		Cutoff for N=16
 * @v c64		Cutoff for N=64
 * @v c256		Cutoff for N=256
 * @v c4096		Cutoff for N=4096
 * @v c65536		Cutoff for N=65536
 */
#define APC_TABLE_ROW( h, c16, c64, c256, c4096, c65536)	   \
	case APC_N_H ( 16, h ) :	return c16;		   \
	case APC_N_H ( 64, h ) :	return c64;   		   \
	case APC_N_H ( 256, h ) :	return c256;		   \
	case APC_N_H ( 4096, h ) :	return c4096;		   \
	case APC_N_H ( 65536, h ) :	return c65536;

/** Value used to represent "N/A" in adaptive proportion cutoff table */
#define APC_NA 0

/**
 * Look up value in adaptive proportion test cutoff table
 *
 * @v n			N (window size)
 * @v h			H (min-entropy)
 * @ret cutoff		Cutoff
 *
 * This is the table of cutoff values defined in ANS X9.82 Part 2
 * (October 2011 Draft) Section 8.5.2.1.3.1.2.
 */
static inline __attribute__ (( always_inline )) unsigned int
entropy_adaptive_proportion_cutoff_lookup ( unsigned int n, unsigned int h ) {
	switch ( APC_N_H ( n, h ) ) {
		APC_TABLE_ROW (  1, APC_NA,     51,    168,   2240,  33537 );
		APC_TABLE_ROW (  2, APC_NA,     35,    100,   1193,  17053 );
		APC_TABLE_ROW (  3,     10,     24,     61,    643,   8705 );
		APC_TABLE_ROW (  4,      8,     16,     38,    354,   4473 );
		APC_TABLE_ROW (  5,      6,     12,     25,    200,   2321 );
		APC_TABLE_ROW (  6,      5,      9,     17,    117,   1220 );
		APC_TABLE_ROW (  7,      4,      7,     15,     71,    653 );
		APC_TABLE_ROW (  8,      4,      5,      9,     45,    358 );
		APC_TABLE_ROW (  9,      3,      4,      7,     30,    202 );
		APC_TABLE_ROW ( 10,      3,      4,      5,     21,    118 );
		APC_TABLE_ROW ( 11,      2,      3,      4,     15,     71 );
		APC_TABLE_ROW ( 12,      2,      3,      4,     11,     45 );
		APC_TABLE_ROW ( 13,      2,      2,      3,      9,     30 );
		APC_TABLE_ROW ( 14,      2,      2,      3,      7,     21 );
		APC_TABLE_ROW ( 15,      1,      2,      2,      6,     15 );
		APC_TABLE_ROW ( 16,      1,      2,      2,      5,     11 );
		APC_TABLE_ROW ( 17,      1,      1,      2,      4,      9 );
		APC_TABLE_ROW ( 18,      1,      1,      2,      4,      7 );
		APC_TABLE_ROW ( 19,      1,      1,      1,      3,      6 );
		APC_TABLE_ROW ( 20,      1,      1,      1,      3,      5 );
	default:
		return APC_NA;
	}
}

/**
 * Calculate cutoff value for the adaptive proportion test
 *
 * @v min_entropy_per_sample	Min-entropy per sample
 * @ret cutoff			Cutoff value
 *
 * This is the cutoff value for the Adaptive Proportion Test defined
 * in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.
 */
static inline __attribute__ (( always_inline )) unsigned int
entropy_adaptive_proportion_cutoff ( min_entropy_t min_entropy_per_sample ) {
	unsigned int h;
	unsigned int n;
	unsigned int cutoff;

	/* Look up cutoff value in cutoff table */
	n = ADAPTIVE_PROPORTION_WINDOW_SIZE;
	h = ( min_entropy_per_sample / MIN_ENTROPY_SCALE );
	cutoff = entropy_adaptive_proportion_cutoff_lookup ( n, h );

	/* Fail unless cutoff value is a compile-time constant */
	build_assert ( __builtin_constant_p ( cutoff ) );

	/* Fail if cutoff value is N/A */
	build_assert ( cutoff != APC_NA );

	return cutoff;
}

/**
 * Calculate number of samples required for startup tests
 *
 * @v repetition_count_cutoff	Repetition count test cutoff value
 * @v adaptive_proportion_cutoff Adaptive proportion test cutoff value
 * @ret num_samples		Number of samples required
 *
 * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
 * that at least one full cycle of the continuous tests must be
 * performed at start-up.
 */
static inline __attribute__ (( always_inline )) unsigned int
entropy_startup_test_count ( unsigned int repetition_count_cutoff,
			     unsigned int adaptive_proportion_cutoff ) {
	unsigned int num_samples;

	/* At least max(N,C) samples shall be generated by the noise
	 * source for start-up testing.
	 */
	num_samples = repetition_count_cutoff;
	if ( num_samples < adaptive_proportion_cutoff )
		num_samples = adaptive_proportion_cutoff;
	build_assert ( __builtin_constant_p ( num_samples ) );

	return num_samples;
}

/**
 * Initialise entropy source
 *
 * @v source			Entropy source
 * @v min_entropy_per_sample	Min-entropy per sample
 *
 * The cutoff value calculations for the repetition count test and the
 * adaptive proportion test are provided as static inline functions
 * since the results will always be compile-time constants.
 */
static inline __attribute__ (( always_inline )) void
entropy_init ( struct entropy_source *source,
	       min_entropy_t min_entropy_per_sample ) {
	unsigned int repetition_count_cutoff;
	unsigned int adaptive_proportion_cutoff;
	unsigned int startup_test_count;

	/* Sanity check */
	build_assert ( min_entropy_per_sample > MIN_ENTROPY ( 0 ) );
	build_assert ( min_entropy_per_sample <=
		       MIN_ENTROPY ( 8 * sizeof ( noise_sample_t ) ) );

	/* Calculate test cutoff values */
	repetition_count_cutoff =
		entropy_repetition_count_cutoff ( min_entropy_per_sample );
	adaptive_proportion_cutoff =
		entropy_adaptive_proportion_cutoff ( min_entropy_per_sample );
	startup_test_count =
		entropy_startup_test_count ( repetition_count_cutoff,
					     adaptive_proportion_cutoff );

	/* Record min-entropy per sample and test cutoff values */
	source->min_entropy_per_sample = min_entropy_per_sample;
	source->repetition_count_test.cutoff = repetition_count_cutoff;
	source->adaptive_proportion_test.cutoff = adaptive_proportion_cutoff;
	source->startup_test.count = startup_test_count;
}

extern int entropy_enable ( struct entropy_source *source );
extern void entropy_disable ( struct entropy_source *source );
extern int get_noise ( struct entropy_source *source, noise_sample_t *noise );

#endif /* _IPXE_ENTROPY_H */