Merge pull request #6512 from yanesca/extract_uint_table_lookup_core
Implement mbedtls_mpi_core_ct_uint_table_lookup()
diff --git a/library/bignum_core.c b/library/bignum_core.c
index b401fa3..b3bb3bc 100644
--- a/library/bignum_core.c
+++ b/library/bignum_core.c
@@ -540,4 +540,17 @@
return( ret );
}
+void mbedtls_mpi_core_ct_uint_table_lookup( mbedtls_mpi_uint *dest,
+ const mbedtls_mpi_uint *table,
+ size_t limbs,
+ size_t count,
+ size_t index )
+{
+ for( size_t i = 0; i < count; i++, table += limbs )
+ {
+ unsigned char assign = mbedtls_ct_size_bool_eq( i, index );
+ mbedtls_mpi_core_cond_assign( dest, table, limbs, assign );
+ }
+}
+
#endif /* MBEDTLS_BIGNUM_C */
diff --git a/library/bignum_core.h b/library/bignum_core.h
index 9a5b89f..ccccebb 100644
--- a/library/bignum_core.h
+++ b/library/bignum_core.h
@@ -452,4 +452,22 @@
int mbedtls_mpi_core_get_mont_r2_unsafe( mbedtls_mpi *X,
const mbedtls_mpi *N );
+/**
+ * Copy an MPI from a table without leaking the index.
+ *
+ * \param dest The destination buffer. This must point to a writable
+ * buffer of at least \p limbs limbs.
+ * \param table The address of the table. This must point to a readable
+ * array of \p count elements of \p limbs limbs each.
+ * \param limbs The number of limbs in each table entry.
+ * \param count The number of entries in \p table.
+ * \param index The (secret) table index to look up. This must be in the
+ * range `0 .. count-1`.
+ */
+void mbedtls_mpi_core_ct_uint_table_lookup( mbedtls_mpi_uint *dest,
+ const mbedtls_mpi_uint *table,
+ size_t limbs,
+ size_t count,
+ size_t index );
+
#endif /* MBEDTLS_BIGNUM_CORE_H */
diff --git a/scripts/mbedtls_dev/bignum_core.py b/scripts/mbedtls_dev/bignum_core.py
index 0d238e7..9929e13 100644
--- a/scripts/mbedtls_dev/bignum_core.py
+++ b/scripts/mbedtls_dev/bignum_core.py
@@ -69,6 +69,43 @@
for count in counts:
yield cls(input_hex, descr, count).create_test_case()
+class BignumCoreCTLookup(BignumCoreTarget, metaclass=ABCMeta):
+ """Test cases for mbedtls_mpi_core_ct_uint_table_lookup()."""
+ test_function = "mpi_core_ct_uint_table_lookup"
+ test_name = "Constant time MPI table lookup"
+
+ bitsizes = [
+ (32, "One limb"),
+ (192, "Smallest curve sized"),
+ (512, "Largest curve sized"),
+ (2048, "Small FF/RSA sized"),
+ (4096, "Large FF/RSA sized"),
+ ]
+
+ window_sizes = [0, 1, 2, 3, 4, 5, 6]
+
+ def __init__(self,
+ bitsize: int, descr: str, window_size: int) -> None:
+ self.bitsize = bitsize
+ self.bitsize_description = descr
+ self.window_size = window_size
+
+ def arguments(self) -> List[str]:
+ return [str(self.bitsize), str(self.window_size)]
+
+ def description(self) -> str:
+ return '{} - {} MPI with {} bit window'.format(
+ BignumCoreCTLookup.test_name,
+ self.bitsize_description,
+ self.window_size
+ )
+
+ @classmethod
+ def generate_function_tests(cls) -> Iterator[test_case.TestCase]:
+ for bitsize, bitsize_description in cls.bitsizes:
+ for window_size in cls.window_sizes:
+ yield (cls(bitsize, bitsize_description, window_size)
+ .create_test_case())
class BignumCoreOperation(bignum_common.OperationCommon, BignumCoreTarget, metaclass=ABCMeta):
#pylint: disable=abstract-method
diff --git a/tests/suites/test_suite_bignum_core.function b/tests/suites/test_suite_bignum_core.function
index 57c2f37..d5d58d8 100644
--- a/tests/suites/test_suite_bignum_core.function
+++ b/tests/suites/test_suite_bignum_core.function
@@ -941,3 +941,54 @@
mbedtls_mpi_free( &RR_REF );
}
/* END_CASE */
+
+/* BEGIN_CASE */
+void mpi_core_ct_uint_table_lookup( int bitlen, int window_size )
+{
+ size_t limbs = BITS_TO_LIMBS( bitlen );
+ size_t count = ( (size_t) 1 ) << window_size;
+
+ mbedtls_mpi_uint *table = NULL;
+ mbedtls_mpi_uint *dest = NULL;
+
+ ASSERT_ALLOC( table, limbs * count );
+ ASSERT_ALLOC( dest, limbs );
+
+ /*
+ * Fill the table with a unique counter so that differences are easily
+ * detected. (And have their relationship to the index relatively non-trivial just
+ * to be sure.)
+ */
+ for( size_t i = 0; i < count * limbs; i++ )
+ {
+ table[i] = ~i - 1;
+ }
+
+ for( size_t i = 0; i < count; i++ )
+ {
+ mbedtls_mpi_uint *current = table + i * limbs;
+ memset( dest, 0x00, limbs * sizeof( *dest ) );
+
+ /*
+ * We shouldn't leak anything through timing.
+ * We need to set these in every loop as we need to make the loop
+ * variable public for the loop head and the buffers for comparison.
+ */
+ TEST_CF_SECRET( &i, sizeof( i ) );
+ TEST_CF_SECRET( dest, limbs * sizeof( *dest ) );
+ TEST_CF_SECRET( table, count * limbs * sizeof( *table ) );
+
+ mbedtls_mpi_core_ct_uint_table_lookup( dest, table, limbs, count, i );
+
+ TEST_CF_PUBLIC( dest, limbs * sizeof( *dest ) );
+ TEST_CF_PUBLIC( table, count * limbs * sizeof( *table ) );
+ ASSERT_COMPARE( dest, limbs * sizeof( *dest ),
+ current, limbs * sizeof( *current ) );
+ TEST_CF_PUBLIC( &i, sizeof( i ) );
+ }
+
+exit:
+ mbedtls_free(table);
+ mbedtls_free(dest);
+}
+/* END_CASE */