[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

IP Authentication using Keyed MD5 / The ESP DES-CBC Transform



======================================================================
Some comments on Keyed-MD5 for Message Authentication 
and on the ESP DES-CBC Transform

Bart Preneel

Katholieke Universiteit Leuven,  Belgium

Summary

In this document we comment on the security of keyed-MD5 for message 
authentication and on some alternatives which have been put forward.
We also make a note on the ESP DES-CBC transform.


1. Keyed-MD5 for Message Authentication
---------------------------------------

In [Krawczyk] H. Krawczyk proposes a modification to the keyed MD5 
method proposed in [Metzger-Simpson].  The new method has a security 
proof based on the pseudo-randomness of the function MD5#, which is 
the MD5 compression function keyed with the IV [Krawczyk2].


THE PSEUDO-RANDOMNESS ASSUMPTION

A first remark is that while the collision resistance of MD4 and
MD5 has been analyzed, no one has ever published any results regarding
an evaluation to verify whether MD5# is actually a pseudo-random function.
Both properties (collision resistance of MD5 and pseudo-randomness of
MD5#) are independent, i.e., either of them can be present without the
other one. A related observation has been made in [Roe et al.].

Second, weaknesses have been found in the compression function of
MD5, and recent work on MD4 [Vaudenay] and RIPEMD [Dobbertin] suggests
that the internal structure of these hash functions could be used to
find collisions faster than by a brute force birthday attack
(2^{64} operations).  It is not clear what the implications of this
are on the pseudo-randomness of MD5#, but it seems quite plausible that
the internal structure of these functions can be exploited in an attack
as well.

Note that in [Krawczyk2] it is stated that "everybody uses these functions
[MD5, SHA] to generate (pseudo) random keys": while it is true that this 
is based on the pseudo-randomness of MD5#, it should be noted that when 
MD5 is used for key derivation, an attacker has much less input-output 
pairs available, which makes statistical attacks infeasible. 

In view of the above it would appear more secure (or at least prudent) to 
key not only the beginning and the end of the hashing process, but also the
compression function as done in MD5-MAC. In this way, the MAC is more
robust against weaknesses of the underlying hash function. By keeping
the modification as simple as possible, it is highly unlikely that new
vulnerabilities are introduced. While both the scheme proposed by
Krawczyk and MD5-MAC use a key as IV, the introduction of a secret key
in the compression function is a major difference between both schemes.
Note that this does not preclude a security proof based on the
pseudo-randomness of the compression function MD5-MAC#.

The following quote of [Krawczyk] seems to support this statement:
% However, the proposed scheme does not suffer of any practical weakness
% known today. On the other hand, if the above properties are to be relaxed
% then other designs which may prove more robust to future attacks are
% possible.
%
% A separate note by Paul Van Oorschot to these lists proposes going in this
% direction. I support his position if the above conditions (no modification
% of MD5, speed, etc) are relaxed. Otherwise, I propose the adoption of
% keyed-MD5 as described in the above draft (draft-krawczyk-keyed-md5-00.txt).
%

In [Krawczyk2], it is also remarked that "functions completely unrelated
to MD5 or similar hash functions could be used". However, no concrete 
proposal along these lines has been made yet. 

SIZE OF THE MAC: 64 vs. 128 BITS

The reference [crypto'95] explains why keeping 64 bits of the MAC rather
than 128 can increase the security. Indeed, a birthday attack on the 64-bit 
MAC requires 2^{64} chosen and 2^{64} known texts, while the same attack on
the 128-bit MAC requires 2^{64} known texts and only a single chosen text 
(under the assumption that the appended key is padded to a complete block).
A point to drive this home: this *known* attack demonstrates that one method
is better than the other, vs. this attack.  While both may be unrealistic,
it is reasonable to argue that this may well indicate that the same scheme
is more secure than the other against yet-unknown attacks, which may be
feasible in the one case and not in the other.

In [Krawczyk2], it is stated that the birthday attack requires strictly 
speaking 2^{64} chosen messages for his proposal [Krawczyk], even with a 
128-bit result: indeed, the attack requires that the last block is constant,
which need not be true for all texts.  This is the motivation to omit the 
padding of the appended key.  However, it is likely that mixing in a 
single block the secret key and data under complete control of an attacker 
makes it easier to obtain information on that secret key. 

Note that the model in [Bellare94] does not make a distinction between 
chosen and known text attacks, while in practice there is a major difference 
between both types of attacks.


CBC-MAC

In [Roe et al.], it is proposed to make DES based CBC-MAC the default algorithm.
We do not support this proposal for the following reasons:
1. While it is shown in [Bellare94] that certain variants of the CBC-MAC
   are secure, provided the underlying encryption algorithm is pseudo-random, 
   it should also be noted that in [crypto95] a practical attack is described 
   on DES CBC-MAC, which requires 2^{32} known text-MAC pairs and a single 
   chosen text.  One can argue that the key should be changed more frequently, 
   but if the CBC-MAC key is changed after 2^{25} messages, the success
   probability equals 1/30,000, which is still non-negligible.
2. It is suggested in [Roe et al.] to use simple CBC mode as defined in
   [Fips81]; however, if no additional measures are taken (such as a special
   processing of the last block), simple CBC-MAC is vulnerable to an attack 
   requiring 2 known and 1 chosen texts.
3. Because of the short key size, single DES does not offer a sufficient
   security level, as noted in [Metzger-Karn-Simpson].
4. The fastest DES implementations in software are about 5 times slower than
   a fast MD5 implementation on the same machine. Current DES hardware
   solutions are in general not much faster due to communication overhead and
   loss of pipelining in CBC/CFB mode. Note that the 1 Gbit implementation 
   referenced in [Metzger-Karn-Simpson] is a very expensive GA-As chip, which 
   was an academic design exercise; it is far from a commercial product 
   (the fastest chips available are about 4 times slower).  This problem will 
   become more important if one moves to triple-DES, which is about 2.5 times 
   slower in software.


2. The ESP DES-CBC Transform
----------------------------

THE INITIALIZATION VALUE (IV)

The IV in CBC-mode should be unpredictable and should be kept secret;
it must be impossible to correlate subsequent IV's (see also [Roe et al.]).
Therefore the solution proposed in [Metzger-Karn-Simpson] is not acceptable.
If one wants to use a counter, one could encrypt it with the session key 
(or with a key derived from the session key) to obtain the IV.
A second alternative is to use a pseudo-random generator based on the OFB 
mode of DES. Both solutions require only a negligible amount of computation 
compared to the encryption of a complete message.

The problem of the IV could be eliminated by using 64-bit CFB mode, which 
has the same performance as the CBC-mode, but allows to send the IV in clear 
(since it is encrypted before it is used).  Also, the IV need not be a 
pseudo-random value (it can be a counter).  The integrity protection of the 
last 64 bits of a message is weaker than that of the CBC mode (with a 
secret IV), but encryption should not be used to provide integrity anyway.


REFERENCES

[Bellare94] M. Bellare, J. Kilian, P. Rogaway,
   "The Security of Cipher Block Chaining,"
   Proc. Crypto'94, Springer-Verlag LNCS 839, 1994, pp. 341-358

[crypto95] B. Preneel, P.C. van Oorschot,
   "MDx-MAC and Building Fast MACs from Hash Functions,"
   Proc. Crypto'95, Springer-Verlag LNCS (to appear, Aug. 1995).
   {ftp: ftp.esat.kuleuven.ac.be, directory pub/COSIC/preneel}

[Dobbertin] H. Dobbertin, "Collisions for the Last Two Rounds of
   the RIPEMD Compress Function," presented at rump session of Eurocrypt'95,
   St. Malo, France, May 1995.  {email: dobbertin@skom.rhein.de}

[FIPS180-1] Secure Hash Standard,
   NIST, US Department of Commerce, Washington D.C., April 1995.
   {http://csrc.ncsl.nist.gov/fips/fip180-1.txt}

[Krawczyk] H.~Krawczyk,
   "Keyed MD5 for Message Authentication",
   draft-krawczyk-keyed-md5-00.txt.

[Krawczyk2] H.~Krawczyk,
   "Analysis of Keyed MD5 (sketch)",
   June 30, 1995.

[Metzger-Karn-Simpson] P. Metzger, P, Karn, W.A. Simpson,
   "The ESP DES-CBC transform",
   draft-ietf-ipsec-esp-des-cbc-04.txt.

[Metzger-Simpson] P. Metzger, W.A. Simpson,
   "IP Authentication Using Keyed MD5",
   draft-ietf-ipsec-ah-md5-03.txt.

[Roe et al.] M Roe, R. Needham, M. Lomas, R. Anderson, I. Jackson,
   "Comments on the IP Security Internet Drafts,"
   June 30, 1995.

[Vaudenay] S. Vaudenay, "On the Need for Multipermutations:
   Cryptanalysis of MD4 and SAFER," Fast Software Encryption,
   Springer-Verlag LNCS, 1995 (to appear).  (Proc. of Algorithms Workshop,
   Leuven, Belgium, Dec. 1994).  {email: Serge.Vaudenay@ens.fr}

==============================================================================