Side-channel leakage in the mpz_powm_sec interface

[Hubert Kario]

On Friday, 25 August 2023 12:14:46 CEST, Torbjörn Granlund wrote:
> marco.bodrato at 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