BigInteger.ModPow asserting in SubtractSelf

bartonjs commented 9 months ago

Description

Trying to use BigInteger for test authoring is currently impeded by it asserting.

Reproduction Steps

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
BigInteger m = new BigInteger(buf, true, true);
BigInteger e = 65537;

buf = new byte[]
{
    0xB1, 0x7C, 0xEE, 0x77, 0xB4, 0x59, 0xA4, 0x65,
    0x92, 0x8D, 0x7F, 0x55, 0x77, 0x80, 0x39, 0xBA,
    0x22, 0xBA, 0x29, 0xA5, 0xFF, 0xE5, 0x53, 0xFB,
    0x40, 0x98, 0xA8, 0x35, 0xE5, 0x2D, 0x0A, 0xDC,
    0x85, 0x17, 0x6E, 0xE4, 0xD6, 0x93, 0x82, 0x20,
    0x71, 0x8D, 0xE9, 0xDD, 0xC9, 0xD5, 0xBD, 0x30,
    0x47, 0xEE, 0x59, 0xB9, 0xE6, 0xA8, 0x79, 0x9E,
    0x47, 0x96, 0x8E, 0x63, 0xCD, 0xA6, 0x28, 0x9D,
    0x7B, 0x6D, 0x83, 0xAA, 0x68, 0xE2, 0x46, 0xD6,
    0x1C, 0x8C, 0x2B, 0xA1, 0xC4, 0x04, 0x12, 0xAE,
    0x61, 0x07, 0xAF, 0x6F, 0xE9, 0x2B, 0x48, 0x5C,
    0xCA, 0xC2, 0x0E, 0x52, 0x71, 0x21, 0x03, 0xE0,
    0x05, 0x1C, 0x07, 0xC0, 0x56, 0xFD, 0x8A, 0x61,
    0x7A, 0x95, 0x39, 0x4B, 0xAA, 0x5A, 0x9D, 0x03,
    0x6D, 0x7A, 0x51, 0x3E, 0x7A, 0xE4, 0xAB, 0xED,
    0xB4, 0x0A, 0x88, 0x80, 0x3C, 0x07, 0xED, 0x19,
    0x21, 0xA2, 0xDC, 0xD7, 0x9C, 0x3F, 0x3B, 0x19,
    0x59, 0x33, 0x39, 0x8A, 0x25, 0xDB, 0xCE, 0x8D,
    0x8E, 0x10, 0xDA, 0xB1, 0x38, 0x32, 0xCA, 0x59,
    0xA1, 0x69, 0x3C, 0x23, 0x76, 0x50, 0x37, 0xB3,
    0xBF, 0x73, 0x58, 0x77, 0x38, 0xC5, 0x16, 0x03,
    0x60, 0x36, 0x0D, 0x31, 0x8C, 0xBE, 0xA5, 0x12,
    0x2F, 0xE5, 0x16, 0xAD, 0x1C, 0x80, 0x01, 0x50,
    0xEB, 0x3C, 0x86, 0x79, 0x22, 0xD3, 0x7F, 0xD4,
    0x90, 0x85, 0xB8, 0xEB, 0xB0, 0x7D, 0xD8, 0xC8,
    0x8B, 0xBB, 0x88, 0xBE, 0xFE, 0xB8, 0xBA, 0xAD,
    0x61, 0xC7, 0xF9, 0x68, 0x20, 0xB2, 0xA9, 0x1D,
    0xB4, 0xDC, 0xB0, 0x5B, 0xC7, 0xB3, 0xF2, 0x83,
    0x35, 0x43, 0xB0, 0xAE, 0x19, 0x2B, 0xA6, 0xFA,
    0x88, 0x48, 0xB9, 0xFB, 0xB3, 0xCD, 0xF8, 0xA9,
    0x9C, 0x20, 0x6F, 0x63, 0x23, 0xE5, 0xC2, 0x85,
    0xCD, 0x75, 0x7A, 0x55, 0x04, 0xA4, 0x08, 0x99,
};

BigInteger n = new BigInteger(buf, true, true);
BigInteger c = BigInteger.ModPow(m, e, n);

Expected behavior

No assertion.

Actual behavior

Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

Definitely happens on bc0b28f564f0f3fdfa0c0856bd1b3b38d5371c4d on both osx and win. The osx build merged up through 3bf9beecd5f68a59fc407488ce8120ee3d4240c7 (main as of about an hour ago) and still sees the assert.

ghost commented 9 months ago

Tagging subscribers to this area: @dotnet/area-system-numerics See info in area-owners.md if you want to be subscribed.

Issue Details

