[lo] H. Dobbertin. The Status of MD5 after a Recent Attack.

CryptoBytes, 2( 2): 1-6, 1996 For more information on this and other recent secu-

[l l] H. Dobbertin. RIPEMD with two round compress func- rity developments, contact RSA Laboratories at one

tion is not collision-free. ]ournal of Cryptology. To appear. of the addresses below.

[12] H. Dobbertin, A. Bosselaers, and B. Preneel. RIPEMD-

RSA Laboratories

160: A strengthened version of RIPEMD. Final version

available via ftp at f tp. esat . kuleuven. ac . be/pub/ 100 Marine Parkway, Suite 500

COSIC/bosselae/ripemd/. Redwood City, CA 94065 USA

4151595-7703

[13] B.S. Kaliski Jr. RFC 1319: The MD2 Message-Digest Algo-

rithm. RSA Data Security, Inc., April 1992. 415/595-4126 (fax)

[14] R.C. Merkle. One way hash functions and DES. In rsa-Iubs@rsa.com

Advunces in Cryptology - Crypto ˜89, pages 428-446, http:llwww.rsa.comlrsaIubsl

Springer-Verlag, 1990.

[15] R.C. Merkle. Note on MD4. 1990. Unpublished. (A de-

scription can be found in [S].)

Page 7

Previous Page Home Next Page5 . 1996

NUMBER 3 - JANUARY 2

Netvs andadvicefmm RSA Laboratories

Proper Initialization for the

BSAFE Random Number Generator

2.x) assumes that each call will pass a substantial

Dr. Robertw. Baldwin

amount of unpredictability in each block of seed

ISA Data Security, Inc.

bytes. However, in this case, there is only one byte

in each seed block, and it is likely to be a character

Abstract

from the home row of the keyboard, of which there

This bulletin will help you avoid a particularly poor

are only 10. That is very little unpredictability per

way of initializing the random number generators in

seed block.

the BSAFE 1.x or BSAFE 2.x toolkit. If you have

followed the advice in the BSAFE 2.1 Users Manual,

which is to initialize the generators with large blocks

DisplayMessage

of seed bytes, then you do not have this security

("Please enter 20 random keystrokes");

weakness. However, random number generators are

for (i = 0 ; i < 20 ; it+)

often used to produce encryption keys, so the impact

