crypto: ecc - regularize scalar for scalar multiplication
Subsystems (2)
PATCH v2 1/1 crypto: ecc - regularize scalar for scalar multiplication
ecc_point_mult is supposed to be used with a regularized scalar, otherwise, it's possible to deduce the position of the top bit of the scalar with timing attack. This is important when the scalar is a private key.
ecc_point_mult is already using a regular algorithm (i.e. having an operation flow independent of the input scalar) but regularization step is not implemented.
Arrange scalar to always have fixed top bit by adding a multiple of the curve order (n).
References:
The constant time regularization step is based on micro-ecc by Kenneth MacKay and also referenced in the literature (Bernstein, D. J., & Lange, T. (2017). Montgomery curves and the Montgomery ladder. (Cryptology ePrint Archive; Vol. 2017/293). s.l.: IACR. Chapter 4.6.2.)
---
Changes from v1:
- No code changes, only description updates to be more informative.
crypto/ecc.c | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-)
crypto/ecc.c +12 -4
@@ -842,15 +842,23 @@ static void xycz_add_c(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime,static void ecc_point_mult (struct ecc_point *result,const struct ecc_point *point,const u64 *scalar, -u64 *initial_z,u64 *curve_prime, +u64 *initial_z,const struct ecc_curve *curve,unsigned int ndigits) {/* R0 and R1 */ u64 rx[2 ][ECC_MAX_DIGITS ];u64 ry[2 ][ECC_MAX_DIGITS ];u64 z[ECC_MAX_DIGITS ]; +u64 sk[2 ][ECC_MAX_DIGITS ]; +u64 *curve_prime = curve->p;int i, nb; -int num_bits =vli_num_bits (scalar, ndigits); +int num_bits; +int carry; + + carry =vli_add (sk[0 ], scalar, curve->n, ndigits); +vli_add (sk[1 ], sk[0 ], curve->n, ndigits); + scalar = sk[!carry]; + num_bits =sizeof (u64) * ndigits *8 +1 ;vli_set (rx[1 ], point->x, ndigits);vli_set (ry[1 ], point->y, ndigits);
@@ -1004,7 +1012,7 @@ int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits, goto out; } -ecc_point_mult (pk, &curve->g, priv,NULL , curve->p, ndigits); +ecc_point_mult (pk, &curve->g, priv,NULL , curve, ndigits);if (ecc_point_is_zero (pk)) { ret = -EAGAIN ; goto err_free_point;
@@ -1090,7 +1098,7 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, goto err_alloc_product; } -ecc_point_mult (product, pk, priv, rand_z, curve->p, ndigits); +ecc_point_mult (product, pk, priv, rand_z, curve, ndigits);ecc_swap_digits (product->x, secret, ndigits);
Signature · 1 line
2.11.0
Herbert Xu
maintainerQuoted 20 lines · Vitaly Chikunov
ecc_point_multis supposed to be used with a regularized scalar, otherwise, it's possible to deduce the position of the top bit of the scalar with timing attack. This is important when the scalar is a private key.
ecc_point_multis already using a regular algorithm (i.e. having an operation flow independent of the input scalar) but regularization step is not implemented.Arrange scalar to always have fixed top bit by adding a multiple of the curve order (n).
References:
The constant time regularization step is based on micro-ecc by Kenneth MacKay and also referenced in the literature (Bernstein, D. J., & Lange, T. (2017). Montgomery curves and the Montgomery ladder. (Cryptology ePrint Archive; Vol. 2017/293). s.l.: IACR. Chapter 4.6.2.)Signed-off-by Vitaly Chikunov <[email protected]>
Quoted 7 lines
---
Changes from v1:
- No code changes, only description updates to be more informative.crypto/ecc.c | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-)
Patch applied. Thanks.
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt