From 751c6e6100726b7159eac4d7bd011cb1fb177263 Mon Sep 17 00:00:00 2001
From: Tomas Mraz <tomas@openssl.org>
Date: Wed, 15 Jan 2025 18:27:02 +0100
Subject: [PATCH] Fix timing side-channel in ECDSA signature computation

There is a timing signal of around 300 nanoseconds when the top word of
the inverted ECDSA nonce value is zero. This can happen with significant
probability only for some of the supported elliptic curves. In particular
the NIST P-521 curve is affected. To be able to measure this leak, the
attacker process must either be located in the same physical computer or
must have a very fast network connection with low latency.

Attacks on ECDSA nonce are also known as Minerva attack.

Fixes CVE-2024-13176

Reviewed-by: Tim Hudson <tjh@openssl.org>
Reviewed-by: Neil Horman <nhorman@openssl.org>
Reviewed-by: Paul Dale <ppzgs1@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/26429)

(cherry picked from commit 63c40a66c5dc287485705d06122d3a6e74a6a203)
---
 crypto/bn/bn_exp.c      | 23 ++++++++++++++++-------
 crypto/ec/ec_lib.c      |  8 ++++----
 include/crypto/bn.h     |  3 +++
 include/openssl/bnerr.h |  1 +
 4 files changed, 24 insertions(+), 11 deletions(-)

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index 517e3c29fc..1f64f35cba 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -601,7 +601,7 @@ static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,
  * out by Colin Percival,
  * http://www.daemonology.net/hyperthreading-considered-harmful/)
  */
-int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+int bn_mod_exp_mont_fixed_top(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
                               const BIGNUM *m, BN_CTX *ctx,
                               BN_MONT_CTX *in_mont)
 {
@@ -618,12 +618,8 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     unsigned int t4 = 0;
 #endif
 
-    bn_check_top(a);
-    bn_check_top(p);
-    bn_check_top(m);
-
     if (!BN_is_odd(m)) {
-        BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME, BN_R_CALLED_WITH_EVEN_MODULUS);
+        BNerr(BN_F_BN_MOD_EXP_MONT_FIXED_TOP, BN_R_CALLED_WITH_EVEN_MODULUS);
         return 0;
     }
 
@@ -1141,7 +1137,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
             goto err;
     } else
 #endif
-    if (!BN_from_montgomery(rr, &tmp, mont, ctx))
+    if (!bn_from_mont_fixed_top(rr, &tmp, mont, ctx))
         goto err;
     ret = 1;
  err:
@@ -1155,6 +1151,19 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     return ret;
 }
 
+int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+                              const BIGNUM *m, BN_CTX *ctx,
+                              BN_MONT_CTX *in_mont)
+{
+    bn_check_top(a);
+    bn_check_top(p);
+    bn_check_top(m);
+    if (!bn_mod_exp_mont_fixed_top(rr, a, p, m, ctx, in_mont))
+        return 0;
+    bn_correct_top(rr);
+    return 1;
+}
+
 int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
 {
diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c
index 08db89fcee..9f0b480705 100644
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -12,8 +12,8 @@
 
 #include <openssl/err.h>
 #include <openssl/opensslv.h>
-
 #include "ec_local.h"
+#include "crypto/bn.h"
 
 /* functions for EC_GROUP objects */
 
@@ -1155,10 +1155,10 @@ static int ec_field_inverse_mod_ord(const EC_GROUP *group, BIGNUM *r,
     if (!BN_sub(e, group->order, e))
         goto err;
     /*-
-     * Exponent e is public.
-     * No need for scatter-gather or BN_FLG_CONSTTIME.
+     * Although the exponent is public we want the result to be
+     * fixed top.
      */
-    if (!BN_mod_exp_mont(r, x, e, group->order, ctx, group->mont_data))
+    if (!bn_mod_exp_mont_fixed_top(r, x, e, group->order, ctx, group->mont_data))
         goto err;
 
     ret = 1;
diff --git a/include/crypto/bn.h b/include/crypto/bn.h
index 250914c46a..8484047fd0 100644
--- a/include/crypto/bn.h
+++ b/include/crypto/bn.h
@@ -72,6 +72,9 @@ int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words);
  */
 int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                           BN_MONT_CTX *mont, BN_CTX *ctx);
+int bn_mod_exp_mont_fixed_top(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+                              const BIGNUM *m, BN_CTX *ctx,
+                              BN_MONT_CTX *in_mont);
 int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
                          BN_CTX *ctx);
 int bn_from_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
diff --git a/include/openssl/bnerr.h b/include/openssl/bnerr.h
index 5c83777f9f..f6aef13441 100644
--- a/include/openssl/bnerr.h
+++ b/include/openssl/bnerr.h
@@ -73,6 +73,7 @@ int ERR_load_BN_strings(void);
 # define BN_F_BN_STACK_PUSH                               148
 # define BN_F_BN_USUB                                     115
 # define BN_F_OSSL_BN_RSA_DO_UNBLIND                      151
+# define BN_F_BN_MOD_EXP_MONT_FIXED_TOP                   152
 
 /*
  * BN reason codes.
-- 
2.33.0

