If information leaks through a physical side- emerging technology called “precharged dual

channel there are two defensive strategies. The rail logic” where each bit is represented by a

¬rst consists in decorrelating the secret data from double circuitry. At a given time a logical 0 is

the side-channel. The second consists in decorre- represented physically by a 01, and a logical 1

lating the side-channel from the secret data. The by 10. The transition to the next time unit goes

borderline between both is sometimes fuzzy but through a physical 00 or 11 state so that the

roughly speaking, the former is rather software same amount of switching occurs whatever the

oriented and intends to mask the data since they subsequent state is. Consequently if both rails

have to leak anyway, whereas the latter is more are perfectly balanced, the overall consumption

hardware oriented and intends to shut the side- of a microprocessor does not depend on the data

channel physically in order to make the device anymore.

tamper-resistant. Software countermeasures enclose a large vari-

Chip manufacturers have introduced into their ety of techniques going from the application level

hardware designs many security features against to the most speci¬c algorithmic tricks. One can

power attacks. They are stricto sensu countermea- classify them into three categories: application

sures since they aim at impeding the power mea- constraints, timing counter-measures and data

surement and make the recorded signal unwork- masking.

r

able. Application constraints represent an obvious

r Some countermeasures consist in blurring the but often forgotten means to thwart statisti-

signal using smoothing techniques, additive cal analyses. For instance DPA requires known

noise or desynchronisation effects. These coun- data with a high variability. An application

termeasures are poorly ef¬cient against SPA wherein an input challenge (or an output cryp-

working on broad scale traces. They are rather togram) would be strictly formatted, partially

designed against statistical attacks. They may visible and constrained to vary within hard lim-

require some complementary circuits to gen- its (like a counter) would resist DPA fairly well.

r

erate parasitic components into the consumed Timing countermeasures mean the usage of em-

current. Desynchronisation aims at misaligning pirical programming tricks in order to tune the

a set of power traces by the means of unstable time progress of a process. A critical instruction

576 Side-channel attacks

may have its execution instant randomised by in Computer Science, vol. 1962, ed. Y. Frankel.

Springer-Verlag, Berlin, 157“173.

software: if it never occurs at the same time,

[3] Fahn, Paul N. and Peter K. Pearson (1999). “IPA:

statistical analysis becomes more dif¬cult. Con-

A new class of power attacks.” Cryptographic Hard-

versely other situations require the code to be

ware and Embedded Systems (CHES™99), Lecture

executed in a constant time, in order to protect

Notes in Computer Science, vol. 1717, eds. C.K. Koc

¸ ¸

it from SPA or timing analysis. For instance a

and C. Paar. Springer-Verlag, Berlin, 173“186.

conditional branch may be compensated with [4] Gandol¬, Karine, Christophe Mourtel, and Francis

a piece of fake code with similar duration and Olivier (2001). “Electromagnetic analysis: Concrete

electrical appearance.

r results.” Cryptographic Hardware and Embedded

Data masking (also known as whitening or ran- Systems”CHES 2001, Lecture Notes in Computer

domization), covers a large set of numerical Science, vol. 2162, eds. C.K. Koc, D. Naccache, and

¸ ¸

techniques designed by cryptographers and de- C. Paar. Springer-Verlag, Berlin, 251“261.

[5] Kocher, Paul (1996). “Timing attacks on implemen-

clined in various manners according to the al-

tations of Dif¬e“Hellman, RSA, DSS, and other sys-

gorithm they apply to. Their purpose is to pre-

tems.” Advances in Cryptology”CRYPTO™96, Lec-

vent the data from being handled in clear and to

ture Notes in Computer Science, vol. 1109, ed. N.

disable any prediction regarding their behavior

Koblitz. Springer-Verlag, Berlin, 104“113.

when seen through the side channel. For exam-

[6] Kocher, Paul, Joshua Jaffe, and Benjamin Jun

ple, the modular exponentiation y = x d mod n (1999). “Differential power analysis.” Advances in

(as used in the RSA public key cryptosystem) Cryptology”CRYPTO™99, Lecture Notes in Com-

can be evaluated as: puter Science, vol. 1666, ed. M. Wiener. Springer-

Verlag, Berlin, 388“397.

y = {(x + r1 n)d+r2 •(n) mod r3 n} mod n [7] Messerges, Thomas S. (2000). “Using second-order

power analysis to attack DPA resistant software.”

for randoms ri and where φ denotes Euler to- Cryptographic Hardware and Embedded Systems”

tient function. CHES 2000, Lecture Notes in Computer Science,

