Pull Request Bugfix for incorrect results from BigInteger exponentModulo

General JUCE discussion
1

Hi,

Curious to see if people have found BigInteger::exponentModulo and/or RSAKey::applyToValue to behave unexpectedly and if this might be the reason.

Raised this as a git issue but then I also found a potential fix.

Issue #1431:

Detailed steps on how to reproduce the bug

auto base = juce::BigInteger{3};
auto exponent = juce::BigInteger{8};
auto modulus = juce::BigInteger{5};
base.exponentModulo(exponent, modulus);
// Result is 2, should be 1

auto base = juce::BigInteger{static_castjuce::int64(85899345927)};
auto exponent = juce::BigInteger{static_castjuce::int64(85899345926)};
auto modulus = juce::BigInteger{static_castjuce::int64(85899345925)};
base.exponentModulo(exponent, modulus);
// Result is 2, should be 67108864 (0x4000000)

Created pull request #1433.

Tests for fix are in my side project aiming to port key file generation to node.
Re-ran fuzz tests for 4hrs again just to be sure (on hex strings ranging 300-1000 chars).

Cheers,
Ian.

2

I’ve been using this for years. It works without any problem. We break tons of code when we change something in this area.

I think it is a big/little endian issue. You may need to reverse the bytes of the result to get the right value.

3

have you tried the code that reproduces the bug?

Modular exponentiation is a well defined function…

4

If you see my pull request and my side project, there would be nothing that would make me happier than to be wrong.

5

I have some tests by myself with bigger keys. They work and I can use them together with other frameworks. I compared the result with the .Net framework.

I’m not using plain numbers. I’m using byte arrays. I’m pretty sure it is an endian problem. You need to reverse the result. Maybe padding is also required.

You will find some examples in this forum. Here is the decryption code of a key created with the Microsoft c# RSA library:

    BigInteger encodedTextBigInteger;
    encodedTextBigInteger.parseString(textHexString, 16);
    BigInteger rsaExponent;
    rsaExponent.parseString (exponentHexString, 16);
    BigInteger rsaModulus;
    rsaModulus.parseString (moduloHexString, 16);
    encodedTextBigInteger.exponentModulo(rsaExponent, rsaModulus);

    juce::MemoryBlock mbDecrypted = encodedTextBigInteger.toMemoryBlock();

    const int EXPECTED_LENGTH = plainKeyLength;
    if(mbDecrypted.getSize() >= EXPECTED_LENGTH)
    {
        std::unique_ptr<char[]> decrypted(new char[EXPECTED_LENGTH + 1]);
        auto p = (char*)mbDecrypted.getData() + (EXPECTED_LENGTH - 1);
        for(int i=0; i < EXPECTED_LENGTH; ++i)
        {
            decrypted[i] = *p;
            --p;
        }
        decrypted[EXPECTED_LENGTH] = 0;

        String plainText((CharPointer_ASCII)decrypted.get());
        return plainText;
    }
6

Ok but if you’re encrypting with an incorrect modPow function and then using the same function to decrypt doesn’t that give you a false positive?

Does 3^8mod 5 using juce give you 2 or 1?

The applyToValue function uses a while loop that depends on the correctness of the modPow to avoid infinite loop so this concerns me a bit.

Do you pay for compute on a server that runs applyToValue?

7

As I said. I encrypt with the c# library and decrypt with juce.

I don’t use this method.

The docs say:

Creates a BigInteger containing an integer value in its low bits.

You need to read the result the right way.

You will find more examples if you search the forum.

8

decrypt with juce?

static XmlElement decryptXML (String hexData, RSAKey rsaPublicKey)
    {
        BigInteger val;
        val.parseString (hexData, 16);

        RSAKey key (rsaPublicKey);
        jassert (key.isValid());

        std::unique_ptr<XmlElement> xml;

        if (! val.isZero())
        {
            key.applyToValue (val);

            auto mb = val.toMemoryBlock();

            if (CharPointer_UTF8::isValidString (static_cast<const char*> (mb.getData()), (int) mb.getSize()))
                xml = parseXML (mb.toString());
        }

        return xml != nullptr ? *xml : XmlElement ("key");
    }

Also, my primary focus is on the correctness of the exponentModulo function as per the title.

9

Yes, we use exponentModulo to decrypt something and it does it the right way.

You probably need to inverse the bytes from the memory block to get a valid String.

10

Please, if the following is wrong, then I am wrong, there is no other way here (juce 8.0.2):

auto base = juce::BigInteger{3};
auto exponent = juce::BigInteger{8};
auto modulus = juce::BigInteger{5};
base.exponentModulo(exponent, modulus);
// Result is 2, should be 1

auto base = juce::BigInteger{static_castjuce::int64(85899345927)};
auto exponent = juce::BigInteger{static_castjuce::int64(85899345926)};
auto modulus = juce::BigInteger{static_castjuce::int64(85899345925)};
base.exponentModulo(exponent, modulus);
// Result is 2, should be 67108864 (0x4000000)
11

I was on the wrong way here. The test didn’t pass.

