add support for noble-curves

[paulmillr]

https://github.com/paulmillr/noble-curves

[paulmillr]

@guidovranken ping

[paulmillr]

@guidovranken we need this

[guidovranken]

Thanks. How can we create a noble-curves.js that doesn't have any require statements? Basically we need to pack all JS code into 1 file.

[paulmillr]

modules/noble-curves have proper rollup config in place that allows to build file

[guidovranken]

When I run the npm command in the Makefile I get this:

$ npm i && npm run build

up to date, audited 87 packages in 2s

11 packages are looking for funding
  run `npm fund` for details

5 vulnerabilities (1 low, 4 critical)

To address issues that do not require attention, run:
  npm audit fix

Some issues need review, and may require choosing
a different dependency.

Run `npm audit` for details.

> build
> rollup -c rollup.config.js

harness.js → noble-curves.js...
(!) Plugin node-resolve: Could not resolve import "@noble/curves/p192" in /home/jhg/paul-miller-js/cryptofuzz/modules/noble-curves/harness.js using exports defined in /home/jhg/paul-miller-js/cryptofuzz/modules/noble-curves/node_modules/@noble/curves/package.json.
(!) Plugin node-resolve: Could not resolve import "@noble/curves/p224" in /home/jhg/paul-miller-js/cryptofuzz/modules/noble-curves/harness.js using exports defined in /home/jhg/paul-miller-js/cryptofuzz/modules/noble-curves/node_modules/@noble/curves/package.json.
(!) Unresolved dependencies
https://rollupjs.org/guide/en/#warning-treating-module-as-external-dependency
@noble/curves/p192 (imported by harness.js)
@noble/curves/p224 (imported by harness.js)
created noble-curves.js in 665ms
(base) jhg@jhg-System-Product-Name:~/paul-miller-js/cryptofuzz/modules/noble-curves$ head -n5 noble-curves.js 
'use strict';

const p192 = require('@noble/curves/p192');
const p224 = require('@noble/curves/p224');

So it complains about missing imports, which are then present as require's in the javascript file.

[paulmillr]

@guidovranken fixed

[guidovranken]

Thank you. How shall we deal with this?

$ ./cryptofuzz --force-module=noble-curves ./crash-0001f73e5e9ceabae6cf7d3d0483fb1ec033b010
INFO: found LLVMFuzzerCustomMutator (0x557045189420). Disabling -len_control by default.
INFO: libFuzzer ignores flags that start with '--'
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 1374452351
INFO: Loaded 1 modules   (165211 inline 8-bit counters): 165211 [0x557045942f48, 0x55704596b4a3), 
INFO: Loaded 1 PC tables (165211 PCs): 165211 [0x55704596b4a8,0x557045bf0a58), 
INFO: 65536 Extra Counters
./cryptofuzz: Running 1 inputs 1 time(s) each.
Running: ./crash-0001f73e5e9ceabae6cf7d3d0483fb1ec033b010
Error: The environment doesn't have randomBytes function
    at randomBytes (noble-curves.js:3240)
    at randomPrivateKey (noble-curves.js:4427)
    at k2sig (noble-curves.js:4559)
    at genUntil (noble-curves.js:3051)
    at sign (noble-curves.js:4592)
    at OpECDSA_Sign (noble-curves.js:8741)
    at <anonymous> (noble-curves.js:9173)

[paulmillr]

How are you dealing with this usually? Some randomBytes shim?

[guidovranken]

We should have Math.random. How can we make it use that? I'm trying things like adding this to harness.js:

var crypto = {}
crypto.web = {};
crypto.web.getRandomValues = Math.random;

but to no avail.

[paulmillr]

@guidovranken removed dependency on crypto.random.

[guidovranken]

IsBignumCalc_Mod_BLS12_381_P() and IsBignumCalc_Mod_BLS12_381_R() are in ids.js, but don't end up in noble-curves.js. So I get:

