liEi

1995

THE LABORATORIES - SPRING CRYPTOBYTES

TECHNICAL NEWSLETTER OF RSA

Page 61

Previous Page Home Next Page

simple 2-bit quantum gates such as the natural quan-

but-did-not has no influence whatsoever on the ac-

It is possible

tum extension of the classical exclusive-or. Experi-

tual outcome. In contrast, it is possible to program a

to program

mental physicists such as Serge Haroche and

quantum computer so that all potential computation

a quantum

Jean-Michel Raimond are already attempting to build

paths are taken simultaneously in quantum super-

computer so

simple quantum gates based on atomic interferometxy

position. What makes this so powerful-and myste-

that all potential

and microwave cavities capable of trapping single

rious-is the exploitation of constructive and

computation

photons for a significant fraction of one second. Even

destructive interference phenomena, which allows for

paths are taken

though a full-fledged quantum computer may take a

the reinforcement of the probability of obtaining de-

simultaneously

long time to come, I like to think that I shall see a

sired results at the expense of the probability of ob-

in quantum

special-purpose quantum factorization device in my

taining spurious results. This happens because the

superposition.

lifetime. If this happens, RSA will have to be aban-

amplitude of reaching any given state is the sum of

doned. Most other practical public-key systems will

the amplitudes of reaching this state by all possible

be compromised as well because Peter Shor has also

computation paths. Because amplitudes can be nega-

devised a quantum algorithm for extracting discrete

tive (even complex), the amplitude of reaching an

logarithms.

undesirable result from one path can be annihilated

by the amplitude of reaching it from another path.

But do not despair for the fate of cryptography: there

In the words of Richard Feynman, “somehow or other

will always be quantum cryptography to come to the

it appears as if the probabilities would have to go nega-

rescue! Quantum cryptographic systems take advan-

tive.” It is not easy to put such interference phenom-

tage of the uncertainty principle, according to which

ena to practical use, but Peter Shor™s tourdeforce

measuring a quantum system in general disturbs it and

proves that it is possible, at least in principle.

yields incomplete information about its state before

the measurement-which is precisely what makes

The actual implementation of a quantum computer

quantum computers difficult to program. When in-

will be very challenging. It may even turn out to re-

formation is encoded with non-orthogonal quantum

main forever out of reach of human technology. One

states, any attempt from an eavesdropper to access

difficulty is to keep quantum coherence in the com-

the information necessarily entails a probability of

puter. The problem is that coherent superpositions

spoiling it irreversibly, which can be detected by the

are very fragile: they spontaneously turn into inco-

legitimate users. Using protocols that I have designed

herent statistical mixtures-which are unsuitable for

with Charles H. Bennett, building on earlier work of

quantum parallelism-because of residual interactions

Stephen Wiesner, this phenomenon can be exploited

with the environment. Consequently, quantum in-

to implement a key distribution system that is secure

formation disappears gradually from the computer.

even against an eavesdropper with unlimited com-

Rolf Landauer has pointed out the additional prob-

puting power, indeed even against an eavesdropper

lem that quantum computation may be susceptible

who has a quantum computer at her disposal! Sev-

to spontaneous reversals, which would unpredictably

eral prototypes have been built in recent years. In

cause the computation to go backwards. Yet another

particular, British Telecom announced in September

difficulty is that of error correction despite early work

1994 the successful completion of their fully work-

by Asher Peres and more recent work by Andre

ing apparatus, perfected by Paul Townsend, capable

Berthiaume, David Deutsch and Richard Jozsa: in

I like to think

of implementing quantum key distribution over 10

classical digital computing, discrete states are con-

that t shall see a

kilometres of ordinary optical fibre. For more infor-

tinuously snapped back onto the proper voltages for

special-purpose

mation on quantum cryptography, please consult my

0 and 1; no similar process is available for quantum

quantum

article in the March 1335 sesquicentennial Anniver-

computing even if the program is such that the le-

factorization

sary Edition of Scientifi American on “The Computer

gitimate states have discrete amplitudes. As a result,

device in my

in the 21st Century” (reprinted with updates from

the computer may drift away from its intended state.

lifetime.

their October 192 regular issue).

Nevertheless, Seth Lloyd has promising ideas on how

To paraphrase the Book of Job,

to build “a potentially realizable quantum computer.”

7bequunfumtaktb aumy

Furthermore, it was discovered by David DiVincenzo

that universal quantum computation can be based on andtbequantumgixtb Lxxkr

NEWSLETTER OF LABORATORIES

CRYPTOBYTES 1995 - THE TECHNICAL RSA

SPRING

Page 62

Previous Page Home Next Page

Message Authentication with MD5

A hash function can provide message authentication

BurtKa&ki and hf&tRobshaw

in a most satisfying manner when combined with a

RSA Laboratories

100 Marine Parkway, Suite 500 digital signature algorithm, which does have a key.

Redwood City, CA 94065 USA But typical digital signature schemes have some per-

formance overhead, which while acceptable for the

Message authentication is playing an important role periodic setup of communications sessions, is often

in a variety of applications, especially those related too large on a message-by-message basis. Thus, the

to the Internet protocols and network management, focus is on message authentication based on a shared

where undetected manipulation of messages can secret key, which is ideally integrated into the hash A more practical

have disastrous effects. function in some manner. solution seemed

to be to base the

There is no shortage of good message authentication As an illustration of the challenges, consider the authentication

