8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One caveat. If you access the key for your prng, you may introduce another side channel. $\endgroup$ – user27950 Oct 1 '17 at 8:51
  • $\begingroup$ Does "I don't have access to an entropy source" also mean that you do not have access to half-decent PRNG expected to give different results form one call to the other (without relying on message and key)? What about making such PRNG using some remanent memory (EEPROM, Flash..) rendered tear proof the usual (and hard) way? $\endgroup$ – fgrieu Oct 5 '17 at 15:41
  • 1
    $\begingroup$ @fgrieu The RSA private key operation (exponentiation or using CRT parameters) must be deterministic and purely functional. It only takes the key and message as parameters and may not access global variables or perform input/output. The higher-level function rsa_sign takes an additional parameter rng_state which the caller must initialize from good entropy, that's why padding works fine but blinding is a problem. As an engineering problem, I have a workaround anyway, but I want to know whether I can implement RSA with useful blinding under these constraints. $\endgroup$ – Gilles Oct 5 '17 at 16:00
4
$\begingroup$

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 process:
    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 expected 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 requires 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 consider as a good entropy source, but this is only a one-time entropy source, so if you simply seeds 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.

$\endgroup$
  • $\begingroup$ Let me try to summarize. The concern is a leak of the exponent in the modular exponentiation operation(s). If the adversary can deduce the exponent in one observation then all is lost, they have (a representation of) the private key. If the adversary needs to observe the operation many times to reconstruct the key, blinding thwarts her by exposing a different representation of the key each time. A deterministic blinding where the same exponents are used many times defeats the purpose because she gets to make many observations with the same exponent and so can reconstruct the key. Correct? $\endgroup$ – Gilles Oct 5 '17 at 17:22
  • $\begingroup$ That's what I'm thinking... But I don't want to be categorical, I couldn't really find a relevant paper on the topic, so I'll think about it a bit more, research it a bit more and let you know if the message mask saves you or not. The problem is that when you blind the decryption, what you want to do is to decorrelate the leakage and the input ciphertext, but if the mask is fixed, then the correlation is still there. $\endgroup$ – Lery Oct 5 '17 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.