Incorrect result when using Integer::ModInverse

[noloader]

This issue was privately reported in an email:

$ cat test.cxx
#include "integer.h"
#include "nbtheory.h"
#include <iostream>

int main(int argc, char* argv[])
{
    using namespace CryptoPP;

    Integer a("0x2F0500010000018000000000001C1C000000000000000A000B0000000000000000000000000000FDFFFFFF00000000");
    Integer b("0x3D2F050001");

    Integer x = a.InverseMod(b);
    std::cout << std::hex << x << std::endl;

    return 0;
}

Crypto++ result:

$ ./test.exe
342188107fh

Botan and OpenSSL result:

0x3529E4FEBC

---

Here is Integer::InverseMod:

Integer Integer::InverseMod(const Integer &m) const
{
	if (IsNegative())
		return Modulo(m).InverseMod(m);

	if (m.IsEven())
	{
		if (!m || IsEven())
			return Zero();	// no inverse
		if (*this == One())
			return One();

		Integer u = m.Modulo(*this).InverseMod(*this);
		return !u ? Zero() : (m*(*this-u)+1)/(*this);
	}

	SecBlock<word> T(m.reg.size() * 4);
	Integer r((word)0, m.reg.size());
	unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
	DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
	return r;
}

[denisbider]

Python agrees with OpenSSL and Botan when using this one-liner for the modular multiplicative inverse:

>>> a = 0x2F0500010000018000000000001C1C000000000000000A000B0000000000000000000000000000FDFFFFFF00000000
>>> b = 0x3D2F050001
>>> MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]
>>> m = MMI(a, b)
>>> hex(m)
'0x3529e4febcL'

[noloader]

Thanks @denisbider, @mouse07410, @MarcelRaad,

So it looks like two problems. First is a memory error due to m.reg.size() * 4:

SecBlock<word> T(m.reg.size() * 4);
Integer r((word)0, m.reg.size());
unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());

After clearing the memory error:

$ git diff
diff --git a/integer.cpp b/integer.cpp
index e9846bd..b9b4215 100644
--- a/integer.cpp
+++ b/integer.cpp
@@ -4393,8 +4393,9 @@ Integer Integer::InverseMod(const Integer &m) const
                return !u ? Zero() : (m*(*this-u)+1)/(*this);
        }

-       SecBlock<word> T(m.reg.size() * 4);
-       Integer r((word)0, m.reg.size());
+       unsigned int t = STDMAX(m.WordCount(), WordCount()) * 4;^M
+       SecBlock<word> T(t);^M
+       Integer r((word)0, t);^M
        unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
        DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
        return r;

We have the second problem, which is the incorrect result.

[noloader]

This patch will need more testing, but it arrives at the correct result for the test case above. The patch also passes cryptest.exe {v|tv}, but the test suite is [obviously] missing proper coverage here.

I asked WD about the bigint implementation several years ago because I did not recognize it. WD said he created the numerical algorithms, so we don't really have a reference to work with like Knuth, Karatsuba or the HAC.

I'm not entirely clear on the preconditions to AlmostInverse and DivideByPower2Mod. I believe WD expected most computation on a to occur over the range [0, 2m-1]. You can see the expectation in classes like ModularArithmetic. The ModularArithmetic class only produces correct results when a value a is within 2m (and the value a can be made equivalent using an addition or subtraction of m). I think a similar precondition is surfacing here, but it is only a guess.

$ cat integer.diff
diff --git a/integer.cpp b/integer.cpp
index e9846bd..d66b506 100644
--- a/integer.cpp
+++ b/integer.cpp
@@ -4380,7 +4380,20 @@ Integer Integer::InverseMod(const Integer &m) const
        CRYPTOPP_ASSERT(m.NotNegative());

        if (IsNegative())
