*This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post (spoiler alert!) we enumerate various flavours of side-channel attacks.*

A
few months ago (back in March) you may remember I posted for the 23

^{rd}of the 52 things in this series (can be found here). The article was entitled “Write a C program to implement Montgomery arithmetic” and contained parts of an implementation to do this. In this article we are going to look at this implementation and see how it could leak information to give us a practical idea of what leakage may look like.
Before
progressing however I would like to remind you of my last post which
examined the difference between SPA and DPA attacks. You will
remember from there that SPA attacks use a single or very few traces and
work by spotting trends in the pattern (such as timing or instruction
sequences) while DPA attacks use many traces and aim to derive
intermediate vales of an algorithm and thus the secret information by using hypotheses of the secret data and a correct leakage model.
Before looking at the Montgomery multiplication algorithm then it is
worth stating from the outset that if hypotheses of secret data and
corresponding leakage models can be derived for the algorithm, DPA style attacks can be used to derive
intermediate values which will mean that the algorithm will leak data
being processed. If this data is therefore secret, we can
already say that this algorithm is going to leak through using DPA
style attacks.

As
mentioned in my last post however, we know that DPA style attacks
are significantly harder than SPA as they require the ability to form
hypotheses of secret data, more traces and their success will depend
significantly on the noise produced by the device. The question then
is how our implementation will leak using SPA attacks where things
such as timing or sequences of instructions being executed can be
exploited. To understand this lets look at each of the four stages I
presented for the algorithm last time separately. Things we are
interested in are things such as conditional statements or loops as
this may be exploited for timing attacks.

###
**1.****
****The
GCD Operation**

**This section uses the binary extended gcd operation to find the integers**

**r**

^{-1}**and**

**m’**

**such that**

**rr**

^{-1}**= 1 + mm’**

**. If we assume therefore that our algorithm for the extended gcd operation runs in constant time then we can assume that this operation is safe.**

###
**2.****
****Transform
the Multipliers**

**This stage computes**

**abar = ar mod m**

**and**

**bbar = br mod m**

**and therefore as this is a simple operation, it is unlikely to leak provided the operations and instructions required (such as the multiplier) run in constant time.**

###
**3.
Montgomery Multiplication**

**This is the main section of the algorithm. The first sub-stage to of the function is to calculate**

**t = abar*bbar**

**and in the same way as the previous two stages we can assume no leakage.**

**The second stage however is the computation of**

**u = (t + (tm’ mod r)m)/r**

**and it is here that we encounter**

**two conditional statements the first i:**

**if (ulo < tlo) uhi = uhi + 1;****which allows for a carry as we have a 128 bit implementation on a 64 bit architecture (see article for more information). Observing the time of execution or a power trace will therefore give insight into whether or not this conditional was executed and therefore whether or not these ulo was higher than tlo.**

**Again we have a second conditional statement which tests if u >= m.**

**if (ov > 0 || ulo >= m)**

**ulo = ulo - m;****This will also reveal whether either of these conditions is true and thus leak information about the**

**values being worked on**

**.**

###
**4.
The Inverse Transformation**

**He**

**re**

**we compute**

**ur**

^{-1}**mod m which is the product of**

**a and b modulo m**

**.**

**In the same way as stages 1 and 2 did not leak we can also say that this stage will not leak.**

## No comments:

## Post a Comment