### Description Trying to use BigInteger for test authoring is currently impeded by it asserting. ### Reproduction Steps ```C# byte[] buf = new byte[2048 >> 3]; buf[1] = 2; buf.AsSpan(2, 8).Fill(1); BigInteger m = new BigInteger(buf, true, true); BigInteger e = 65537; buf = new byte[] { 0xB1, 0x7C, 0xEE, 0x77, 0xB4, 0x59, 0xA4, 0x65, 0x92, 0x8D, 0x7F, 0x55, 0x77, 0x80, 0x39, 0xBA, 0x22, 0xBA, 0x29, 0xA5, 0xFF, 0xE5, 0x53, 0xFB, 0x40, 0x98, 0xA8, 0x35, 0xE5, 0x2D, 0x0A, 0xDC, 0x85, 0x17, 0x6E, 0xE4, 0xD6, 0x93, 0x82, 0x20, 0x71, 0x8D, 0xE9, 0xDD, 0xC9, 0xD5, 0xBD, 0x30, 0x47, 0xEE, 0x59, 0xB9, 0xE6, 0xA8, 0x79, 0x9E, 0x47, 0x96, 0x8E, 0x63, 0xCD, 0xA6, 0x28, 0x9D, 0x7B, 0x6D, 0x83, 0xAA, 0x68, 0xE2, 0x46, 0xD6, 0x1C, 0x8C, 0x2B, 0xA1, 0xC4, 0x04, 0x12, 0xAE, 0x61, 0x07, 0xAF, 0x6F, 0xE9, 0x2B, 0x48, 0x5C, 0xCA, 0xC2, 0x0E, 0x52, 0x71, 0x21, 0x03, 0xE0, 0x05, 0x1C, 0x07, 0xC0, 0x56, 0xFD, 0x8A, 0x61, 0x7A, 0x95, 0x39, 0x4B, 0xAA, 0x5A, 0x9D, 0x03, 0x6D, 0x7A, 0x51, 0x3E, 0x7A, 0xE4, 0xAB, 0xED, 0xB4, 0x0A, 0x88, 0x80, 0x3C, 0x07, 0xED, 0x19, 0x21, 0xA2, 0xDC, 0xD7, 0x9C, 0x3F, 0x3B, 0x19, 0x59, 0x33, 0x39, 0x8A, 0x25, 0xDB, 0xCE, 0x8D, 0x8E, 0x10, 0xDA, 0xB1, 0x38, 0x32, 0xCA, 0x59, 0xA1, 0x69, 0x3C, 0x23, 0x76, 0x50, 0x37, 0xB3, 0xBF, 0x73, 0x58, 0x77, 0x38, 0xC5, 0x16, 0x03, 0x60, 0x36, 0x0D, 0x31, 0x8C, 0xBE, 0xA5, 0x12, 0x2F, 0xE5, 0x16, 0xAD, 0x1C, 0x80, 0x01, 0x50, 0xEB, 0x3C, 0x86, 0x79, 0x22, 0xD3, 0x7F, 0xD4, 0x90, 0x85, 0xB8, 0xEB, 0xB0, 0x7D, 0xD8, 0xC8, 0x8B, 0xBB, 0x88, 0xBE, 0xFE, 0xB8, 0xBA, 0xAD, 0x61, 0xC7, 0xF9, 0x68, 0x20, 0xB2, 0xA9, 0x1D, 0xB4, 0xDC, 0xB0, 0x5B, 0xC7, 0xB3, 0xF2, 0x83, 0x35, 0x43, 0xB0, 0xAE, 0x19, 0x2B, 0xA6, 0xFA, 0x88, 0x48, 0xB9, 0xFB, 0xB3, 0xCD, 0xF8, 0xA9, 0x9C, 0x20, 0x6F, 0x63, 0x23, 0xE5, 0xC2, 0x85, 0xCD, 0x75, 0x7A, 0x55, 0x04, 0xA4, 0x08, 0x99, }; BigInteger n = new BigInteger(buf, true, true); BigInteger c = BigInteger.ModPow(m, e, n); ``` ### Expected behavior No assertion. ### Actual behavior ``` Process terminated. Assertion failed. at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135 at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc ulator.FastReducer.cs:line 114 at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\ Numerics\BigIntegerCalculator.FastReducer.cs:line 61 at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength, Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539 at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\ git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer ics\BigIntegerCalculator.PowMod.cs:line 416 at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow Mod.cs:line 243 at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti me.Numerics\src\System\Numerics\BigInteger.cs:line 1005 ``` ### Regression? _No response_ ### Known Workarounds _No response_ ### Configuration _No response_ ### Other information Definitely happens on bc0b28f564f0f3fdfa0c0856bd1b3b38d5371c4d on both osx and win. The osx build merged up through 3bf9beecd5f68a59fc407488ce8120ee3d4240c7 (main as of about an hour ago) and still sees the assert.

