<<

. 16
( 19 .)



>>



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-

<<

. 16
( 19 .)



>>