From: "paul (p.c.) van oorschot" To: ietf@cnri.reston.va.us Cc: ipsec@ans.net, iesg@cnri.reston.va.us Subject: 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 > 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 ======= 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} ----------------------------------------------------------------------