Side-channel leakage in the mpz_powm_sec interface

[Niels Möller]

Hubert Kario <hkario at redhat.com> writes:

> On Friday, 25 August 2023 07:51:10 CEST, Niels Möller wrote:
>> And that's for all inputs? Nice.

> Well, not all, I mostly tested ones that had obvious patterns, like
> zero to power zero, 0xff to power 0xff, full word to power of 1, full
> word to power (mod-1), etc. All with 2048 bit operands.

Ah, I didn't mean for all possible input values, just all the input
*arguments*.

> If we're doing CRT, then the modulus isn't public either,

You're right, of course.

The leak I was thinking of was using plain binvert_limb on the least
significant limb of the modulo, which includes this table lookup on bits
7-1: https://gmplib.org/repo/gmp/file/tip/gmp-impl.h#l3378

I think older versions of mpn_sec_pown use to do that, and at the time, I
figured it was not a big problem. I'm not aware of any interesting
attacks on RSA where it helps to know just a few of the least
significant bits of the secret factors.

> I did test GnuTLS (and we have discovered an issue: CVE-2023-0361),
> but haven't found any side-channels related to numerical operations.
> AFAIK, that was fixed as a result of CVE-2018-16868, and GnuTLS is
> using only mpn interfaces throughout for RSA operations now.

Nice. Then I should have a look at how they do things if/when I rework
RSA in Nettle.

> Thus, I think it's more of a documentation issue than code issue:
> it will be much better to just say that mpz_powm_sec() is not usable for
> cryptographic purposes and to deprecate it.

Not sure if "unusable" is right, but besides that, I agree documenting
the problem, and discouraging usage, is reasonable action.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.