Reading a power trace

A smart card computing c^d mod n one bit of d at a time. What does its current draw look like while it does that?

The trace, unlabelled

Eleven bumps in supply current, roughly periodic, four of them following another closely enough to read as one wider group

timesupply current

Nothing here is labelled yet — that is the point of looking once before knowing what to look for.

The algorithm behind it

result = 1
for bit in d (high to low):
    result = result * result mod n      # always happens
    if bit == 1:
        result = result * c mod n       # only on a 1-bit

Every loop iteration squares. Only a 1-bit also multiplies.

The trace, labelled

The same eleven bumps, each marked as a squaring or a multiply; the four squaring-and-multiply pairs fall exactly on the 1 bits of the exponent

SMSSMSMSSSM1011001bits of d, high to low

The key is now readable by eye, one bit at a time.

One trace was enough here

Because this implementation never varied its own timing or shape by anything but the secret bit. Real implementations try hard not to be this readable — which is exactly why differential power analysis exists: average enough traces, and even a much smaller, noisier difference survives.

Before the Bench

Bring the habit of reading a trace as a sequence of operations, not a waveform. The Trace Analysis Lab supplies a trace from a program that does not make it this easy.