adding edge case for ecmulmuladd

[rdubois-crypto]

adding edge case following https://github.com/rdubois-crypto/FreshCryptoLib/pull/48 issue on Fuzzing

[nlordell]

I've narrowed it down to a smaller test case the shows the issue:

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.19 <0.9.0;

import "forge-std/Test.sol";

import "@solidity/FCL_elliptic.sol";

contract EcmulmulEdge is Test {
    function test_EdgeCase() external {
        uint256 Qx = 102369864249653057322725350723741461599905180004905897298779971437827381725266;
        uint256 Qy = 14047598098721058250371778545974983789701612908526165355421494088134814672697;
        uint256 u = 9;
        uint256 v = 6;

        uint256 r1 = FCL_Elliptic_ZZ.ecZZ_mulmuladd_S_asm(Qx, Qy, u, v);
        console.log("r1 = %d", r1);

        (uint256 uGx, uint256 uGy) = ecAff_naivemul(u, FCL_Elliptic_ZZ.gx, FCL_Elliptic_ZZ.gy);
        (uint256 vQx, uint256 vQy) = ecAff_naivemul(v, Qx, Qy);
        (uint256 r2,) = FCL_Elliptic_ZZ.ecAff_add(uGx, uGy, vQx, vQy);
        console.log("r2 = %d", r2);

        assertEq(r1, r2);
    }

    function ecAff_naivemul(uint256 a, uint256 x, uint256 y) private view returns (uint256 ax, uint256 ay) {
        while (a > 0) {
            (ax, ay) = FCL_Elliptic_ZZ.ecAff_add(ax, ay, x, y);
            a = a - 1;
        }
    }
}

[nlordell]

And even smaller one:

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.19 <0.9.0;

import "forge-std/Test.sol";

import "@solidity/FCL_ecdsa_utils.sol";
import "@solidity/FCL_elliptic.sol";

contract EcmulmulEdge is Test {
    function test_EdgeCase() external {
        uint256 s = FCL_Elliptic_ZZ.n - 1;
        (uint256 Qx, uint256 Qy) = FCL_ecdsa_utils.ecdsa_derivKpub(s);
        console.log("Qx = %d", Qx);
        console.log("Qy = %d", Qy);

        uint256 u = 3;
        uint256 v = 1;

        uint256 r1 = FCL_Elliptic_ZZ.ecZZ_mulmuladd_S_asm(Qx, Qy, u, v);
        console.log("r1 = %d", r1);

        (uint256 uGx, uint256 uGy) = ecAff_naivemul(u, FCL_Elliptic_ZZ.gx, FCL_Elliptic_ZZ.gy);
        (uint256 vQx, uint256 vQy) = ecAff_naivemul(v, Qx, Qy);
        (uint256 r2,) = FCL_Elliptic_ZZ.ecAff_add(uGx, uGy, vQx, vQy);
        console.log("r2 = %d", r2);

        (uint256 twoGx, ) = ecAff_naivemul(2, FCL_Elliptic_ZZ.gx, FCL_Elliptic_ZZ.gy);
        console.log("2Gx = %d", twoGx);

        assertEq(r1, r2);
    }

    function ecAff_naivemul(uint256 a, uint256 x, uint256 y) private view returns (uint256 ax, uint256 ay) {
        while (a > 0) {
            (ax, ay) = FCL_Elliptic_ZZ.ecAff_add(ax, ay, x, y);
            a = a - 1;
        }
    }
}

I think I have some intuition on what is going on... So this seems to happen for Q where the pk is the order n minus some very small amount. In particular, in the above example, we have G + Q = 0 (and in the previous one, 4G + Q = 0).

In the second case, we are computing 3G + Q = 2G + G + Q = 2G + 0 = 2G, but ecZZ_mulmuladd_S_asm is returning the wrong value. If I understand the Shamir multiplication trick correctly (biiiiig if), the way it works is you have:

• (1): Sum = u{255}G + v{255}Q = 0G + 0Q = 0 (where x{n} is the n-th bit of the value x)
• (2): Sum = dbl(Sum) + u{254}G + v{254}Q = 0 + 0G + 0Q = 0
• ...
• (255): dbl(Sum) + u{1}G + v{1}Q = 0 + 1G + 0Q = G
• (256): dbl(Sum) + u{0}G + v{0}Q = 2G + 1G + 1Q = 2G

So it appears that there is some weird interaction where elements of the sum are adding to the point at infinity and causing issues in the implementation.

In the previous example, you have something similar noting that u = 0b1001 and v = 0b011* (both v = 6 and v = 7 cause the test to fail), so if my understanding of the Shamir multiplication trick is correct, you will end up adding 4G with Q which will also add to 0.

I'm sorry if my conjecture is wrong :see_no_evil: - but at least I hope I helped in finding some reduced examples that are causing issues with ecZZ_mulmuladd_S_asm :sweat_smile:. It feels like it is related to points adding to 0.

[rdubois-crypto]

It gonna be easier to patch thx. You understand well, it is what I said about coverage on the other PR. I thought having wycheproofed the code and used forge cover would cover the 'if' section supposed to handle this, (and let the todo undone) https://github.com/rdubois-crypto/FreshCryptoLib/blob/e2830cb5d7b0f6ae35b5800287c0f5c92388070b/solidity/src/FCL_elliptic.sol#L438

Forge cover is not able to proceed 'for loops'.