We probably have a bug in the toInteger() method. This returns the right result: 
    auto base = juce::BigInteger((uint32)3);
    auto exponent = juce::BigInteger((uint32)8);
    auto modulus = juce::BigInteger((uint32)5);
    base.exponentModulo(exponent, modulus);

    juce::MemoryBlock mbDecrypted = base.toMemoryBlock();

    const int EXPECTED_LENGTH = 16;
    if(mbDecrypted.getSize() >= EXPECTED_LENGTH)
    {
        char decrypted[EXPECTED_LENGTH + 1];
        auto p = (char*)mbDecrypted.getData() + (EXPECTED_LENGTH - 1);
        for(int i=0; i < EXPECTED_LENGTH; ++i)
        {
            decrypted[i] = *p;
            --p;
        }
        decrypted[EXPECTED_LENGTH] = 0;

        String plainText(decrypted);
        std::cout << plainText << std::endl;
        REQUIRE(plainText == "2");
    }

toInteger() and the other helper functions probably do not reverse the bytes before converting them to the value.
12

I agree with your initial assessment, I think this function is broken when the modulus is smaller than the exponent. I’m not too familiar with cryptography, but perhaps this is an uncommon situation? In any case, the fix you suggested looks sensible, and I expect we’ll merge that or something very similar. I’ll update this thread once the change is published.

1 Like
13

I think this is another issue. It looks like the toInteger() function is broken. We get the right result when we read and reverse the bytes.

14

The following test fails for me, with no calls to toInteger.

static constexpr int64_t intPow (int64_t base, int64_t exponent)
{
    return exponent == 0 ? 1 : base * intPow (base, exponent - 1);
}

//...

constexpr auto base = 3;
constexpr auto exponent = 8;
constexpr auto modulus = 5;
constexpr auto expected = (intPow (base, exponent) % modulus);

BigInteger result { base };
result.exponentModulo (exponent, modulus);
expect (result == expected);
1 Like
15

Thank you for your swift attention.

16

Be careful with changes here. A lot of people use exponentModulo. It probably fails because the comparison is also broken.
The byte result works.

17

I will run fuzzing again with modulus < exponent and report back.

18

In case it’s helpful, I used the following procedure to create some tests. Run the following using python3 to generate some tuples of inputs and expected results:

import random
for i in range(100):
    b = random.getrandbits(256)
    e = random.getrandbits(256)
    m = random.getrandbits(256)
    print(f'{{ "{b:x}", "{e:x}", "{m:x}", "{pow(b, e, m):x}" }},')

Then, paste the tuples into the TestCase array in this C++ snippet:

constexpr TestCase cases[]
{
    // paste here
};

for (const auto [base, exponent, modulus, result] : cases)
{
    const auto parseAsBigInt = [] (const char* str)
    {
        BigInteger b;
        b.parseString (str, 16);
        return b;
    };

    auto computed = parseAsBigInt (base);
    computed.exponentModulo (parseAsBigInt (exponent), parseAsBigInt (modulus));
    expect (computed == parseAsBigInt (result));
}

For me, a substantial number of the test cases generated in this way fail.

1 Like
19

ok i’m using fast-check in typescript. The JuceBigInteger class is named for being a port that uses the jsbn package. The actual juce::BigInteger is coming from execTestBin:

const hexArbitrary = fc.string({
    unit: fc.constantFrom(...'0123456789abcdef'),
    minLength: 300,
    maxLength: 1000
})

    it('exponentModulo', ctx => {
        console.log(`Testing ${ctx.task.name}...`)
        type TestParams = {
            baseHex: string
            exponentHex: string
            modulusHex: string
        }
        const toResult = (params: TestParams) => ({
            fromJuce: JSON.parse(
                execTestBin('exponent-modulo', JSON.stringify(params))
            ),
            fromUtil: (() => {
                const base = JuceBigInteger.fromHex(params.baseHex)
                const exponent = JuceBigInteger.fromHex(params.exponentHex)
                const modulus = JuceBigInteger.fromHex(params.modulusHex)
                base.exponentModulo(exponent, modulus)
                return {
                    exponentModuloHex: base.toHex()
                }
            })()
        })
        // const baseString = `{"baseHex":"3","exponentHex":"8","modulusHex":"5"}`
        const baseString = `{"baseHex":"1400000007","exponentHex":"1400000006","modulusHex":"1400000005"}`
        const baseCase = JSON.parse(baseString)
        const baseResult = toResult(baseCase)
        console.log({ baseCase, baseResult })
        // expect(baseResult.fromUtil.exponentModuloHex).toBe(
        //     baseResult.fromJuce.exponentModuloHex
        // )
        let latest
        fc.assert(
            fc.property(
                fc
                    .record({
                        baseHex: hexArbitrary,
                        exponentHex: hexArbitrary,
                        modulusHex: hexArbitrary
                    })
                    .filter(
                        input =>
                            BigInt(`0x${input.modulusHex}`) <
                            BigInt(`0x${input.exponentHex}`)
                    ),
                input => {
                    const result = toResult(input)
                    latest = { input, result }
                    return (
                        result.fromUtil.exponentModuloHex ===
                        result.fromJuce.exponentModuloHex
                    )
                }
            ),
            { numRuns: 1, seed: 3 }
        )
        console.log(latest)
    })
22

Forget my tests, they don’t pass… you are probably right. It has to do with the key text and key length. We encrypt text that is smaller than the key and probably have no problem because of this.