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™,

CONTRACT

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

replaced!

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

References

evaluation and design ofcryptographic aIguritJnns. He can be

[l] Dobbertin, H.: Cryptanalysis ofMD4, preprint. e4

contacted at dobbertin@skom.rhein.de.

Ia

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES -AUTUMN 1995 CRYPTOBYTES

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

l

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

CRYPTOBYTES AUTUMN 1995 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

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

widely.

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

comparison

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

otherwise.

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-

technology

tion and is defined as follows. (m,,m2)e = m,e.mc(modn) a n d

correctly.

(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.

(P-1)(+-1).

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.

CRYPTOBYTES

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - AUTUMN 1995 la ˜˜˜˜˜˜-

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