of instruction decoders that frustrate modi¬ca- analysis determines secret-key bits by correlat-

tions aimed at simplifying access to all memory ing measured current curves with externally

locations [1]. simulated intermediate results of a symmetric

r Fault generation techniques or fault attacks use cipher. It has been demonstrated as a practi-

abnormal environmental conditions to generate cal attack technique, even in situations where

malfunctions in the processor aimed at provid- there has not been a microprobing attack ¬rst

ing additional access. A simple example would to disassemble the software in the targeted

be a deliberately caused and carefully timed smartcard. Countermeasures include the addi-

glitch that disrupts the correct execution of tion of ¬lters and shields against compromising

a single security-critical machine instruction, emanations, circuitry and routines for adding

such as the conditional branch at the end of a random noise and delays, new balanced or dual-

password comparison. Carefully placed, a single rail logic design techniques that lead to inher-

glitch can help to bypass many layers of cryp- ently less information in the power signal, and

tographic protection. Such glitches have been algorithmic techniques for reducing the num-

generated by increasing the provided clock fre- ber of intermediate results useful for eavesdrop-

quency for a single cycle, by brief supply volt- pers.

age ¬‚uctuations, by applying light ¬‚ashes to Microprobing requires time and careful prepara-

the entire chip or single gates, and with the tion in a laboratory environment and is therefore

help of electromagnetic pulses. Another class primarily a challenge of tamper resistance. The

of fault generation attacks attempts to reduce other three attack classes are noninvasive and

the entropy generated by hardware random-bit can, with suitable preparation, be performed in

generators. For example, where multiple noisy just a few seconds with attack equipment that

oscillators are used to generate randomness, could be disguised as a regular smartcard reader.

externally applied electromagnetic ¬elds with The holder of the card might not notice such an

carefully selected frequencies can result in a attack, and then even the tamper evidence would

phase lock and more predictable output. Coun- be lost.

termeasures against fault generation include

Markus Kuhn

adding ¬lters into supply lines, regular statis-

tical checks of random-bit generators, redun-

References

dant consistency checks in the software, and

new logic design techniques that lead to inher-

[1] Kömmerling, Oliver and Markus G. Kuhn (1999).

ently glitch-resistant circuits.

r “Design principles for tamper-resistant smartcard

Eavesdropping or side-channel analysis tech-

processors.” Proceedings of the USENIX Workshop

niques monitor with high time resolution the

on Smartcard Technology (Smartcard ™99), Chicago,

characteristics of all supply and interface con-

IL, USA, May 10“11, Berkeley, CA, US. USENIX

nections and any other electromagnetic radia-

Association, 9“20, ISBN 1-880446-34-0.

tion produced by a processor. A simple exam- [2] Weingart, Steve H. (1965). “Physical security de-

ple is the determination of the length of the vices for computer subsystems: A survey of attacks

correct pre¬x of an entered password from the and defenses.” Workshop on Cryptographic Hard-

runtime of the string-compare routine that re- ware and Embedded Systems (CHES 2000), Lec-

jects it. This can signi¬cantly reduce the aver- ture Notes in Computer Science, vol. 1965. Springer-

Verlag, Berlin, 302“317.

age number of guesses needed to ¬nd the correct

string. The nature of the executed instruction,

as well as parts of the processed data, are ev-

ident in the power-supply current of a CPU. A

S/MIME

conditional branch that takes effect can easily

be distinguished from one that passes through

by examining with an oscilloscope the voltage S/MIME (see also Security Standards Activities)

drop over a 10 resistor inserted into the pro- is the IETF Internet Security Syntax for MIME

cessor™s ground connection line. The current (Multipurpose Internet Mail Extensions), cur-

consumed by the write operation into memory rently available in version 3, under constant de-

cells is often proportional to the number of bits velopment and communicated in a range of RFCs

that change their value. Even status register (abbreviation for “Request for Comments”). It

592 Smoothness

For t, c ∈ R such that 0 ¤ t ¤ 1 the complexity-

basically speci¬es the syntax for the integration

of various cryptographic mechanisms and algo- theoretic L-notation is de¬ned by

rithms within the MIME format scope.

Lx [t, γ ] = e(γ +o(1))(log x) (log log x) ,

t 1’t

The Cryptographic Message Syntax (CMS) (see

where x ’ ∞. Note that for t = 0 this equals

RFC 3369) is cryptographic algorithm indepen-

