. 7
( 19 .)


Hans Dobbertin M2 = Ox8bf37fa2 M,. = 0x20656369
German Information Security Agency Mj = Oxld630daf M,, = Ox2420666f
P.O. Box 20 10 63, M,2 = Ox2C363731
M4 = Ox63247e24
D-53 133 Bonn, Germany M,J = 0x20353934
MS = Ox4e4f430a
M,4 = 0x20666˜41
M6 = Ox43415254
Alf wanted to sell Ann his house, and Ann was MT = Ox410aOa54 MIS = Ox776f6C42
interested. They agreed on a price of $176,495. Alf asked
Ann to sign a contract using a digital signature scheme The twenty bytes of MO-M+ are the above mentioned
which is based on some public-key algorithm and the “random bytes”. The bytes of MS, in reverse ordering
hash function MD4. The contract read as follows: (according to the definition of MD4) and interpreted as
- - - - ASCII read as follows:
Oa 43 4f 4e = Line-feed ˜CON™,

At the price of $176,495 Alf Blowfish sells and so on to Ml5 which reads
his house to Ann Bonafide. . . .
42 6c 6f 77 = ˜Blow™.

“The first 20 bytes (each of them is represented by an
The sequence Mi (i<16) has been chosen such that set-
asterisk above) are random. They have been placed be-
ting M™12 = Ml*+1 and Mli = Mi for i<16, i + 12 gives a
fore the text for security reasons!” claimed Alf, and Ann
collision, i.e.
signed the contract. Later, however, Alf substituted
the contract file by another which read as follows:
compress( IV; M) = compress( IV; M™)
-_-._-_“˜ ---,- -.-__..
Where MD4
for the compress function of MD4 and its fixed initial
is stil/ in use,
CONTRACT value IV. In [l] the basic method of generating such
it should be
collisions was described. They can be found in less than
At the price of $276,495 Alf Blowfish sells
one hour on a PC. Interpreting Ml2 = 0x2˜363731 and
his house to Ann Bonafide. . . .
M™12 = 0x2˜363732 we get:

The contract had been prepared by him such that re- M,2 =3137362c=˜176,™
placing $176,495 by $276,495 does not change the M™,2 = 32 37 36 2c = ˜276,™
MD4 hash value!
In view of the definition of MD4 as the iterative appli-
How Alf did it cation of compress, we obtain a collision by taking any
For the precise definition of the above digital contract bit string and appending it to M and M™.
note that the first sixteen 32-bit words are:
Where MD4 is still in use, it should be replaced!

Professor Hans Dobbertin is particularly interested in the
evaluation and design ofcryptographic aIguritJnns. He can be
[l] Dobbertin, H.: Cryptanalysis ofMD4, preprint. e4
contacted at dobbertin@skom.rhein.de.

Page 31
Previous Page Home Next Page

A 1 G 0 R I T H M S U P D A T E

More Developments with The increased work and data requirements for the
Keyed Hash Functions new attack over that offering MAC-forgery depend
on the length of k, since this determines the num-
At the rump session of Crypto™95, Bart Preneel in
joint work with Paul van Oorschot described a new ber of guesses a cryptanalyst is required to try in the
attack on one method of message authentication second phase. However, since the cryptanalyst can
using a keyed hash function (see CryptoBytes vol- choose this length, the requirements of the attack
ume 1, number 1). are effectively dominated by the requirements for
the MAC-forgery attack.
. . . the new In what is sometimes called the envelope method, a
attack does hash function H can be used to provide authentica- Since the MAC-forgery attack is barely practical the
demonstrate a tion of a message m under the action of two keys k, same must be said of this new attack which recovers
certificational and kz by using the result of H(kl * m . k,) as a mes- the key. However the new attack does demonstrate
weakness in sage authentication code for the message m. A vari- a certificational weakness in the envelope method
the envelope ety of padding schemes might also be specified as since the secret key can be recovered with much less
method . . . additional security measures. work than the length of the secret key might imply.
While the use of additional padding (to prevent the
Previously (see CryptoBytes volume 1, number 2), splitting of k,) would thwart this attack, it seems
Preneel and van Oorschot have reported that the fair to recommend different mechanisms than the
envelope method of keyed-MD5 allows a MAC forg envelope method for providing message authentica-
ery attack with “2@ known message-MAC pairs and tion with a keyed hash function. CryptoBytes will
a single chosen text.” These known messages have report on future developments.
to be the same length and additional reductions in
A linear Protocol Failure for RSA
the data requirements are possible if the messages
With Exponent Three
are known to have a particular form.
At the rump session of Crypto ˜95, Matthew Franklin
At the rump session of Crypto ˜95, Preneel described and Michael Reiter of AT&T Bell Laboratories pre-
a new attack on the envelope method which allows sented a new weakness of RSA with low encrypting
recovery of the secret key rather than just a MAC exponent. This weakness depends on two messages
forgery. For the new attack to succeed, the length of being encrypted with exponent three with respect
the messages being authenticated is carefully chosen to the same RSA modulus, and on a (non-trivial)
by the cryptanalyst to ensure that the action of the linear relationship being known to exist between the
second key kz is split into two parts, one under the two messages. In such cases the messages can be
influence of k, and the other under kb, where kz is computed efficiently by an attacker that has access
equal to the concatenation k, h. only to the public key, the two ciphertexts, and the

