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" )

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static void	repetition_count_test_init (struct entropy_source *source)
	Initialise repetition count test. More...
static int	repetition_count_test (struct entropy_source *source, noise_sample_t sample)
	Perform repetition count test. More...
static void	adaptive_proportion_test_init (struct entropy_source *source)
	Initialise adaptive proportion test. More...
static int	adaptive_proportion_test (struct entropy_source *source, noise_sample_t sample)
	Perform adaptive proportion test. More...
static int	get_entropy (struct entropy_source *source, entropy_sample_t *entropy)
	Get entropy sample. More...
static void	startup_test_init (struct entropy_source *source)
	Initialise startup test. More...
static int	startup_test (struct entropy_source *source)
	Perform startup test. More...
int	entropy_enable (struct entropy_source *source)
	Enable entropy gathering. More...
static int	entropy_enable_and_test (struct entropy_source *source)
	Enable and test entropy source. More...
static int	entropy_enable_working (struct entropy_source **source)
	Enable first working entropy source. More...
void	entropy_disable (struct entropy_source *source)
	Disable entropy gathering. More...
static uint32_t	make_next_nonce (void)
	Create next nonce value. More...
int	get_entropy_input_tmp (min_entropy_t min_entropy, uint8_t *tmp, size_t tmp_len)
	Obtain entropy input temporary buffer. More...
	REQUIRING_SYMBOL (entropy_enable)
	REQUIRE_OBJECT (config_entropy)

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.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

repetition_count_test_init()

static void repetition_count_test_init ( struct entropy_source *  source )

static

Initialise repetition count test.

Parameters

source

Entropy source

Definition at line 58 of file entropy.c.

                                                                         {
        struct entropy_repetition_count_test *test =
                &source->repetition_count_test;

        /* Sanity checks */
        assert ( test->repetition_count == 0 );
        assert ( test->cutoff > 0 );
}

References assert(), entropy_source::repetition_count_test, and test.

Referenced by entropy_enable().

repetition_count_test()

static int repetition_count_test ( struct entropy_source *  source, noise_sample_t  sample  )

static

Perform repetition count test.

Parameters

source	Entropy source
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 77 of file entropy.c.

                                                           {
        struct entropy_repetition_count_test *test =
                &source->repetition_count_test;

        /* 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 == test->most_recent_sample ) &&
             ( test->repetition_count > 0 ) ) {

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

                /*    i.  If B >= C, then an error condition is raised
                 *        due to a failure of the test
                 */
                if ( test->repetition_count >= test->cutoff ) {
                        DBGC ( source, "ENTROPY %s excessively repeated "
                               "value %d (%d/%d)\n", source->name, sample,
                               test->repetition_count, test->cutoff );
                        return -EPIPE_REPETITION_COUNT_TEST;
                }

        } else {

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

                /*    ii. B = 1 */
                test->repetition_count = 1;
        }

        return 0;
}

References DBGC, EPIPE_REPETITION_COUNT_TEST, entropy_source::name, entropy_source::repetition_count_test, and test.

Referenced by get_entropy().

adaptive_proportion_test_init()

static void adaptive_proportion_test_init ( struct entropy_source *  source )

static

Initialise adaptive proportion test.

Parameters

source

Entropy source

Definition at line 128 of file entropy.c.

                                                                            {
        struct entropy_adaptive_proportion_test *test =
                &source->adaptive_proportion_test;

        /* Sanity checks */
        assert ( test->sample_count == 0 );
        assert ( test->repetition_count == 0 );
        assert ( test->cutoff > 0 );

        /* Ensure that a new test run starts immediately */
        test->sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE;
}

References entropy_source::adaptive_proportion_test, ADAPTIVE_PROPORTION_WINDOW_SIZE, assert(), and test.

Referenced by entropy_enable().

adaptive_proportion_test()

static int adaptive_proportion_test ( struct entropy_source *  source, noise_sample_t  sample  )

static

Perform adaptive proportion test.

Parameters

source	Entropy source
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 151 of file entropy.c.

                                                              {
        struct entropy_adaptive_proportion_test *test =
                &source->adaptive_proportion_test;

        /* A = the sample value currently being counted
         * S = 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 ( test->sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) {

                /* a.  A = the current sample */
                test->current_counted_sample = sample;

                /* b.  S = 0 */
                test->sample_count = 0;

                /* c. B = 0 */
                test->repetition_count = 0;

        } else {

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

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

                        /* i.   B = B + 1 */
                        test->repetition_count++;

                        /* ii.  If S (sic) > C then raise an error
                         *      condition, because the test has
                         *      detected a failure
                         */
                        if ( test->repetition_count > test->cutoff ) {
                                DBGC ( source, "ENTROPY %s excessively "
                                       "repeated value %d (%d/%d)\n",
                                       source->name, sample,
                                       test->repetition_count, test->cutoff );
                                return -EPIPE_ADAPTIVE_PROPORTION_TEST;
                        }
                }
        }

        return 0;
}

