What is “Blinding” used for in cryptography?

Question

What does "blinding" mean in cryptography, and where do we usually use it? Can you describe a sample implementation?

1) Blind RSA signatures 2) Avoiding certain side-channel attacks by working on blinded data
You might want to review Blinding and www.riscure.com/benzine/documents/rsacc_ctrsa_final.pdf

D.W. · Answer 1 · 2013-01-10 06:31:02Z

As @CodesInChaos explains:

It might refer to blind signatures.
It also might refer to a method to harden (typically) RSA implementations against timing/side-channel attacks, by blinding the data before operating on it.

Example: suppose you are writing code to decrypt data, i.e., to compute $y=x^d \bmod n$, given the input $x$. The naive way to do is just to compute $x^d \bmod n$; but it turns out this can be vulnerable to timing and other side-channel attacks. One defense is to blind the data before raising the $d$th power. In more detail, pick a random number $r$; compute $s=r^e \bmod n$; compute $X=xs \bmod n$ and then $Y=X^d \bmod n$ and then $y=Y/r \bmod n$. You can notice that $Y/r=X^d/r=(xs)^d/r = x^d s^d/r = x^d r/r = x^d \bmod n$, which is what we wanted to compute. However, this process makes it hard for an attacker to learn anything about $d$ using a timing attack, because the exponentiation process works on a random value $X$ that's not known to the attacker, rather than on the known value $x$.

Then again, it is usually not the value $x$ to-be-raised that has to be blinded, but the private exponent $d$. Your method does not blind $d$, so if the timing attack works independently of the value-to-be-raised, it has no effect at all.
@HenrickHellström, the defense I have described (namely, blinding $x$) is a standard defense against timing attacks on RSA. To my knowledge, this method of blinding defends against all known timing attacks against RSA (i.e., against all attacks that are capable of recovering $d$). I do not know of any timing attack that works if $x$ is blinded in this way (i.e., any timing attack that can recover $d$ without knowledge of the value-to-be-raised). If you know of anything that contradicts this, I'd certainly be interested to hear.
I describe it informally in my answer to this question: crypto.stackexchange.com/questions/6538/…. Basically, if you are targeting e.g. a server that performs the private key operation using CPU operations, you make it (or observe it) perform other tasks at different relative timing offsets to the start of the private key operation to be attacked. For most exponentiation implementations this will reveal each bit of the private exponent with an accuracy that depends only on how accurate the timing is.

1 Answer