Author:	bartonjs
Assignees:	-
Labels:	`area-System.Numerics`, `untriaged`
Milestone:	-

jeffhandley commented 9 months ago

Tentatively marked this as 9.0.0. If it's not fully blocking though, we'll move it to Future.

bartonjs commented 9 months ago

This is blocking test authoring for https://github.com/dotnet/runtime/pull/97738; so, yes, it's "fully blocking"

eiriktsarpalis commented 9 months ago

It appears that there is a flaw in the SubMod implementation in the "FastReducer" algorithm:

https://github.com/dotnet/runtime/blob/9367edc6fbd500e45cf80b3f00135de771766620/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.FastReducer.cs#L102-L114

in that it incorrectly assumes that left is greater than or equal to right after truncating to the k least significant digits of the representation. The FastReducer was introduced as a performance optimization in https://github.com/dotnet/corefx/pull/2182.

Minimal Reproduction

BigInteger modulus = (BigInteger)3 << 1024;
BigInteger value = modulus;
int exponent = 2;

BigInteger.ModPow(value, exponent, value); // Assertion failure in debug builds

It should be noted that superficially, the result appears to be correct using the following validation logic:

BigInteger result = BigInteger.ModPow(value, exponent, modulus);

BigInteger expectedResult = 1;
for (int i = 0; i < exponent; i++)
{
    expectedResult = (expectedResult * value) % modulus;
}

Assert.Equal(expectedResult, result); // Passes for given inputs

However, I don't think it would be safe to simply comment out the asserts. The SubtractSelf algorithm --where the assertion is failing-- has not been designed for cases where left < right:

https://github.com/dotnet/runtime/blob/9367edc6fbd500e45cf80b3f00135de771766620/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.AddSub.cs#L132-L162

The final assert checking that carry == 0 also ends up failing. It isn't clear to me whether the final result is accidentally correct for the particular examined inputs or because it happens to work with the invariants required by this particular implementation of Barrett's algorithm.

eiriktsarpalis commented 9 months ago

I fuzzed the .NET 8 implementation with FsCheck, using parameters that trigger the assert failing:

using FsCheck;
using FsCheck.Fluent;
using System.Numerics;

Config configuration = Config.Quick.WithMaxTest(10_000_000);

Parallel.For(0, Environment.ProcessorCount, i =>
{
    Prop.ForAll<(int, int, byte)>(t => ModPowPropertyTest(t.Item1, t.Item2, t.Item3))
        .Check(configuration);
});

static bool ModPowPropertyTest(int valueSeed, int modulusSpread, ushort exponent)
{
    if (Math.Abs(valueSeed) < 2 || exponent < 2)
    {
        return true; // Skip trivial values
    }

    // Arrange
    BigInteger value = (BigInteger)valueSeed << 1024; // To trigger the bug, uint[] representation needs to start with at least 32 zeros.
    BigInteger modulus = value + modulusSpread; // The modulus must be approximately the same size as the value.

    // Act
    BigInteger result = BigInteger.ModPow(value, exponent, modulus);

    // Assert
    BigInteger expectedResult = 1;
    for (int i = 0; i < exponent; i++)
    {
        expectedResult = (expectedResult * value) % modulus;
    }

    return expectedResult == result;
}

After 160 million runs, no invalid outputs were detected. @jeffhandley I think we could try removing the asserts to unblock @bartonjs's work.

bartonjs commented 9 months ago

BigInteger value = (BigInteger)valueSeed << 1024; // To trigger the bug, uint[] representation needs to start with at least 32 zeros.

If keeping a bit set in the least significant segment works around the problem, I'll give that a go.

bartonjs commented 9 months ago

It seems to be more nuanced than just keeping a low bit set, since the number described by

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
buf[^1] = 1;

still asserted; but 00 02 01 01 01 01 ... 01 01 01 01 didn't). So it's probably a "can't have a chunk of all zeros" where chunk is, presumably, defined.

bartonjs commented 9 months ago

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);

yields

 Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

adding in buf[^1] = 1

yields

  Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

Which looks the same to me.

eiriktsarpalis commented 9 months ago

The two inputs trigger the same condition. TL;DR the implementation calculates the value $n^2$ and then attempts to subtract from it a value $q_2$ that is known to be smaller than that square (modulo $m + 1$). The problem is that it does so by applying a performance optimization that truncates the input values down to the $\log (m + 1)$ least significant digits, however this truncation operation can invalidate the original assumption that $n^2 \ge q_2$.

If the least significant digits of the input value $n$ are zero, or almost zero, then squaring that value will essentially double the number of least significant digits that are zero, which triggers the above condition.

dotnet / runtime