[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 <mcb30@ipxe.org>

3 files changed, 94 insertions, 0 deletions

diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c
index ac9670ef6..656f979e5 100644
--- a/src/crypto/bigint.c
+++ b/src/crypto/bigint.c
@@ -51,6 +51,31 @@ 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
  *
  * @v multiplicand0	Element 0 of big integer to be multiplied
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index 820d306b8..3dc344dff 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -190,6 +190,19 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 	} 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
  *
  * @v multiplicand	Big integer to be multiplied
@@ -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 484c59134..f09d7c76a 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,
@@ -431,6 +441,42 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
 	} 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
  *
  * @v multiplicand	Big integer to be multiplied
@@ -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 ) );