Deterministic RSA blinding

Question

I have an implementation of the RSA private key operation in a context where I don't have access to an entropy source. I'd like to add blinding to it (both message and exponent), to make it resist some side channel attacks.

(The subsequent padding operation does have access to an entropy source. It's only the exponentiation operation that can't use an RNG.)

I can run a PRNG inside the RSA private operation if I want. My constraint is that rsa_private has to be deterministic: its operation can only depend on its inputs (message and private key).

Is it sensible to do blinding deterministically, i.e. use a PRNG that is seeded by the message and the key? And if so should it be seeded by message+key or key alone? Or does the blinding need to be unpredictable?

I'm interested in the answer for both CRT and straight $m^d$ implementations.

Answer 1

Alright, let's first agree on a few things:

• The rsa_private operation is the operation requiring knowledge of the secret RSA key. This operation is required by one of the following processes:

1. RSA signature, to ensure authenticity and integrity of a given message in a way publicly verifiable
2. RSA decryption, to decrypt a message which was sent to you, encrypted with your public key,
3. more rarely, it might also be used to encrypt a message so that it can be decrypted by anybody knowing your public key. This latest usage is disputable since it provided nothing more than a signature.

• In RSA, randomness is required at different stages:

1. When signing, with RSA-PSS (the provably secure RSA signature scheme), you'll need randomness in the PSS-encoding operation.
2. When encrypting, with RSA-OAEP (the provably secure RSA encryption scheme), you'll need randomness in the OAEP encoding operation.
3. When performing blinding on RSA operation, the blind is randomly generated.

Now, you're asking about how you could be generating your randomness without entropy, and you mentioned a PRNG, the key, and $m^d$, so I'll assume you only need randomness for RSA decryption, and to blind it.

Remark that it is not the same kind of properties that one would expect from a PRNG used in a masking scheme and a PRNG used for keys generation. When you are masking something, the PRNG mainly requires uniform distribution and other such good statistical properties. But it does not necessarily require to be a cryptographically secure PRNG. This is due to the fact that all generated values are supposed to be a secret, so you mostly require a good initial entropy source... Which could contradict your current requirements.

In my opinion, generating your randomness out of (part of) your secret key, plus the message (typically by hashing the concatenation of (part of) your secret key together with the message), is providing you with a seed that an attacker could not possibly guess without knowing your private key, so there is no security risk there.

Furthermore by definition, the private key can be considered as a good entropy source, since its generation requires good entropy and the security of the RSA scheme crucially relies on the randomness used when generating the key pair.

The method of using (part of) the private key is actually already used by EdDSA for example to deterministically generate a secret nonce, whose disclosure would allow for private key material recovery.

Now, you asked:

And if so should it be seeded by message+key or key alone? Or does the blinding need to be unpredictable?

And as I tried to explain, the private key can be considered as a good entropy source, but this is only a one-time entropy source, so if you simply seed your PRNG using the private key, and there is a way to reset the device so that it would get seeded again with that same private key, then there would be a way to get every new RSA operations to be conducted using the same random values, which actually means that you could not rely on your random values as being nonces, and the same mask would always get generated after $x$ calls to the just seeded PRNG...

One solution against this would have to be sure you can rely on a counter and seed your PRNG with the hash of your private key concatenated with that counter.
Finally, taking even more "pseudo-entropy" by also adding in the message value cannot hurt.

Fixed randomness certainly hurts, but the question is to which extent?

You didn't mentioned why and how you wanted to perform blinding, but let's say you are trying to protect against timings or power analysis (or such side-channel) attacks, and you are using blinding.

Now, it all depends on how you actually do the blinding, if you perform simple blinding by tacking a random $r$ value, computing $r^e\bmod n$ and then decrypting the message $m^e=c$ by doing $(r^ec)^d \bmod n$ and multiplying your result by $r^{-1} \bmod n$, then you really want to take a different $r$ for each computation, even of the same message, since otherwise, you would leak the secret value $d$, since the attacks target recovery of the exponent used.

Now, if you have another way to blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing: $(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem... So in the end, you really want to have a different blind for each computation.

Notice that relying on a counter means that if an attacker is able to reset that counter, then the attacker can cause the PRNG to repeat itself, which brought us back to the problem of using fixed blinds... But this might not be a problem for you, depending on the fact whether the attacker is supposed to have access, or not, to the device.

By the way, since you mentioned those, attacks against both common $m^d$ and CRT implementations exist, see most notably:

P. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS and Other Systems. In: N. Koblitz (ed.): Crypto 1996, Springer, Lecture Notes in Computer Science 1109, Heidelberg 1996, 104–113.

W. Schindler: A Timing Attack against RSA with the Chinese Remainder Theorem. In: Ç.K. Koç, C. Paar (eds.): Cryptographic Hardware and Embedded Systems — CHES 2000, Springer, Lecture Notes in Computer Science 1965, Berlin 2000, 110–125.

Finally, let me add a word regarding side-channels such as SPA and DPA: if you are using a vulnerable exponentiation algorithm (e.g. plain square and multiply, see maybe this paper for more info), SPA cannot be prevented using just masking, it depends more on your exponentiation algorithm. Timing attacks and DPA are both working if the attacker is able to gather enough traces which are correlated, so they should be defeated by using masking, as long as you avoid fixed masks.