commit b764ee1603bc03d3838ed5814cd1da6940a92fac
author Janos Follath <janos.follath@arm.com> Tue Oct 04 14:00:09 2022 +0100
committer Janos Follath <janos.follath@arm.com> Tue Nov 22 15:04:10 2022 +0000
tree 55f609d13634b983ddf4552d9a4015a4747eae18
parent 8e7d6a03869e4578c16d98bcc7309a09df4dc776

mpi_exp_mod: protect out of window zeroes

Out of window zeroes were doing squaring on the output variable
directly. This leaks the position of windows and the out of window
zeroes.

Loading the output variable from the table in constant time removes this
leakage.

Signed-off-by: Janos Follath <janos.follath@arm.com>

library/bignum.c

diff --git a/library/bignum.c b/library/bignum.c
index 1c42ef2..2ba6b7c 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1975,6 +1975,7 @@
     size_t bufsize, nbits;
     mbedtls_mpi_uint ei, mm, state;
     mbedtls_mpi RR, T, W[ ( 1 << MBEDTLS_MPI_WINDOW_SIZE ) + 1 ], WW, Apos;
+    const size_t w_count = sizeof( W ) / sizeof( W[0] );
     int neg;
 
     MPI_VALIDATE_RET( X != NULL );
@@ -2026,7 +2027,7 @@
      * lookup. From this point on we need to use the table entry in each
      * calculation, this makes it safe to use simple assignment.
      */
-    const size_t x_index = sizeof( W ) / sizeof( W[0] ) - 1;
+    const size_t x_index = w_count - 1;
     W[x_index] = *X;
 
     /*
@@ -2137,7 +2138,8 @@
             /*
              * out of window, square W[x_index]
              */
-            mpi_montmul( &W[x_index], &W[x_index], N, mm, &T );
+            MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, x_index ) );
+            mpi_montmul( &W[x_index], &WW, N, mm, &T );
             continue;
         }
 
@@ -2155,12 +2157,15 @@
              * W[x_index] = W[x_index]^wsize R^-1 mod N
              */
             for( i = 0; i < wsize; i++ )
-                mpi_montmul( &W[x_index], &W[x_index], N, mm, &T );
+            {
+                MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, x_index ) );
+                mpi_montmul( &W[x_index], &WW, N, mm, &T );
+            }
 
             /*
              * W[x_index] = W[x_index] * W[wbits] R^-1 mod N
              */
-            MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
+            MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, wbits ) );
             mpi_montmul( &W[x_index], &WW, N, mm, &T );
 
             state--;
@@ -2174,12 +2179,16 @@
      */
     for( i = 0; i < nbits; i++ )
     {
-        mpi_montmul( &W[x_index], &W[x_index], N, mm, &T );
+        MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, x_index ) );
+        mpi_montmul( &W[x_index], &WW, N, mm, &T );
 
         wbits <<= 1;
 
         if( ( wbits & ( one << wsize ) ) != 0 )
-            mpi_montmul( &W[x_index], &W[1], N, mm, &T );
+        {
+            MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, 1 ) );
+            mpi_montmul( &W[x_index], &WW, N, mm, &T );
+        }
     }
 
     /*