entropy.c File Reference

Entropy source. More...

#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <errno.h>
#include <ipxe/crypto.h>
#include <ipxe/hash_df.h>
#include <ipxe/entropy.h>

Go to the source code of this file.

Macros
#define	EPIPE_REPETITION_COUNT_TEST   __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )
#define	EINFO_EPIPE_REPETITION_COUNT_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )
#define	EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )
#define	EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )
#define	ADAPTIVE_PROPORTION_WINDOW_SIZE   64
	Window size for the adaptive proportion test. More...
#define	APC_N_H(n, h)   ( ( (n) << 8 ) | (h) )
	Combine adaptive proportion test window size and min-entropy. More...
#define	APC_TABLE_ROW(h, c16, c64, c256, c4096, c65536)
	Define a row of the adaptive proportion cutoff table. More...
#define	APC_NA   0
	Value used to represent "N/A" in adaptive proportion cutoff table. More...

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static	__attribute__ ((always_inline))
	Calculate cutoff value for the repetition count test. More...
static int	repetition_count_test (noise_sample_t sample)
	Perform repetition count test. More...
static int	adaptive_proportion_test (noise_sample_t sample)
	Perform adaptive proportion test. More...
static int	get_entropy (entropy_sample_t *entropy)
	Get entropy sample. More...
static uint32_t	make_next_nonce (void)
	Create next nonce value. More...
int	get_entropy_input_tmp (unsigned int num_samples, uint8_t *tmp, size_t tmp_len)
	Obtain entropy input temporary buffer. More...

Detailed Description

Entropy source.

This algorithm is designed to comply with ANS X9.82 Part 4 (April 2011 Draft) Section 13.3. This standard is unfortunately not freely available.

Definition in file entropy.c.

Macro Definition Documentation

EPIPE_REPETITION_COUNT_TEST

#define EPIPE_REPETITION_COUNT_TEST   __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )

Definition at line 44 of file entropy.c.

EINFO_EPIPE_REPETITION_COUNT_TEST

#define EINFO_EPIPE_REPETITION_COUNT_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )

Definition at line 46 of file entropy.c.

EPIPE_ADAPTIVE_PROPORTION_TEST

#define EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )

Definition at line 48 of file entropy.c.

EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST

#define EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )

Definition at line 50 of file entropy.c.

ADAPTIVE_PROPORTION_WINDOW_SIZE

#define ADAPTIVE_PROPORTION_WINDOW_SIZE   64

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.

Definition at line 156 of file entropy.c.

APC_N_H

#define APC_N_H	(		n,
			h
	)		( ( (n) << 8 ) | (h) )

Combine adaptive proportion test window size and min-entropy.

Parameters

n	N (window size)
h	H (min-entropy)

Return values

n_h	(N,H) combined value

Definition at line 165 of file entropy.c.

APC_TABLE_ROW

#define APC_TABLE_ROW	(		h,
			c16,
			c64,
			c256,
			c4096,
			c65536
	)

Value:

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;

Define a row of the adaptive proportion cutoff table.

Parameters

h	H (min-entropy)
c16	Cutoff for N=16
c64	Cutoff for N=64
c256	Cutoff for N=256
c4096	Cutoff for N=4096
c65536	Cutoff for N=65536

Definition at line 177 of file entropy.c.

APC_NA

#define APC_NA   0

Value used to represent "N/A" in adaptive proportion cutoff table.

Definition at line 185 of file entropy.c.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

__attribute__()

static __attribute__ ( (always_inline)  )

inlinestatic

Calculate cutoff value for the repetition count test.

Calculate number of samples required for startup tests.

Calculate cutoff value for the adaptive proportion test.

Look up value in adaptive proportion test cutoff table.

Return values

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.

Parameters

n	N (window size)
h	H (min-entropy)

Return values

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.

Return values

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.

Return values

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.

