initialize array S to a particular fixed (key-indepen- The encryption/decryption routines are very simple.

feature of RC5

dent) pseudo-random bit pattern, using an arithmetic While other operations (such as substitution opera-

is its heavy

progression modulo 2w determined by the “magic con- tions) could have been included in the basic round

use of data-

stants” P, and Qw Since Q, is odd, the arithmetic operations, our objective is to focus on the data-de-

dependent

progression has period 2w. pendent rotations as a source of cryptographic strength.

rotations

Some of the expanded key table Sis initially added to

WI = pw;

the plaintext, and each round ends by adding expanded

FORi= ITOt-IDO

s[i] =fli-l] + Qw; key from S to the intermediate values just computed.

This assures that each round acts in a potentially dif-

The third algorithmic step of key expansion is to mix ferent manner, in terms of the rotation amounts used.

in the users secret key in three passes over the arrays The xor operations back and forth between A and B

S andL. More precisely, due to the potentially differ- provide some avalanche properties, causing a single-

ent sizes of S and L, the larger array will be processed bit change in an input block to cause multiple-bit

three times, and the other may be handled more times. changes in following rounds.

The use of variable rotations helps defeat differential

i=j=O;

cryptanalysis (Biham/Shamir [˜I) and linear crypt-

A=B=O;

CRYPTCSYTES SPRIfiG 1™)˜)s - THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

Page 68

Previous Page Home Next Page

References

analysis (Matsui Is]), since bits are rotated to “ran-

dom” positions in each round; Kaliski and Yin ana- [ 11 E. Biham and A. Shamir. DiiktentialC?yptanalysisoftheData

lyze the security of RC5 against both types of crypt- Enqixion Standard. Springer-X&lag, New York, 1993.

analysis t21. For the standard word size w = 32, their [2] B. S. Kaliski Jr. and Y. L. Yin. On dvferentialand linear

differential attack can be applied to RC5 with less cryptanalysis of the RC5 encryption algon™thm. Accepted to

than 12 rounds and their linear attack can be applied Crypto ˜95.

to RC5 with less than six rounds. An assessment of [3] M. Matsui. The first experimental cryptanalysis of the Data

the RC5 encryption algorithm will appear in the Sum- Encryption Standard. In Y. G. Desmedt, editor, Advances in

mer issue of CryptoBytes; meanwhile, I invite the C?yptology- C?ypto™%, volume 839 ofLecture Notes in Com-

reader to help determine the strength of RC5. puterScience, pages l-11, Springer-Verlag, New York, 1994.

t-r

N E W S A N D I N F 0 R M A T I 0 N

X9Fl Considers Triple-DES Standard tack by Wiener and van Oorschot. No such attacks are Modes involving

The ANSI-accredited X9Fl working group has be- known for three-key triple-DES. single-DES

gun work on a standard for bulk data encryption for instead of triple-

financial services based on so-called triple-DES, a Balloting of the standard is expected in 1996. DES as primitive

method of extending the security of the Data Encryp- I...] have been

tion Standard by encrypting three times with DES. RSA Laboratories Publishes PKCS #l 1 shown to be

Culminating a year of development, RSA Laborato- potentially no

While triple-DES has been a standard mechanism for ries has published the latest in its series of Public-Key stronger than

several years for encrypting keys as part of ANSI Cryptography Standards, PKCS #I 1: @@tographic single-DES

X9.17, attention has turned recently to triple-DES Token Interface Stunuhrd (GyptoW. against certain

for bulk data encryption, in response to the decreas- attacks.

ing security of DES™s 56-bit key and the shortage of PKCS #ll specifies an application programming in-

trusted alternatives to DES. terface (API) called Cryptoki to devices which hold

cryptographic information and perform cryptographic

The specifics of the standard are yet to be determined, functions, such as IS0 smart cards, PCMCIA cards,

but two recommendations by cryptography experts and the SmartDisk. Cryptoki isolates applications from

are likely to have strong influence: that the three en- the device technology, presenting a common, logical

cryptions involve three different keys (X9.17 involves view of the device called a “cryptographic token.”

only two, where the first and third encryption is with

the same key), and that modes of operation for bulk The interface supports a wide range of cryptographic

data encryption, such as cipher block chaining, be mechanisms, including RSA, DSA, Diffie-Hellman,

built around triple-DES as a primitive. DES, triple-DES, RC2, RC4, MD2, MD5, and SHA;

tokens are expected to support subsets of these mecha-

Modes involving single-DES instead of triple-DES as nisms according to application profiles.

a primitive, such as encrypting three times with single-

DES in cipher block chaining mode, have been shown Cryptoki is at the algorithm-specific, technology- Cryptoki I...]

by Eli Biham in the past year to be potentially no independent layer in the current cryptographic API is expected to

stronger than single-DES against certain attacks. En- standardization effort, and is expected to combine combine nicely

crypting with triple-DES in cipher block chaining nicely with interfaces at the algorithm-independent, with interfaces

mode is not vulnerable to those attacks. security-service-oriented layer such as the Generic Se- at the algorithm-

curity Services API (GSSAPI). independent,

And while two-key triple-DES is significantly stron- security-service-

ger than single-DES, it has a certain “certificational Copies of PKCS #ll and other PKCS standards can be oriented layer.

weakness” observed by Merkle and Hellman in 1980 obtained by anonymous FI™P to ftp.rsa.com in the pub/

which was revealed in 1990 as a known-plaintext at- pkcs directory, or by E-mail to pkcs@rsa.com. -4

-$I

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - s P R I 11 G 1995 CRYPTOBYTES

Page 69

Previous Page Home Next Page

A N N 0 U N C E M E N T S

1995 RSA Laboratories 19-21; the West Coast Seminar Series will be

Seminar Series held at the Hotel Sofitel in Redwood Shores,

RSA Laboratories is pleased to announce CA, from August 23-25. Contact RSA Labora-

details of the 1995 Seminar Series. Now in its tories for more information on how to register.

third year, the Seminar Series has been

expanded again and will now be presented at RSA Laboratories Technical Reports

two US locations. The RSA Laboratories Technical Reports are

now available via a subscription service. These

The Seminar Series is an intensive three-day reports offer detailed summaries of current

presentation on all aspects of cryptography. research on a variety of topics and they bring

In a slight departure from previous years, the together information from a wide variety of

first day of the Seminar Series will be a self- sometimes obscure sources. Subscription to the

contained overview of the basic ideas and cryp- Technical Reports will be at one of two levels;

tographic techniques that are used today. individual or corporate. As well as receiving all

Building on this introduction, the remainder of previously written reports, subscribers will

the seminar series will provide detailed analy- receive new reports as they appear as well as

sis on many of the algorithms, techniques and current research notes on items of major for subscription

theoretical foundations which dominate cur- significance. information,

rent cryptographic thinking. see page 2 of

Contact RSA Laboratories for more informa- this newsletfer.

The East Coast Seminar Series will be held at tion about the Technical Report subscription

the Columbia Inn in Columbia, MD, from July service.

FIRST CLASS

U.S. POSTAGE

100 MARINE PARKWAY

REDWOOD CITY

CA. 94065.1031

T E L 41.5/595-7703

F A X 415/595-4126

rsa-labs@rsa.com

Copyright 0 1995 RSA laboratories, a division of RSA Data Security, Inc. All rights reserved.

Page 70

Suggestions for

Random Number Generation in Software

quence. Rolling a die would give such results. But

TimMaafKws

RsALMLlsfmrlly computers are logical and deterministic by nature,

and fulfilling Knuth™s requirements is not something

Introduction they were designed to do. %-called random number

The generation of random numbers is critical to ayp generators on computers actually produce pseudo-

random numbers. Pseudo-nndom numbers am num-

tographic systems. Symmetric ciphers such as DES,

RC2, and RC5 all require a randomly seIected en- bers generated in a deterministic way, which only

cryption key. Public-key algorithms - like RSA, appear to be random.

Diffie-Hellman, and DSA - begin with randomly

generated values when generating prime numbers. Most programming languages include a pseudcxan-

At a higher level, SSL and other cryptographic pro- dom number generator, or “PRNG.” This PRNG

tocols use random challenges in the authentication may produce a sequence adequate for a computer-

process to foil replay attacks. ized version of blackjack, but it is probably not good

enough to be used for grptography. The reason is

But truly random numbers are difficult to come by that someone knowledgeable in cryptanalysis might

in softwamonly solutions, where ekxtrical noise and notice patterns and correlations in the numbers that

get generated. Depending on the quality of the

sources of ha&are randomness are not available (or

at least not convenient). This poses a challenge for PRNG, one of two things may happen. If the PRNG

software developers implementing cryptography. has a short period, and repeats itself after a relatively

There are methods, however, for generating suff- short number of bits, the number of possibilities the

ciently random sequences in software that can pro- attacker will need to try in order to deduce keys will

vide an adequate level of security. This bulletin be significantly reduced. Even worse, if the distribu-

offers suggestions on generating mndom numbers in tion of ones and zeros has a noticeable pattern, the

software, along with a bit of background on random attacker may be able to predict the sequence of num-

bers, thus limiting the possible number of resulting

numbers.

keys. An attacker may know that a PRNG will never

