From 1dfa4dd1c6cf9c1d6bbe5eaaf9fc9787d415df42 Mon Sep 17 00:00:00 2001 From: Sergei Trofimovich 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 --- 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