4
$\begingroup$

I am trying to understand how one can retrieve the secret exponent via a simple power analysis.

Lets suppose that the exponentiation by squaring algorithm is implemented in its simplest form :

Function exp-by-squaring(x,n)
    if n<0 then return exp-by-squaring(1/x, -n);
    else if n=0 then return 1;
    else if n=1 then return x;
    else if n is even then return exp-by-squaring(x2, n/2);
    else if n is odd then return x * exp-by-squaring(x2, (n-1)/2).

As i understand,if i am to probe the consumption while the machine is calculating the exponent i will be able to see the individual operations on the spectrogram. There will be a spike between different operations so i will be able to tell when it entered the "even" condition or when it entered the "odd" condition. This simply gives me an idea about the exponent and not the actual exponent.

So if the secret exponent is 2012 (https://math.stackexchange.com/questions/563708/exponentiation-by-squaring), i will simply see that the even condition was entered 6 times and the odd condition was entered 4 times but how exactly do i use that information to find the secret exponent?

Thanks in advance

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hint: execute exp-by-squaring instrumented by printing a S each time x2 is computed (computation of either two last lines) and a M each time x * is computed (computation of last line). See how what's printed relates to n. $\endgroup$
    – fgrieu ♦
    Commented Mar 3, 2015 at 9:44
  • 1
    $\begingroup$ With he exponent 2012, you got: even (1006), even (503), odd (251), odd (125)... (rest is up to you). Even corresponds to a $0$, odd to a $1$. And one correction, it is actually 8 times even and 4 times odd. They did not actually evaluate your algorithm at math SE, but factored in things again, which they had split off previously. $\endgroup$
    – tylo
    Commented Mar 3, 2015 at 14:15

2 Answers 2

Reset to default
1
$\begingroup$

You can begin by first reading the seminal paper of Paul Kocher. He gave the reference for Timing and Power analysis attacks. The best is to read the papers, and understand the philosophy of Side Chanel Attacks. The method he described, has been enhanced by many authors, and it become impossible to ignore how to securelly implement algorithm on embedded systems. After that the most destructive attacks is the one introduced by Dan Boneh known as the "Faults Attack".

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Mael: The implementation of a exponentiation algorithm, must obey to the following principle (Not exhaustive): 1- Don't dissociate the Square from the Multiply operation, despite the loss of performances. The Square must be balanced in order to fit the chatacteristics of Multiply OP. 2- You also at least add dummy operation when scanning the current bit of exponent. The regular method is called "AllWays Multiply", but you can adapt the method called "Montgomery Ladder" initially set for Ellitic Curves to Exponentiation. $\endgroup$
    – Robert NACIRI
    Commented Dec 28, 2014 at 17:00
  • $\begingroup$ @Mael: And after, you can also try countermeasure against the faults attacks, which are the most destructive attacks. Ref: On the importance of checking cryptographic protocols for faults; D. Boneh, R. DeMillo, and R. Lipton $\endgroup$
    – Robert NACIRI
    Commented Dec 28, 2014 at 17:02
  • $\begingroup$ Thank you for contributing this answer! I do think your answer would be much improved if you could briefly summarize the key points from the references you cite in it. As it stands, your answer does not really provide a stand-alone answer to the question asked. You should also edit the additional information you've posted in the comments directly into your answer, if you think it's potentially worth retaining. $\endgroup$
    – Ilmari Karonen
    Commented Dec 28, 2014 at 17:32
  • $\begingroup$ Thanks a lot.I did take a look at Montgomery's Ladder implementation.It seems immune to the normal power analysis attacks because all conditions essentially use the same circuitry.I am however taking baby steps at a time.Some of the older systems use the basic exponentiation implementation and i am trying to understand how they were exploited. $\endgroup$
    – Mael
    Commented Dec 28, 2014 at 18:08
  • $\begingroup$ @llmari Karonen: The subject is so vast that it's better to give the best reference than trying to resume 20 years of R&D. Mael: take a look of this paper which exploit the two basic algorithms for exponentiation or equivalently how computing over a algebraic curve. Montgomery Ladder can be easilly adaptedd to RSA. cr.yp.to/bib/2003/joye-ladder.pdf $\endgroup$
    – Robert NACIRI
    Commented Dec 28, 2014 at 18:24
0
$\begingroup$

"Even" / "odd" conditions give you exactly the bits of the exponent. If you use only counts (not orders) of these conditions, you lose most of the information.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, this is true when the implementation isn't protected against timing and power analysis. Programmers try to hide the behaviours (current consumption, electronic radiation), by some appropriate countermeasures as Allways Multiply, Montgomery Ladder and other refinements. The litterature since the first attacks of Paul Kocher and many other autors, is so vast in this domain, that it's impossible to resume it here. $\endgroup$
    – Robert NACIRI
    Commented Jan 2, 2015 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.