6
$\begingroup$

In the so called "blinding" technique for RSA, prior to decryption, the ciphertext is multiplied by random $r$ raised to the power of $e$; e.g., $C$ is replaced with $C\cdot r^e$; and then after decryption, the result $(C\cdot r^e)^d\equiv C^d\cdot r\pmod n$ is divided by the random $r\pmod n$.

Is that efficient against timing or power attack? I saw that technique in some articles, nevertheless I though that the power / timing attacks are aiming at discovering the bits of the exponent $d$, and if so, the value of the cipher text, whether its $C$ or $C\cdot r^e$ does not really matter, does it?

$\endgroup$
8
$\begingroup$

Blinding protects against some side channels attacks in RSA: those that target variations in timing or other side channel information as a known function of $C$ (or $C^d\bmod n$ should that end up to be available).


As noted in the question, blinding is pointless against the most basic (Simple) Power Analysis attack, which determines the bits of the private exponent $d$ (or the CRT exponents $d_p$ or/and $d_q$) by finding from power traces if binary exponentiation is performing a multiply or not. Protection against such attacks must be by other ways (e.g. using a Montgomery ladder, a randomized exponentiation algorithm, or/and making square fully undistinguishable from multiply from a hardware standpoint, including when measuring execution time between these operations).

However, blinding is useful as a countermeasure against some timing attacks, which operate differently. In essence, they correlate variations of execution time (for the same unknown $d$ ) with the particular value of $C$ being deciphered, or the deciphered result. The original idea is in Paul C. Kocher's Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, in proceedings of Crypto 1996. With blinding, the attacker is deprived from direct information about what the exponentiation has as input or output, which both are masked with random secret $r$. Some implementations do not even care to make the computation of $r^e\bmod n$, $C\cdot r^e\bmod n$, or $r^{-1}\bmod n$ constant-time, or/and make $r$ much smaller than $C$.

Even when exponentiation is inherently constant-time (as many carefully written or/and hardware implementations are), blinding can also be useful against other side-channel attacks, in particular those targeting variations in power consumption / electromagnetic emission according to known $C$ .


Details per comment

One of the reason that the execution time of the computation of $C^d\bmod n$ depends on $C$ can be that modular reduction modulo $n$ sometime needs to fix a bad estimation of quotient. For example, the HAC's algorithm 14.28 for classical modular multiplication uses algorithm 14.20 for multiple-precision division, which step 3.4 reads

if $x<0$ then set $x\gets x+y\,b^{i−t−1}$ and $q_{i−t−1}\gets q_{i−t−1}-1$

with the condition $x<0$ rare (enough that it won't occur for most parameters to algorithm 14.28, but still frequent enough to be observable for random inputs), and the conditional computation lasting a significant time ($x$ and $y$ are vectors of machine words).

In the following, we'll assume that modular multiplication takes sizably varying time according to parameters; that the time it takes is predictable as a function of the two inputs to be multiplied; that the adversary measures execution time of the computation of $C^d\bmod n$ for many values of random $C$ (no power analysis involved); and that this computation is per left-to-right binary exponentiation, as:

  • $S\gets C$
  • for each bit of $d$ from high order to low, except the highest one
    • $S\gets S^2\bmod n$
    • if the current bit of $d$ is set
      • $S\gets C\cdot S\bmod n$

The attack tests if overall execution time conclusively correlates positively with the (computable!) execution time of $S\gets C\cdot S\bmod n$ with $S$ initially $C^2\bmod n$. That computations occurs if the bottom step of the algorithm is executed on the first iteration of the for loop. If such correlation is found, the attack concludes that the second-highest order bit of $d$ is set; otherwise, clear. While there are other sources of timing variation than those in the particular $S\gets C\cdot S\bmod n$ targeted, and they are cumulatively much larger, correlation of enough measurements cancels out these other sources, because they occur practically independently of the tiny variation targeted.

The attack can then proceed and test if overall execution time conclusively correlates positively with the execution time of $S\gets C\cdot S\bmod n$ with $S$ initially $C^4\bmod n$ (if the previous detection found the bit clear), or $C^6\bmod n$ (otherwise). This will reveal the third-highest order bit of $d$.

All bits of $d$ can be found this way (though only some fraction is enough to mount a factorization). The attack can be improved, in particular leverage timing variations in the next $S\gets S^2\bmod n$ step; guess several bits of $d$ simultaneously to get even stronger correlation; and recover from an accidental wrong decision (no later correlation is observed). There's a trade-of between number of available measurements, and post-processing cleverness/effort necessary to find $d$.

Reference for essentially that attack: Jean-François Dhem, François Koeune, Philippe-Alexandre Leroux, Patrick Mestré, Jean-Jacques Quisquater and Jean-Louis Willems; A Practical Implementation of the Timing Attack, in proceedings of CARDIS 1998.

Blinding prevents this archetypal class of timing attacks very well. It is also effective against some power-analysis variants, which test if power traces varying according to $C$ best correlate with this or that hypothesis on early-tested bits of $d$.


[Note following other comment: the attack does not directly target the timing variation caused by the guessed bit of $d$ being set or not (it can't, because that bit is fixed, thus there is no such variation). Rather, the attack targets the timing variation caused by $C$. The attack determines if the overall computation time is correlated with variations that would occur, or not, depending on if the guessed bit of $d$ is set or not.]

$\endgroup$
  • 1
    $\begingroup$ Why in the binary exponentiation the execution time is a function of the deciphered word C ? $\endgroup$ – Evgeni Vaknin Jan 17 '18 at 12:08
  • $\begingroup$ Thank you so much....so I think you said that if the bit of C *C^2 is 1 you do step 3.4 if the bit of d is set and this affects the timing...I want to ask again about the power attack. If I do it in Hardware, and instantiates two modules to work in parallel in synchronize manner, one with d and one with d' (binary complement), would that consume the same power for any value of d? Thanks! $\endgroup$ – Evgeni Vaknin Jan 17 '18 at 16:04
  • $\begingroup$ @Evgeni Vaknin: I'm saying something significantly different from your summary. I edited my answer again, adding a bracketed note explaining that difference. Also, I introduce earlier that the HAC's algorithm 14.20 step 3.4 is only a possible source of timing variation, but that the same attack work generically regardless of the cause of such variation. I do not answer your hardware question, because the attack (and those that blinding prevent) do not target variations according to $d$, which would fail since $d$ is fixed. They target variations according to $C$, and how they depend on $d$. $\endgroup$ – fgrieu Jan 17 '18 at 16:52

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.