Side-channel leakage in the mpz_powm_sec interface

[Hubert Kario]

On Friday, 25 August 2023 07:51:10 CEST, Niels Möller wrote:
> Hubert Kario <hkario at redhat.com> writes:
>
>> I was able to confirm that the low-level functions, like the 
>> mpn_sec_powm()
>> function have no timing leakage with regards to operands or result
>> (exactly like section 8.1 of the manual[2] states).
>
> And that's for all inputs? Nice. (I think an earlier version used a
> potentially leaking table lookup on the lowest few modulo bits, as the
> first step in computing a partial inverse. Which is probably benign in
> most use-cases, but still undesirable for a function claimed to be
> side-channel silent).

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.

If you could give me few examples of inputs that would trigger use of
different elements in the table lookups, I may look into that.

>> I wasn't able to do the same with regards to the mpz_powm_sec() function.
>> 
>> Irrespective of how I initialised the used mpz_t objects, if the operands
>> don't have high order words set, the timing of the operation is different.
>> Thus I believe that if mpz_powm_sec() is used for RSA or Diffie-Hellman
>> it would be vulnerable to the Bleichenbacher or Raccoon attacks
>> respectively.
>
> Is the main problem the normalization of the *output* of mpz_powm_sec?
> For this class of attacks, my understanding is that the secret exponents
> are fixed (when doing repeated operations on the secret key under
> attack), while the modulo is public, and the base is under the control
> of the attacker and hence already known to them.

If we're doing CRT, then the modulus isn't public either, but then that 
brings
a whole lot of other problems to the mpz interface (multiplication for
unlblinding, modulo operation, conversion from mpz to byte string, etc.)...

I haven't delved deep enough to say if it is caused by input or output, 
just
enough to be able to say that secure use of mpn API was obvious and 
trivial,
while mpn was not possible (no matter how I initialised the mpn objects
from the byte strings that were the real inputs).

>> Did I miss the methods to ensure that the objects are not clamped, or
>> should
>> the mpz_powm_sec() interface be marked as _not_ secure for cryptographic
>> purposes?
>
> It's preferable to use the mpn_powm_sec. When using mpz_t, I see no
> reasonable to avoid leakage of the normalized size (or number of
> all-zero limbs at the most significant end).
>
> Regarding Nettle (which uses GMP, and is used by GnuTLS): The RSA code
> dates from the 1990s (it's one of the oldest algorithms in Nettle), and
> has seen a series of incremental improvements over the years, but aiming
> to not break api compatibility more than necessary. Most recently
> side-channel-silent "decoding" in pkcs#1 RAS decryption. The current
> interface is more complex than I'd like, with several variants of most
> private key operations, which is a bit confusing.

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.

> It would be desirable to with a larger rework; it would be better to (i)
> use byte strings, rather than mpz_t values, for the interface to
> applications, and (ii) use only mpn-level GMP functions internally. And
> I would recommend the same approach for any other implementation of RSA
> on top of GMP.

Honestly, I don't think it's a good idea to rework mpz interfaces so that
they are actually safe for cryptography, the mpn interface is far better
to that, as you point out, all numbers in crypto should be considered
a constant length byte strings, not integers. And mpn is far more natural 
for
handling them as byte strings.

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