Remove a secret-dependent branch in Montgomery multiplication
In mpi_montmul, an auxiliary function for modular
exponentiation (mbedtls_mpi_mod_exp) that performs Montgomery
multiplication, the last step is a conditional subtraction to force
the result into the correct range. The current implementation uses a
branch and therefore may leak information about secret data to an
adversary who can observe what branch is taken through a side channel.
Avoid this potential leak by always doing the same subtraction and
doing a contant-trace conditional assignment to set the result.
Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
diff --git a/library/bignum.c b/library/bignum.c
index c6948d6..ef8344f 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1765,12 +1765,15 @@
memcpy( A->p, d, ( n + 1 ) * ciL );
/* If A >= N then A -= N. Do the subtraction unconditionally to prevent
- * timing attacks. Modify T as a side effect. */
- if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
- mpi_sub_hlp( n, N->p, A->p );
- else
- /* prevent timing attacks */
- mpi_sub_hlp( n, A->p, T->p );
+ * timing attacks. */
+ /* Set d to A + (2^biL)^n - N. */
+ d[n] += 1;
+ mpi_sub_hlp( n, N->p, d );
+ /* Now d - (2^biL)^n = A - N so d >= (2^biL)^n iff A >= N.
+ * So we want to copy the result of the subtraction iff d->p[n] != 0.
+ * Note that d->p[n] is either 0 or 1 since A - N <= N <= (2^biL)^n. */
+ mpi_safe_cond_assign( n + 1, A->p, d, d[n] );
+ A->p[n] = 0;
}
/*