Masked RSA/BigInt Arithmetic?

Mark

5/25/23, 11:40 PM

Masking is the process of replacing operations (internally to some cryptographic algorithm) on intermediate values with operations on secret shared values. Then, even if some number of these secret-shared values leak (say due to various side-channel attacks), one can maintain security (due to the information-theoretic security of the secret-sharing scheme).

I'm interested in the possibility of masked bigint arithmetic. Namely, one represents $x\in \mathbb{Z}_{2^{2048}}$ (for example) as

$$x = \sum_{i = 0}^{63} x_i 2^{32i}$$

where each $x_i \in\mathbb{Z}_{2^{32}}$, and we sill be masking each $x_i$ individually. Standard addition and multiplication of the masked shares are rather straightforward --- I'm in particular curious how one deals with carrying.

This seems like the kind of thing that someone should have worked-out in the literature, specifically to mask RSA implementations. But I haven't been able to find anything (I've seen some discussion of masked RNS implementations of RSA, which is more straightforward conceptually). Is it known how to mask BigInt arithmetic?

0 + 0

rsa

side-channel-attack

kelalaka

5/25/23, 11:43 PM

Doesn't OpenSSL have implementation for masking? AFAIK there is nothing special since it has some ported GNU/GMP.

Mark

5/25/23, 11:53 PM

@kelalaka has anyone written up somewhere what they do? Thanks to your pointer I've found [this](https://github.com/openssl/openssl/blob/1c0eede9827b0962f1d752fa4ab5d436fa039da4/crypto/bn/bn_blind.c), but it would definitely be preferable for me to look at pseudocode.

kelalaka

5/25/23, 11:57 PM

It takes time to read the code, I now, What are you looking [here](https://github.com/openssl/openssl/blob/1c0eede9827b0962f1d752fa4ab5d436fa039da4/crypto/bn/bn_blind.c#L134) and see the line 155 there.

kelalaka

5/26/23, 12:23 AM

_and we s**t**ill be masking each $x_i$ individually._ It is impossible since there is a mangling of the masks, right?

Mark

5/26/23, 2:03 AM

@kelalaka It doesn't seem straightforward, but neither does masked multiplication (which iirc in the general case of $n$th order masking reduces to the multiplication protocol of the GMW MPC protocol). Here, I'm mostly wondering if there is another non-obvious way to compute the "carrying" step masked --- if not, for my particular application I can appeal to a RNS type of arithmetic, but it is somewhat more awkward.

j.p.

5/26/23, 9:41 AM

Which kind of attacks are you worrying about? Timing, DPA or white-box? OpenSSL would care only about timing, so they don't need to use costly countermeasures required for the stronger attacks. For securing RSA against gray-box attack one has to protect mostly the exponent, which can be done by an additive sharing modulo phi(modulus). Additionally one can mask the base multiplicatively modulo the modulus. For stronger countermeasures need for white-box implementation, you can take a look at the [last white-box competition](https://whibox.io/contests/2021/rules) featuring elliptic curves.

kelalaka

5/26/23, 10:42 AM

@Mark would you link to GMW MPC paper?

kelalaka

5/26/23, 1:33 PM

GNU/GMP has [secure modular multiplication](https://gmplib.org/manual/Integer-Exponentiation) against side-channel. This might be what you need?