On Sun, 16 Jul 2017 18:18:34 +0100 Sergei Trofimovich <[email protected]> wrote:
> GMP's mpn_mul_n must never take overlapping source and > destination buffers as the implementation makes a few > passes over source while updating destination at each > pass: > > ``` > > https://gmplib.org/manual/Low_002dlevel-Functions.html#Low_002dlevel-Functions > > Function: void mpn_mul_n (mp_limb_t *rp, > const mp_limb_t *s1p, > const mp_limb_t *s2p, > mp_size_t n) > > Multiply {s1p, n} and {s2p, n}, and write the 2*n-limb result to rp. > > The destination has to have space for 2*n limbs, > even if the product’s most significant limb is zero. > No overlap is permitted between the destination and > either source. > ``` > > Violation of this invariant make nettle to compute > curve25519 incorrectly at least on sparc and hppa > architectures, see https://bugs.gentoo.org/613418 > for some details. > > The overlap happens in `ecc-add-eh.c` where layout > of local GMP variables on scratch space is the > following: > > ``` > |x1|y1|z1|........|B| > |x3|y3|z3|... > ``` > > x1/x3, y1/y3, z1/z3 pairs share the same memory region. > > Overlap happens at a call of > ``` > ecc_modp_mul (ecc, y3, B, z1); > ``` > which is basically > ``` > mpn_mul_n (y3, B, z1, m->size), > ``` > > Note how y3 overwrites z1. This is scary type of aliasing. > > The bug manifested in testsuite failure in nettle and gnutls. > I've trailed the bug down to faulty function by adding printf() > and comparing exact output of scratch space on x86 versus sparc. > > `mpn_mul_n` on the same source numbers produces different results. > > This change does not fix the underlying overlap but exposes the > problem on all architectures and crashes the testsuitewith asset(). > > Reported-by: Matt Turner > Bug: https://bugs.gentoo.org/613418 > Signed-off-by: Sergei Trofimovich <[email protected]> > --- > ecc-mod-arith.c | 12 ++++++++++++ > 1 file changed, 12 insertions(+) > > diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c > index f2e47f67..735b1238 100644 > --- a/ecc-mod-arith.c > +++ b/ecc-mod-arith.c > @@ -109,11 +109,23 @@ ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t > *rp, > assert (hi == 0); > } > > +static int no_overlap(const mp_limb_t * a, size_t la, > + const mp_limb_t * b, size_t lb) > +{ > + if (a < b) > + return (size_t)(b - a) >= la; > + /* a >= b */ > + return (size_t)(a - b) >= lb; > +} > + > /* NOTE: mul and sqr needs 2*m->size limbs at rp */ > void > ecc_mod_mul (const struct ecc_modulo *m, mp_limb_t *rp, > const mp_limb_t *ap, const mp_limb_t *bp) > { > + /* NOTE: mpn_mul_n does not work correctly when source and destination > overlap */ > + assert (no_overlap (rp, 2 * m->size, ap, m->size)); > + assert (no_overlap (rp, 2 * m->size, bp, m->size)); > mpn_mul_n (rp, ap, bp, m->size); > m->reduce (m, rp); > } > -- > 2.13.3 > Attaching a proof-of-concept patch nettle-3.3-noclobber.patch which fixes tests on sparc. I don't expect it to be applied upstream as it adds another memory allocation/free to a low-level operation but it's a good workaround to make sure it was the only problem blocking sparc. Thanks! -- Sergei
From 1dfa4dd1c6cf9c1d6bbe5eaaf9fc9787d415df42 Mon Sep 17 00:00:00 2001 From: Sergei Trofimovich <[email protected]> Date: Sun, 16 Jul 2017 18:06:52 +0100 Subject: [PATCH] ecc-mod-arith.c: fix 'ecc_mod_mul' not to clobber nearby limb MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit GMP's mpn_mul_n must never take overlapping source and destination buffers as the implementation makes a few passes over source while updating destination at each pass: ``` https://gmplib.org/manual/Low_002dlevel-Functions.html#Low_002dlevel-Functions Function: void mpn_mul_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n) Multiply {s1p, n} and {s2p, n}, and write the 2*n-limb result to rp. The destination has to have space for 2*n limbs, even if the productâs most significant limb is zero. No overlap is permitted between the destination and either source. ``` Violation of this invariant make nettle to compute curve25519 incorrectly at least on sparc and hppa architectures, see https://bugs.gentoo.org/613418 for some details. The overlap happens in `ecc-add-eh.c` where layout of local GMP variables on scratch space is the following: ``` |x1|y1|z1|........|B| |x3|y3|z3|... ``` x1/x3, y1/y3, z1/z3 pairs share the same memory region. Overlap happens at a call of ``` ecc_modp_mul (ecc, y3, B, z1); ``` which is basically ``` mpn_mul_n (y3, B, z1, m->size), ``` Note how y3 overwrites z1. This is scary type of aliasing. The bug manifested in testsuite failure in nettle and gnutls. I've trailed the bug down to faulty function by adding printf() and comparing exact output of scratch space on x86 versus sparc. `mpn_mul_n` on the same source numbers produces different results. This change makes 'ecc_mod_mul' not to go outsize operand limb sizes. Reported-by: Matt Turner Bug: https://bugs.gentoo.org/613418 Signed-off-by: Sergei Trofimovich <[email protected]> --- ecc-mod-arith.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c index f2e47f67..893c51a3 100644 --- a/ecc-mod-arith.c +++ b/ecc-mod-arith.c @@ -114,8 +114,13 @@ void ecc_mod_mul (const struct ecc_modulo *m, mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *bp) { - mpn_mul_n (rp, ap, bp, m->size); - m->reduce (m, rp); + mp_size_t itch = 2 * m->size; + mp_limb_t *scratch = gmp_alloc_limbs (itch); + + mpn_mul_n (scratch, ap, bp, m->size); + m->reduce (m, scratch); + mpn_copyi (rp, scratch, m->size); + gmp_free_limbs (scratch, itch); } void -- 2.13.3
pgpOl8GancFxy.pgp
Description: Цифровая подпись OpenPGP
_______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
