Transcript Differential Power Analysis

A paper by: Paul Kocher, Joshua Jaffe, and Benjamin
Jun
Presentation by: Michelle Dickson
Power Analysis
 Introduction
 Simple Power Analysis (SPA)
 Theory
 Experimental Results
 Prevention
 Differential Power Analysis (DPA)
 Theory
 Experimental Results
 Prevention
 Comments
Introduction
 About the paper…
 Written by Paul Kocher, Joshua Jaffe, and Benjamin Jun
of Cryptography Research, Inc in 1998
 This was the first introduction of power analysis based
side channel attacks on cryptographic systems
 All analysis and experimentation was performed on a
DES implementation
Introduction
 Power Analysis
 Power Analysis is a form of side channel attack in which
operation and key material can be exposed through the
measurement of a cryptographic device’s power
consumption
 To measure a circuit’s power consumption



A small resistor (e.g. 50Ω) is placed
in series with the power or ground input
An oscilloscope or other sampling device
captures voltage drop across the resistor
Data is transferred to a PC for analysis
Simple Power Analysis
 Theory
 This technique directly interprets power consumption
measurements to expose information about an
encryptor/decryptor
 A trace refers to a set of power consumption measurements
taken across a cryptographic operation
 Higher resolution traces reveal more information about the
circuit’s operation
 Claim
 SPA traces can reveal the sequence of instructions and can
therefore be used to break cryptographic implementations in
which execution path depends on the data being processed
Simple Power Analysis
 Experimental Results
 The figure below clearly shows the 16 rounds of a DES
operation
Simple Power Analysis
 Experimental Results
 A more detailed view shows small variations between the rounds


28-bit DES key registers C & D are rotated once in round 2 and
twice in round 3
Discernable features typically caused by conditional jumps based
on key bits and computational intermediates
Simple Power Analysis
 Experimental Results
 An even higher resolution view shows details of a single clock cycle
 Comparison of trace through two regions shows visible variations
between clock cycles caused by different processor instructions
 Upper trace shows
where a jump
instruction is
performed
 Lower trace shows
where a jump
instruction is not
performed
Simple Power Analysis
 Motivation for Prevention
 Because SPA can reveal the sequence of instructions executed, it can be
used to break cryptographic implementations in which the execution
path depends on the data being processed, such as





DES key schedule computations
DES permutations
Comparisons
Multipliers
Exponentiators
 Prevention Techniques
 Avoid procedures that use secret intermediates or keys for conditional
branching operations

Creative coding, performance penalty
 Implement hard-wired symmetric cryptographic algorithms in
hardware

Small power consumption variations
Differential Power Analysis
 Theory
 In addition to large-scale power variations addressed by
SPA, there are effects correlated to the specific data
values that are being manipulated
 Using statistical functions tailored to the target
algorithm, these much smaller variations can be
detected
Differential Power Analysis
 Detailed Theory
 A DPA selection function, D(C,b,Ks), computes the
value of bit 0 ≤ b < 32 of the DES intermediate L at the
beginning of the 16th round


C is ciphertext
Ks is the 6 key bits entering the S box corresponding to bit b
 To implement, an attacker



Observes m encryption operations
Captures m traces, each with k samples
Records m ciphertext values
Differential Power Analysis
 Detailed Theory
 Using the observation, the attacker computes a k-sample
differential trace ∆[1..k] by finding the difference between the
average of the traces for which D(C,b,Ks) is one and the average of
the traces for which D(C,b,Ks) is zero

For each sample, the differential trace ∆[j] is the average over the
measured ciphertexts of the effect caused by the selector function
D(C,b,Ks) on the power consumption measurement at the sample point
 If Ks is incorrect, the probability that D will yield the correct bit b is
½, so the trace components and D are uncorrelated. The result is
that ∆[j] approaches zero for large m.
 If Ks is correct, the computed value for D will equal the actual value
of the target bit b with probability 1, making the selection function
correlated to the bit. The result will be spikes in the differential
trace where D is correlated to the value being processed.
Differential Power Analysis
 Claim
 The correct Ks can be identified from the spikes in the
differential trace.
 Four values of b correspond to each S box, providing
confirmation of key block guesses.
 Finding all 8 key block guesses yields the entire 48-bit
round subkey.
 The remaining 8 key bits can be found by trial-and-error
or by analyzing an additional round.
Differential Power Analysis
 Experimental Results
 The figure shows 4 traces prepared using known plaintexts entering
a DES encryption function




The top trace is power
reference
Next trace is a correct key
block guess
Last two traces are incorrect
key block guesses
m = 1000 samples
Differential Power Analysis
 Experimental Results
 A more detailed view shows the average effect of a single bit on
detailed power consumption measurements




Reference power consumption
trace is on top
Standard deviation of power
consumption measurements is
next
Differential trace is last
m = 10,000
Differential Power Analysis
 Prevention
 Reduce signal sizes (still vulnerable to attacker with infinite samples)
 Constant execution path code
 Choose operations that leak less information in their power consumption
 Balance hamming weights and state transitions
 Physically shielding the device
 Introduce noise into power consumption measurements
 Randomize execution timing and order
 Design cryptosystems with realistic assumptions about the underlying
hardware
 Nonlinear key update procedures can be employed to ensure that power
traces cannot be correlated between transactions


Hashing
Aggressive use of exponent and modulus multiplication processes

Prevent attacker from gathering large numbers of samples
Comments
 Pros
 Innovative concepts, given the timeframe of the paper
 The authors successfully demonstrate that power analysis attacks
are a real security vulnerability that must be considered in new
designs and fielded devices
 Cons
 The authors claim that the attacks are (or can be) effective even if
nothing is known about the encryption implementation; however,
no evidence of this is presented
 Likely due to the pioneering nature of the paper, it lacked the level
of detail I would have desired



Discussion of how to come up with a selection function?
Quantitative comparisons for hardware vs. software implementations?
Demonstration of performance improvement for suggested prevention
methods?
Questions?
Contact information:
Michelle Dickson
[email protected]
[email protected]