Fix a SCA leak using BN_bn2bin()

BN_bn2bin() is not constant-time and leaks the number of bits in the
processed BIGNUM.

The specialized methods in ecp_nistp224.c, ecp_nistp256.c and
ecp_nistp521.c internally used BN_bn2bin() to convert scalars into the
internal fixed length representation.

This can leak during ECDSA/ECDH key generation or handling the nonce
while generating an ECDSA signature, when using these implementations.
The amount and risk of leaked information useful for a SCA attack
varies for each of the three curves, as it depends mainly on the
ratio between the bitlength of the curve subgroup order (governing the
size of the secret nonce/key) and the limb size for the internal BIGNUM
representation (which depends on the compilation target architecture).

To fix this, we replace BN_bn2bin() with BN_bn2binpad(), bounding the
output length to the width of the internal representation buffer: this
length is public.

Internally the final implementation of both BN_bn2binpad() and
BN_bn2bin() already has masking in place to avoid leaking bn->top
through memory access patterns.
Memory access pattern still leaks bn->dmax, the size of the lazily
allocated buffer for representing the BIGNUM, which is inevitable with
the current BIGNUM architecture: reading past bn->dmax would be an
out-of-bound read.
As such, it's the caller responsibility to ensure that bn->dmax does not
leak secret information, by explicitly expanding the internal BIGNUM
buffer to a public value sufficient to avoid any lazy reallocation
while manipulating it: this is already done at the top level alongside
setting the BN_FLG_CONSTTIME.

Finally, the internal implementation of BN_bn2binpad() indirectly calls
BN_num_bits() via BN_num_bytes(): the current implementation of
BN_num_bits() can leak information to a SCA attacker, and is addressed
in the next commit.

Thanks to David Schrammel and Samuel Weiser for reporting this issue
through responsible disclosure.

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Bernd Edlinger <bernd.edlinger@hotmail.de>
(Merged from https://github.com/openssl/openssl/pull/9511)

(cherry picked from commit 805315d3a20f7274195eed75b06c391dacf3b197)

diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c
index 025273a1444087f708a1ab43a63da1b8fd25759a..a3ac109a6a64221a437d770da4fdf46de42ab18f 100644 (file)
--- a/crypto/ec/ecp_nistp224.c
+++ b/crypto/ec/ecp_nistp224.c
@@ -339,8 +339,6 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
     felem_bytearray b_out;
     unsigned num_bytes;
 
-    /* BN_bn2bin eats leading zeroes */
-    memset(b_out, 0, sizeof(b_out));
     num_bytes = BN_num_bytes(bn);
     if (num_bytes > sizeof(b_out)) {
         ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
@@ -350,7 +348,7 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
         ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
         return 0;
     }
-    num_bytes = BN_bn2bin(bn, b_in);
+    num_bytes = BN_bn2binpad(bn, b_in, sizeof(b_in));
     flip_endian(b_out, b_in, num_bytes);
     bin28_to_felem(out, b_out);
     return 1;
@@ -1501,9 +1499,9 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
                         ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
                         goto err;
                     }
-                    num_bytes = BN_bn2bin(tmp_scalar, tmp);
+                    num_bytes = BN_bn2binpad(tmp_scalar, tmp, sizeof(tmp));
                 } else
-                    num_bytes = BN_bn2bin(p_scalar, tmp);
+                    num_bytes = BN_bn2binpad(p_scalar, tmp, sizeof(tmp));
                 flip_endian(secrets[i], tmp, num_bytes);
                 /* precompute multiples */
                 if ((!BN_to_felem(x_out, p->X)) ||
@@ -1547,9 +1545,9 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
                 ECerr(EC_F_EC_GFP_NISTP224_POINTS_MUL, ERR_R_BN_LIB);
                 goto err;
             }
-            num_bytes = BN_bn2bin(tmp_scalar, tmp);
+            num_bytes = BN_bn2binpad(tmp_scalar, tmp, sizeof(tmp));
         } else
