## Friday, July 24, 2015

### 52 Things: Number 42: Look at your C code for Montgomery multiplication above; can you determine where it could leak side channel information?

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 23rd 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

Here 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.