On Sun, 16 Jul 2017 18:18:34 +0100 Sergei Trofimovich slyfox@gentoo.org 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 slyfox@gentoo.org

---

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!