From bac13ba1f658a1e742b9ceb958e670086affebe7 Mon Sep 17 00:00:00 2001 From: Michael Brown Date: Fri, 19 Jan 2024 12:34:02 +0000 Subject: [crypto] Add bigint_swap() to conditionally swap big integers Add a helper function bigint_swap() that can be used to conditionally swap a pair of big integers in constant time. Signed-off-by: Michael Brown --- src/crypto/bigint.c | 25 ++++++++++++++++++++++ src/include/ipxe/bigint.h | 15 +++++++++++++ src/tests/bigint_test.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 94 insertions(+) diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c index ac9670ef..656f979e 100644 --- a/src/crypto/bigint.c +++ b/src/crypto/bigint.c @@ -50,6 +50,31 @@ static struct profiler bigint_mod_multiply_rescale_profiler __profiler = static struct profiler bigint_mod_multiply_subtract_profiler __profiler = { .name = "bigint_mod_multiply.subtract" }; +/** + * Conditionally swap big integers (in constant time) + * + * @v first0 Element 0 of big integer to be conditionally swapped + * @v second0 Element 0 of big integer to be conditionally swapped + * @v size Number of elements in big integers + * @v swap Swap first and second big integers + */ +void bigint_swap_raw ( bigint_element_t *first0, bigint_element_t *second0, + unsigned int size, int swap ) { + bigint_element_t mask; + bigint_element_t xor; + unsigned int i; + + /* Construct mask */ + mask = ( ( bigint_element_t ) ( ! swap ) - 1 ); + + /* Conditionally swap elements */ + for ( i = 0 ; i < size ; i++ ) { + xor = ( mask & ( first0[i] ^ second0[i] ) ); + first0[i] ^= xor; + second0[i] ^= xor; + } +} + /** * Perform modular multiplication of big integers * diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 820d306b..3dc344df 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -189,6 +189,19 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); bigint_shrink ( (source), (dest) ); \ } while ( 0 ) +/** + * Conditionally swap big integers (in constant time) + * + * @v first Big integer to be conditionally swapped + * @v second Big integer to be conditionally swapped + * @v swap Swap first and second big integers + */ +#define bigint_swap( first, second, swap ) do { \ + unsigned int size = bigint_size (first); \ + bigint_swap_raw ( (first)->element, (second)->element, size, \ + (swap) ); \ + } while ( 0 ) + /** * Multiply big integers * @@ -296,6 +309,8 @@ void bigint_grow_raw ( const bigint_element_t *source0, void bigint_shrink_raw ( const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size ); +void bigint_swap_raw ( bigint_element_t *first0, bigint_element_t *second0, + unsigned int size, int swap ); void bigint_multiply_raw ( const bigint_element_t *multiplicand0, unsigned int multiplicand_size, const bigint_element_t *multiplier0, diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c index 484c5913..f09d7c76 100644 --- a/src/tests/bigint_test.c +++ b/src/tests/bigint_test.c @@ -159,6 +159,16 @@ void bigint_copy_sample ( const bigint_element_t *source0, bigint_copy ( source, dest ); } +void bigint_swap_sample ( bigint_element_t *first0, bigint_element_t *second0, + unsigned int size, int swap ) { + bigint_t ( size ) *first __attribute__ (( may_alias )) + = ( ( void * ) first0 ); + bigint_t ( size ) *second __attribute__ (( may_alias )) + = ( ( void * ) second0 ); + + bigint_swap ( first, second, swap ); +} + void bigint_multiply_sample ( const bigint_element_t *multiplicand0, unsigned int multiplicand_size, const bigint_element_t *multiplier0, @@ -430,6 +440,42 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0, ok ( max_set_bit == (expected) ); \ } while ( 0 ) +/** + * Report result of big integer swap test + * + * @v first Big integer to be conditionally swapped + * @v second Big integer to be conditionally swapped + */ +#define bigint_swap_ok( first, second ) do { \ + static const uint8_t first_raw[] = first; \ + static const uint8_t second_raw[] = second; \ + uint8_t temp[ sizeof ( first_raw ) ]; \ + unsigned int size = bigint_required_size ( sizeof ( temp) ); \ + bigint_t ( size ) first_temp; \ + bigint_t ( size ) second_temp; \ + {} /* Fix emacs alignment */ \ + \ + assert ( sizeof ( first_raw ) == sizeof ( temp ) ); \ + assert ( sizeof ( second_raw ) == sizeof ( temp ) ); \ + bigint_init ( &first_temp, first_raw, sizeof ( first_raw ) ); \ + bigint_init ( &second_temp, second_raw, sizeof ( second_raw ) );\ + bigint_swap ( &first_temp, &second_temp, 0 ); \ + bigint_done ( &first_temp, temp, sizeof ( temp ) ); \ + ok ( memcmp ( temp, first_raw, sizeof ( temp ) ) == 0 ); \ + bigint_done ( &second_temp, temp, sizeof ( temp ) ); \ + ok ( memcmp ( temp, second_raw, sizeof ( temp ) ) == 0 ); \ + bigint_swap ( &first_temp, &second_temp, 1 ); \ + bigint_done ( &first_temp, temp, sizeof ( temp ) ); \ + ok ( memcmp ( temp, second_raw, sizeof ( temp ) ) == 0 ); \ + bigint_done ( &second_temp, temp, sizeof ( temp ) ); \ + ok ( memcmp ( temp, first_raw, sizeof ( temp ) ) == 0 ); \ + bigint_swap ( &first_temp, &second_temp, 1 ); \ + bigint_done ( &first_temp, temp, sizeof ( temp ) ); \ + ok ( memcmp ( temp, first_raw, sizeof ( temp ) ) == 0 ); \ + bigint_done ( &second_temp, temp, sizeof ( temp ) ); \ + ok ( memcmp ( temp, second_raw, sizeof ( temp ) ) == 0 ); \ + } while ( 0 ) + /** * Report result of big integer multiplication test * @@ -1373,6 +1419,14 @@ static void bigint_test_exec ( void ) { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff ), 1024 ); + bigint_swap_ok ( BIGINT ( 0x68, 0x65, 0x6c, 0x6c, 0x6f ), + BIGINT ( 0x77, 0x6f, 0x72, 0x6c, 0x64 ) ); + bigint_swap_ok ( BIGINT ( 0xc8, 0x1c, 0x31, 0xd7, 0x13, 0x69, 0x47, + 0x32, 0xb0, 0x0a, 0xf7, 0x2d, 0xb9, 0xc3, + 0x35, 0x96 ), + BIGINT ( 0x8b, 0x1d, 0x8f, 0x21, 0x76, 0x16, 0x4c, + 0xf8, 0xb2, 0x63, 0xed, 0x89, 0x5e, 0x6b, + 0x35, 0x7c ) ); bigint_multiply_ok ( BIGINT ( 0xf0 ), BIGINT ( 0xeb ), BIGINT ( 0xdc, 0x50 ) ); -- cgit v1.2.3-55-g7522