Problem with mont form inversion

[dvdplm]

Test to illustrate a potential problem with the Bernstein&Yang code to invert numbers in Montgomery form. The specific parameters shown here come from intermittent test failures of homomorphic_mul in the Synedrion signining library (i.e. parameters are generated with an unseeded CSPRNG).

Run the test with cargo t inversion_v06_vs_v055.

For convenience, after the test follows a commented out version of the same that passes with crypto-bigint v0.5.5.

To compare with v0.5.5 do the following:

1. Checkout the old code: git checkout v0.5.5
2. Run cargo update -p proc-macro2 to work around a recent compiler incompatibility
3. Paste the commented out v0.5 test in the test module of runtime_mod.rs
4. Run the test with cargo t inversion_v06v_v055
5. Notice it passes

[tarcieri]

@dvdplm it looks like this test is making use of internals / private fields. Can you write it entirely in terms of the public API? Otherwise I can't tell if you're miscomputing constants.

It would also be good to generate reference values with e.g. sage, and show your work for that.

[dvdplm]

Can you write it entirely in terms of the public API?

You mean to instantiate the MontyForm values? Sure, I can try to do that.

I think having known good values would be very good, and I had a look at the Sage docs but couldn't find much info on how to do modular maths with it. I'll try again though.

[dvdplm]

Can you write it entirely in terms of the public API?

Done.

[tarcieri]

@dvdplm as an alternative to sage, you could also compare results with num-modular, which is already one of the dev-dependencies

[dvdplm]

also compare results with num-modular

@tarcieri I added a test using num-modular. It agrees with crypto-bigint v0.5.5.

[dvdplm]

@tarcieri @fjarri I think I have found another clue that might help us narrow down what is going wrong here. The problem seems to lie in the modulus, in the size of the modulus. In the latest commit (e0da58b) I have added more tests to illustrate how moduli of sizes U2048 and U4096 seem to break on v0.6. Weirdly enough U1024 moduli seem fine. I did not try U8192 yet.

Not sure what the next steps should be but I wanted to leave as much information as possible here.

[tarcieri]

@dvdplm that's a good data point to know re: specific sized integers being impacted

My best guess would be it's a bug in the bernstein_yang_nlimbs! macro which computes the number of 62-bit limbs needed to represent a given-sized value:

https://github.com/RustCrypto/crypto-bigint/blob/2b81eae18c6dd89927b66f0f9af4413402b6bbea/src/macros.rs#L12-L19

That's used here when writing impls of the PrecomputeInverter trait: https://github.com/RustCrypto/crypto-bigint/blob/2b81eae18c6dd89927b66f0f9af4413402b6bbea/src/uint/macros.rs#L11

[tarcieri]

I was able to produce a test failure using the existing test suite by modifying the proptests for modular inversion in tests/monty_form.rs to use U2048 instead of U256.

I then made those same tests pass by modifying bernstein_yang_nlimbs to be the following:

 macro_rules! bernstein_yang_nlimbs { 
     ($bits:expr) => { 
         (($bits / 64) + (($bits / 64) * 2).div_ceil(64) + 2) 
     }; 
 } 

That probably isn't the best way to fix this specific problem, but I believe it does demonstrate that there are currently too few 62-bit limbs for a given sized integer, leading to truncation and thus the miscomputed results.

@dvdplm I haven't tested your specific vectors, but perhaps you could try that locally and see if it corrects the issue?

[tarcieri]

I'm also a little confused why the current calculation for the number of limbs is insufficient, but I'll have to go back through the paper and find where it's defined.

FWIW, it currently computes 34 limbs for a 2048-bit integer, where 34 * 62 = 2108 bits

[tarcieri]

Aha, so the issue is for a given UNSAT_LIMBS, we can calculate the maximum allowed size of any modulus or input value in bits as:

(UNSAT_LIMBS * 62) - 64

We currently compute 34 limbs for a 2048-bit integer:

(34 * 62) - 64 = 2044

That's 4-bits too small.

[tarcieri]

Draft PR with a fix here: #610

@dvdplm I'd appreciate it if you could rebase on that and see if it fixed your issues

[dvdplm]

That's 4-bits too small.

Awesome sleuthing! I was thiiiiiis close, but you got there first! :)

[dvdplm]

I'd appreciate it if you could rebase on that and see if it fixed your issues

Yep, will do first thing in the morning.

[dvdplm]

@dvdplm I haven't tested your specific vectors, but perhaps you could try that locally and see if it corrects the issue?

Changing the + 1 to + 2 fixes the failing tests, so that's a good first indication that your fix is good. I'll test the PR properly as well.

[dvdplm]

I'd appreciate it if you could rebase on that and see if it fixed your issues

I have checked that #610 indeed fixes all test failures on this branch. 🎉

To check upstream it would be really good to have a new pre-release of crypto-bigint, is that possible?

[tarcieri]

Yes, I can cut another release soon

[tarcieri]

Released in v0.6.0-rc.0

[tarcieri]

Going to close this out, but I'd still be curious in getting some of these tests in if you'd like to resubmit just those