-            num_bytes = BN_bn2bin(scalar, tmp);
+            num_bytes = BN_bn2binpad(scalar, tmp, sizeof(tmp));
         flip_endian(g_secret, tmp, num_bytes);
         /* do the multiplication with generator precomputation */
         batch_mul(x_out, y_out, z_out,

diff --git a/crypto/ec/ecp_nistp256.c b/crypto/ec/ecp_nistp256.c
index a21e5f78fc9065370f1a3744b06d8cf1685a5fa1..64d5ef4d2cfab2d216df4087bd46aa545bb7e5ef 100644 (file)
--- a/crypto/ec/ecp_nistp256.c
+++ b/crypto/ec/ecp_nistp256.c
@@ -161,8 +161,6 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
     felem_bytearray b_out;
     unsigned num_bytes;
 
-    /* BN_bn2bin eats leading zeroes */
-    memset(b_out, 0, sizeof(b_out));
     num_bytes = BN_num_bytes(bn);
     if (num_bytes > sizeof(b_out)) {
         ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
@@ -172,7 +170,7 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
         ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
         return 0;
     }
-    num_bytes = BN_bn2bin(bn, b_in);
+    num_bytes = BN_bn2binpad(bn, b_in, sizeof(b_in));
     flip_endian(b_out, b_in, num_bytes);
     bin32_to_felem(out, b_out);
     return 1;
@@ -2128,9 +2126,9 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
                         ECerr(EC_F_EC_GFP_NISTP256_POINTS_MUL, ERR_R_BN_LIB);
                         goto err;
                     }
-                    num_bytes = BN_bn2bin(tmp_scalar, tmp);
+                    num_bytes = BN_bn2binpad(tmp_scalar, tmp, sizeof(tmp));
                 } else
-                    num_bytes = BN_bn2bin(p_scalar, tmp);
+                    num_bytes = BN_bn2binpad(p_scalar, tmp, sizeof(tmp));
                 flip_endian(secrets[i], tmp, num_bytes);
                 /* precompute multiples */
                 if ((!BN_to_felem(x_out, p->X)) ||
@@ -2176,9 +2174,9 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
                 ECerr(EC_F_EC_GFP_NISTP256_POINTS_MUL, ERR_R_BN_LIB);
                 goto err;
             }
-            num_bytes = BN_bn2bin(tmp_scalar, tmp);
+            num_bytes = BN_bn2binpad(tmp_scalar, tmp, sizeof(tmp));
         } else
-            num_bytes = BN_bn2bin(scalar, tmp);
+            num_bytes = BN_bn2binpad(scalar, tmp, sizeof(tmp));
         flip_endian(g_secret, tmp, num_bytes);
         /* do the multiplication with generator precomputation */
         batch_mul(x_out, y_out, z_out,

diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c
index 1e45f1eec54fafb02b02272e2f5072d5636bb3c0..d2d73526f6d7c98eed1c9da94018adb6476e5641 100644 (file)
--- a/crypto/ec/ecp_nistp521.c
+++ b/crypto/ec/ecp_nistp521.c
@@ -184,8 +184,6 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
     felem_bytearray b_out;
     unsigned num_bytes;
 
-    /* BN_bn2bin eats leading zeroes */
-    memset(b_out, 0, sizeof(b_out));
     num_bytes = BN_num_bytes(bn);
     if (num_bytes > sizeof(b_out)) {
         ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
@@ -195,7 +193,7 @@ static int BN_to_felem(felem out, const BIGNUM *bn)
         ECerr(EC_F_BN_TO_FELEM, EC_R_BIGNUM_OUT_OF_RANGE);
         return 0;
     }
-    num_bytes = BN_bn2bin(bn, b_in);
+    num_bytes = BN_bn2binpad(bn, b_in, sizeof(b_in));
     flip_endian(b_out, b_in, num_bytes);
     bin66_to_felem(out, b_out);
     return 1;
@@ -1968,9 +1966,9 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r,
                         ECerr(EC_F_EC_GFP_NISTP521_POINTS_MUL, ERR_R_BN_LIB);
                         goto err;
                     }
-                    num_bytes = BN_bn2bin(tmp_scalar, tmp);
+                    num_bytes = BN_bn2binpad(tmp_scalar, tmp, sizeof(tmp));
                 } else
-                    num_bytes = BN_bn2bin(p_scalar, tmp);
+                    num_bytes = BN_bn2binpad(p_scalar, tmp, sizeof(tmp));
                 flip_endian(secrets[i], tmp, num_bytes);
                 /* precompute multiples */
                 if ((!BN_to_felem(x_out, p->X)) ||
@@ -2014,9 +2012,9 @@ int ec_GFp_nistp521_points_mul(const EC_GROUP *group, EC_POINT *r,
                 ECerr(EC_F_EC_GFP_NISTP521_POINTS_MUL, ERR_R_BN_LIB);
                 goto err;
             }
-            num_bytes = BN_bn2bin(tmp_scalar, tmp);
+            num_bytes = BN_bn2binpad(tmp_scalar, tmp, sizeof(tmp));
         } else
-            num_bytes = BN_bn2bin(scalar, tmp);
+            num_bytes = BN_bn2binpad(scalar, tmp, sizeof(tmp));
         flip_endian(g_secret, tmp, num_bytes);
         /* do the multiplication with generator precomputation */
         batch_mul(x_out, y_out, z_out,