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

response to Last Call on: IP Authentication using Keyed MD5

This note is in response to the Last Call on the Keyed MD5 draft:

>  From: The IESG <iesg-secretary@CNRI.Reston.VA.US>
>  Subject: Last Call: Security Architecture for the Internet Protocol to
>  	    Proposed Standard
>  Date: Fri, 16 Jun 95 13:14:01 -0400
>  Sender: scoya@CNRI.Reston.VA.US

> The IESG has received a request from the IP Security Protocol Working Group
> to consider the followingt documents for the status of Proposed Standard:

> 4. IP Authentication using Keyed MD5 <draft-ietf-ipsec-ah-md5-03.txt>

=======
Summary
=======
The following are apparent deficiencies of the current Keyed MD5 draft.

1. Despite the inclusion of a section ``Security Considerations'',
   the I-D gives no estimate of the security level of the proposed keyed
   hash function (e.g. work factor 2^{n} to break, etc.).  Moreover, from 
   reading the I-D itself, it is not clear what the conjectured level is. 

2. The I-D does not seem to be aware of, nor take into consideration, 
   recent work in the areas of hash functions and keyed hash functions.
   This includes both generic results, and results specific to functions 
   like MD4 and MD5, both of which indicate that the proposed method is
   almost certainly less secure than hoped (cf. point 1.). 

3. The current I-D does not offer the best (w.r.t. security and speed) 
   solution currently available for the proposed application.  One 
   alternative is discussed below; others almost certainly exist.

4. Some technical statements in the current I-D regarding security are
   both inaccurate and misleading.

I suggest that it is unacceptable for such an I-D to be progressed without
specifying a conjectured level of security; without this, it cannot be 
decided if it meets the requirements of an application, or compared with 
alternatives.  I further suggest that upon investigation, it will be found 
that recent attacks, both generic and MD4/MD5-specific (as noted below), will
show the proposed method is weaker than has been believed to date.  As a 
consequence, alternative algorithms should be considered (as discussed below).  

I suggest that serious attention be given to these points 
before a decision is taken on the progression of this I-D.

Some technical discussion follows in support of these statements.

Sincerely,
Paul C. Van Oorschot
1995 June 26 

------------------------------------------------------------------------------
Paul Van Oorschot           Bell-Northern Research     | EMAIL: paulv@bnr.ca |
MAIL TO:                    SHIP TO:                   | VOICE: 613-763-4199 | 
BNR, Box 3511, Station C,   BNR, 2 Constellation Cr.   | FAX:   613-765-3520 |
Ottawa, Canada K1Y 4H7      Nepean, ON, Canada K2G 5J9 |                     |
------------------------------------------------------------------------------

===============================================================
Additional Discussion and Technical Details on the above points
===============================================================
The technical content of the I-D is as follows.  A keyed hash function is 
built from MD5 using below will be referred to as the ``envelope method'':

   ``The variable length secret authentication key is ... concatenated
     with ... the invariant fields of the entire IP datagram ...
     concatenated with the variable length secret authentication key
     again (trailing padded is added by the MD5 algorithm). The resulting
     128-bit digest is inserted into the Authentication Data field.''

1. The ID makes no mention of the level of security which the proposed
   technique offers.  Since historically security of this nature cannot
   be proven, it is customary to state a conjectured level of security,
   which essentially summarizes how much work would be required using the
   best currently-known attack.
   
   Some relevant information can be found in a recent newletter article
   [rsabytes] in which three MD5-based MAC proposals are made for the 
   IPSEC working group, by Matt Robshaw and Burt Kaliski (citing help 
   from Hugo Krawczyk and Mihir Bellare). The three methods are:

   i.   The envelope method with K1 = K2 
        where K1 is a 128-bit key (padded to a complete first block)

   ii.  MAC(x) = h( K1, h(K2,x) )

   iii. MAC(x) = h( K1, h(K1,x) )  

   Scheme (i) here is essentially that of the proposed I-D.
   The paper suggests (without details) that the best known attack on 
   these schemes requires 2^{64} chosen message texts. 
   
   Another paper, to be presented at Crypto'95 [crypto95], provides actual
   details of an attack which applies to (i).  When applied to the
   proposal of the current I-D with a 128-bit key K = K1, the attack
   requires 2^{64} _known_ message-MAC pairs, and reduces the number 
   further in the case that the known messages contain a common sequence 
   of s trailing blocks (e.g. reduced to 2^{56.5} known text-MAC pairs 
   for s=2^{16}). (As an aside, the same type of attack can be applied to
   scheme (ii), using a divide and conquer strategy as outlined in
   [crypto95], effectively reducing its security to the larger of K1 and K2.)
   The results are general for an n-bit key (n=128 is discussed above);
   for n=64, the attack requires on the order of 2^{32} known text-MAC
   pairs or less, which becomes more worrisome in practice.
   Perhaps more significantly, the attacks continue to apply in cases 
   where messages are of fixed length, or are prepended by length fields.

