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 _______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
