Side-channel leakage in the mpz_powm_sec interface

[Hubert Kario]

On Friday, 25 August 2023 14:02:51 CEST, Niels Möller wrote:
> 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*.

haven't tested with different moduli

>> 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'm afraid this is too deep in the code for me to immediately follow...
Is this with relation to the input or the output?
Which low order bits should I test, base, exponent, modulus, or result?

> 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.

could help with other side-channel attacks, like power attack

>> 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.

without a _sec variant of the mpz_limbs_write()/mpz_limbs_finish() pair
I don't see how it can be used. And given that there is no 
mpz_mul_mod_sec(),
I don't see how mpz_powm_sec() alone can be used for RSA (given that means 
no
CRT). While you can do RSA without CRT, that sounds to me like a toy
implementation, not something you'd would want to use in production.

So that means it is useful for FFDH only, but then you should use ephemeral
one where side channel doesn't matter much...

-- 
Regards,
Hubert Kario
Principal Quality Engineer, RHEL Crypto team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic