Di(cid:11)erential Power Analysis
`
`Paul Kocher, Joshua Ja(cid:11)e, and Benjamin Jun
`
`Cryptography Research, Inc.
` Market Street, th Floor
`San Francisco, CA  , USA.
`http://www.cryptography.com
`E-mail: fpaul,josh,beng@cryptography.com.
`
`Abstract. Cryptosystem designers frequently assume that secrets will
`be manipulated in closed, reliable computing environments. Unfortu-
`nately, actual computers and microchips leak information about the op-
`erations they process. This paper examines speci(cid:12)c methods for analyz-
`ing power consumption measurements to (cid:12)nd secret keys from tamper
`resistant devices. We also discuss approaches for building cryptosystems
`that can operate securely in existing hardware that leaks information.
`
`Keywords: di(cid:11)erential power analysis, DPA, SPA, cryptanalysis, DES
`
` Background
`
`Attacks that involve multiple parts of a security system are di(cid:14)cult to predict
`and model. If cipher designers, software developers, and hardware engineers do
`not understand or review each other’s work, security assumptions made at each
`level of a system’s design may be incomplete or unrealistic. As a result, security
`faults often involve unanticipated interactions between components designed by
`di(cid:11)erent people.
`Many techniques have been designed for testing cryptographic algorithms in
`isolation. For example, di(cid:11)erential cryptanalysis[ ] and linear cryptanalysis[]
`can exploit extremely small statistical characteristics in a cipher’s inputs and
`outputs. These methods have been well studied because they can be applied by
`analyzing only one part of a system’s architecture | an algorithm’s mathemat-
`ical structure.
`A correct implementation of a strong protocol is not necessarily secure. For
`example, failures can be caused by defective computations[, ] and information
`leaked during secret key operations. Attacks using timing information[, ] as
`well as data collected using invasive measuring techniques[, ] have been demon-
`strated. The U.S. government has invested considerable resources in the classi-
`(cid:12)ed TEMPEST program to prevent sensitive information from leaking through
`electromagnetic emanations.
`
` Introduction to Power Analysis
`
`Most modern cryptographic devices are implemented using semiconductor logic
`gates, which are constructed out of transistors. Electrons (cid:13)ow across the sili-
`
`244MAX032885
`
`Maxim Exhibit 2012 - Groupon, CBM2014-00090 – Page 2012-001
`
`

`

`con substrate when charge is applied to (or removed from) a transistor’s gate,
`consuming power and producing electromagnetic radiation.
`To measure a circuit’s power consumption, a small (e.g.,  ohm) resistor
`is inserted in series with the power or ground input. The voltage di(cid:11)erence
`across the resistor divided by the resistance yields the current. Well-equipped
`electronics labs have equipment that can digitally sample voltage di(cid:11)erences at
`extraordinarily high rates (over GHz) with excellent accuracy (less than %
`error). Devices capable of sampling at MHz or faster and transferring the
`data to a PC can be bought for less than $.[]
`Simple Power Analysis (SPA) is a technique that involves directly interpret-
`ing power consumption measurements collected during cryptographic operations.
`SPA can yield information about a device’s operation as well as key material.
`
`Figure : SPA trace showing an entire DES operation.
`
`A trace refers to a set of power consumption measurements taken across a
`cryptographic operation. For example, a millisecond operation sampled at 
`MHz yields a trace containing  points. Figure shows an SPA trace from a
`typical smart card as it performs a DES operation. Note that the  DES rounds
`are clearly visible.
`
`Figure : SPA trace showing DES rounds  and .
`
`Figure  is a more detailed view of the same trace showing the second and
`
`
`
`244MAX032886
`
`Page 2012-002
`
`

