PolarSSL and RSA blinding

I have made a patch for PolarSSL. But it seemed not to be included.

Also, I wrote to the authors of the paper in October, but I haven't got any reply, unfortunately.

So, I am writing here, my thought around the improvement as a record.

Note that this changes are included within my own branch of PolarSSL in Gnuk.

This would mean doing the Right Thing is difficult. But my philosophy is that: it's enough when I am not defeated, it's no need to pursue triumph.

The paper in question

This is the paper: "Timing Attack against protected RSA-CRT implementation used in PolarSSL", written by Cyril Arnaud and Pierre-Alain Fouque.

This is an excellent paper. However, in my humble opinion, the implementation was not "protected" well enough. Thus, I think that the description of "protected" is not accurate and it led to "blind" approach with no fixing the cause.

PolarSSL Security Advisory 2013-05

We have CVE number: CVE-2013-5915, and it is explained in PolarSSL Security Advisory 2013-05.

The work around was introduced to prevent the attack. It's called RSA blinding.

RSA blining

This technique is old one. I would like to refer the RSA bulletin #2: Timing Attacks on Cryptosystems. You see the URL. It's FTP.

This is basically work around. Besides, the algorighm was not accurately described in the bulletin. In the step 1, we need to check the secret random number is relatively prime to N. If not, loop the step 1.

Well, this check was not there in the original change of PolarSSL. I reported this issue, and it was fixed in 1.3.x.

The fix

The attack mounts the timing difference of mpi_mul_hlp, which is shown in Fig. 5 in page 6, as green and blue/red curves (as MONTMUL) in the paper.

There is also have timing difference between blue and red curves. If my analysis is correct, this is due to mpi_sub_hlp.

I fixed those two implementations to be constant time, without losing its performance. Patch for PolarSSL 1.1.4 and Patch for PolarSSL 1.2.10 are available on this site.