Definition at line 61 of file entropy.c.

                                 {
        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++;
        linker_assert ( ( cutoff >= max_repetitions ), rounding_error );

        /* 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.
         */
        linker_assert ( __builtin_constant_p ( cutoff ),
                        repetition_count_cutoff_not_constant );

        return cutoff;
}

References linker_assert, MIN_ENTROPY, and min_entropy_per_sample().

Referenced by get_entropy_input_tmp().

repetition_count_test()

static int repetition_count_test ( noise_sample_t  sample )

static

Perform repetition count test.

Parameters

sample

Noise sample

Return values

rc	Return status code

This is the Repetition Count Test defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.

Definition at line 104 of file entropy.c.

                                                           {
        static noise_sample_t most_recent_sample;
        static unsigned int repetition_count = 0;

        /* A = the most recently seen sample value
         * B = the number of times that value A has been seen in a row
         * C = the cutoff value above which the repetition test should fail
         */

        /* 1.  For each new sample processed:
         *
         * (Note that the test for "repetition_count > 0" ensures that
         * the initial value of most_recent_sample is treated as being
         * undefined.)
         */
        if ( ( sample == most_recent_sample ) && ( repetition_count > 0 ) ) {

                /* a) If the new sample = A, then B is incremented by one. */
                repetition_count++;

                /*    i.  If B >= C, then an error condition is raised
                 *        due to a failure of the test
                 */
                if ( repetition_count >= repetition_count_cutoff() )
                        return -EPIPE_REPETITION_COUNT_TEST;

        } else {

                /* b) Else:
                 *    i.  A = new sample
                 */
                most_recent_sample = sample;

                /*    ii. B = 1 */
                repetition_count = 1;
        }

        return 0;
}

References EPIPE_REPETITION_COUNT_TEST.

Referenced by get_entropy().

adaptive_proportion_test()

static int adaptive_proportion_test ( noise_sample_t  sample )

static

Perform adaptive proportion test.

Parameters

sample

Noise sample

Return values

rc	Return status code

This is 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.

Definition at line 264 of file entropy.c.

                                                              {
        static noise_sample_t current_counted_sample;
        static unsigned int sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE;
        static unsigned int repetition_count;

        /* A = the sample value currently being counted
         * B = the number of samples examined in this run of the test so far
         * N = the total number of samples that must be observed in
         *     one run of the test, also known as the "window size" of
         *     the test
         * B = the current number of times that S (sic) has been seen
         *     in the W (sic) samples examined so far
         * C = the cutoff value above which the repetition test should fail
         * W = the probability of a false positive: 2^-30
         */

        /* 1.  The entropy source draws the current sample from the
         *     noise source.
         *
         * (Nothing to do; we already have the current sample.)
         */

        /* 2.  If S = N, then a new run of the test begins: */
        if ( sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) {

                /* a.  A = the current sample */
                current_counted_sample = sample;

                /* b.  S = 0 */
                sample_count = 0;

                /* c. B = 0 */
                repetition_count = 0;

        } else {

                /* Else: (the test is already running)
                 * a.  S = S + 1
                 */
                sample_count++;

                /* b.  If A = the current sample, then: */
                if ( sample == current_counted_sample ) {

                        /* i.   B = B + 1 */
                        repetition_count++;

                        /* ii.  If S (sic) > C then raise an error
                         *      condition, because the test has
                         *      detected a failure
                         */
                        if ( repetition_count > adaptive_proportion_cutoff() )
                                return -EPIPE_ADAPTIVE_PROPORTION_TEST;

                }
        }

        return 0;
}

References ADAPTIVE_PROPORTION_WINDOW_SIZE, and EPIPE_ADAPTIVE_PROPORTION_TEST.

Referenced by get_entropy().

get_entropy()

static int get_entropy ( entropy_sample_t *  entropy )

static

Get entropy sample.

Return values

entropy	Entropy sample
rc	Return status code

This is the GetEntropy function defined in ANS X9.82 Part 2 (October 2011 Draft) Section 6.5.1.