`

`third rounds of a DES encryption operation. Many details of the DES operation
`are now visible. For example, the -bit DES key registers C and D are rotated
`once in round  (left arrow) and twice in round (right arrows). In Figure
`, small variations between the rounds just can be perceived. Many of these
`discernable features are SPA weaknesses caused by conditional jumps based on
`key bits and computational intermediates.
`Figure shows even higher resolution views of the trace showing power con-
`sumption through two regions, each of seven clock cycles at .  MHz. The
`visible variations between clock cycles result primarily from di(cid:11)erences in the
`power consumption of di(cid:11)erent microprocessor instructions. The upper trace in
`Figure shows the execution path through an SPA feature where a jump in-
`struction is performed, and the lower trace shows a case where the jump is not
`taken. The point of divergence is at clock cycle  and is clearly visible.
`
`Figure : SPA trace showing individual clock cycles.
`
`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. For example:
`
`DES key schedule: The DES key schedule computation involves rotating -
`bit key registers. A conditional branch is commonly used to check the bit
`shifted o(cid:11) the end so that \ " bits can be wrapped around. The resulting
`power consumption traces for a \ " bit and a \" bit will contain di(cid:11)erent
`SPA features if the execution paths take di(cid:11)erent branches for each.
`DES permutations: DES implementations perform a variety of bit permuta-
`tions. Conditional branching in software or microcode can cause signi(cid:12)cant
`
`
`
`244MAX032887
`
`Page 2012-003
`
`

`

`power consumption di(cid:11)erences for \" and \ " bits.
`Comparisons: String or memory comparison operations typically perform a
`conditional branch when a mismatch is found. This conditional branching
`causes large SPA (and sometimes timing) characteristics.
`Multipliers: Modular multiplication circuits tend to leak a great deal of infor-
`mation about the data they process. The leakage functions depend on the
`multiplier design, but are often strongly correlated to operand values and
`Hamming weights.
`Exponentiators: A simple modular exponentiation function scans across the
`exponent, performing a squaring operation in every iteration with an addi-
`tional multiplication operation for each exponent bit that is equal to \ ".
`The exponent can be compromised if squaring and multiplication operations
`have di(cid:11)erent power consumption characteristics, take di(cid:11)erent amounts of
`time, or are separated by di(cid:11)erent code. Modular exponentiation functions
`that operate on two or more exponent bits at a time may have more complex
`leakage functions.
`
` Preventing SPA
`
`Techniques for preventing simple power analysis are generally fairly simple to
`implement. Avoiding procedures that use secret intermediates or keys for condi-
`tional branching operations will mask many SPA characteristics. In cases such
`as algorithms that inherently assume branching, this can require creative coding
`and incur a serious performance penalty.
`Also, the microcode in some microprocessors cause large operand-dependent
`power consumption features. For these systems, even constant execution path
`code can have serious SPA vulnerabilities.
`Most (but not all) hard-wired hardware implementations of symmetric cryp-
`tographic algorithms have su(cid:14)ciently small power consumption variations that
`SPA does not yield key material.
`
` Di(cid:11)erential Power Analysis of DES Implementations
`
`In addition to large-scale power variations due to the instruction sequence, there
`are e(cid:11)ects correlated to data values being manipulated. These variations tend to
`be smaller and are sometimes overshadowed by measurement errors and other
`noise. In such cases, it is still often possible to break the system using statistical
`functions tailored to the target algorithm.
`Because of its widespread use, the Data Encryption Standard (DES) will
`be examined in detail. In each of the  rounds, the DES encryption algorithm
`performs eight S box lookup operations. The  S boxes each take as input six
`key bits exclusive-ORed with six bits of the R register and produce four output
`bits. The  S output bits are reordered and exclusive-ORed onto L. The halves
`L and R are then exchanged. (For a detailed description of the DES algorithm,
`see [ ].)
`
`
`
`244MAX032888
`
`Page 2012-004
`
`