(

of poor initialization could be substantial.

c = GetUserKeystroke();

if (0 != B-RandomUpdate(randomObj,

We first explain how you can recognize whether your

&c, 1, NULL-CONTEXT))

product has this problem. If it does, we have in-

return (ERROR-XXX);

cluded a simple fix that can be added to your

I

product™s source code. Alternatively, you can up-

grade to the BSAFE 3.x toolkit which eliminates the

The number of states for the generator does not de-

problem without any need for changes in your

pend on the order in which the seed blocks are pro-

product™s source code.

cessed by B-RandomUpdate. After executing the

sample code, the random number generator will be

Recognizing the problem

in one of (20+10-1)!/(20!(10-l)!) possible states,

You need to look at all places that your product calls

which is about 23 bits of randomness. This is not

B-RandomUpdate. If the number of seed bytes

even enough randomness to generate a good 40 bit

passed to each invocation of B-RandomUpdate is

key for an exportable cryptographic product, let

small, then you may have the weakness, even if

alone provide strong domestic security. The

B-RandomUpdate is called may times.

implementer of this code may have expected that

there would be lo**20 possible states, roughly 66

In the sample code, B-RandomUpdate is called 20

bits of randomness, which is reasonable for systems

times, but each call only passes a single seed byte.

that use the DES cipher.

The algorithm used to update the state of the ran-

dom number generator (in BSAFE 1.x and BSAFE

Fixing the problem

There are several ways to fix the problem. One

would be to gather up all the seed bytes and pass

Page 8

Previous Page Home Next Page

#3 -

I. A E Cl R A T 0 R I E S e u 1. L E T I N JASUARY

RSA % 5 1996

For further information contact technical support by

them via a single call to B-RandomUpdate. This

calling (4151595-7705 between 9 A.M. and 5 P.M.

would extract the maximum amount of randomness

Pacific time, or fax at (415)595-1873, or email at

from all the seed bytes. For example:

tech-support@lsa.COm.

DisplayMessage

(“Please enter 20 random keystrokes”);

for (i = 0 ; i < 20 ; it+) For more information on this and other recent

developments in cryptography, contact RSA Iabo-

{

seedBuffer[il = GetUserKeystrokeO; ratorics at one of the addresses below.

1

i f (0 ! = B-RandomUpdate(randomObj, RSAIaboraiorks

seedBuffer, 20, NULL-CONTEXT)) 100 Marine Parkway, Suite 500

return (ERROR-XXX) ; Redwood City, CA 94065 USA

415/595-7703

415/595-4126 (fax)

An alternative is to include a counter value with

rschkza.com

each byte of seed. Surprisingly, this fures the prob-

http:/w.m.cdwkabd

lem with small seeds. For user input, the counter

could be replaced with a sample from a clock that is

updated at least 10 times per second. The code for

this alternative is shown below. This approach ex-

tracts nearly as much randomness from the input as

the previous approach and it is well suited for appli-

cations that periodically update the random object

as they executes.

/* Update the random object anytime a key is pressed. *I

int AddNewRandomness ( )

t

/* Using a clock (10th of second OK) would be better than *I

I* a counter and would not require static storage. *I

static struct ( /* Static, so counter is persistent. */

long counter;

keystroke;

char

) seedBlock;

seedBlock.countertt;

seedBlock.keystroke = GetLastKeystrokeO;

i f (0 ! = B-RandomUpdate(randomObj,

(char *)&seedBlock,sizeof(seedBlock),

NULL-CONTEXT))

return (ERROR-XXX) ;

return (0) ;

1

Page 9

Previous Page Home Next Page

/

l%

Labora tories

News andaduicefmm RSA L&oratories

Timing Attacks on Cryptosystems

graphic operations. Thus operations in an inter

Dr.BurtKa&ki

active protocol such as SSL, or in a cryptographic

RSA Laboratories

module in the attacker™s possession, such as a smart

Summary card, are at the greatest risk. This is true even if

A new class of “timing attacks” published recently there is some “noise” in the measurement, such as

by Paul Kocher, an independent cryptography con- transmission delays, since the attacker can factor out

sultant (see J. Markoff, “Secure digital transactions the noise by averaging enough measurements. Op-

just got a little less secure,” New York Times, De- erations performed privately and without external

cember 11, 19!3), poses a potential risk to a variety feedback, on the other hand, such as off-line digital

of cryptosystems, including RSA, DSA, Diffie-Hell- signatures or file encryption, are unaffected.

man and RC5.

Impact on RSA Data Security Products

The concept of timing attacks has been known for The timing attacks potentially affect the imple

years, but Kocher™s results are new and significant in mentations of the RSA and DSA algorithms in

that they can recover complete key information BSAFE and RSAREF, which, like many other imple-

given only the running time of an operation. Previ- mentations, are optimized for performance, and

ous attacks could only recover partial key informa- hence take an amount of time that can poten

tion or required timing information on the individual tially be correlated with the input. (TIPEM and

steps within a cryptographic operation. other products based on BSAFE are similarly af-

fected.)

Of greatest concern are algorithms with a key-de-

pendent correlation between input and running The attacks do not affect the implementation of

time, including RSA, DSA, Diffie-Hellman, and Diffie-Hellman key agreement in BSAFE and

RC5. Algorithms without such correlations are un- RSAREF, as the Diffie-Hellman exponent is not a

affected. In general, DES, DESX, triple-DES, RC2, fixed key, but instead varies from one call to an-

RC4, and standard message-digest algorithms (for other. They also do not affect the implementation

which the “key information” might be the input of RC5 in BSAFE on standard platforms as the RC5

message) are not affected, although in special cases, rotations take a constant amount of time on those

according to Kocher, there may be some minor leak- platforms and so do not give opportunity for corre-

age of key information. lation. However, RC5 may be affected on other plat-

forms.

For one of the new attacks to succeed, it must be

possible to measure the running time of crypto- Other algorithms in BSAFE and RSAREF, includ-

ing DES, DESX, triple-DES, RC2, RC4, and the

message-digest algorithms, as noted above, are in

Burt Kaliski is chief scientist at RSA Laboratories. He can be

general not affected.

umtactedatbu˜.win

Page 10 Previous Page Home Next Page

JANUARY % 3 !Y™i6

i. A t! 0 R A T 0 R I E S $2 -

e 1J L I,. E T I N

R s A

A practical way to generate the r value in step 1,

Countermeasures

suggested by Steve Burnett, is to compute a one-way

A simple way to prevent timing attacks, regardless

function on the input x and the RSA private key;

of algorithm, is to ensure that all operations with a

given algorithm take the same amount of time by this makes the r value vary from one input value to

“quantizing” the operations into a fixed time period. another, and also keeps the r value unknown. This is

This approach is highly dependent on the environ- being done in BSAFE 3.0 following techniques based

on MD5 similar those of Krawcyzk et al. for message

ment, and may degrade performance, but it requires

no modification to the algorithm implementations. authentication (see “Keyed-MD5 for message au-

“Quantizing” code was recently offered by Matt Blaze thentication” submitted as an Internet-Draft in No-

of AT&T Bell Laboratories atftp://research.att.com/ vember 1995, and M. Bellare, R. Canetti, and H.

Krawczyk, “Keyed hash functions and message au-

d&$%n&+atiAar

thentication,” to be presented at the 1996 RSA Data

For RC5, it is sufficient to ensure that the rotations Security Conference). In particular, the seed is com-

in RC5 take a constant amount of time, which is the puted as

case on all platforms supported by BSAFE 3.0.

(q I I pad, I I c>>

seed := MD5 @ 11 padp 11 MD5

For RSA, one can prevent the attacks by introduc-

ing what is called “blinding” into the cryptographic wherep and q are the RSA primes, least significant

operations, without changing the underlying imple- byte first, pa% and pad, are strings of zero bytes suffi-

mentation. This approach, suggested by Ron Rivest, cient to extendp and q to lengths that are multiples

is being incorporated into BSAFE 3.0 for RSA. of MDS™s block size of 64 bytes, and I I denotes con-

(Similar algorithmic could be incorporated for coun- catenation. The random r value is generated from

termeasures for DSA and Diffie-Hellman.) Specifi- the seed with BSAFE™s MD5Random pseudorandom

cally, the RSA private-key operationy := ti mod n, generator.

where x is the input, y is the output, n is the RSA

modulus and d is the private exponent, is imple-

mented as follows:

r For more information on this and other recent

1. Generate a secret random number r between 0 developments in cryptography, contact RSA Lab

andn-1. ratodes at one of the addresses below.

!

!

/

2. Compute x™ := XF mod n, where e is the public RSAIabomtories

! 100 Marine Parkway, Suite 500

exponent.

Redwood City, CA 94065 USA

Compute y™ := (˜3˜ mod n with the ordinary

3. 415/595-7703

415/595-4126 (fax)

RSA implementation.

tsa-lam.cm

Compute y := y™r™ mod n. It is easy to see

4.

that the result is as expected by noting that