References entropy_source::adaptive_proportion_test, ADAPTIVE_PROPORTION_WINDOW_SIZE, DBGC, EPIPE_ADAPTIVE_PROPORTION_TEST, entropy_source::name, and test.

Referenced by get_entropy().

get_entropy()

static int get_entropy ( struct entropy_source *  source, entropy_sample_t *  entropy  )

static

Get entropy sample.

Parameters

source

Entropy source

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 225 of file entropy.c.

                                                     {
        noise_sample_t noise;
        int rc;

        /* Any failure is permanent */
        if ( ( rc = source->rc ) != 0 )
                goto err_broken;

        /* Get noise sample */
        if ( ( rc = get_noise ( source, &noise ) ) != 0 )
                goto err_get_noise;

        /* 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 ( source, noise ) ) != 0 )
                goto err_repetition_count_test;
        if ( ( rc = adaptive_proportion_test ( source, noise ) ) != 0 )
                goto err_adaptive_proportion_test;

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

        return 0;

 err_adaptive_proportion_test:
 err_repetition_count_test:
 err_get_noise:
        source->rc = rc;
 err_broken:
        return rc;
}

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

Referenced by get_entropy_input_tmp(), and startup_test().

startup_test_init()

static void startup_test_init ( struct entropy_source *  source )

static

Initialise startup test.

Parameters

source

Entropy source

Definition at line 265 of file entropy.c.

                                                                {
        struct entropy_startup_test *test = &source->startup_test;

        /* Sanity check */
        assert ( test->tested == 0 );
        assert ( test->count > 0 );
}

References assert(), entropy_source::startup_test, and test.

Referenced by entropy_enable().

startup_test()

static int startup_test ( struct entropy_source *  source )

static

Perform startup test.

Parameters

source

Entropy source

Return values

rc	Return status code

Definition at line 279 of file entropy.c.

                                                          {
        struct entropy_startup_test *test = &source->startup_test;
        entropy_sample_t sample;
        int rc;

        /* Perform mandatory number of startup tests */
        for ( ; test->tested < test->count ; test->tested++ ) {
                if ( ( rc = get_entropy ( source, &sample ) ) != 0 ) {
                        DBGC ( source, "ENTROPY %s failed: %s\n",
                               source->name, strerror ( rc ) );
                        return rc;
                }
        }

        return 0;
}

References DBGC, get_entropy(), entropy_source::name, rc, entropy_source::startup_test, strerror(), and test.

Referenced by entropy_enable_and_test().

entropy_enable()

int entropy_enable

(

struct entropy_source *

source

)

Enable entropy gathering.

Parameters

source

Entropy source

Return values

rc	Return status code

Definition at line 302 of file entropy.c.

                                                     {
        int rc;

        /* Refuse to enable a previously failed source */
        if ( ( rc = source->rc ) != 0 )
                return rc;

        /* Enable entropy source */
        if ( ( rc = source->enable() ) != 0 ) {
                DBGC ( source, "ENTROPY %s could not enable: %s\n",
                       source->name, strerror ( rc ) );
                source->rc = rc;
                return rc;
        }

        /* Sanity check */
        assert ( source->min_entropy_per_sample > 0 );

        /* Initialise test state if this source has not previously been used */
        if ( source->startup_test.tested == 0 ) {
                repetition_count_test_init ( source );
                adaptive_proportion_test_init ( source );
                startup_test_init ( source );
        }

        DBGC ( source, "ENTROPY %s enabled\n", source->name );
        return 0;
}

References adaptive_proportion_test_init(), assert(), DBGC, entropy_source::enable, entropy_source::min_entropy_per_sample, entropy_source::name, entropy_source::rc, rc, repetition_count_test_init(), entropy_source::startup_test, startup_test_init(), strerror(), and entropy_startup_test::tested.

Referenced by entropy_enable_and_test(), and entropy_sample().

entropy_enable_and_test()

static int entropy_enable_and_test ( struct entropy_source *  source )

static

Enable and test entropy source.

Parameters

source

Entropy source

Return values

rc	Return status code