Random vs. Pseudo-Random Numbers produce 10 binary ones in a row, for example, and

What is a truly random number? The definition can not bother searching for keys that contain that se-

quence.

get a bit philosophical. Knuth speaks of a sequence

of independent random numbers with a specified dis

The detail of what makes a PRNG cryptographical-

tribution, each number being obtained by chance

and not influenced by the other numbers in the se- ly “good” is a bit beyond the scope of this paper.

Briefly stated, a PRNG must have a high degree of

unpredictabiIity. Even if nearly every bit of output is

known, those that are unknown should remain hard

to predict. The “hardness” is in the sense of compu-

Page 71

tational difficulty - predicting the bits should re- an attacker has a high likelihood of recreating your

quire an infeasible amount of computation. A true sequence of pseudo-random bytes by guessing the

random number generator, like a hardware device, exact seeding time. Once he has the pseudo-ran-

will have maximum unpredictability. A good PRNG dom bytes, he can recreate your keys. ˜Ihe security

will have a high degree of unpredictability, making issue becomes one of making sure an attacker can-

the output unguessable, which is the goal. not determine your seed.

One essential ingredient in prrxkicing good random You may be wondering why use a random number

numbers in software, then, is to use a good PFtNG. generator to generate random bytes, if to use it, you

Important to note is that although the PRNG may need to first generate random bytes. Seeding is a

pm&e statistically good looking output, it also has bootstrap operation. Once done, generating subse-

to withstand analysis to be considered strong. Since quent keys will be more efficient. Another impor-

the one included with your compiler or operating tant point is that the information collected for the

systemrmyormaynotbe,wemcommendyoudon7 seed does not need to be truly random, but

use it. Instead, use a PRNG that has been verified unguessable and unpredictable. Once the seed is fed

to have a high degree of randomness. RSA™S BSAFE into MD5, the output becomes pseudorandom. If

toolkit uses the MD5 message digest function as a attackers annot guess or predict seeds, they will be

random number genemtor. BSAPE uxs a state value unable to predict the output.

that is digested with MD5. The strength of this ap-

proach relies on MD5 being a one-way function - There are two aspects to a random seed: quantity

from the random output bytes it is difficult to deter- and quality. They are related. The quality of a tan-

mine the state vaIue, and hence the other output dom seed refers to the entropy of its bits. Cryptogm-

bytes remain secure. Similar generators can be con- phers use the word entropy a lot, so it is worth know-

structed with other hash functions, such as SHAl. ing. In a system that produces the same output each

time, each bit is fxed, so there is no uncertainty, or

zero entropy per bit. If every possible sequence of

Sysfemlh-ique LtYbthClndUngueaable 6ckmalRcndcfn

-_- outputs is equally IikeIy (i.e. truly random) then

.._... -.. ._-_

.-----.. .-........ -.-.-..“.” - . . . . ” ...” “.

there is total uncertainty, or one bit of entropy per

cumar padian with time

ca&gumtial files contents of screal

Keys&e timing

Driwczcn˜ Cuteandtinw output bit. There are precise mathematical formulas

Hiih resdution dak

bm™rannlentJrings for entropy, but the short summary is the more en-

yvJJ=& iwfn,

=mples tropy per bit, the better. Since the quality may vary,

Mause d i i t i m i n g

t-adkeyp”sed

it is a good idea to account for this with quantity.

Lcgfikbkckr h4wn3 -t

Sufficient quantity makes it impractical for an at-

Vii input

Memwy stutistics

tacker to exhaustively try all likely seed values. Iet™s

l-ktwwk statiti

start with quality.

Plvct?ss skdistics

zzYi2P-

Table 1 shows a list of potential sources for building

the initial seed pool. External random events are

the lxst, but harder to get than variable or unique

information. Sources that are variable, while not

random, are very difficult for an attacker to guess.

The Seed Quantities that are unique to a system are also hard

The other component in producing good random to guess and usable if mom bytes are needed.

numbers is providing a nndom seed. A good PRNG

In general, collect as much external random infor-

like BSAFT™s will produce a sequence that is suffi-

mation as possible. Supplement this with sources

ciently random for cryptographic operations, with

fromtheiwoothercolumnsifmorebytesareneeded.

one catch: it needs to be properly initialized, or

Using a composite of many items makes the

“seeded.” Using a bad seed (or no seed at ail) is a

attacker™s task more difficult. In an application

common flaw in poorly implemented aypcographic

where several keys will be generated, it may make

systems. A PRNG wiI1 always generate the same out-

put if started with the same seed. If you are using sense to collect enough seed bytes for multiple keys,

even before the first is generated. Be careful of in-