TFM fp_exptmod producing unexpected result

[git-n-pissed]

I've been playing around with various RSA libraries and found an oddity in the pow3_ function which uses TFM fp_exptmod. I'm not sure if what I'm seeing is an error, but it isn't what I'm expecting. Here is the test I'm running on an ESP32-S3:

from _crypto import NUMBER as tfm
from adafruit_rsa.core import fast_pow as adf_pow
from time import ticks_diff, ticks_ms

import random
import sys

tfm_pow = tfm.exptmod

def main():
    l = []
    for i in range(0, 10):
        a = random.randint(0, sys.maxsize)
        b = random.randint(0, sys.maxsize)
        # b = 65537  # 65537 is standard for reasons
        c = random.randint(0, sys.maxsize)
        # c = 2048  # 2048 bit max to prevent overflow per TFM_CHECK comment

        l.append((a, b, c))

    # Test tfm
    tfm_results = []
    start = ticks_ms()
    for a, b, c in l:
        tfm_results.append(tfm_pow(a, b, c))

    stop = ticks_ms()
    print('tfm_pow: ', ticks_diff(stop, start))

    # Test adf
    adf_results = []
    start = ticks_ms()
    for a, b, c in l:
        adf_results.append(adf_pow(a, b, c))

    stop = ticks_ms()
    print('adf_pow: ', ticks_diff(stop, start))

    # Verify both functions had the same output
    print('Results are identical: ', tfm_results == adf_results)

    if tfm_results != adf_results:
        print('Test inputs:')
        print(l)
        print()
        print('TFM results:')
        print(tfm_results)
        print()
        print('ADF results:')
        print(adf_results)

if __name__ == "__main__":
    main()

And here is the adafruit fast_pow function. The output of the function below always matches the output of CPython's pow function as well:

def fast_pow(x: int, e: int, m: int) -> int:
    """
    Performs fast modular exponentiation, saves RAM on small CPUs/micros.

    :param int x: Base
    :param int e: Exponent
    :param int m: Modulo
    """

    X = x
    E = e
    Y = 1
    while E > 0:
        if E % 2 == 0:
            X = (X * X) % m
            E = E // 2
        else:
            Y = (X * Y) % m
            E = E - 1
    return Y

And here are the results:

MicroPython v1.19.1-709-g0219c40e2-dirty on 2022-12-16; ESP32S3 module with ESP32S3
Type "help()" for more information.
>>> import pow
>>> pow.main()
tfm_pow:  9
adf_pow:  112
Results are identical:  False
Test inputs:
[(1965509468, 1387443297, 1605567237), (1871294224, 1902723300, 752900670), (1233710178, 1838389496, 1357457465), (1632487816, 1367755825, 1923817713), (442177334, 385651918, 144762972), (488834613, 74276846, 1063867451), (1029344430, 2060678614, 294479980), (1412723309, 1652848341, 2144438478), (457083566, 747582368, 583126214), (580365312, 1089030014, 32)]

TFM results:
[1132155764, 0, 81381301, 488747596, 0, 681878736, 0, 0, 0, 0]

ADF results:
[1132155764, 278440606, 81381301, 488747596, 28485700, 681878736, 227706460, 238573763, 62767214, 0]

It is unclear to me why the fp_exptmod output isn't matching other pow implementations. I have tried disabling TFM_CHECK and TFM_TIMING_RESISTANT, but disabling the former doesn't appear to make any difference, and disabling the latter results in a stackoverflow.

[dmazzella]

@git-n-pissed fixed by 6695e73 can you verify?

[git-n-pissed]

@git-n-pissed fixed by 6695e73 can you verify?

Yup, that fixed it! Any idea why TFM is exhibiting this behavior?

[dmazzella]

the montgomery reduction d = a**b (mod c) need odd c (modulus) to work correctly

probably a clean solution could be

if (fp_isodd(&c_fp_int) == FP_YES)
{
    fp_exptmod(&a_fp_int, &b_fp_int, &c_fp_int, &d_fp_int);
}
else
{
    fp_pow3(&a_fp_int, &b_fp_int, &c_fp_int, &d_fp_int);
} 

[dmazzella]

Honestly, I would like to leave the exptmod function unchanged and trigger an exception in the case of even modulus. in addition to the exptmod method I also add the fast_pow method to be called if it is required.

what do you think?

[git-n-pissed]

I think checking for an odd modulus was a good idea. Should be more performant than letting the unnecessary processing of exptmod happen only to then have to handle an exception and then call fast_pow. Another option would be leaving exptmod as is, but updating fast_pow to use exptmod in the event of an odd modulus.

[dmazzella]

i have opted to tomsfastmath.exptmod(x, y, z, safe=True) with default value false and added fast_pow method

[dmazzella]

closed this issue as resolved, in case of problems do not hesitate to reopen it.

Thanks for the report and testing

[git-n-pissed]

closed this issue as resolved, in case of problems do not hesitate to reopen it.

Thanks for the report and testing

I think one additional change may be needed here, or perhaps a revert. Before this change was implemented, an even modulus would fail. I think that implementation was correct, because if an even modulus is allowed, that means one of its factors is 2. If the intent was for the exptmod function to perform generic modular exponentiation operations I think this change would have been appropriate, but the goal is the generation of strong RSA keys.

The documentation for TFM's exptmod function also claims only an odd exponent should be used. This I'm still trying to understand completely. If ucrypto uses a default exponent of 65537 as is standard, maybe it doesn't matter?

[dmazzella]

The change made by default is disabled for the very reasons you stated

[git-n-pissed]

The change made by default is disabled for the very reasons you stated

Is it not possible then for ucrypto to provide this function with an even exponent or modulus? If you believe the change made by this issue was still a good one, TFM's invmod also only works with odd modulus, and exptmod (even the current implementation which also uses fast_pow) does not accept a negative exponent. I don't think these changes are necessary, just saying ;)

EDIT:

I think the TFM documentation for invmod is incorrect (not surprising, the authors don't seem big on documentation). My testing shows it does work with even modulus. In fact, I think it invmod must work with an even modulus because n = (p - 1) * (q - 1) will always be even (right?). From the docs:

The fp invmod() function will find the modular inverse of a modulo an odd modulus b and store it in c (provided it exists).