Re: Side-channel leakage in the mpz_powm_sec interface
On Friday, 25 August 2023 14:02:51 CEST, Niels Möller wrote: Hubert Kario writes: On Friday, 25 August 2023 07:51:10 CEST, Niels Möller wrote: 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. So... how do we do that? Should I prepare a patch for this (I'm guessing that the doc sources are together with code), or are you going to do that? -- 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 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
> Therefore, > additional layers of side-channel obfuscation is needed, like standard > RSA message blinding, mod argument blinding, exponent blinding. sure, but I think that should be performed by upper level code, as how you do blinding depends on the algorithm and operation you're performing I don't think it would be mathematically possible to do any of these blinding operations in mpn_sec_powm. Not unless you successfully factor the modulus operand locally, but that might be a tad bit expensive, in particular if the factoring is to be side channel silent. :-) -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
On Friday, 25 August 2023 12:14:46 CEST, Torbjörn Granlund wrote: marco.bodr...@tutanota.com writes: This sounds not too complex to do. Even if, as usual, C code is prone to compiler optimizations... I think this is a good idea. The concern for compilers messing up secure code is very valid. An example is that clang makes our mpn_sec_tabselect useless by inserting a conditional branch instead of our mask; the generated code actually adheres to the volatile declaration, but is utterly useless for its intended purpose. In my experience inserting an __asm__ block that does nothing but uses a variable (to make it seem volatile to the compiler), is quite effective in combating this kind of optimisations It is a pity that we cannot write certain sensitive code in C. A C language extension would be welcome, perhaps some kind of "strict volatile", or an annotated conditional requiring that no branch or other conditional execution is generated as a result of it. A side note: CPU conditional move and conditional select instructions are usually poorly defined. Is there a true dependency on all inputs, or only on the actually chosen input? I've used my contacts at CPU manufacturers to address this concern, but never seen any real interest. Back to the main subject: We should probably exclude certain sec_ functions when not all sensitive functions are provided in asm, and thereby as a result of --disable-assembly? We should in essence not provide C versions of e.g., mpn_sec_tabselect. And we should perhaps provide a normalisation asm function for what Niels proposes here? I think we should document mpz_powm_sec as somewhat problematic, but also fix it along the lines of Niels' proposal. The right GMP level for side-channel sensitive application is clearly mpn; we should say that. If you decide to fix it, then both the loading of the operands from byte strings in constant time and then converting the output to a byte string in constant time will have to be both ensured and documented. As well as the fact the the operands can't be used for anything but this specific operation or the processing won't be side-channel secure. We might want to be more cautions about what we promise also for mpn. It is not necessarily sufficient to do what we do here, i.e. perform the exact same instruction sequence an data reference sequence for any two n-bit operand sets. Careful power measurements typically can fingerprint either or both operands of a bignum multiply. Therefore, additional layers of side-channel obfuscation is needed, like standard RSA message blinding, mod argument blinding, exponent blinding. sure, but I think that should be performed by upper level code, as how you do blinding depends on the algorithm and operation you're performing like, both RSA signing and decryption mathematically perform the exact same operation, but what constitutes side-channel free for them is very different -- 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 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
On Friday, 25 August 2023 14:02:51 CEST, Niels Möller wrote: Hubert Kario 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 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
On Friday, 25 August 2023 07:51:10 CEST, Niels Möller wrote: Hubert Kario 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 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
Hubert Kario 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. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
Niels Möller writes: I know you've done more work on that recently, while I have no idea how "mod argument blinding" works... A random ring extension. Yes, mod argument invariance will still be there, unless one changes extension for each multiply/squaring inside the modexp loop, but an attacker cannot cause unlimited invariance. ... if GMP can provide advice and/or tools to do it, that's nice of course. Educating people is good, and here we in particular want to make sure nobody thinks GMP's "sec" functions are the silver bullet. -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
Torbjörn Granlund writes: > We should probably exclude certain sec_ functions when not all sensitive > functions are provided in asm, and thereby as a result of > --disable-assembly? We should in essence not provide C versions of > e.g., mpn_sec_tabselect. I would suggest testing of side channel silence. That's reasonably easy to do on platforms supported by valgrind. We probably don't want to make valgrind a hard requirement for make check, but we could recommend it. > And we should perhaps provide a normalisation asm function for what > Niels proposes here? It's not quite clear to me how that is useful. It could make mpz_powm_sec silent with respect to leading zero bits in the output, but as soon as anything uses the resulting size field for accessing the limbs, we'll leak the resulting size anyway. > I think we should document mpz_powm_sec as somewhat problematic, but > also fix it along the lines of Niels' proposal. The right GMP level for > side-channel sensitive application is clearly mpn; we should say that. Agreed. > We might want to be more cautions about what we promise also for mpn. > It is not necessarily sufficient to do what we do here, i.e. perform the > exact same instruction sequence an data reference sequence for any two > n-bit operand sets. If docs don't already say explicitly what kind of side channels we try to silence, that should be made more clear. My understanding is that by ensuring that same instruction sequence and same memory accesses, we should silence leaks via timing and cache, but not leaks via any other kind of data dependency in the hardware. > Careful power measurements typically can fingerprint either or both > operands of a bignum multiply. Therefore, additional layers of > side-channel obfuscation is needed, like standard RSA message > blinding, mod argument blinding, exponent blinding. I know you've done more work on that recently, while I have no idea how "mod argument blinding" works... To me physical side channels, like consumed power in a circuit, seem too dependent both on hardware details and on the kind of access the attacker can gain to the system. And rather difficult to devise general and portable countermeasures. That said, if GMP can provide advice and/or tools to do it, that's nice of course. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
marco.bodr...@tutanota.com writes: This sounds not too complex to do. Even if, as usual, C code is prone to compiler optimizations... I think this is a good idea. The concern for compilers messing up secure code is very valid. An example is that clang makes our mpn_sec_tabselect useless by inserting a conditional branch instead of our mask; the generated code actually adheres to the volatile declaration, but is utterly useless for its intended purpose. It is a pity that we cannot write certain sensitive code in C. A C language extension would be welcome, perhaps some kind of "strict volatile", or an annotated conditional requiring that no branch or other conditional execution is generated as a result of it. A side note: CPU conditional move and conditional select instructions are usually poorly defined. Is there a true dependency on all inputs, or only on the actually chosen input? I've used my contacts at CPU manufacturers to address this concern, but never seen any real interest. Back to the main subject: We should probably exclude certain sec_ functions when not all sensitive functions are provided in asm, and thereby as a result of --disable-assembly? We should in essence not provide C versions of e.g., mpn_sec_tabselect. And we should perhaps provide a normalisation asm function for what Niels proposes here? I think we should document mpz_powm_sec as somewhat problematic, but also fix it along the lines of Niels' proposal. The right GMP level for side-channel sensitive application is clearly mpn; we should say that. We might want to be more cautions about what we promise also for mpn. It is not necessarily sufficient to do what we do here, i.e. perform the exact same instruction sequence an data reference sequence for any two n-bit operand sets. Careful power measurements typically can fingerprint either or both operands of a bignum multiply. Therefore, additional layers of side-channel obfuscation is needed, like standard RSA message blinding, mod argument blinding, exponent blinding. -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
marco.bodr...@tutanota.com writes: >> 1. Document that the mpz_t result from mpz_powm_sec always has an alloc >> size >= n, where n is the limb size of the modulo input, and that the >> limb array is zero padded up to n. >> > > You write ">= n" and not "=n" because if it was larger we avoid to > re-allocate it, right? Yep. > The application does not really need to "take advantage of" the fact > that allocated space may be larger than the strictly-needed space, > should it? I was thinking that the typical next step would be converting to an octet string, and to avoid leakage, it has to do that via some method that ignores the size field and instead uses n (the size of the modulo). Which works only assuming the new behavior. Hmm, but for the use case of an RSA secret key operation, the next step would be CRT reconstruction (since it's a standard performance optimization to do powm separately for the two secret vectors p and q). And then maybe unblinding. And then all of those operations must be done using mpn functions and size n, not mpz. So I'm leaning towards documenting this problem with mpz_powm_sec, and recommending mpn_sec_powm for applications that need side-channel silence. > A possible implementation of your 2-3 points (I didn't look at > documentation) could be the following. Looks rather neat! But I'm still not quite convinced that it is worth doing. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
Ciao,
25 ago 2023, 08:11 da ni...@lysator.liu.se:
> Niels Möller writes:
>
>> 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).
>>
> One possibly unreasonable approach for consideration:
>
> 1. Document that the mpz_t result from mpz_powm_sec always has an alloc
> size >= n, where n is the limb size of the modulo input, and that the
> limb array is zero padded up to n.
>
You write ">= n" and not "=n" because if it was larger we avoid to re-allocate
it, right?
> 2. Ensure that the implementation complies with (1) (probably easy, if
> array is written by a call to mpn_sec_powm).
>
The current implementation uses a buffer, and copies only the relevant
(non-zero) limbs at the end. As usual, this is done to handle reuse of an
operand as the result variable.
> 3. Do the normalization, i.e., assignment of the size field, by
> side-channel silent logic iterating over all n limbs.
>
This sounds not too complex to do. Even if, as usual, C code is prone to
compiler optimizations...
I think this is a good idea.
> However, any application taking advantage of (1) (and thus avoiding
> calling any other mpz functions on the result) could maybe just as well
> use mpn_sec_powm directly?
>
The application does not really need to "take advantage of" the fact that
allocated space may be larger than the strictly-needed space, should it?
But this can heal the allocation problem on the result-side. If the operand to
be passed to mpz_powm_sec is previously handled by some other mpz_ non _sec
function, then its size in memory can be different...
A possible implementation of your 2-3 points (I didn't look at documentation)
could be the following.
Also the if branch could be replaced with silent logic, but I'd rather document
that the function is silent if the base is positive.
Gis,m
--- a/mpz/powm_sec.c Fri Oct 28 16:31:44 2022 +0200
+++ b/mpz/powm_sec.c Fri Aug 25 10:38:35 2023 +0200
@@ -85,7 +85,13 @@
rn = n;
- MPN_NORMALIZE (rp, rn);
+ {
+ int z = ! rp[--rn];
+ mp_size_t cz = z;
+ for (; rn; cz += (z &= ! rp[--rn]) )
+ ;
+ rn = n - cz;
+ }
if ((ep[0] & 1) && SIZ(b) < 0 && rn != 0)
{
@@ -94,9 +100,9 @@
MPN_NORMALIZE (rp, rn);
}
- MPZ_NEWALLOC (r, rn);
+ MPZ_NEWALLOC (r, n);
SIZ(r) = rn;
- MPN_COPY (PTR(r), rp, rn);
+ MPN_COPY (PTR(r), rp, n);
TMP_FREE;
}
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
Niels Möller writes: > 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). One possibly unreasonable approach for consideration: 1. Document that the mpz_t result from mpz_powm_sec always has an alloc size >= n, where n is the limb size of the modulo input, and that the limb array is zero padded up to n. 2. Ensure that the implementation complies with (1) (probably easy, if array is written by a call to mpn_sec_powm). 3. Do the normalization, i.e., assignment of the size field, by side-channel silent logic iterating over all n limbs. However, any application taking advantage of (1) (and thus avoiding calling any other mpz functions on the result) could maybe just as well use mpn_sec_powm directly? Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Side-channel leakage in the mpz_powm_sec interface
Hubert Kario 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). > 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. > 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. 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. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
