<<

. 3
( 19 .)



>>

at the rump session of Eurocrypt ˜96, May 14, 1996.
[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

<<

. 3
( 19 .)



>>