0
$\begingroup$

I am trying to perform simple power analysis on RSA. In particular focusing the modular exponentiation module and for this I have implemented left-to-right variant of binary exponentiation.

pseudo code of the implemented algorithm is as follows:

Result = a^b mod N
k = length(b);

Result = 1;
for i = k-1 to 0 do
  Result = (Result X Result) mod N;   // SQUARING

  if b[i] == 1
    Result = (Result X a) mod N;     // MULTIPLICATION
  end if

end for

From the acquired power trace, I cannot differentiate between square and multiplication samples just by looking at the trace.

I also tried by performing a correlation test between the first operation(i.e. square) and all the other operations but i get the same level of correlation peaks for all the operations.

So from these observations can I conclude that my implementation is SPA resistant at least with respect to the regularity between the patterns of both operations.

My second question is, if it is SPA resistant then why in some of the cases which I read on internet have different pattern for both operations. Even though in practice they also use same multiplication algorithm for both squaring and multiplication as I did.

$\endgroup$
  • $\begingroup$ It is difficult to comment without the description of the actual modular multiplication used. Could you provide more detail/reference ? $\endgroup$ – Ruggero Oct 17 '17 at 12:25
  • $\begingroup$ I used the in-built multiplication algorithm provided by the 32-bit micro controller. $\endgroup$ – TechJ Oct 17 '17 at 12:48
  • $\begingroup$ @Techj: if N is less than about 25 32-bit words (800 bit), then you can conclude this is not secure. $\endgroup$ – fgrieu Oct 17 '17 at 17:11
  • $\begingroup$ @Techj You are supposed to work on large integer numbers. If you use the built-in multiplication it means you are dealing with 32-bit numbers. That's not RSA. $\endgroup$ – Ruggero Oct 18 '17 at 7:27
  • $\begingroup$ @Ruggero Only the modulus and message are 32-bit numbers but for the exponent I am using more than 32-bits. For this, I first convert the exponent value which is greater than 32-bit into a binary string format and then pass it to the algorithm. I know this is not the RSA used in practice, but my only question is how do I get the same pattern for both square and multiplication operations. Is it because of the multiplication algorithm implemented in hardware ? If so then how can I get to know what countermeasures are used at the hardware level to make these patterns similar to each other. $\endgroup$ – TechJ Oct 18 '17 at 15:23
1
$\begingroup$

Clearly, your code is not SPA safe. The if condition over a sensitive bit will certainly leak in timing. The time taken by a square is slower that a multiplication due to this if condition. Exemple: bit 000 will induce a Square Square Square in term of cpu instruction will have less than a bit 100 where you will perform Square Multiply Square ... Try to compare couple of operations instead of individual.

Regarding, the difference between a square and a multiply it depends on the chip you are working on, does modular operation are provided by a crypto processor? In this case, some countermeasures might have been implemented to avoid differences between a multiplication and a square.

You can share your traces if you like.

edit

Here is two SPA safe algorithm

Atomic The most elegant SPA safe algorithm, imo http://bcm.crypto.free.fr/pdf/CCJ04.pdf Fig2

The Montgomery Powering Ladder Less efficient as it is a square and multiply always (trash multiply for square) https://www.iacr.org/workshops/ches/ches2002/presentations/Joye.pdf

$\endgroup$
  • $\begingroup$ If you say that there are some countermeasures implemented at the hardware level, then how can I find which countermeasures are implemented for this purpose. $\endgroup$ – TechJ Oct 18 '17 at 15:27
  • $\begingroup$ What is the chip you are working on ? $\endgroup$ – FdLSifu Oct 19 '17 at 9:09
  • $\begingroup$ STM32F3 - ARM Cortex-M4 Microcontroller $\endgroup$ – TechJ Oct 19 '17 at 14:19
  • $\begingroup$ You don't have secure crypto coprocessor so no (hardware) countermeasures. $\endgroup$ – FdLSifu Oct 19 '17 at 15:42
  • $\begingroup$ How do you get to know if the processor is secure or not. Is it written on the website of the microcontroller, because I browsed their website but cannot find specifically written if modular multiplication is secure or not or if it is a SPA resistant. $\endgroup$ – TechJ Oct 19 '17 at 16:03

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.