`

`The DPA selection function D(C; b; Ks) is de(cid:12)ned as computing the value of
`bit (cid:20) b <  of the DES intermediate L at the beginning of the th round for
`ciphertext C, where the  key bits entering the S box corresponding to bit b are
`represented by (cid:20) Ks < . Note that if Ks is incorrect, evaluating D(C; b; Ks)
`will yield the correct value for bit b with probability P (cid:25)
` for each ciphertext.
`To implement the DPA attack, an attacker (cid:12)rst observes m encryption op-
`erations and captures power traces T ::m[ ::k] containing k samples each. In
`addition, the attacker records the ciphertexts C ::m. No knowledge of the plain-
`text is required.
`DPA analysis uses power consumption measurements to determine whether a
`key block guess Ks is correct. The attacker computes a k-sample di(cid:11)erential trace
`(cid:1)D[ ::k] by (cid:12)nding the di(cid:11)erence 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.
`Thus (cid:1)D[j] is the average over C ::m of the e(cid:11)ect due to the value represented
`by the selection function D on the power consumption measurements at point
`j. In particular,
`
`(cid:0) Pm
`Pm
`(cid:0) Pm
`
`i= ( (cid:0) D(Ci; b; Ks)) Ti[j]
`i= ( (cid:0) D(Ci; b; Ks))
`
`i= Ti[j]
`m
`
`(cid:19) :
`
`(cid:1)D[j] = Pm
`Pm
`(cid:25) (cid:18)Pm
`Pm
`
`i= D(Ci; b; Ks)Ti[j]
`i= D(Ci; b; Ks)
`
`i= D(Ci; b; Ks)Ti[j]
`i= D(Ci; b; Ks)
`
`If Ks is incorrect, the bit computed using D will di(cid:11)er from the actual target
`bit for about half of the ciphertexts Ci. The selection function D(Ci; b; Ks) is
`thus e(cid:11)ectively uncorrelated to what was actually computed by the target device.
`If a random function is used to divide a set into two subsets, the di(cid:11)erence in
`the averages of the subsets should approach zero as the subset sizes approach
`in(cid:12)nity. Thus, if Ks is incorrect,
`
`(cid:1)D[j] (cid:25)
`
`lim
`m!
`because trace components uncorrelated to D will diminish with
`pm , causing the
`di(cid:11)erential trace to become (cid:13)at. (The actual trace may not be completely (cid:13)at,
`as D with Ks incorrect may have a weak correlation to D with the correct Ks.)
`If Ks is correct, however, the computed value for D(Ci; b; Ks) will equal the
`actual value of target bit b with probability . The selection function is thus
`correlated to the value of the bit manipulated in the th round. As a result,
`the (cid:1)D[j] approaches the e(cid:11)ect of the target bit on the power consumption as
`m ! . Other data values, measurement errors, etc. that are not correlated to
`D approach zero. Because power consumption is correlated to data bit values,
`the plot of (cid:1)D will be (cid:13)at with spikes in regions where D is correlated to the
`values being processed.
`The correct value of Ks can thus be identi(cid:12)ed from the spikes in its di(cid:11)erential
`trace. Four values of b correspond to each S box, providing con(cid:12)rmation of key
`block guesses. Finding all eight Ks yields the entire -bit round subkey. The
`remaining  key bits can be found easily using exhaustive search or by analyzing
`
`
`
`244MAX032889
`
`Page 2012-005
`
`

`

`one additional round. Triple DES keys can be found by analyzing an outer DES
`operation (cid:12)rst, using the resulting key to decrypt the ciphertexts, and attacking
`the next DES key. DPA can use known plaintext or known ciphertext and can
`(cid:12)nd encryption or decryption keys.
`Figure  shows four traces prepared using known plaintexts entering a DES
`encryption function on another smart card. On top is the reference power trace
`showing the average power consumption during DES operations. Below are three
`di(cid:11)erential traces, where the (cid:12)rst was produced using a correct guess for Ks. The
`lower two traces were produced using incorrect values for Ks. These traces were
`prepared using samples (m = ). Although the signal is clearly visible in
`the di(cid:11)erential trace, there is a modest amount of noise.
`
`Figure : DPA traces, one correct and two incorrect, with power reference.
`
`Figure  shows the average e(cid:11)ect of a single bit on detailed power consump-
`tion measurements. On top is a reference power consumption trace. The center
`trace shows the standard deviation in the power consumption measurements. Fi-
`nally, the lower trace shows a di(cid:11)erential trace prepared with m = . Note that
`regions that are not correlated to the bit are more than an order of magnitude
`closer to zero, indicating that little noise or error remains.
`
`
`
`244MAX032890
`
`Page 2012-006
`
`

`

