Alternative fix for CVE-2022-4304

This is about a timing leak in the topmost limb
of the internal result of RSA_private_decrypt,
before the padding check.

There are in fact at least three bugs together that
caused the timing leak:

First and probably most important is the fact that
the blinding did not use the constant time code path
at all when the RSA object was used for a private
decrypt, due to the fact that the Montgomery context
rsa->_method_mod_n was not set up early enough in
rsa_ossl_private_decrypt, when BN_BLINDING_create_param
needed it, and that was persisted as blinding->m_ctx,
although the RSA object creates the Montgomery context
just a bit later.

Then the infamous bn_correct_top was used on the
secret value right after the blinding was removed.

And finally the function BN_bn2binpad did not use
the constant-time code path since the BN_FLG_CONSTTIME
was not set on the secret value.

In order to address the first problem, this patch
makes sure that the rsa->_method_mod_n is initialized
right before the blinding context.

And to fix the second problem, we add a new utility
function bn_correct_top_consttime, a const-time
variant of bn_correct_top.

Together with the fact, that BN_bn2binpad is already
constant time if the flag BN_FLG_CONSTTIME is set,
this should eliminate the timing oracle completely.

In addition the no-asm variant may also have
branches that depend on secret values, because the last
invocation of bn_sub_words in bn_from_montgomery_word
had branches when the function is compiled by certain
gcc compiler versions, due to the clumsy coding style.

So additionally this patch stream-lined the no-asm
C-code in order to avoid branches where possible and
improve the resulting code quality.

Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/20282)

1 files changed, 13 insertions, 13 deletions

diff --git a/crypto/bn/bn_local.h b/crypto/bn/bn_local.h
index 981f57bc5b..fcd262b163 100644
--- a/crypto/bn/bn_local.h
+++ b/crypto/bn/bn_local.h
@@ -522,10 +522,10 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         ret =  (r);                     \
         BN_UMULT_LOHI(low,high,w,tmp);  \
         ret += (c);                     \
-        (c) =  (ret<(c))?1:0;           \
+        (c) =  (ret<(c));               \
         (c) += high;                    \
         ret += low;                     \
-        (c) += (ret<low)?1:0;           \
+        (c) += (ret<low);               \
         (r) =  ret;                     \
         }
 
@@ -534,7 +534,7 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         BN_UMULT_LOHI(low,high,w,ta);   \
         ret =  low + (c);               \
         (c) =  high;                    \
-        (c) += (ret<low)?1:0;           \
+        (c) += (ret<low);               \
         (r) =  ret;                     \
         }
 
@@ -550,10 +550,10 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         high=  BN_UMULT_HIGH(w,tmp);    \
         ret += (c);                     \
         low =  (w) * tmp;               \
-        (c) =  (ret<(c))?1:0;           \
+        (c) =  (ret<(c));               \
         (c) += high;                    \
         ret += low;                     \
-        (c) += (ret<low)?1:0;           \
+        (c) += (ret<low);               \
         (r) =  ret;                     \
         }
 
@@ -563,7 +563,7 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         high=  BN_UMULT_HIGH(w,ta);     \
         ret =  low + (c);               \
         (c) =  high;                    \
-        (c) += (ret<low)?1:0;           \
+        (c) += (ret<low);               \
         (r) =  ret;                     \
         }
 
@@ -596,10 +596,10 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         lt=(bl)*(lt); \
         m1=(bl)*(ht); \
         ht =(bh)*(ht); \
-        m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS((BN_ULONG)1); \
+        m=(m+m1)&BN_MASK2; ht += L2HBITS((BN_ULONG)(m < m1)); \
         ht+=HBITS(m); \
         m1=L2HBITS(m); \
-        lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \
+        lt=(lt+m1)&BN_MASK2; ht += (lt < m1); \
         (l)=lt; \
         (h)=ht; \
         }
@@ -616,7 +616,7 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         h*=h; \
         h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \
         m =(m&BN_MASK2l)<<(BN_BITS4+1); \
-        l=(l+m)&BN_MASK2; if (l < m) h++; \
+        l=(l+m)&BN_MASK2; h += (l < m); \
         (lo)=l; \
         (ho)=h; \
         }
@@ -630,9 +630,9 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         mul64(l,h,(bl),(bh)); \
  \
         /* non-multiply part */ \
-        l=(l+(c))&BN_MASK2; if (l < (c)) h++; \
+        l=(l+(c))&BN_MASK2; h += (l < (c)); \
         (c)=(r); \
-        l=(l+(c))&BN_MASK2; if (l < (c)) h++; \
+        l=(l+(c))&BN_MASK2; h += (l < (c)); \
         (c)=h&BN_MASK2; \
         (r)=l; \
         }
@@ -646,7 +646,7 @@ unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
         mul64(l,h,(bl),(bh)); \
  \
         /* non-multiply part */ \
-        l+=(c); if ((l&BN_MASK2) < (c)) h++; \
+        l+=(c); h += ((l&BN_MASK2) < (c)); \
         (c)=h&BN_MASK2; \
         (r)=l&BN_MASK2; \
         }
@@ -676,7 +676,7 @@ BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
                            int cl, int dl);
 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
                 const BN_ULONG *np, const BN_ULONG *n0, int num);
-
+void bn_correct_top_consttime(BIGNUM *a);
 BIGNUM *int_bn_mod_inverse(BIGNUM *in,
                            const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
                            int *noinv);