Definition at line 333 of file entropy.c.

                                                     {
        static int rc = 0;
        noise_sample_t noise;

        /* Any failure is permanent */
        if ( rc != 0 )
                return rc;

        /* Get noise sample */
        if ( ( rc = get_noise ( &noise ) ) != 0 )
                return rc;

        /* Perform Repetition Count Test and Adaptive Proportion Test
         * as mandated by ANS X9.82 Part 2 (October 2011 Draft)
         * Section 8.5.2.1.1.
         */
        if ( ( rc = repetition_count_test ( noise ) ) != 0 )
                return rc;
        if ( ( rc = adaptive_proportion_test ( noise ) ) != 0 )
                return rc;

        /* We do not use any optional conditioning component */
        *entropy = noise;

        return 0;
}

References adaptive_proportion_test(), get_noise(), rc, and repetition_count_test().

Referenced by get_entropy_input_tmp().

make_next_nonce()

static uint32_t make_next_nonce ( void  )

static

Create next nonce value.

Return values

nonce

Nonce

This is the MakeNextNonce function defined in ANS X9.82 Part 4 (April 2011 Draft) Section 13.3.4.2.

Definition at line 393 of file entropy.c.

                                         {
        static uint32_t nonce;

        /* The simplest implementation of a nonce uses a large counter */
        nonce++;

        return nonce;
}

References nonce.

Referenced by get_entropy_input_tmp().

get_entropy_input_tmp()

int get_entropy_input_tmp	(	unsigned int	num_samples,
		uint8_t *	tmp,
		size_t	tmp_len
	)

Obtain entropy input temporary buffer.

Parameters

num_samples	Number of entropy samples
tmp	Temporary buffer
tmp_len	Length of temporary buffer

Return values

rc	Return status code

This is (part of) 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.

To minimise code size, the number of samples required is calculated at compilation time.

Definition at line 419 of file entropy.c.

                                             {
        static unsigned int startup_tested = 0;
        struct {
                uint32_t nonce;
                entropy_sample_t sample;
        } __attribute__ (( packed )) data;;
        uint8_t df_buf[tmp_len];
        unsigned int i;
        int rc;

        /* Enable entropy gathering */
        if ( ( rc = entropy_enable() ) != 0 )
                return rc;

        /* Perform mandatory startup tests, if not yet performed */
        for ( ; startup_tested < startup_test_count() ; startup_tested++ ) {
                if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
                        goto err_get_entropy;
        }

        /* 3.  entropy_total = 0
         *
         * (Nothing to do; the number of entropy samples required has
         * already been precalculated.)
         */

        /* 4.  tmp = a fixed n-bit value, such as 0^n */
        memset ( tmp, 0, tmp_len );

        /* 5.  While ( entropy_total < min_entropy ) */
        while ( num_samples-- ) {
                /* 5.1.  ( status, entropy_bitstring, assessed_entropy )
                 *       = GetEntropy()
                 * 5.2.  If status indicates an error, return ( status, Null )
                 */
                if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
                        goto err_get_entropy;

                /* 5.3.  nonce = MakeNextNonce() */
                data.nonce = make_next_nonce();

                /* 5.4.  tmp = tmp XOR
                 *             df ( ( nonce || entropy_bitstring ), n )
                 */
                hash_df ( &entropy_hash_df_algorithm, &data, sizeof ( data ),
                          df_buf, sizeof ( df_buf ) );
                for ( i = 0 ; i < tmp_len ; i++ )
                        tmp[i] ^= df_buf[i];

                /* 5.5.  entropy_total = entropy_total + assessed_entropy
                 *
                 * (Nothing to do; the number of entropy samples
                 * required has already been precalculated.)
                 */
        }

        /* Disable entropy gathering */
        entropy_disable();

        return 0;

 err_get_entropy:
        entropy_disable();
        return rc;
}

References __attribute__(), data, entropy_disable(), entropy_enable(), entropy_hash_df_algorithm, get_entropy(), hash_df(), make_next_nonce(), memset(), nonce, num_samples, rc, tmp, and tmp_len.