6
$\begingroup$

I'm trying to reconstruct the fairly well-known RSA timing attack by Kocher. I'm working with simulated timing data, so I have completely noise-free "measurements". My attack is successful in guessing the exponent, as long as I use a "right-to-left" square and multiply method, i.e. an algorithm as follows (R=b^d mod m, with d having w bits):

R = 1
for i from 0 to w-1:
  if getbit(d, i) == 1:
    R = R * b mod m
  b = b * b mod m

The attack hinges on the conditional reduction when using Montgomery modular arithmetic, which my simulation uses. For each bit, I simulate the two paths (bit is zero/one) and group my measurements by whether an additional reduction was performed. I choose the path which shows the larger difference of means between the groups. Another criteria that works well is checking which path reduces the empirical variance of all measurements when I subtract the time taken by the square+mult vs just square.

Now I'm trying to adapt the attack to a left-to-right square and multiply:

R = 1
for i from w-1 to 0:
  R = R * R mod m
  if getbit(d, i) == 1:
    R = R * b mod m

I can't seem to find a suitable criteria to choose between the two paths when iteratively guessing the bits. When I just press on, correcting wrongly guessed bits as I go along, the attack still works on the lower bits, but is completely wrong (always guessing 1) for the higher bits in the beginning. I can't find any sources on how to adapt the attack to this kind of square and multiply algorithm.

$\endgroup$
2
  • $\begingroup$ On how many upper bits? $\endgroup$
    – kelalaka
    Aug 24 '20 at 7:17
  • $\begingroup$ Only the lower 8-10 bits start to produce a correct result, no matter how long the exponent. $\endgroup$
    – Richard
    Aug 24 '20 at 7:29
1
$\begingroup$

I was finally able to adapt the attack. The solution is to use the reduction of the squaring of the following bit as a discriminator between the two groups. That is we split into two paths, i.e. (R^2 mod m)^2 mod m and (R^2*b mod m)^2 mod m. For each path we create two groups by whether the final mod has an additional reduction. Finally we check which two groups has a higher difference of means, just like the right-to-left variant. This works very nicely, except for the last bit, which we can simply solve by checking for a difference in variance as before.

$\endgroup$

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.