codes, beginning with DES-MAC, as defined in “prefur” approach where the message authentication codes [...I on

FIPS PUB 113 1™1. However, message authentication code is computed simply as the hash of the concat- hash functions.

codes based on encryption functions such as DES, enation of the key and the message, where the key

which were designed for hardware implementation, comes first and which we denote as MD5 (/z. m).

may be somewhat limited in performance for soft-

ware, and there is also the question of U.S. export MD5 follows the Damgard/Merkle f4v61 iterative

restrictions on encryption functions. structure, where the hash is computed by repeated

application of a compression function to successive

In standards efforts such as the Simple Network blocks of the message. (See Figure 1.) For MD5, the

Management Protocol IsI and proposals for Internet compression function takes two inputs -a 12%bit

Protocol security, a more practical solution seemed chaining value and a 512-bit message block-and

to be to base the authentication codes not on DES produces as output a new 128-bit chaining value,

but on hash functions designed

for fast software implement-

ation which are widely avail-

able without restriction, such

as the MD5 message-digest

algorithm c91.

But how to do it? Hash func-

Initial Value

tions are intended to resist in-

version - finding a message

with a given hash value -and

collision - finding two mes-

sages with the same hash value. Message authentica- which is input to the next iteration of the compres-

tion codes, on the other hand, are intended to resist sion function. The message to be hashed is first pad-

forgery - computing a message authentication code ded to a multiple of 512 bits, and then divided into a

without knowledge of a secret key. Building a mes- sequence of 512-bit message blocks. Then the com-

sage authentication code on an encryption function pression function is repeatedly applied, starting with

thus seems a logical choice (and the security rela- an initial chaining value and the first message block,

tionship has been recently settled - in work by and continuing with each new chaining value and

Mihir Bellare, Joe Kilian and Phillip Rogaway L31). successive message blocks. After the last message

Building one on a hash function, however, is not as block has been processed, the final chaining value is

simple, because the hash function doesn™t have a key. output as the hash of the message.

Because of the iterative design, it is possible, from

Bu˜Kaliskn™˜cbiefscientistandMattRohshaw˜a˜˜b˜-

only the hash of a message, to compute the hash of

tistatR9 Laaboratonix 7lxy can becontactedatburt@r.com

longer messages that start with the initial message

orrruzn@lsa.com.

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SPRING 1995 CRYPTOBYTES

iii

Page 63

Previous Page Home Next Page

and include the padding required for the initial mes- only on the message; the last part of the message;

sage to reach a multiple of 512 bits. Applying this to and the padding.)

the prefx approach, it follows that from MD5 (Jz . m),

one can compute MD5 (!z . m 3 for any m™ that starts An opponent who sees the message authentication

with m . p, wherep is the padding on k - m. In other codes for many messages thus sees the result of

words, from the message authentication code of m, applying the compression function to many different

one can forge the message authentication code of known values and the same key, which may reveal

m . p * x for any x, without even knowing the key k, information about the key. While our analysis

and without breaking MD5 in any sense. This is called suggests MD5™s compression function is unlikely

a “message extension” or “padding” attacktlOl. to reveal information about the key, other hash

functions may not fare as well, and so we prefer a

Other hash functions with an iterative design, such more robust design.

as NIST™s Secure Hash Algorithm IsI, are also vulner-

able to the message extension attack, and similar at- The prefix approach is also affected by these issues,

tacks can also be mounted on tree-structured designs. but only when the message is very short and there is

only a single iteration of the compression function.

(Note also that if only part of the hash were output,

say only 64 bits, this attack would not be possible; Recommendations

however, this is not a completely satisfying solution In joint work with Mihir Bellare and Hugo Krawczyk

because of other con- of IBM, we have considered a number of approaches

.

cerns raised below. In to message authentication with MD5, settling on

SNMP, the message ex- three which we recommended to the Internet Proto-

tension attack is not a col Security (IPSEC) working group:

Key 2 Message

I

problem because mes-

sages are a fvred length. 1. MD5 (kl . MD5 (k2 . m)), where kl and k2 are in-

Another way to avoid dependent 128-bit keys

the attack is to include 2. MD5 (k . p . m . k), where k is a 128-bit key and

an explicit length field p is 384 bits of padding

at the beginning of the 3. MD5 (k . MD5 (k . m)), where k is a 12%bit key

˜=$F.>

The first and third approaches (see Figure 2) are

Because of the message similar, and solve the message extension attack on

extension attack on the prefw approach by the outer application of MD5,

the prefix approach, which conceals the chaining value which is needed

the “suffix” approach, for the attack. The outer MD5 also solves the con-

MD5 (m . k), would cerns of cryptanalysis of the suffix approach, because

the message authentication code is a function of the

seem to be preferred.

But another problem unknown secret key and other varying values, which

arises: the key may be are unknown. These approaches also approximate

certain “provably secure” constructions developed by

vulnerable to crypt-

analysis, depending on Bellare, Ran Canetti and Krawczyk [il.

l-7 the properties of the

(As a disclaimer, we can imagine hash functions for

compression function.

MAC

This is because the which this construction still doesn™t solve the

message authentica- cryptanalytic problems because information from the

tion code is a function inner application leaks to the outer one, but this

of known values and the key, assuming the key is seems more of a pathological case.)

passed entirely to the last iteration of the compres-

sion function. (The known values are the next-to- The third approach may be more vulnerable to at-

last chaining value, which by assumption depends tack than the first since there is only one key and so

CRYPiOSYTES SPRING 1995 - THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

Page 64

Previous Page Home Next Page

authentication code. We do not consider this an in-