(log x)γ , while for t = 1 we obtain x γ (neglecting

dent, but, typically, applying an actual algorithm

is not entirely de¬ned uniquely and requires the o(1) term). Hence we see that for values of t be-

some attendance and care for seamless interoper- tween 0 and 1 the function L interpolates between

ability. polynomial time and exponential time behaviour.

As part of the speci¬cation update, a new suite For these values we say that L is subexponential

of “mandatory to implement” algorithms are con- in x (see subexponential time).

stantly being selected, re¬‚ected in updates to Cer- The main observation about the distribution of

ti¬cate Handling (RFC 2632), and S/MIME v3 smooth numbers in an interval [0, a] is that if the

Message Speci¬cation (RFC 2633). smoothness bound B is chosen subexponentially

Building on the CMS Compressed Data content in x, then the probability that a random integer

type speci¬ed in RFC 3274, the update to RFC in this interval is B“smooth (or more precisely the

speci¬es conventions for message compression as inverse of that probability) is also subexponential.

More precisely, set a = Lx [r, ±] and B = Lx [s, β],

well as to message signature and encryption. Few

where r, s, ±, β ∈ R>0 and s < r ¤ 1, then the prob-

are used in reality.

To aid implementers, documentation containing ability that a random number in [0, a] is B“smooth

example output for CMS is made available, some of is given (see smoothness probability) by

which for example, include structures and signed

Lx [r ’ s, ’±(r ’ s)/β] (1)

attributes de¬ned in the Enhanced Security Ser-

where x ’ ∞.

vices (ESS) (RFC 2634) document.

CMS, and thus S/MIME version 3 and later, per- A similar result holds for the polynomial case:

Assume r, s, ±, β ∈ R>0 such that r ¤ 1 and essen-

mit the use of previously distributed symmetric

tially s < r . Then the probability that a random

key-encryption keys, and the underlying Public

element of F p[x] of norm bounded by Lx [r, ±] is

Key Infrastructure (PKI) is based on the PKIX

Lx [s, β]“smooth is given exactly by expression 1

standard, e.g. for certi¬cates and CRLs (see cer-

ti¬cate revocation), whilst the underlying syntax (see [3] for details).

for cryptographic mechanisms rely on the PKCS Smooth numbers or polynomials are used in

standards. the most effective methods to factor natural num-

bers (see integer factoring) and compute discrete

Peter Landrock

logarithms in ¬nite ¬elds (see discrete logarithm

problem). The overall subexponential complexity

Reference of these methods is a direct consequence of the fact

that the number of smooth elements in a given in-

[1] See http://www.networksorcery.com/enp/ for all terval grows subexponentially if the smoothness

RFCs.

bound is chosen subexponential as well.

For further background, please see [1, 2, 4].

Kim Nguyen

SMOOTHNESS

References

A natural number n is called B-smooth if its factor-

ization does not contain any prime factors larger [1] Can¬eld, E.R., P. Erd¨ s, and C. Pomerance (1983).

o

“On a problem of Oppenheim concerning ˜Factorisa-

than B, i.e.

tio Numenerorum.™ ” Journal of Number Theory, 17,

n= pn p . 1“28.

[2] De Bruijn, N.G. (1966). “On the number of positive

p¤B

integers ¤ x and free of prime factors > y.” Indag.

Analogously, we can also consider elements of the Math., 38, 239“247.

polynomial ring F p[x]. For a polynomial f of degree [3] Odlyzko, A.M. (1985). “Discrete logarithms in ¬-

deg( f ) de¬ne the norm of f to be pdeg( f ) . An element nite ¬elds and their cryptographic signi¬cance.”

of F p[x] is called B-smooth if its factorisation does Advances in Cryptology”EUROCRYPT™84, Lecture

not contain any irreducible polynomials of norm Notes in Computer Science, vol. 209, eds. T. Beth, N.

greater than B. Cot, and I. Ingemarsson. Springer-Verlag, Berlin.

SPKI/SDSI 593

References

[4] Ramaswami, V. (1949). “The number of positive in-

tegers ¤ x and free of prime divisors < x c , and a

problem of S.S. Pillai.” Duke Math. J., 16, 99“109. [1] Stephenson, Neal (2002). Cryptonomicom. Avon Eos