Accept elementary types for Q

[mmv08]

Currently, the public key is accepted as a fixed-size array in the webauthn/ecdsa functions. This is a concern for https://github.com/rdubois-crypto/FreshCryptoLib/issues/9

When using EIP-1271, you can slice all the variables and pass them as call data, except for the public key (Q), which most likely exists as a state variable of some form in the signer contract.

A very naive POC implementation would look like:

    function isValidSignature(
        bytes memory _hash,
        bytes calldata _signature
    ) public view returns (bytes4) {
        uint256 authenticatorDataSize = uint256(bytes32(_signature[0:32]));
        bytes calldata authenticatorData = _signature[32:32 +
            authenticatorDataSize];
        uint256 clientDataSize = uint256(
            bytes32(
                _signature[32 + authenticatorDataSize:64 +
                    authenticatorDataSize]
            )
        );
        bytes calldata clientData = _signature[64 + authenticatorDataSize:64 +
            authenticatorDataSize +
            clientDataSize];
        uint256 challengeOffset = uint256(
            bytes32(
                _signature[64 + authenticatorDataSize + clientDataSize:96 +
                    authenticatorDataSize +
                    clientDataSize]
            )
        );
        uint256[2] calldata rs = [
            uint256(
                bytes32(
                    _signature[96 + authenticatorDataSize + clientDataSize:128 +
                        authenticatorDataSize +
                        clientDataSize]
                )
            ),
            uint256(
                bytes32(
                    _signature[128 +
                        authenticatorDataSize +
                        clientDataSize:160 +
                        authenticatorDataSize +
                        clientDataSize]
                )
            )
            ....

(will be open sourced if this PR gets accepted)

Exisiting workarounds include creating a wrapper library with an external function which is inefficient.

This PR adds new functions in a backwards-compatible manner that accept Q as two elementary uint256 variables.

The original idea comes from @nlordell, many thanks to him :)

[rdubois-crypto]

Hi Mikhail !

Thanks a lot for submitting this PR. However modifying the API breaks the CI. In order for it to be accepted, it would require to update FCL_ecdsa_utils.t.sol and FCL_ecdsa.t.sol accordingly.

[mmv08]

Hi Mikhail !

Thanks a lot for submitting this PR. However modifying the API breaks the CI. In order for it to be accepted, it would require to update FCL_ecdsa_utils.t.sol and FCL_ecdsa.t.sol accordingly.

Hey, I will tackle this today. That's strange because I haven't touched the files, and the tests passed locally.

One question - do you think it makes sense to add tests for the new functions we're proposing? We suspect they might be also slightly more gas-efficient.

[rdubois-crypto]

Yeah, weird cause it is overloading. By the way as overloading, it might suffice to just make a separate call in the existing test (just by adding two uint256 and use the existing callcata as input).

[rdubois-crypto]

For the gas cost i'm on a 140K gas version, still experimental, should push it in the next weeks.

[mmv08]

@rdubois-crypto the formatting is now fixed.

Regarding the failed tests, it seems that test_Fuzz_SigVerif in solidity/tests/WebAuthn_forge/test/FCL_ecdsa_utils.t.sol fails sometimes (Like 2 runs out of 5). The counter-example I got:

[FAIL. Reason: assertion failed; counterexample: calldata=0x69a6990e0000000000000000000000000000000000000000000000000000000000003e7fffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc63255000000000000000000000000000000000000000000000000000000000000025ee args=[15999 [1.599e4], 115792089210356248762697446949407573529996955224135760342422259061068512044368 [1.157e77], 9710]]

I'm unsure if this is something I need to fix or better be fixed in a separate PR.

[mmv08]

The private key in the failed tests matches the one here: https://github.com/kmackay/micro-ecc/issues/141

Also, quoting one of the comments:

If I remember correctly, these are not fixable and special cases of underlying algorithm. (base_point-2 is an artifact of regularization?) And thus not a bug of implementation. For security, perhaps, you should check for these inputs and return them as invalid points.

[rdubois-crypto]

Wow, thanks, as wycheproof is used in the invariant test, problems must be circomvented.

It should be investigated if the problem comes also on the verification part, or only signature, added to be able to make fuzzing (it compute the signature part, which of course is not meant to be onchain). Signing requires many more functions, cause we abuse the x only double multiplication (we choose v=0) and perform point decompression.

[mmv08]

Wow, thanks, as wycheproof is used in the invariant test, problems must be circomvented.

It should be investigated if the problem comes also on the verification part, or only signature, added to be able to make fuzzing (it compute the signature part, which of course is not meant to be onchain). Signing requires many more functions, cause we abuse the x only double multiplication (we choose v=0) and perform point decompression.

So @nlordell and me debugged this and here are our findings. We compared all the outputs to the @noble/curves library. The inputs we used:

        uint256 k = 115792089210356248762697446949407573529996955224135760342422259061068512033193;
        uint256 kpriv = 115792089210356248762697446949407573529996955224135760342422259061068512044365;
        uint256 message = 9827;

        // signature generated with ecdsa_sign in solidity:
         uint256 r = 93995665850302450053183256960521438033484268364047930968443817833761593125805;
        // fails with this s
         uint256 s =  103713978113049050748794388390351080356729909448942622178820089629156017036551;
        // passes with this s
        uint256 sLow = 12078111097307198013903058559056493173267045775193138163602169431912495007818;

1. The public key generated matched the FCL_ecdsa_utils.ecdsa_derivKpub function output and the NIST test cases from here
2. The r and s values also matched.
3. The most interesting thing happens at the verification step. If you use the dark side S value, then the verification fails. But if you use the low S, then the test passes.

the real hero behind that is @nlordell, he will jump into the discussion and provide more thoughts

[mmv08]

Also, if you use a smaller K value, the verification passes.

[nlordell]

I don't think there is anything inherently wrong with verifying signatures with s on the dark side of the curve (I would expect tests to fail 50% of the time if it did). I imagine (as the wycheproof test case description suggests) that it is a weird edge case in the Shamir multiplication trick that manifests when k is high for certain values of s.

Take this with a grain of salt, as it is just an intuition and not really confirmed.

[nlordell]

Very specifically, this appears to be returning an incorrect value:

ecZZ_mulmuladd_S_asm(
    102369864249653057322725350723741461599905180004905897298779971437827381725266,
    14047598098721058250371778545974983789701612908526165355421494088134814672697,
    94632330233094393099906091027057584450760066982961548963789323460936666616340,
    23658082558273598274976522756764396112690016745740387240947330865234166656879
)

Compared to manually computing:

94632330233094393099906091027057584450760066982961548963789323460936666616340 * G + 23658082558273598274976522756764396112690016745740387240947330865234166656879 * (x=102369864249653057322725350723741461599905180004905897298779971437827381725266, y=14047598098721058250371778545974983789701612908526165355421494088134814672697)

[rdubois-crypto]

Very specifically, this appears to be returning an incorrect value:

ecZZ_mulmuladd_S_asm(
    102369864249653057322725350723741461599905180004905897298779971437827381725266,
    14047598098721058250371778545974983789701612908526165355421494088134814672697,
    94632330233094393099906091027057584450760066982961548963789323460936666616340,
    23658082558273598274976522756764396112690016745740387240947330865234166656879
)

Compared to manually computing:

94632330233094393099906091027057584450760066982961548963789323460936666616340 * G + 23658082558273598274976522756764396112690016745740387240947330865234166656879 * (x=102369864249653057322725350723741461599905180004905897298779971437827381725266, y=14047598098721058250371778545974983789701612908526165355421494088134814672697)

Thx a lot, i will investigate this edge case. It appears that forge coverage is not working on loops and that code i thought covered is not. This is very usefull !

[rdubois-crypto]

Ok, now this edge case captures it https://github.com/rdubois-crypto/FreshCryptoLib/pull/49/files#diff-80c8f8afb06afd4ea8342b2f9033a56dc70b73f6350e373173efbd3499c212bb

Expected X results is 93995665850302450053183256960521438033484268364047930968443817833761593125805

[nlordell]

I posted an additional (and arguably smaller) test case that also shows the issue in the aforementioned PR.