From 0f18f07efe103718ca79f5a206a08c3a3cc6c410 Mon Sep 17 00:00:00 2001 From: Daiki Ueno Date: Fri, 2 Apr 2021 16:01:21 +0200 Subject: nettle: port upstream hardening of EC point multiplication Some internal functions used in point multiplications are known to misbehave if the scaler is out-of-range. This performs canonical reduction on scalers, before point multiplication. This ports the fixes from Nettle upstream to the bundled EC code. See the Nettle 3.7.2 release announcement for details: https://lists.lysator.liu.se/pipermail/nettle-bugs/2021/009458.html Signed-off-by: Daiki Ueno --- .gitignore | 3 ++- .x-sc_space_tab | 3 +++ devel/import-ecc-from-nettle.sh | 4 +++ lib/nettle/ecc/override/ecc-gostdsa-verify.c.diff | 19 ++++++++++++++ lib/nettle/ecc/override/ecc-internal.h.diff | 26 ++++++++++++++++++++ lib/nettle/ecc/override/ecc-mod-arith.c.diff | 19 ++++++++++++++ lib/nettle/ecc/override/eddsa-hash.c.diff | 30 +++++++++++++++++++++++ lib/nettle/ecc/override/gostdsa-vko.c.diff | 16 ++++++++++++ 8 files changed, 119 insertions(+), 1 deletion(-) create mode 100644 .x-sc_space_tab create mode 100644 lib/nettle/ecc/override/ecc-gostdsa-verify.c.diff create mode 100644 lib/nettle/ecc/override/ecc-internal.h.diff create mode 100644 lib/nettle/ecc/override/ecc-mod-arith.c.diff create mode 100644 lib/nettle/ecc/override/eddsa-hash.c.diff create mode 100644 lib/nettle/ecc/override/gostdsa-vko.c.diff diff --git a/.gitignore b/.gitignore index 2b23292693..fb11a657b4 100644 --- a/.gitignore +++ b/.gitignore @@ -235,7 +235,8 @@ lib/minitasn1/Makefile lib/minitasn1/Makefile.in lib/nettle/libcrypto.la lib/nettle/backport -lib/nettle/ecc +lib/nettle/ecc/* +!lib/nettle/ecc/override lib/opencdk/libminiopencdk.la lib/opencdk/Makefile lib/opencdk/Makefile.in diff --git a/.x-sc_space_tab b/.x-sc_space_tab new file mode 100644 index 0000000000..4311834933 --- /dev/null +++ b/.x-sc_space_tab @@ -0,0 +1,3 @@ +^lib/nettle/ecc/override/ecc-gostdsa-verify.c.diff +^lib/nettle/ecc/override/ecc-internal.h.diff +^lib/nettle/ecc/override/eddsa-hash.c.diff diff --git a/devel/import-ecc-from-nettle.sh b/devel/import-ecc-from-nettle.sh index 2ce6285d39..30b7c58a88 100755 --- a/devel/import-ecc-from-nettle.sh +++ b/devel/import-ecc-from-nettle.sh @@ -96,6 +96,10 @@ for f in $IMPORTS; do echo "Copying file $dst" fi cp $src $dst + if test -e $DST/override/$f.diff; then + echo "Patching file $dst" + patch -s -d $DST -p1 < $DST/override/$f.diff + fi # Use for public headers. for h in $PUBLIC; do p=$(echo $h | sed 's/\./\\./g') diff --git a/lib/nettle/ecc/override/ecc-gostdsa-verify.c.diff b/lib/nettle/ecc/override/ecc-gostdsa-verify.c.diff new file mode 100644 index 0000000000..143143e66d --- /dev/null +++ b/lib/nettle/ecc/override/ecc-gostdsa-verify.c.diff @@ -0,0 +1,19 @@ +diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c +index 29b82c84..906abbf3 100644 +--- a/ecc-gostdsa-verify.c ++++ b/ecc-gostdsa-verify.c +@@ -102,11 +102,11 @@ ecc_gostdsa_verify (const struct ecc_curve *ecc, + ecc->q.invert (&ecc->q, vp, hp, vp + 2*ecc->p.size); + + /* z1 = s / h, P1 = z1 * G */ +- ecc_mod_mul (&ecc->q, z1, sp, vp); ++ ecc_mod_mul_canonical (&ecc->q, z1, sp, vp); + + /* z2 = - r / h, P2 = z2 * Y */ +- ecc_mod_mul (&ecc->q, z2, rp, vp); +- mpn_sub_n (z2, ecc->q.m, z2, ecc->p.size); ++ mpn_sub_n (hp, ecc->q.m, rp, ecc->p.size); ++ ecc_mod_mul_canonical (&ecc->q, z2, hp, vp); + + /* Total storage: 5*ecc->p.size + ecc->mul_itch */ + ecc->mul (ecc, P2, z2, pp, z2 + ecc->p.size); diff --git a/lib/nettle/ecc/override/ecc-internal.h.diff b/lib/nettle/ecc/override/ecc-internal.h.diff new file mode 100644 index 0000000000..170191836c --- /dev/null +++ b/lib/nettle/ecc/override/ecc-internal.h.diff @@ -0,0 +1,26 @@ +diff --git a/ecc-internal.h b/ecc-internal.h +index 9e24e0ce..2cc9b137 100644 +--- a/ecc-internal.h ++++ b/ecc-internal.h +@@ -49,6 +49,7 @@ + #define ecc_mod_submul_1 _nettle_ecc_mod_submul_1 + #define ecc_mod_mul _nettle_ecc_mod_mul + #define ecc_mod_sqr _nettle_ecc_mod_sqr ++#define ecc_mod_mul_canonical _nettle_ecc_mod_mul_canonical + #define ecc_mod_random _nettle_ecc_mod_random + #define ecc_mod _nettle_ecc_mod + #define ecc_mod_inv _nettle_ecc_mod_inv +@@ -256,6 +257,13 @@ void + ecc_mod_sqr (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap); + ++/* mul function produces a canonical result, 0 <= R < M, needs 2*m->size limbs ++ * at rp. ++ */ ++void ++ecc_mod_mul_canonical (const struct ecc_modulo *m, mp_limb_t *rp, ++ const mp_limb_t *ap, const mp_limb_t *bp); ++ + /* mod q operations. */ + void + ecc_mod_random (const struct ecc_modulo *m, mp_limb_t *xp, diff --git a/lib/nettle/ecc/override/ecc-mod-arith.c.diff b/lib/nettle/ecc/override/ecc-mod-arith.c.diff new file mode 100644 index 0000000000..17b2592e30 --- /dev/null +++ b/lib/nettle/ecc/override/ecc-mod-arith.c.diff @@ -0,0 +1,19 @@ +diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c +index f2e47f67..959eae1c 100644 +--- a/ecc-mod-arith.c ++++ b/ecc-mod-arith.c +@@ -125,3 +125,14 @@ ecc_mod_sqr (const struct ecc_modulo *m, mp_limb_t *rp, + mpn_sqr (rp, ap, m->size); + m->reduce (m, rp); + } ++ ++void ++ecc_mod_mul_canonical (const struct ecc_modulo *m, mp_limb_t *rp, ++ const mp_limb_t *ap, const mp_limb_t *bp) ++{ ++ mp_limb_t cy; ++ ecc_mod_mul(m, rp, ap, bp); ++ ++ cy = mpn_sub_n (rp + m->size, rp, m->m, m->size); ++ cnd_copy (!cy, rp, rp + m->size, m->size); ++} diff --git a/lib/nettle/ecc/override/eddsa-hash.c.diff b/lib/nettle/ecc/override/eddsa-hash.c.diff new file mode 100644 index 0000000000..f2237e503f --- /dev/null +++ b/lib/nettle/ecc/override/eddsa-hash.c.diff @@ -0,0 +1,30 @@ +diff --git a/eddsa-hash.c b/eddsa-hash.c +index e05f6ac1..743dc4be 100644 +--- a/eddsa-hash.c ++++ b/eddsa-hash.c +@@ -44,13 +44,14 @@ + #include "ecc-internal.h" + #include "nettle-internal.h" + +-/* Convert hash digest to integer, and reduce modulo q, to m->size +- limbs. Needs space for 2*m->size + 1 at rp. */ ++/* Convert hash digest to integer, and reduce canonically modulo q. ++ Needs space for 2*m->size + 1 at rp. */ + void + _eddsa_hash (const struct ecc_modulo *m, + mp_limb_t *rp, size_t digest_size, const uint8_t *digest) + { + mp_size_t nlimbs = (8*digest_size + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS; ++ mp_limb_t cy; + + mpn_set_base256_le (rp, nlimbs, digest, digest_size); + +@@ -75,4 +76,8 @@ _eddsa_hash (const struct ecc_modulo *m, + assert (hi == 0); + } + m->mod (m, rp); ++ /* Ensure canonical reduction. */ ++ cy = mpn_sub_n (rp + m->size, rp, m->m, m->size); ++ cnd_copy (cy, rp + m->size, rp, m->size); ++ mpn_copyi (rp, rp + m->size, m->size); + } diff --git a/lib/nettle/ecc/override/gostdsa-vko.c.diff b/lib/nettle/ecc/override/gostdsa-vko.c.diff new file mode 100644 index 0000000000..8a058db99e --- /dev/null +++ b/lib/nettle/ecc/override/gostdsa-vko.c.diff @@ -0,0 +1,16 @@ +diff --git a/gostdsa-vko.c b/gostdsa-vko.c +index 7bdcdfc3..c6697ab3 100644 +--- a/gostdsa-vko.c ++++ b/gostdsa-vko.c +@@ -87,7 +87,8 @@ gostdsa_vko (const struct ecc_scalar *priv, + if (mpn_zero_p (UKM, size)) + UKM[0] = 1; + +- ecc_mod_mul (&ecc->q, TEMP, priv->p, UKM); /* TEMP = UKM * priv */ ++ ecc_mod_mul_canonical (&ecc->q, TEMP, priv->p, UKM); /* TEMP = UKM * priv */ ++ + ecc->mul (ecc, XYZ, TEMP, pub->p, scratch + 4*size); /* XYZ = UKM * priv * pub */ + ecc->h_to_a (ecc, 0, TEMP, XYZ, scratch + 5*size); /* TEMP = XYZ */ + mpn_get_base256_le (out, bsize, TEMP, size); +-- +2.31.1 -- cgit v1.2.1