-               return Modulo(m).InverseMod(m);
+               return Modulo(m).InverseModNext(m);
+
+       // Place *this in the range [0, 2m-1]
+       // https://github.com/weidai11/cryptopp/issues/602
+       if (*this >= (m << 1))
+               return Modulo(m).InverseModNext(m);
+
+       return InverseModNext(m);
+}
+
+Integer Integer::InverseModNext(const Integer &m) const
+{
+       CRYPTOPP_ASSERT(m.NotNegative());
+       CRYPTOPP_ASSERT(*this < 2*m);

        if (m.IsEven())
        {
@@ -4389,12 +4402,12 @@ Integer Integer::InverseMod(const Integer &m) const
                if (*this == One())
                        return One();

-               Integer u = m.Modulo(*this).InverseMod(*this);
+               Integer u = m.Modulo(*this).InverseModNext(*this);
                return !u ? Zero() : (m*(*this-u)+1)/(*this);
        }

-       SecBlock<word> T(m.reg.size() * 4);
-       Integer r((word)0, m.reg.size());
+       size_t t = STDMAX(reg.size(), m.reg.size())*4;
+       IntegerSecBlock T(t); Integer r((word)0, t);
        unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
        DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
        return r;
diff --git a/integer.h b/integer.h
index 864cdec..f073180 100644
--- a/integer.h
+++ b/integer.h
@@ -630,6 +630,10 @@ public:
        CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
 #endif

+protected:
+       // https://github.com/weidai11/cryptopp/issues/602
+       Integer InverseModNext(const Integer &n) const;
+
 private:

        Integer(word value, size_t length);

[noloader]

Cleared at Commit ff82b5a886d3 and Commit 932f392b2d33.

The ff82b5a commit cleared the bulk of the problems, including the memory error. The if (*this >= (m << 1)) to bring a into the range [0, 2m-1] was not the correct strategy, and it got fixed in the next commit.

The 932f392 commit cleared a more obscure corner case. Most runs were OK. About 1 in 13 runs produced 1 failure (each run performs about 2048 individual tests). cryptest.sh caught the problem during comprehensive testing. 90 configurations produced 7 failures.

[denisbider]

Thanks for this fix, Jeff. :) This explains a mystery that's been on the back of my mind for perhaps 15 years, that I never quite figured out previously. :D

[noloader]

@denisbider, @mouse07410, @MarcelRaad,

I think I should summarize the fix here since the first check-in was incomplete, and we needed a second check-in. In between there were lots of check-ins that added self-tests, so they created a lot of noise.

Here was the original code causing problems:

Integer Integer::InverseMod(const Integer &m) const
{
	if (IsNegative())
		return Modulo(m).InverseMod(m);

	if (m.IsEven())
	{
		if (!m || IsEven())
			return Zero();	// no inverse
		if (*this == One())
			return One();

		Integer u = m.Modulo(*this).InverseMod(*this);
		return !u ? Zero() : (m*(*this-u)+1)/(*this);
	}

	SecBlock<word> T(m.reg.size() * 4);
	Integer r((word)0, m.reg.size());
	unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
	DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
	return r;
}

Here is the fixed code. We kept the recursion but we split it into a first/next call. The "first" part validates/fixes the parameters. The "next" part applies the algorithm without the parameter fixes/validations:

Integer Integer::InverseMod(const Integer &m) const
{
	CRYPTOPP_ASSERT(m.NotNegative());
	CRYPTOPP_ASSERT(m.NotZero());

	if (IsNegative())
		return Modulo(m).InverseModNext(m);

	// http://github.com/weidai11/cryptopp/issues/602
	if (*this >= m)
		return Modulo(m).InverseModNext(m);

	return InverseModNext(m);
}

Integer Integer::InverseModNext(const Integer &m) const
{
	CRYPTOPP_ASSERT(m.NotNegative());
	CRYPTOPP_ASSERT(m.NotZero());

	if (m.IsEven())
	{
		if (!m || IsEven())
			return Zero();	// no inverse
		if (*this == One())
			return One();

		Integer u = m.Modulo(*this).InverseModNext(*this);
		return !u ? Zero() : (m*(*this-u)+1)/(*this);
	}

	// AlmostInverse requires a 4x workspace
	IntegerSecBlock T(m.reg.size() * 4);
	Integer r((word)0, m.reg.size());
	unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
	DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
	return r;
}

The modular reduction in InverseMod fixed the memory error. Once *this was reduced, the wild read and write was not a problem because the a in (a ^ -1) mod n was small enough.

The code also moved to IntegerSecBlock. This was a small cosmetic change. The rest of Integer class used IntegerSecBlock and the consistency makes it easier to audit the class for {un}aligned access.

Finally, a lot of tests were checked in to cover this case an more. Also see validat0.cpp : TestIntegerOps.

---

@randombit also suggested we setup OSS-Fuzz. I started the process yesterday.

OSS-Fuzz is a Google project and it requires a GMail address. I tried to register cryptopp@gmail.com but someone else was using it. I wrote to them and asked they give it to us for use with OSS-Fuzz.

If we don't get the email address we want then we'll use another GMail address that satisfies OSS-Fuzz and can be shared among folks like @noloader, @denisbider, @mouse07410 and @MarcelRaad.