<<

. 18
( 19 .)



>>

A distinguishing
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-

<<

. 18
( 19 .)



>>