linear relation. This differs from the “small expo-
The attack requires two phases, the first of which is nent” protocol failure, generalized by Hastad (de-
in effect the previously mentioned MAC-forgery scribed opposite in The Secure Use of RSA), which
attack. Using information obtained from this first requires that messages be encrypted with respect to
different moduli. It also differs from the “common
phase, the cryptanalyst requests the MACs on 21bl
pairs of chosen messages (2 1 knl+l messages in total) modulus” protocol failure, observed by Simmons,
where 1 k, 1 denotes the number of bits in k,. These which requires that a single message be encrypted
with different exponents. This weakness can be ex-
new message pairs are chosen according to different
guesses for k,. ploited to yield passive attacks on protocols that en-
crypt related messages. Examples of such protocols
When the guess for k, is correct, the MACs gener- are a signature sharing protocol for RSA, proposed
ated for that pair of messages will be the same and k, by Franklin and Reiter at Eurocrypt ˜95, and a key
can be correctly identified. The rest of k2 can be distribution protocol, proposed by Tatebayashi,
found either by exhaustive search, or by using mes- Matsuzaki, and Newman at Crypto ˜89. This weak-
sages of a second carefully chosen length to split the ness does not affect the encryption of arbitrary unre-
unknown remainder of k, once again. lated messages. m

Page 32
Previous Page Home Next Page
The Secure Use of RSA

is the encrypted message. The legitimate receiver uses
Burt Kaliski and Matt Robshaw
the private decryption key (n, d) to compute cd mod n.
RSA Laboratories
The underlying mathematics guarantees that
100 Marine Parkway, Suite 500
Redwood City, CA 940651031
cd c (me)d zt m(d) E m™ E m (modn)
Since its invention over fifteen years ago, the RSA
and the original message can be recovered.
cryptosystem [21] has been submitted to extensive
scrutiny and analysis. Its continuing resistance to at-
Closely following the original Diffie-Hellman model
tack has resulted in its being well trusted and used
for a public-key cryptosystem [8], the private and
public keys in RSA can be used to provide a digital
signature. Here the digital signature is generated us-
One of the most notable features about RSA is its
ing the private key (which is known to only one
apparent simplicity and considerable elegance. This
user) and verification of the signature can be com-
elegance is due in most part to the algebraic frame-
pleted with the corresponding public key. The sig
work in which the algorithm is defined. But this
nature s of message m with the private key (n, d) is
framework can itself be a dangerous environment in
given by s = md mod n while public verification of
which to practice cryptography. Indeed it is straight-
the signature s can be achieved using (n, e) since the
forward to write down a few mathematical identities
that at first sight seem to threaten the integrity of
RSA when used either for encryption or for the pro-
vision of digital signatures. m f se (mod n)

will hold for a legitimate digital signature and fail
As we will see, however, for each of these apparent
threats to RSA there is a simple and practical coun-
termeasure. It is all a matter of using the technology
. . . for each of
Both encryption and the creation of digital signa-
correctly. In this article we will show how RSA can
these apparent
tures are simple and straightforward operations. The
be used to its full potential.
threats to RSA
mathematical structure underpinning the cryptosys-
The RSA Cryptosystem there is a simple
tern ensures that the link between these operations and
and practical
their reverse can be easily established. But other links
RSA is a public-key cryptosystem and digital signa-
can be made and as motivation for what follows we countermeasure.
ture scheme that was invented in the late 1970s at
It is all a matter
MIT by Ron Rivest, Adi Shamir and Len Adleman will make note of two, easily established identities:
of using the
[21]. The system depends on modular exponentia-
tion and is defined as follows. (m,,m2)e = m,e.mc(modn) a n d
(m.f-)d = md . r (mod n).
We will denote the public key by (n, e) and the pri-
vate key by (n, d). The integer n, which is known as We will see that exploitation of these identities and
the modulus, is chosen as the product of two primes other properties can lead to attacks on both the gen-
P and q. The integers e and d are exponents and they eration of RSA signatures and on RSA encryption.
are chosen so that ed = l(mod 4(n)) where q(n) = In this article we will describe these attacks and some
straightforward and practical counter-measures.

Aims of the Attacker
Encryption and decryption of a message m can be
Three consequences of a successful attack on a pub-
described as follows. Using the public key (n, e) the
sender of the message computes c = me mod n and c lic-key cryptosystem or digital signature scheme such
as RSA might be:

1. recovery of the private key,
Burt Kaliski is chief scientist and Mutt Rob&w is a research sci-
2. message decryption, and
entist at RSA Laboratwies. They can be contacted at bu&rsa.com
3. signature forgery.
or matt@rsa.com.

Page 33
Previous Page Home Next Page

It ir general/y the article by Adi Shamir in this issue of Crypto-
It may well be possible that an attack achieving the
accepted that Bytes on using RSA moduli with two primes that are
second or third result can be mounted without the
widely differing in size!) For large enough numbers,
attacker actually recovering the private key. In this
RSA numbers
and certainly for the size of numbers we use in today™s
article we consider attacks that might be used to
composed of
implementations of RSA, the general number field
primes of about achieve each of these goals in turn, and give rules of
the same size sieve (GNFS) is the best “general-purpose” factoring
thumb which prevent the attacks being successful.
are among method. The older quadratic sieve and its variants
the hardest are faster below a certain size of modulus (currently
We note that in a practical implementation of RSA
around 116 decimal digits in length [2]). Most im-
to factor... there are additional security considerations beyond
portantly however, users of RSA can determine the
those covered here. For instance, the interchange-
current level of factoring ability and make allowances
ability of signatures and decryption might lead to
for a certain amount of future improvement. As a
unexpected security weaknesses if the same key were
consequence, general-purpose factoring need not be
used for both. Additionally, the source of random-
a concern to users of RSA if the primes (and hence
ness for key generation and the storage of the pri-
the RSA modulus) are chosen to be sufficiently large.
vate key are vital issues in the secure implementa-
tion of RSA. Suffice it to say that no implementa-
Depending on the form of the primes p and q that
tion of RSA can be considered fully secure unless all
are multiplied together to give the user™s modulus, it


. 7
( 19 .)