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.
No comments:
Post a Comment