Definition at line 337 of file entropy.c.

                                                                     {
        int rc;

        /* Enable source */
        if ( ( rc = entropy_enable ( source ) ) != 0 )
                goto err_enable;

        /* Test source */
        if ( ( rc = startup_test ( source ) ) != 0 )
                goto err_test;

        DBGC ( source, "ENTROPY %s passed %d startup tests\n",
               source->name, source->startup_test.count );
        return 0;

 err_test:
        entropy_disable ( source );
 err_enable:
        assert ( source->rc == rc );
        return rc;
}

References assert(), entropy_startup_test::count, DBGC, entropy_disable(), entropy_enable(), entropy_source::name, entropy_source::rc, rc, entropy_source::startup_test, and startup_test().

Referenced by entropy_enable_working().

entropy_enable_working()

static int entropy_enable_working ( struct entropy_source **  source )

static

Enable first working entropy source.

Parameters

source

Entropy source to fill in

Return values

rc	Return status code

Definition at line 365 of file entropy.c.

                                                                     {
        int rc;

        /* Find the first working source */
        rc = -ENOENT;
        for_each_table_entry ( *source, ENTROPY_SOURCES ) {
                if ( ( rc = entropy_enable_and_test ( *source ) ) == 0 )
                        return 0;
        }

        DBGC ( *source, "ENTROPY has no working sources: %s\n",
               strerror ( rc ) );
        return rc;
}

References DBGC, ENOENT, entropy_enable_and_test(), ENTROPY_SOURCES, for_each_table_entry, rc, and strerror().

Referenced by get_entropy_input_tmp().

entropy_disable()

void entropy_disable

(

struct entropy_source *

source

)

Disable entropy gathering.

Parameters

source

Entropy source

Definition at line 385 of file entropy.c.

                                                       {

        /* Disable entropy gathering, if applicable */
        if ( source->disable )
                source->disable();

        DBGC ( source, "ENTROPY %s disabled\n", source->name );
}

References DBGC, entropy_source::disable, and entropy_source::name.

Referenced by entropy_enable_and_test(), entropy_sample(), and 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 402 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	(	min_entropy_t	min_entropy,
		uint8_t *	tmp,
		size_t	tmp_len
	)

Obtain entropy input temporary buffer.

Parameters

min_entropy	Min-entropy required
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.

Definition at line 425 of file entropy.c.

                                             {
        struct entropy_source *source;
        struct {
                uint32_t nonce;
                entropy_sample_t sample;
        } __attribute__ (( packed )) data;;
        uint8_t df_buf[tmp_len];
        min_entropy_t entropy_total;
        unsigned int num_samples;
        unsigned int i;
        int rc;

        /* Enable entropy gathering */
        if ( ( rc = entropy_enable_working ( &source ) ) != 0 )
                goto err_enable_working;

        /* Sanity checks */
        assert ( source->startup_test.count > 0 );
        assert ( source->startup_test.tested >= source->startup_test.count );

        /* 3.  entropy_total = 0 */
        entropy_total = MIN_ENTROPY ( 0 );

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

        /* 5.  While ( entropy_total < min_entropy ) */
        for ( num_samples = 0 ; entropy_total < min_entropy ; num_samples++ ) {
                /* 5.1.  ( status, entropy_bitstring, assessed_entropy )
                 *       = GetEntropy()
                 * 5.2.  If status indicates an error, return ( status, Null )
                 */
                if ( ( rc = get_entropy ( source, &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 */
                entropy_total += source->min_entropy_per_sample;
        }

        /* Disable entropy gathering */
        entropy_disable ( source );

        DBGC ( source, "ENTROPY %s gathered %d bits in %d samples\n",
               source->name, ( min_entropy / MIN_ENTROPY_SCALE ), num_samples );
        return 0;

 err_get_entropy:
        entropy_disable ( source );
        assert ( source->rc == rc );
 err_enable_working:
        return rc;
}

References __attribute__, assert(), entropy_startup_test::count, data, DBGC, entropy_disable(), entropy_enable_working(), entropy_hash_df_algorithm, get_entropy(), hash_df(), make_next_nonce(), memset(), MIN_ENTROPY, entropy_source::min_entropy_per_sample, MIN_ENTROPY_SCALE, entropy_source::name, nonce, entropy_source::rc, rc, entropy_source::startup_test, entropy_startup_test::tested, and tmp.

Referenced by get_entropy_input().

REQUIRING_SYMBOL()

REQUIRING_SYMBOL

(

entropy_enable

)

REQUIRE_OBJECT()

REQUIRE_OBJECT

(

config_entropy

)