Due Sunday March 17, 2002, 2359 PST

Show that the following code correct and that it is not vulnerable to
differential timing/power analysis attacks. Assume that `a mod
b` is a number from `0` to `b-1` inclusive, and that
`mod_inv(a,n)` returns `b = a ^{-1}`, the
multiplicative of

/* * computes xThe attacker will try to mount a differential timing or power analysis attack. This means that the attacker can control the value of^{e}mod n, * but vulnerable to differential timing/power analysis */ static Int modexp_intern(Int x, Int e, Int n) { Int y = 1, z = x; while (e <> 0) { if (e odd) { y = y * z mod n; } z = z^{2}mod n; e = e div 2; } return y; } /* * should also compute x^{e}mod n, but does it? * should not be vulnerable to DTA/DPA, but is it? */ Int modexp(Int x, Int e, Int n) { { Int r = random(1,n); // truly random number from 1 to n-1 Int rpowe = modexp_intern(r,e,n); Int masked_x = x * r mod n; Int rpowe_inv = mod_inv(rpowe,n); // multiplicative inverse using EGCD return modexp_intern(masked_x,e,n) * rpowe_inv mod n; }

Observe that you need to do more than figure out whether one or two
"expensive operations" -- the modular multiplies -- will be done per
iteration of the loop. Since the exponent is a fixed (but secret)
value, the loop can actually be unrolled and `e`'s bit value
constant propagated to get a straight-line program. The number of
modular multiplies that occur is *fixed* and does not depend on
the input value `x` at all, even in the original vulnerable
version of `modexp` (our `modexp_intern`).

For those of you who may be having some trouble understanding the number theory, here are some simple examples.

Let's say `n = 15`, so the prime factorization is `n = 3 *
5`. The multiplicative inverse of `2` is `8`, since
`2 * 8 = 16 = 1 mod 15`. The multiplicatve inverse of
`7` is `13`, since `7 * 13 = 91 = 6*15+1 = 1 mod
15`. This is what `mod_inv` is assumed to compute. Note
that some numbers do not have multiplicative inverses. In particular,
a multiple of one of the prime factors will not: there is no number to
which `6` can be multiplied that will give you `1 mod
15`. For very large `n`, the chances of chosing such a
number randomly is negligible. (Otherwise you can factor `n`
this way: EGCD is cheap to compute, and `EGCD(6,15)=3`, giving
the factor.)

Some of you believe you can get a series of time-domain power waveforms and average them to figure out the bits of e.

*Differential* Power Analysis (DPA) is done differently,
essentially the same way that DTA is done. Often the power signal is
so full of noise -- or there is enough of on-card capacitance -- that
all you can measure is the *total* power consumed over a
long(ish) period of time -- e.g., the duration of the entire modexp
function.

One way to get a better understanding of what's going on is to imagine the following: If you unroll the loop and constant folded in the bits of e, the timing or power signature will be approximately the same. The power (timing) requirements for doing the squarings of z can be estimated with a good power (timing) model, and eliminated from any direct measurements of total power (time) required to compute any input x.

The small signal that you're trying to measure is which z value is getting multiplied into y -- you can basically know the total bit weight of e (this is the zeroth order measurement), but you don't know when these will occur in the loop. However, you can track the running values of z -- and y too, but only up to what you know so far of the (low order) bits of e. At the first unknown value of y, you can estimate the power (time) required to do the y <- y*z mod n operation, and this value of power usage (time duration) will depend on the actual values of y and z, with more power (time) needed when the result is large and require expensive calcuations in the mod n reduction step. If the bit of e that control that assignment is 1, then the power (timing) statistics that you gather should correlate with the estimated power (time) usage for this operation -- this is a weak signal, since the higher order bits of e (still unknown) will essentially be "noise" with respect to this measurement, and a largish number of measurements will be needed to detect it. (Some statistics is needed to figure out how many measurements is necessary, based on the power (timing) model.) If, on the other hand, the controlling bit of e was actually a 0, then there will be no such correlation.

Repeat until all the bits of e are extracted.

[ search CSE | CSE | bsy's home page | links | webster | MRQE | google | yahoo | citeseer | certserver ]

bsy+cse127w02@cs.ucsd.edu, last updated

email bsy.