`The size of the DPA characteristic is about (cid:22)A, which is several times less
`than the standard deviation observed at that point. The rise in the standard de-
`viation at clock cycle  coinciding with a strong characteristic indicates that the
`operand value has a signi(cid:12)cant e(cid:11)ect on the instruction power consumption and
`that there is considerable variation in the operand values being manipulated.
`Because low-level instructions often manipulate several bits, a selection func-
`tion can simultaneously select for values of multiple bits. The resulting DPA
`characteristics tend to have larger peaks, but do not necessarily have better
`signal-to-noise ratios because fewer samples are included in the averaging.
`
`Figure : Quantitative DPA measurements
`
`Several sources introduce noise into DPA measurements, including electro-
`magnetic radiation and thermal noise. Quantization errors due to mismatching
`of device clocks and sample clocks can cause additional errors. Finally, uncor-
`rected temporal misalignment of traces can introduce a large amount of noise
`into measurements.
`Several improvements can be applied to the data collection and DPA analysis
`processes to reduce the number of samples required or to circumvent counter-
`measures. For example, it is helpful to correct for the measurement variance,
`
`
`
`244MAX032891
`
`Page 2012-007
`
`

`

`yielding the signi(cid:12)cance of the variations instead of their magnitude. One vari-
`ant of this approach, automated template DPA, can (cid:12)nd DES keys using fewer
`than  traces from most smart cards.
`More sophisticated selection functions may also be used. Of particular impor-
`tance are high-order DPA functions that combine multiple samples from within
`a trace. Selection functions can also assign di(cid:11)erent weights to di(cid:11)erent traces
`or divide traces into more than two categories. Such selection functions can de-
`feat many countermeasures, or attack systems where partial or no information
`is available about plaintexts or ciphertexts. Data analysis using functions other
`than ordinary averaging are useful with data sets that have unusual statistical
`distributions.
`
` Di(cid:11)erential Power Analysis of Other Algorithms
`
`Public key algorithms can be analyzed using DPA by correlating candidate val-
`ues for computation intermediates with power consumption measurements. For
`modular exponentiation operations, it is possible to test exponent bit guesses
`by testing whether predicted intermediate values are correlated to the actual
`computation. Chinese Remainder Theorem RSA implementations can also be
`analyzed, for example by de(cid:12)ning selection functions over the CRT reduction or
`recombination processes.
`In general, signals leaking during asymmetric operations tend to be much
`stronger than those from many symmetric algorithms, for example because of
`the relatively high computational complexity of multiplication operations. As a
`result, implementing e(cid:11)ective SPA and DPA countermeasures can be challenging.
`DPA can be used to break implementations of almost any symmetric or
`asymmetric algorithm. We have even used the technique to reverse-engineer un-
`known algorithms and protocols by using DPA data to test hypotheses about
`a device’s computational processes. (It may even be possible to automate this
`reverse-engineering process.)
`
` Preventing DPA
`
`Techniques for preventing DPA and related attacks fall roughly into three cate-
`gories.
`A (cid:12)rst approach is to reduce signal sizes, such as by using constant execu-
`tion path code, choosing operations that leak less information in their power
`consumption, balancing Hamming Weights and state transitions, and by phys-
`ically shielding the device. Unfortunately such signal size reduction generally
`cannot reduce the signal size to zero, as an attacker with an in(cid:12)nite number of
`samples will still be able to perform DPA on the (heavily-degraded) signal. In
`practice, aggressive shielding can make attacks infeasible but adds signi(cid:12)cantly
`to a device’s cost and size.
`
`
`
`244MAX032892
`
`Page 2012-008
`
`

`

`A second approach involves introducing noise into power consumption mea-
`surements. Like signal size reductions, adding noise increases the number of sam-
`ples required for an attack, possibly to an infeasibly-large number. In addition,
`execution timing and order can be randomized. Designers and reviewers must
`approach temporal obfuscation with great caution, however, as many techniques
`can be used to bypass or compensate for these e(cid:11)ects. Several vulnerable prod-
`ucts have passed reviews that used na(cid:127)(cid:16)ve data processing methods. For safety, it
`should be possible to disable temporal obfuscation methods during review and
`certi(cid:12)cation testing.
`A (cid:12)nal approach involves designing cryptosystems with realistic assumptions
`about the underlying hardware. Nonlinear key update procedures can be em-
`ployed to ensure that power traces cannot be correlated between transactions. As
`a simple example, hashing a -bit key with SHA[ ] should e(cid:11)ectively destroy
`partial information an attacker might have gathered about the key. Similarly,
`aggressive use of exponent and modulus modi(cid:12)cation processes in public key
`schemes can be used to prevent attackers from accumulating data across large
`numbers of operations. Key use counters can prevent attackers from gathering
`large numbers of samples.
`Using a leak-tolerant design methodology, a cryptosystem designer must de-
`(cid:12)ne what leakage rates and functions that the cryptography can survive. Leakage
`functions can be analyzed as oracles providing information about computational
`processes and data, where the leakage rate is the upper bound on the amount of
`information provided by the leakage function. Implementers can then use leak
`reduction and leak masking techniques as needed to meet the speci(cid:12)ed parame-
`ters. Finally, reviewers must verify that the design assumptions are appropriate
`and correspond to the physical characteristics of the completed device.
`
` Related Attacks
`
`Electromagnetic radiation is a particularly serious issue for devices that pass
`keys or secret intermediates across a bus. Even a simple A.M. radio can detect
`strong signals from many cryptographic devices. A wide variety of other signal
`measurement techniques (such as superconducting quantum imaging devices)
`also show promise. Statistical methods related to SPA and DPA can be used to
`(cid:12)nd signals in noisy data.
`
` Conclusions
`
`Power analysis techniques are of great concern because a very large number
`of vulnerable products are deployed. The attacks are easy to implement, have
`a very low cost per device, and are non-invasive, making them di(cid:14)cult to de-
`tect. Because DPA automatically locates correlated regions in a device’s power
`consumption, the attack can be automated and little or no information about
`the target implementation is required. Finally, these attacks are not theoretical
`
`
`
`244MAX032893
`
`Page 2012-009
`
`

`

`or limited to smart cards; in our lab, we have used power analysis techniques
`to extract keys from almost  di(cid:11)erent products in a variety of physical form
`factors.
`The only reliable solution to DPA involves designing cryptosystems with
`realistic assumptions about the underlying hardware. DPA highlights the need
`for people who design algorithms, protocols, software, and hardware to work
`closely together when producing security products.
`
`References
`
` . R. Anderson, M. Kuhn, \Low Cost Attacks on Tamper Resistant Devices," Security
`Protocol Workshop, April , http://www.cl.cam.ac.uk/ftp/users/rja /
`tamper.ps.gz.
`. R. Anderson and M. Kuhn, \Tamper Resistance { a Cautionary Note", The Second
`USENIX Workshop on Electronic Commerce Proceedings, November , pp. -
` .
` . E. Biham and A. Shamir, Di(cid:11)erential Cryptanalysis of the Data Encryption Stan-
`dard, Springer-Verlag, .
`. E. Biham and A. Shamir, \Di(cid:11)erential Fault Analysis of Secret Key Cryptosys-
`tems," Advances in Cryptology: Proceedings of CRYPTO ’ , Springer-Verlag, Au-
`gust , pp.  -.
`. D. Boneh, R. DeMillo, and R. Lipton, \On the Importance of Checking Cryp-
`tographic Protocols for Faults," Advances in Cryptology: Proceedings of EURO-
`CRYPT ’ , Springer-Verlag, May , pp. - .
`. Jameco Electronics, \PC-MultiScope (part #  )," February Catalog, p.
` .
`. P. Kocher, \Timing Attacks on Implementations of Di(cid:14)e-Hellman, RSA, DSS, and
`Other Systems," Advances in Cryptology: Proceedings of CRYPTO ’ , Springer-
`Verlag, August , pp. - .
`. M. Matsui, \The First Experimental Cryptanalysis of the Data Encryption Stan-
`dard," Advances in Cryptology: Proceedings of CRYPTO ’ , Springer-Verlag, Au-
`gust , pp. - .
` . National Bureau of Standards, \Data Encryption Standard," Federal Information
`Processing Standards Publication , January .
` . National Institute of Standards and Technology, \Secure Hash Standard," Federal
`Information Processing Standards Publication - , April .
` . J. Dhem, F. Koeune, P. Leroux, P. Mestr(cid:19)e, J. Quisquater, and J. Willems, \A prac-
`tical implementation of the timing attack," UCL Crypto Group Technical Report
`Series: CG- / , .
` . R.L. Rivest, A. Shamir, and L.M. Adleman, \A method for obtaining digital sig-
`natures and public-key cryptosystems," Communications of the ACM,  , ,
`pp. - .
`
`
`
`244MAX032894
`
`Page 2012-010
`
`