Running: crash-e28bd7d1412d9efcb764aed4085385ab7915a860
ReferenceError: 'IsBignumCalc_Mod_BLS12_381_P' is not defined
    at <anonymous> (noble-curves.js:9262)

Do you know why that is?

[guidovranken]

The HashToG2 implementation results in this error:

TypeError: cannot read property 'G2' of undefined

[paulmillr]

Crap. Too many changes during last weeks - sorry for that.

bls.hashToCurve.G2.hashToCurve needs to be just bls.G2.hashToCurve

[paulmillr]

Fixed.

[guidovranken]

Thanks.

Do you know how to resolve this?

IsBignumCalc_Mod_BLS12_381_P() and IsBignumCalc_Mod_BLS12_381_R() are in ids.js, but don't end up in noble-curves.js. So I get:

Running: crash-e28bd7d1412d9efcb764aed4085385ab7915a860
ReferenceError: 'IsBignumCalc_Mod_BLS12_381_P' is not defined
    at <anonymous> (noble-curves.js:9262)

[guidovranken]

I think this:

    var msg = FuzzerInput['aug'] + FuzzerInput['cleartext'];                                               

In OpBLS_HashToG1 and OpBLS_HashToG2 must be changed to:

    var msg = hexToBytes(FuzzerInput['aug'] + FuzzerInput['cleartext']);

Otherwise it says

Error: Uint8Array expected

[guidovranken]

Can you also please put something like this at the top of every OpBLS_ function:

if (!ids.IsBLS12_381(BigInt(FuzzerInput['curveType']))) return;

[guidovranken]

operation name: BLS_G2_IsEq
A V:4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
A W:0
A X:0
A Y:0
B V:0
B W:0
B X:0
B Y:0

Module noble-curves result:

false

Module blst result:

true

Are you not reducing inputs?

[paulmillr]

No, inputs are not reduced mod P. Logic is done before point initialization.

Some curves check if it's lower than P, others (ed) must behave differently because of ZIP215 and they check if it's lower than 2^256, and can reduce then

[paulmillr]

@guidovranken updated.

[paulmillr]

@guidovranken ping please

[guidovranken]

Sorry will review and merge tomorrow.

[guidovranken]

I'm reviewing this now.

This bug is still present:

IsBignumCalc_Mod_BLS12_381_P() and IsBignumCalc_Mod_BLS12_381_R() are in ids.js, but don't end up in noble-curves.js. So I get:

Running: crash-e28bd7d1412d9efcb764aed4085385ab7915a860
ReferenceError: 'IsBignumCalc_Mod_BLS12_381_P' is not defined
    at <anonymous> (noble-curves.js:9262)

[paulmillr]

@guidovranken you can comment them out for now

[paulmillr]

Thanks! Now we can update curves to 1.0.0 in cryptofuzz.

[paulmillr]

If you'll decide to do an update, those harness.js changes will need to be done:

• bls12_381.Fp has been moved to bls12_381.fields.Fp, same with Fp2
• bls12_381.hashToCurve.G1.hashToCurve => bls12_381.G1.hashToCurve, same with G2

Other API I think is the same.

[guidovranken]

Done: https://github.com/guidovranken/cryptofuzz/commit/508c3844df9d91f3bf3bde4520e1a40c9c140cc6

hash to curve calls were already ok so I didn't change those.

[guidovranken]

PS I computed a few corner cases for secp256k1 GLV endomorphism: https://github.com/guidovranken/cryptofuzz/blob/508c3844df9d91f3bf3bde4520e1a40c9c140cc6/builtin_tests_importer.cpp#L670-L719

Maybe you can add those as tests, if you haven't already.

[paulmillr]

Thanks! Do those cases pass ok, or they fail?

[guidovranken]

They passed when I checked a month ago, otherwise I would have notified you. But those edge cases are fairly rare to hit with random scalars (e.g. with fuzzing) so it makes sense to target them with tests IMO.