стр. 19 |

principle a DPA peak rises up each time it is pro-

A straightforward (i.e., unprotected) implementa-

cessed. This brings a lot of information about an

tion of the square-and-multiply algorithm is given

algorithm implementation. To achieve the same

in Figure 5.

goal Paul Fahn and Peter Pearson proposed an-

The corresponding power curve exhibits a se-

other statistical approach called Inferential Power

quence of consumption patterns among which

Analysis (IPA). The bits are inferred from the devi-

some have a low level and some have a high level.

ation between a single trace and an average trace

These calculation units are assigned to a crypto-

possibly resulting from the same execution: for in-

processor handling n-bit arithmetic. Knowing that

stance the average trace of a DES round (see Data

a low level corresponds to a squaring and that a

Encryption Standard) can be computed over its

high level corresponds to a multiplication, it is

sixteen instances taken from a single execution.

fairly easy to read the exponent value from the

IPA does not require the knowledge of the random

power trace:

r

data to make a prediction on a bit value. But as

a low-level pattern followed by another low-

counterpart it is less easy to implement and the

level pattern indicates that the exponent bit is

interpretation is less obvious.

0, and

r

After Paul Kocher, Thomas Messerges et al.

a low-level pattern followed by a high-level pat-

have proposed to extend DPA by considering mul-

tern indicates that the exponent bit is 1.

tiple selection bits in order to increase the signal

This previous picture also illustrates why the

to noise ratio (SNR). If the whole machine word is

Hamming weight of exponent d can be disclosed

taken into account, a global approach consists in

by a timing measurement.

considering the transition model as suggested by

Jean-SВґ bastien Coron et al.

e

DPA-Type Attacks

FROM POWER ANALYSIS TO POWER ATTACKS: Historically, DPA-type attacksвЂ”that is, power

Obviously, if the power consumption is sensitive attacks based on Differential Power Analysis

to the executed code or handled data, critical in- (DPA)вЂ”were presented as a means to retrieve the

formation may leak through power analysis. This bits of a DES key.

574 Side-channel analysis

2 E C 6 9 1 5 B F 9 4 A

0010 1 1 10 1 100 0 1 10 100 1000 10 10 1 10 1 1 1 1 1 1 100 10 100 10 10

Fig. 6. SPA trace of the basic square-and-multiply algorithm

At the п¬Ѓrst round of DES, the output nibble of (implementations of) asymmetric algorithms, al-

the ith S-box (1 в‰¤ i в‰¤ 8) can be written as Si (M вЉ• beit in a less direct manner.

K) where

r Other Attacks

M is made of 6 bits constructed from the input

message after IP- and E-permutations: it has to

be chosen at random but is perfectly known and Amongst the other statistical attacks, IPA is more

predictable, and

r difп¬Ѓcult and less efп¬Ѓcient. Its purpose is to retrieve

K is a 6-bit sub-key derived from the key key bits without knowing the processed data. It

scheduling. proceeds by comparing the power trace of a DES

Rising up a DPA bias would require the knowl- round with an average power trace computed for

edge of the output nibble. As K is unknown to the instance over the 16 rounds. In principle, key bits

adversary this is not possible. But sub-key K can could be inferred this way because the differen-

be easily exhausted as it can take only 26 = 64 tial curve should magnify the bits deviation where

possible values. Therefore the procedure consists they are manipulated.

in reiterating the following process for 0 в‰¤ K в‰¤ 63: Dictionary (or template) attacks can be con-

1. form sets S0 = M | g(S-boxi (M вЉ• K)) = 0 and sidered as a generalisation of IPA to very com-

S1 = M | g(S-boxi (M вЉ• K)) = 1 where selec- fortable but realistic situations. They have been

widely studied in the п¬Ѓeld of smart cards where

tion function g returns the value of a given bit

information on secret key or personal identiп¬Ѓca-

in the output nibble; and

tion numbers (PIN) could potentially be extracted.

2. compute the corresponding DPA curve.

They consist in building a complete dictionary of

In principle the bias peak should be maximised

all possible secret values together with the cor-

when the guess K is equal to the real sub-key

responding side-channel behaviour (e.g., power

K. Then inverting the key schedule permutation

trace) when processed by the device (e.g., for au-

leads to the value of 6 key bits. In other words the

thentication purpose). Then a secret value embed-

DPA operator is used to validate sub-key hypothe-

ded in a twin device taken from the п¬Ѓeld can be

ses. The same procedure applies to the 7 other S-

retrieved by comparing its trace and the entries of

boxes of the DES. Therefore the whole procedure

yields 8 Г— 6 = 48 key bits. The 8 remaining key the dictionary.

In practice, things do not happen that easily

bits can be recovered either by exhaustion or by

for statistical reasons and application restrictions.

conducting a similar attack on the second round.

Only part of the secret is disclosed and the infor-

The main feature of a DPA-type attack resides

mation leakage remains difп¬Ѓcult to exploit fully.

in its genericity. Indeed it can be adapted to

Finally, in addition to power consumption, other

many cryptographic routines as soon as varying

side channels can be considered; possible sources

and known data are combined with secret data

of information leakage include running time or

through logical or arithmetic operations.

electro-magnetic radiation.

A similar attack can be mounted against the

п¬Ѓrst round of Rijndael/AES; the difference being

COUNTERMEASURES: The aforementioned at-

that there are 16 byte-wise bijective substitutions

and therefore 256 guesses for each. Finally, we tacks have all been published during the sec-

note that DPA-type attacks are not limited to ond half of the 1990s. In view of this new threat

symmetric algorithms, they also apply to certain the manufacturers of cryptographic tokens have

Side-channel analysis 575

Round 1 Round 2 Round 3

Fig. 7. DPA trace of the three п¬Ѓrst rounds of DES (two upper (respectively lower) curves: power consumption curve

of maxima (respectively minima) of a single execution and DPA curve of maxima (respectively minima))

designed a large set of dedicated countermeasures clocking or the insertion of dummy cycles at ran-

especially to thwart statistical attacks like DPA. dom, making the statistical combination of sev-

All the related research activity has now resulted eral curves ineffective.

r

in tamper resistant devices widely available in the Other countermeasures rather intend to de-

market. It has given rise to the new concept of вЂњse- crease or cancel the signal at the source. Re-

cure implementationвЂќ which states that informa- duction is a natural consequence of the shrink-

tion leakage is not only due to the speciп¬Ѓcation of ing trend in the silicon industry that diminishes

an application (cryptographic processing or what- the power consumption of each elementary

стр. 19 |