To illustrate how fuzzy the borderline between vol. 1965, eds. C.K. Koc and C. Paar. Springer-

¸ ¸

hardware and software countermeasures can be, Verlag, Berlin, 238“251.

we have mentioned that for instance desynchroni- [8] Messerges, Thomas S., Ezzy A. Dabbish, and Robert

H. Sloan (2002). “Examining smart-card security

sation can be implemented by hardware or soft-

under the threat of power analysis attacks.” IEEE

ware means. The same remark applies to data

Transactions on Computers, 51 (5), 541“552.

masking for which some manufacturers have de-

signed dedicated hardware tokens or mechanisms

such as bus encryption or wired fast implementa-

tions of symmetric algorithms. SIDE-CHANNEL ATTACKS

The experience shows that combined counter-

measures act in synergy and increase the com- Side-Channel Attacks or Environmental Attacks

plexity in a much larger proportion than the sum of cryptographic modules exploit characteristic in-

of both. For instance the simple combination of formation extracted from the implementation of

desynchronisation tricks and data masking makes the cryptographic primitives and protocols. This

DPA (or more sophisticated variants thereof) quite characteristic information can be extracted from

harmless. In the same way, new hardware designs timing, power consumption, or electromagnetic

resist the most state-of-the-art and best equipped radiation features (see tempest). Other forms of

experts. side-channel information can be a result of hard-

ware or software faults, computational errors,

Marc Joye

and changes in frequency or temperature. Side-

Francis Olivier

channel attacks make use of the characteristics

of the hardware and software elements as well

References as the implementation structure of the crypto-

graphic primitive. Therefore, in contrast to ana-

[1] Chari, Suresh, Charanjit S. Jutla, Josyula R. Rao, lyzing the mathematical structure and properties

and Pankaj Rohatgi (1999). “Towards sound ap-

of the cryptographic primitives only, side-channel

proaches to counteract power-analysis attacks.” Ad-

analysis also includes the implementation. Some

vances in Cryptology”CRYPTO™99, Lecture Notes

implementations are more vulnerable to speci¬c

in Computer Science, vol. 1666, ed. M. Wiener.

side-channel attacks than others. Examples of

Springer-Verlag, Berlin, 398“412.

attacks based on side-channel analysis are Dif-

[2] Coron, Jean-S´ bastien, Paul Kocher, and David

e

ferential Power Attacks examining power traces

Naccache (2001). “Statistics and secret leakage.”

(see Differential Power Analysis), Timing Attacks

Financial Cryptography (FC 2000), Lecture Notes

Sieving in function ¬elds 577

measuring the amount of time used to complete the Riemann hypothesis has been proven in the

cryptographic operations (see Timing Attack), and function ¬eld case. The most important applica-

Fault Induction Attacks exploiting errors in the tion to cryptography (although a theoretical re-

computation process of cryptographic primitives sult) is the existence of a provable subexponential-

(see Fault Attacks). time algorithm by Adleman et al. in 1992 [1]

for solving the discrete logarithm problem in the

Tom Caddy Jacobian of a hyperelliptic curve (in short called

hyperelliptic cryptosystems), a generalization of

the group of points of an elliptic curve, and an ana-

SIEVING log to the ideal class group of a quadratic number

¬eld in function ¬elds. The result is mostly of a

Sieving refers to a process for selecting candidates theoretical nature, since hyperelliptic cryptosys-

for further processing among a set of elements. tems, as proposed by Koblitz in 1989 [8], are con-

The “sieve” is the test that an element must pass sidered to be not practical enough because of their

to be considered further. complicated arithmetic. Yet there exist some im-

In many cases, by employing arithmetic pro- plementations in the group around Frey showing

gressions, it is possible to identify multiple candi- this performance is not as bad as expected, espe-

dates from the set more ef¬ciently than if each el- cially because the size of the elements is consider-

ement were tested separately. (Indeed, sometimes ably smaller than for elliptic curves which might

the term “sieving” refers only to this speedup.) For make them even more suitable for small comput-

instance, in the Sieve of Eratosthenes (see prime ing devices such as smart cards.

number), candidate primes are selected from a The ¬rst implementation actually solving hy-

range of integers by crossing off elements divis- perelliptic cryptosystems has been done by R.

ible by small primes 2, 3, 5, 7, 11, 13, . . . . Crossing Flassenberg and the author in 1997 [4]. They ap-

off every second, third, ¬fth, seventh element and plied a sieving technique to accelerate a variant

so on is generally faster than testing each element of the Hafner“McCurley algorithm [6] (known to