2. Point 1. above discusses generic attacks.  Regarding attacks on 
   specific hash functions, the I-D notes an attack on the compression 
   function of MD5 by den Boer and Bosselaers, and states:

    ``There is not yet a known method to exploit these collisions
      to attack MD5 in practice, but this fact is disturbing to some
      authors [Schneier94].'' 

   Indeed, considerable additional research has been recently carried out.
   Bert den Boer himself proposed a new hash function, namely RIPEMD,
   which was analyzed under the European RACE/RIPE consortium in 1992. 
   RIPEMD is a ``very strong'' version of MD4 involving essentially two 
   strengthened versions of MD4 running in parallel.  It was designed 
   to counter known two-round attacks on MD4 and MD5.  However, more
   recent cryptanalytic work on MD4 by Vaudenay [md4-attack] and on 
   RIPEMD by Dobbertin [ripemd-attack] suggests that both MD4 and 
   (very likely) MD5 fail to be as resistent as previously believed 
   to manipulations of their internal structures.  

   As a result of this work, some European researchers now believe that 
   collisions for MD4 and MD5 themselves (rather than just for their 
   compression functions) may soon be found by similar techniques.

   Even if this is not the case, a very reasonable (and prudent) 
   conclusion is that if functions like these are to be used as the 
   basis for constructing a MAC, a more conservative design should be 
   used than the envelope method.

   Neither the work of Vaudenay nor Dobbertin is discussed or referenced 
   in the I-D.

3. One alternative to the keyed MD5 method of the I-D is the MDx-MAC 
   construction specified in [crypto95].  This is a conservative design
   (as recommended in Point 2. above), has been fully implemented and
   verified by two independent implementations (one at BNR-Ottawa and
   the other at K.U.Leuven, Belgium), and runs only 5% to 20% slower 
   than MD5 (depending on the processor and implementation). 
   
   Regarding speed, the MDx-MAC construction allows the function to be
   based on any MD4-like function, e.g. MDx = MD4, MD5, SHA or RIPEMD;
   MDx = MD5  yields MD5-MAC.  If speed is a tremendous concern, then 
   MD4-MAC runs fastest, with a similar speed ration to MD5-MAC as 
   MD4 to MD5. If security is more of a concern, SHA-MAC can be used.

   In contrast, the envelope method is not a conservative design.  
   While it may be possible to argue that the envelope method 
   is theoretically secure against various attacks, such proofs 
   typically must assume that the underlying hash function is 
   ``secure'' in some black-box sense (i.e. attacks cannot benefit 
   by taking advantage of details of its internal structure, which 
   the attacks of Vaudenay and Dobbertin noted above clearly do).

4. Two important points in the current I-D are misleading, which is
   particularly alarming given that so little is said about even a
   conjectured security level for the proposed method.

   i) The result from the parallel collision search paper of van Oorschot 
      and Wiener in [OW94] is mis-stated.  The I-D states that the attack
 
      ``could find messages that hash to an arbitrary given MD5 hash''.

      The correct statement is that two messages can be found which have 
      a common hash, where both messages can be almost-entirely chosen by 
      an attacker; however, the hash value cannot be.  While subtle, the
      difference is enormous from a security viewpoint: the relative
      work factors for the two statements are 2^128 and 2^64 operations.

   ii) The I-D suggests, regarding 128-bit hashes: 
   
      ``Although this is not a substantial weakness, it should be 
       recognized that current technology is catching up to the 128-bit 
       hash length used by MD5. Applications requiring extremely high 
       levels of security may wish to move in the near future to algorithms 
       with longer hash lengths."

     I believe this statement to be quite misleading, and may dangerously 
     contribute to further confusion between a MAC and an unkeyed 
     hash algorithm.  A 128-bit MAC should indeed be sufficient for the 
     forseeable future (although one might conceivably desire a larger
     internal chaining variable at some point). In fact, for a hash function
     such as MD5, [crypto95] shows that keeping less than the full 128 bits
     makes the MAC more resistant to certain attacks. On the other hand,
     128 bits soon may well be too short for an unkeyed hash function,
     for applciations requiring very high levels of security.

==================
Concluding remarks
==================
Given the recent work in the area of both hash functions and MACs built 
from hash functions, the method of the proposed I-D appears to have been
either insufficiently analyzed, or improperly placed in context with 
the best currently-known attacks.  The method does not appear sufficiently 
sound to warrant progression of the I-D to RFC.

Given the length of time it has taken for IPSEC to resolve this difficult
matter, it would be ironic for this I-D to be progressed to RFC concurrently 
with the publication of [crypto95] which shows that the level of security 
it and similar constructions offer is considerably less than believed.  

Both the proposal of [crypto95], and other similar proposals, should be 
investigated as alternatives to that of the current I-D.  That of
[crypto95] can be MD5-based, is resistant to all currently known attacks, 
is essentially the same speed as MD5 itself, and would appear to be 
stronger than the envelope method in the case that flaws are found in the
future in MD5 itself.  The authors would be happy to post [crypto95] to 
the usual ftp sites convenient to IPSEC.  It can also be made available from:

               K.U.Leuven ftp server: ftp.esat.kuleuven.ac.be
			   directory: pub/COSIC/preneel

Hopefully this can be discussed further, as appropriate, 
prior to and/or at the Stockholm IETF.

==========
References
==========

[rsabytes] B. Kaliski, M. Robshaw, 
    ``Message authentication with MD5,'', pp.5--8 in
    _CryptoBytes_ (RSA Labs Technical Newsletter), vol.1 no.1 Spring 1995. 

[crypto95] Bart Preneel, Paul C. van Oorschot,
   ``MDx-MAC and Building Fast MACs from Hash Functions'', 
   Proc. Crypto'95, Springer-Verlag LNCS (to appear, Aug. 1995).
   (A preliminary version of this paper excluding the MDx-MAC construction, 
    ``A new generic attack on message authentication codes'',
    has been available to some members of the IPSEC working group.)

[md4-attack] 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}

[ripemd-attack] 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}
----------------------------------------------------------------------