Date: Mon, 26 Jun 95 15:33:23 -0400 From: "Phillip M. Hallam-Baker" To: rivest@theory.lcs.mit.edu, hallam@w3.org Subject: IPSEC Ron, I have been looking into the authentication mechanisms quite a bit. I have a few observations: 1) The change from MD5( a^M^a) to MD5 (MD5^a) (where ^ is concatenation) simplified cryptanalysis of a. In the first case it is necessary to either find a shortcut for calculating the effect of the middle section or on exhaustive search do the work of calculating the Message digest on about 2K of data. the new "improved" version seems to make work harder for the implementation and easier for the crytanalist as instead of working with M one only has 128 bits. In any case since the secret comes last one can save the state of the MD5 calculation routine at that point and simply restart from the saved position each time. So MD5 (M^a) isn't any better. 2) The real crux of the problem is using the same shared secret every time. I'm a big fan of using a session key to avoid repettative use of a shared secret. I would have pressed to do this in the WWW Message digest authentication protocol but since that would require DES it would cause export problems and the whole point of that spec was to avoid any export issues altogether. I much prefer the Kerberos system of using a confounder as the key in the keyed digest, This is simply a random session token. It should be increased to 128 bits though. It could also be further strengthened by preceeding it with 64 bits of randomness which are simply thrown away. This prevents direct cryptanalysis to reveal the key by analysing a single token. The encrypted message digest is lossage however since it allows the attacker a means of direct attack since there is known ciphertext in the message. I'm in a mess with this stuff. I did not want to go to Stockholm. Ordinarily Taher should have been able to shoot it down, but the Netscape SSL proposal means that any comments from him may be seen as special pleading. In addition SSL has all the failings of IPsec and more. Its lossage Taher has inherited from before he joined. I plan to complete the memo over the next few days. How serious do you think all this is? Is it minor lossage we can live with? If its just a question of the specification documents themselves being lossy its not so bad. If the specifiation has security holes then its very serious. Personaly I don't like trying security at this level since the purpose of the layered protocol is to conceal high level abstractions from the lower levels. For me security requirements are determined by the highest abstraction layers. I don't see much that we can gain at that level since secure communications in and out of a site still leaves a lot to trust inside the site. The most worrying aspect is the 64 bit keyspace. I have used some very large machines which have the capcity to exhaust significant keyspaces in feasable times. If the transputer technology were to be adopted by a major manufacturer suh as Sun or DEC we could see a large number of massively parallel machines suddenly appear. If we are successful in getting the modifications we are pressing for in Java large scale parallelism may become a commercial reality ovenight. Sun has a go nowhere processor technology and a potentialy first class parallel language. They can be competative only by expanding beyond the 4-16 processors possible using shared memory. Ergo stealing the transputer design may be commercial salvation. I was using a 20 Gips transputer array almost eight years ago. It was not even prohibitively expensive ($100K). The only thing that prevented its use for a generic cryptanalytic attack was the small memory per node - 2K. A frame with 64K per node would have been about the same price and have the capacity to exhaust at least 2^20 of keyspace per second depending on the algorithm. Since then clock speeds have increased by an order of magnitude and silicon real estate as well. Today we could probably do 2^40 per hour without going into rocket science, custom hardware or such (2^40 sound familiar?). That means that the 64 bit keyspace is still going to take 2000 years to exhaust, but in five years time that may be nervously close. Actually we did hava a hack wich would tripple the clock speed of the thing. Simply cool the whole system in liquid nitrogen. The carrier mobility then goes up and the clock speed can be increased from 20Mhz to 57 Mhz. Note how slow Deep thought's clock rate is - the whole thing is in 3 micron CMOS so its technically obsolete. Phill 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} ---------------------------------------------------------------------- Date: Mon, 26 Jun 95 20:22:51 EDT From: hugo@watson.ibm.com To: ietf@cnri.reston.va.us Cc: ipsec@ans.net, iesg@cnri.reston.va.us, PAULV@BNR.CA Subject: response to Last Call on: IP Authentication using Keyed MD5 The document: draft-ietf-ipsec-ah-md5-03.txt presents what is supposed to become the "must to implement" message authentication function for IPSP and IPv6. The authors of that document have ignored past recommendations I made to this group regarding the choice of this function. This included recommendations worked out together with my colleagues Mihir Bellare and Ran Canetti in IBM Research, and Burt Kaliski and Matt Robshaw from RSA Labs. Out of these recommendations, all based on the idea of keying the (otherwise keyless) MD5 function, I chose one that seems the most acceptable to the WG (based on feedback from people to the list and personal discussions with some of its members). This particular function is presented in an Internet draft that was just posted: draft-krawczyk-keyed-md5-00.txt This draft limits itself to the description of the function in a way which is protocol independent, and can be referenced by other documents specifying its particular use for a given protocol, e.g., the Authentication Header of IPSP and IPv6. (This approach is similar to the way RFC-1321 is referenced for MD5). In particular, the draft does not explain the rationale for this particular transform. Information on that is provided in the articles referenced in the draft. Some of this rationale was also several times sketched in my notes to the IPSEC WG list. The particular choice presented in this new draft is intended to keep the following properties: * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements Departing from these conditions, other constructions with better analytical properties can be suggested . For example, keying the MD5 function via its initial registers as proposed in references BCK and PV of the draft (this requires less assumptions on the compression function of MD5 at the cost of a minimal change in MD5 code). 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). Hugo (Krawczyk) To: hugo@watson.ibm.com Cc: ipsec@ans.net, iesg@cnri.reston.va.us, PAULV@BNR.CA Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Date: Mon, 26 Jun 1995 22:00:48 -0400 From: "Perry E. Metzger" To be very clear here, I'm speaking (as usual) for Perry Metzger -- not for my co-authors, just for me. These are *my* views. Take them as such. hugo@watson.ibm.com writes: > The document: draft-ietf-ipsec-ah-md5-03.txt > presents what is supposed to become the "must to implement" message > authentication function for IPSP and IPv6. The authors of that document > have ignored past recommendations I made to this group regarding > the choice of this function. I'd say that "ignored" is too strong a statement. "Felt exhausted by the battles over the authentication transform and were too desultory about making changes to the document because we were utterly and completely burned out" is perhaps a much more accurate statement. We were sort of depending on people to come up with specific language to insert. There being none mentioned, things slouched towards last call. I'm happy to see the suggestions you made adopted in this round, *PROVIDED* that my co-authors don't object (big provisio) and that the incorporation of your suggestions does not substantially delay the adoption of the document (another big provisio). This has been a draft for some time, and has been in last call for some time -- you did have an opportunity to make objections a long time ago. This is not to say that I don't want the technically best solution adopted, but it is to say that I'm more willing to try to make the changes when the documents move the next notch up the standardization process than I am to let these documents, which should have been out literally years ago, get delayed any longer. The architecture we have adopted permits open addition of new security transforms and it will be a simple matter to make your transform a new one in the suite and to mandate its implementation instead of the the existing MD5 transform in the next round of standardization. The IETF process is very forgiving in this regard. I'd like to say that had your results on this topic in cryptography not been informally discussed in Danvers and had I not enormous (that is to say, overwhelming) respect for you, Hugo, I would be of a mind to work to have your objections tossed out right now because of how ill timed they are. You should have been pressing us with specific language to insert into the drafts two months ago. As it is because I am forced to admit that you know far more about the technical merits of one signed hash method over another than almost anyone else around I feel like we have to bend over backwards to try to accomodate your ideas -- but PLEASE DONT EVER DO THIS AGAIN! Next time, please bring this all up earlier, and be mindful of the fact that the earlier set of working group last calls were in place specifically to remind you to jog our memory about such things. Also remember that this is just the first move towards standardization and that there are plenty of more opportunities to make this sort of technical correction as we move forward. > Hugo (Krawczyk) Perry To: perry@imsi.com, ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Date: Tue, 27 Jun 1995 08:41:43 -0400 From: Amir Herzberg Perry, > > ... The authors of that document > > have ignored past recommendations I made to this group regarding > > the choice of this function. > > I'd say that "ignored" is too strong a statement. "Felt exhausted by > the battles over the authentication transform and were too desultory > about making changes to the document because we were utterly and > completely burned out" is perhaps a much more accurate statement. We > were sort of depending on people to come up with specific language to > insert. There being none mentioned, things slouched towards last call. > > I'm happy to see the suggestions you made adopted in this round, > *PROVIDED* that my co-authors don't object (big provisio) and that the > incorporation of your suggestions does not substantially delay the > adoption of the document (another big provisio). This has been a draft > for some time, and has been in last call for some time -- you did have > an opportunity to make objections a long time ago. Hugo _did_ make his objections known long ago, as you recognize in your note. The one thing he didn't do so far is to contribute replacement text, and your text implies that the only reason you know for not adopting Hugo's suggestions is that such text was not provided and you were too, well, tired to write it yourselves. Your complaint here is not justified, as you (all editors) never expressed your agreement with Hugo's suggestions and asked him to contribute text. > This is not to say that I don't want the technically best solution > adopted, but it is to say that I'm more willing to try to make the > changes when the documents move the next notch up the standardization > process than I am to let these documents, which should have been out > literally years ago, get delayed any longer. We certainly don't want any more delay!! But then, it is folly for the WG to produce a standard where we agree that the basic technique should be changed. The process was delayed too long, and we, and hopefully other vendors, are already planning to offer products which comply to the standard as much as possible this year. If the `draft standard' would contain a wrong function, then it would be implemented, and it'll be difficult to get rid of it. It's not much work to change the draft to make use of Hugo's spec and that seems the best solution. > ... > I feel like we have to bend over backwards to try to accomodate your > ideas -- but PLEASE DONT EVER DO THIS AGAIN! Next time, please bring > this all up earlier, and be mindful of the fact that the earlier set > of working group last calls were in place specifically to remind you > to jog our memory about such things. I'm happy to see you plan to fix things. But please understand: you can't complain that Hugo did not provide text as you never asked him to do so; clearly you were aware of his objections and suggestions. best, Amir Date: Tue, 27 Jun 95 13:21:21 EDT From: hugo@watson.ibm.com To: perry@imsi.com Cc: ipsec@ans.net Subject: response to Last Call on: IP Authentication using Keyed MD5 Ref: Your note of Tue, 27 Jun 1995 09:15:40 -0400 (attached) Perry, > > Hugo, do you suppose you could propose appropriate text changes > quickly? > A simple and healthy way to proceed is to have a document specifying the keyed-MD5 independently of IPSEC/IPv6 etc. The Authentication Header draft could directly reference that document, or your draft with Bill could do it. Not only I had insisted in the past with modifications to keyed-MD5, I also had suggested (in particular, echoing Phil Rogaway's clear request) to have documents that define the transforms independently of the protocol that use them (the "rfc-1321 model"). The draft draft-krawczyk-keyed-md5-00.txt can be used for this purpose (or any accepted modification of it). Hugo Date: Thu, 29 Jun 1995 14:09:01 +0800 From: Phil Rogaway To: rivest@theory.lcs.mit.edu Subject: Draft comments Cc: rogaway@cs.ust.hk Hi, Ron, I am very happy you are writing this letter. A few quick comments.` To: Should include "IESG", which is the audience which will decide this matter. 2.8 My comments on the MD5 mechanism were the ones which are out of date: the mechanism has reverted back to MD5(a.x.a), as you correctly note. BTW: There are simple, firmer-foundation versions of MD5-based authentication. My favorite is an "XOR MAC" based on MD5's compression function. It would only take a couple days to write the spec for such a function, but, unfortunately, we still haven't done this. XOR MACs are defined and proven correct (when the compression-function-derived F_a(x) is a PRF) in the CRYPTO '95 paper by Mihir and me. 3.1 The IPSEC guys --Phil Karn in particular-- ARE defining a key distribution protocol. It's called "Photuris". It's a mess. It's defined in draft-karn-photuris-01.txt. Hugo Krawczyk has tried to help straighten this out, but he has had very little success. 3.3 Basically, the authors have failed to define the "trust model" - what type of agents hold what sort of keys. This has already proven to be a problem: on the mailing list for days was discussion relating to attacks where *hosts* H1 and H2 share a key $a$, and bad *human* user E reads the messages of *good* human user A who shares the same host, H1. (Machine M1 is secure, and user E has not broken into it.) a a H1 <----------> H2 . . . . . . E A B Now is this an attack which is supposed to be guarded against? It is impossible to say. The architecture doc, if it does nothing else, should be providing enough of a model and architecture to make it clear if the above is something that the architecture is designed to protect against. Thanks again -- and thanks for referencing me so generously! Phil Date: Thu, 29 Jun 1995 15:39:30 +0800 From: Phil Rogaway To: hugo@watson.ibm.com, perry@imsi.com Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Cc: PAULV@BNR.CA, iesg@cnri.reston.va.us, ipsec@ans.net Dear Perry, I think it is wrong to characterize Hugo as jumping into this at the last minute: Hugo has been trying, unsuccessfully, to get the MAC mechanism straightened out for a very long time. When you say "PLEASE DONT EVER DO THIS AGAIN!" you do Hugo (and the community) an injustice. Your note suggests that the "correct" model is to have the more knowledgeable scientists press less knowledgeable authors to insert bits of language into their documents. This will never work to yield good cryptographic architecture or mechanisms. In this case the entire MD5 MAC document was in need of being redone (e.g. a transform was not even cleanly (use-independently) specified). Your final remark characterizes Hugo's Internet Draft as a "technical correction" (which is unjust) and suggests that there will be ample opportunities to absorb such "corrections" in the future (a prospect I find extremely unlikely). Phil Rogaway Date: Thu, 29 Jun 1995 16:54:48 +0800 From: Phil Rogaway To: ipsec@ans.net Subject: response to Last Call on: IP Authentication using Keyed MD5 Now that it may finally be on the table to do something about draft-ietf-ipsec-ah-md5-03.txt I would like to remind this community that not only should the MAC be defined independent of its intended use, so too should the encryption transform. I did this two months ago (Internet Draft draft-rogaway-cbc-encrypt-00.txt -- the suggested replacement to what is now draft-ietf-ipsec-esp-des-cbc-04.txt). I received 0 (zero) comments on this work, and the revised IPSEC document (draft-ietf-ipsec-esp-des-cbc-04.txt) was non-responsive. This despite the fact that not only is the transform in draft-ietf-ipsec-esp-des-cbc-04.txt intertwined with its use, but its description has at least two major technical errors. These were already pointed out in earlier notes: incorrectly asserting that the mechanism provides integrity, and incorrectly stating that a counter provides as an acceptable IV. Phil Rogaway To: Phil Rogaway Cc: ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Date: Thu, 29 Jun 1995 08:15:33 -0400 From: "Perry E. Metzger" Phil Rogaway writes: > Now that it may finally be on the table to do something about > draft-ietf-ipsec-ah-md5-03.txt > I would like to remind this community that not only > should the MAC be defined independent of > its intended use, so too should the encryption transform. More properly, you should state that it is your opinion that the transforms should be independant of use. > I did this two months ago > (Internet Draft draft-rogaway-cbc-encrypt-00.txt -- the suggested > replacement to what is now draft-ietf-ipsec-esp-des-cbc-04.txt). > I received 0 (zero) comments on this work, Many of us are too tired to comment in detail on every idea that comes forward. I'm still to tired, myself. Hugo has a legitimate point that his method provides more security, so I'm reluctantly seeing if I can lobby to do something about them. Your changes were gratuitous and actually less efficient, so I didn't think of them as being a good idea. > This despite the fact that not only is the transform in > draft-ietf-ipsec-esp-des-cbc-04.txt intertwined with its use, but > its description has at least two major technical errors. These were > already pointed out in earlier notes: incorrectly asserting that the > mechanism provides integrity, and incorrectly stating that a counter > provides as an acceptable IV. "Major technical errors?" I was an author of that document. There is already an explicit reference in the document to the fact that under some circumstances integrity can be breeched... The usual (ICMP, TCP, UDP) transport checksum can detect | this attack, but on its own is not considered cyptographically | strong. In this situation, user or connection oriented integrity | checking is needed [A-AH]. | and the only other reference to the word "integrity" is in the introductory sentence which generically describes goals of ESP and not specific properties of the DES transform. However, I'm sure in this or a later version of the document a single sentence could easily be inserted to note that DES alone can't guarantee integrity. This is hardly the mark of a "major technical error" in the proposal. At worst it's something that we could say more redundantly. I don't see that this would justify holding up the documents, but I'll find out if we could insert a single line to that effect. As for counters, assuming that DES does in fact work as advertised, flipping one bit in the IV should flip, on average, 50% of the output bits. Do you have evidence that this is insufficient for purposes of disguising identical initial blocks, which is all an IV does in life? Perry Date: Fri, 30 Jun 1995 10:16:55 +0800 From: Phil Rogaway To: perry@imsi.com, rogaway@cs.ust.hk Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Cc: ipsec@ans.net > There is already an explicit > reference in the document to the fact that under some circumstances > integrity can be breeched... I'm not sure what you're trying to say, but the introduction of your document, AND the next higher-level document (draft-ietf-ipsec-esp-01.txt), AND the next higher-level document after that (draft-ietf-ipsec-arch-02.txt) ALL maintain that the encryption mechanism provides integrity. Either DES CBC encryption is architecturally non-compliant (and so the mechanism has to be changed), or else all of the above statements about the encryption buying you integrity need to be changed. (I've said this enough times to turn blue....) > As for counters, assuming that DES does in fact work as advertised, > flipping one bit in the IV should flip, on average, 50% of the output > bits. Do you have evidence that this is insufficient for purposes of > disguising identical initial blocks, which is all an IV does in life? Maybe you don't understand the purpose of the IV: properly used in CBC encryption the method achieves semantic security; improperly used, it does not. A one-line proof of this: simply note that if the IV takes on values <0>, <1>, ... then the adversary can distinguish the encryption of message <0> followed by the encryption of message <0> FROM the encryption of message <0> followed by the encryption of message <1>. (Here means the 64-bit encoding of integer i). (Perry - further discussion on these particular issues need not involve the entire mailing list.) Phil To: Phil Rogaway Cc: ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Date: Fri, 30 Jun 1995 10:08:58 -0400 From: "Perry E. Metzger" Phil Rogaway writes: > > There is already an explicit > > reference in the document to the fact that under some circumstances > > integrity can be breeched... > I'm not sure what you're trying to say, but the introduction of your > document, AND the next higher-level document (draft-ietf-ipsec-esp-01.txt), > AND the next higher-level document after that (draft-ietf-ipsec-arch-02.txt) > ALL maintain that the encryption mechanism provides integrity. Phil, do I have to spell it out yet again? ESP *does* potentially provide integrity. Thats why the language is in there. ESP is *not* the "encryption mechanism". The architecture defines it simply as the the way to encapsulate opaque IPSP packets. Thats why the "E" doesn't stand for "encrypton". One is free to define an ESP transform that combines integrity and privacy. Thats why the documents say what they do. > Either DES CBC encryption is architecturally non-compliant (and so > the mechanism has to be changed), or else all of the above > statements about the encryption buying you integrity need to be > changed. There is a third possibility, which I will leave to people's imaginations. > > As for counters, assuming that DES does in fact work as advertised, > > flipping one bit in the IV should flip, on average, 50% of the output > > bits. Do you have evidence that this is insufficient for purposes of > > disguising identical initial blocks, which is all an IV does in life? > Maybe you don't understand the purpose of the IV: properly used in CBC > encryption the method achieves semantic security; improperly used, it > does not. What is "semantic security"? This is a term I have yet to hear in many years of work in the field of cryptography. Doubtless its just my ignorance at play. I always thought that an IV was just a way to assure identical plaintext doesn't turn to identical cyphertext. Silly me. > A one-line proof of this: simply note that if the IV takes > on values <0>, <1>, ... then the adversary can distinguish the encryption of > message <0> followed by the encryption of message <0> FROM the > encryption of message <0> followed by the encryption of message <1>. > (Here means the 64-bit encoding of integer i). What are you talking about here? Pardon me, but I don't understand your "one line proof". > (Perry - further discussion on these particular issues need not involve > the entire mailing list.) Thank you. In the future, feel free to send private mail. Perry Date: Fri, 30 Jun 95 11:47:40 -0400 From: sh00@illini.gte.com To: rivest@theory.lcs.mit.edu Subject: did you read that ? Did you look at the last round of correspondence between Phil Rogaway and Perry Metzger over ipsec ? Here is a part from Perry's last message: > > As for counters, assuming that DES does in fact work as advertised, > > flipping one bit in the IV should flip, on average, 50% of the output > > bits. Do you have evidence that this is insufficient for purposes of > > disguising identical initial blocks, which is all an IV does in life? > Maybe you don't understand the purpose of the IV: properly used in CBC > encryption the method achieves semantic security; improperly used, it > does not. What is "semantic security"? This is a term I have yet to hear in many years of work in the field of cryptography. Doubtless its just my ignorance at play. I always thought that an IV was just a way to assure identical plaintext doesn't turn to identical cyphertext. Silly me. I always thought that "semantic security" is the first term every cryptographer must know. I guess I was mistaken. -- Shai Date: Fri, 30 Jun 95 15:10:28 EDT From: hugo@watson.ibm.com To: ho@cs.arizona.edu Cc: ipsec@ans.net Subject: response to Last Call on: IP Authentication using Keyed MD5 Ref: Your note of Tue, 27 Jun 1995 15:21:54 -0700 (attached) Hillary and all, The draft I posted was intended to have the minimal information needed for implementation of the keyed-MD5 primitive and not to explain the rationale of the choice of this particular mechanism. Explaining this rationale in a consistent and accurate way is not easy. It requires getting into the mathematical details of the analysis. However, I have sketched the ideas in notes to this list in the past. In a separate message I am sending another (more extensive) explanation of these ideas. As for the cited papers: The Preneel-VanOOrschot paper is now available. I've just learned that the RSA Cryptobytes publication is not yet in electronic form (I am told that it will be soon). As for my own paper with Bellare and Canetti [BCK], which is the strongest basis for the analysis I have, it is currently written in a "very mathematical" form, including detailed proofs of the main results. However, it lacks a good "human interface" which may be more useful for most people in this list (e.g., the practical meaning of these results, the difference in approach to previous work, etc.). This will still take a while until done (we are all busy with many other things). However, I may make the proofs available to you or other specifically interested people; let me know if you are interested. In the meantime, the high level description I am sending in the next message will hopefully help to clarify some of these issues. Hugo ----------------------------- Note follows ------------------------------ Date: Tue, 27 Jun 1995 15:21:54 -0700 From: Hilarie Orman To: hugo@watson.ibm.com Cc: ipsec@ans.net In-Reply-To: Yourmessage <199506270121.AA40361@interlock.ans.net> Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 The draft repeats a defect that Van Oorschot noted with respect to draft-ietf-ipsec-ah-md5-03.txt, that it does not address the desired security properties of the transform. I realize that "better than brand X and costs no more" is meant to be a compelling argument, but some reference to absolute criteria would be useful. Why is the padding is changed from 128-bits to 512-bits in the initial key setup? Is this to allow pre-computation? If so, this should be noted so that it is not confused with a security consideration. I cannot find any of the references for the security of the method. I was only able to see a copy of the preprint of Crypto '95 paper for a few minutes and have received no replies to requests for a copy, the URL http://www.rsa.com/rsalabs/cryptobytes/ is non-existent, another reference is a "manuscript". It seems unreasonable to ask the group to make a decision if none of the background material is available to it. To: hugo@watson.ibm.com Cc: ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Date: Fri, 30 Jun 1995 16:33:46 -0400 From: "Perry E. Metzger" It appears that all that is needed to incorporate Hugo's suggestion is a change of a line or two of the MD5 AH draft to specify that the prepended part of the key be padded out with a 1 bit and some number of 0 bits to 512 bits. Am I correct on this, Hugo? Given the simplicity of this change, I'm inclined to see if we can insert it before RFC publication, in spite of the late timing. Again, this depends on what my co-authors say and on general consensus. It would also be nice if Hugo were to post a message explaining the rationale for this in approximate laymans terms. (I'd still like him to write the language to insert but I don't have much hope that he'll do it.) Perry To: rivest@theory.lcs.mit.edu (Ron Rivest) Cc: ipsec@ans.net Subject: Re: Some comments on IPSEC proposals Date: Fri, 30 Jun 1995 17:52:26 -0400 From: "Perry E. Metzger" It appears that by failing to be as vicious as possible about Phil Rogaway's lack of understanding of the architecture of IPSP that I have inspired people to take him seriously. It also appears that Phil has been lobbying people to have them comment. I can understand how even an intelligent reader, going through his comments, could become confused about the architectural issues here. However, let me say that I found his comments to be almost completely without merit. Other than a few comments about places where the text used ambiguous language (i.e. textual ambiguity) I found almost nothing of value in what he had to say. Ron Rivest writes: > I was stimulated in part to provide these comments by Phil Rogaway's note: > > [ROG] Problems with Proposed IP Cryptography > Phil doesn't understand the architecture. > 2.1 "AUTHENTICITY = INTEGRITY" [cf ROG 1.] > > I agree entirely with Phil here; the distinction between message authenticity > and message integrity is vacuous here, and the proposed documents should be > rewritten to use just a single term (message authenticity) for this notion. > (I support Phil's recommendation 1.) This is a serious problem? It's a textual change. > 2.2 "ENCRYPTION DOES NOT GUARANTEE INTEGRITY" [cf ROG 2.] > > Again, Phil is on target here. No he isn't. > The proposed documents have a confused and ambiguous discussion as > to how authenticity is to be achieved. They are completely clear. The problem is that Phil doesn't undstand that "ESP can provide authentication" doesn't mean "ESP provies authentication". As for how it is achieved, that depends on the individual transform. The DES transform, as defined, does *not* provide authentication. Each transform provides authentication and/or privacy in a transform dependant manner. > 2.3. "IT IS WORTHLESS TO ENCRYPT KNOWN HEADERS" [cf ROG 3.] > > Here Phil recommends (his recommendation 3) that the encryption of > known headers should be forbidden, on the grounds that AH, and not ESP, > should be used for authenticity. I agree. > (I support Phil's recommendation 3.) I'm not sure what you mean here. > 2.4 "DON'T ENCRYPT MESSAGE AUTHENTICATION CODES" [cf ROG 4.] > > Although it is not uncommon to encrypt MACs, Phil is exhibiting excellent > taste by suggesting that the scope of the authentication header should > include the encrypted packet, rather than vice versa. While I don't know > of any security weaknesses from the proposed organization, Phil's suggestion > is cleaner and preferable. This is a transform issue, not an architectural issue. Because Phil seemed to have no understanding of how the architecture works, of course... > (I support Phil's recommendation 4.) > > 2.5 "DEFINE TRANSFORMS GENERICALLY" [cf ROG 5.] > > This recommendation is just common sense in support of better modularity > in the description of what is being proposed. > (I support Phil's recommendation 5.) There is no good reason for this and there is lots of reason not to want it. > 2.6 "MANDATE HARDWARE-EFFICIENT *AND* SOFTWARE-EFFICIENT TRANSFORMS"[cf ROG 6 .] > > Efficiency is clearly an important issue when we are talking about > operations that affect potentially every packet on the Internet. > I think that the main point here is that there should be considerable > freedom to choose alternative encryption techniques. And the drafts make it clear that sides are free to negotiate any security transform they wish. What is the issue here? > (I have no problem with Phil's recommendation 6.) > > 2.7 "USE 128-BIT KEYS" [cf ROG 7] > > The key sizes should either be totally arbitrary (perhaps up to some > generous limit, such as 4096 bits), at the user's discretion, or else > be fixed at 128 bits as Phil proposes. Pardon, but as I've noted, this is a transform issue, not an architectural issue, and individual tranforms are free to pick what parameters they want. We are mandating a few baseline transforms for interoperability, but thats it. > 2.8 "THE MAC MECHANISM" [cf ROG 8] Let me point out that the fact that we have modular transforms renders this entire issue fairly unimportant. We can replace transforms as we like. > Keyed-MD5 may be a plausible choice at the current instant, but we should be > prepared for the fact that in the very near future we may see > significantly better alternatives proposed and sufficiently evaluated > to be considered as replacements. And that is why the architecture makes it easy to replace transforms at will. > 2.9 "THE ENCRYPTION MECHANISM" [cf ROG 9] > > Phil suggests that "at this point, it may be irresponsible for any NEW > proposal to specify DES in a mode of operation which is susceptible to > 2**56 complexity key-exhaustion." I agree. The proposal to use triple-DES > in a mode that is potentially compatible with single-DES (due originally, > I believe, to Walt Tuchman), can satisfy those users who want the efficiency > (and security) of single-DES. I wanted to mandate 3DES but the feeling was that it wasn't a good idea for a variety of reasons. A 3DES transform has been defined but is not being made explicitly part of the baseline -- however it is my expectation that vritually everyone is going to implement it. > 3.1 KEY DISTRIBUTION / KEY AGREEMENT > > These proposals are incomplete and essentially unusable without at > least one specific proposal for non-manual key distribution or key > agreement. We understand that. Thats why we are working on a key distribution proposal. We aren't stupid. It looks like Photuris, which is a variant on the Diffie-Hellman based STS protocol, is going to be used. > I think that the current proposals should be held in abeyance (and worked on) > until a complete package including key distribution and/or key agreement > is also ready for consideration; I see little harm, and much potential > good, in doing so. I see enormous harm. The current proposals do us a lot of good RIGHT NOW. There are dozens of manufacturers preparing to unleash incompatible versions of this same thing on the world. The IPSEC working group has delayed its output for years already -- there is no reason not to move forward to draft right now. > 3.2 LACK OF SPECIFICITY OR CLARITY > > There are many places where the proposals are insufficiently clear about > what is intended, so much so that an implementor can not proceed. Here > is a small list of items I noticed. (This is not intended to be comprehensive .) > [SA] > p 6: "SHOULD let that SPI become stale..." > (when is an SPI stale?) After sufficient time has elapsed for it to be reasonable that the counterparty would not attempt to reuse the value. It is hard to set a time value on this in stone because it is dependant on too many things that will change with time and technology. There are plenty of similar magic values in the TCP documents and we've survived it. > [AH] > (page 6) It is recommended here and in other > places [e.g. AHMD p. 1] to use "pseudo-random" values > (here for the SPI, Actually, the SPI is an *arbitrary* value, not a randomly generated number. The rest of the document makes this clear. in AHMD for the authentication key). > How is a user to pick a "pseudo-random" value? Security considerations makes it clear that the authentication key must selected as any other key is selected -- i.e. it can't be guessable and otherwise can be selected by some random process. We don't specify a process because that is up to the key management system, which might assign it using Diffie-Hellman, a voting mechanism, selection based on a key generator box on one of the machines, etc. > Are > counters suitable for the SPI? Is a linear-congruential generator > suitable? ANY mechanism is suitable. The documents make this clear. Some implementations may wish to assign them in a way that makes hashing efficient. Some may wish to assign them with a counter. Some may wish to assign them by counting upwards by the value of the national debt of Vanuatu modulo the phase of the moon. It makes no difference. > (page 7-8) "This requirement is placed in order to allow for > future IP optional headers which the receiver might not know about > but the sender necessarily knows about if it is including such > options in the packet." (I have no idea what this means.) You removed the context. " The sender MUST compute the authentication over the packet as that packet will appear at the receiver." The construction is awkward but makes it clear that you do the authentication over the packet as it will look when the receiver gets it, excluding things that will be stripped along the way. > [AHMD] > [ESP] > (page 6) "If strict red/black separation is being enforced..." > (This term needs a reference or a definition.) Its a DOD term of art. > (page 7) "If no key exists for this session or the attempt to > decrypt fails," > It is not clear what it means for the decryption to fail. ESP doesn't just mean "privacy", it can also mean "authentication". Also, there are checksums in the underlying packet, like IP layer checksums, that can fail. > The authors seem to imply that the it means that the next > layer of protocol has a problem with the decrypted text, which > is, in my opinion, a poor choice. What is your alternative? > I think that the only reason > decryption should "fail" is that decryption is impossible > (e.g. the ciphertext is not a multiple of the cipher block > size). Authentication failure should be used to detect all > other problems. This is a matter of pragmatism. In practice, there often won't be any other way to detect the problem. > (page 8) If user-oriented keying is not in use..." > This paragraph makes no sense to me. It should be elaborated. > What is the attack that is being prevented here? Bellovin's attack, among others. > [ESPDES] > (page 3) "The session key SHOULD be changed at least as frequently > as every 2**32 datagrams." > What is the justification for this condition? What attack > is being prevented here? Attacks. 1)IV replication and 2) attacks based on excessive use of the key. Its a SHOULD, not a MUST. > (page 3) "This field is considered to be transparent, though most > users will not be able to make sense of its contents." > This sentence pretends to be transparent, but this reader could > not make sense of its contents. Do you grok the Transparent/Opaque boundary in the datagram? The IV is an arbitrary number and thus has no meaning, but it is in the transparent part of the datagram, not the opaque part. > 3.3 HOST-ORIENTED vs USER-ORIENTED KEYING > > In [SA, section 4.4] it is stated that "support for user-oriented keying > SHOULD be present in all IP implementations". > > Since "users" as such are not named principals at the IP protocol level, > we are getting into strange territory here. This has been discussed in detail. Please read the extremely extensive archives and IETF proceedings. > It is not clear what "support for user-oriented keying" means. Does > this merely mean that each user can be associated with a separate SPI, > or does it mean that the host system must support secure multi-user > processing somehow (e.g., so one user can not read another user's key > by probing memory addresses assigned to the other user)? Neither. It really means that there has to be support to allow use of different keys for different TCP or UDP sessions in process between two hosts. The reason is to allow users to avoid sharing keys. There are attacks, due to Bellovin, among others, if two mutually hostile users are sharing a key that they do not know. > The entire discussion on user-oriented keying seems confused (or at least > confusing). This capability ought to be more carefully described, or > dropped. I'm tempted to recommend just dropping it. Perhaps that is because you are stepping in to the middle of a discussion that lasted for a very long time (over a year) without having carefully read all the rationale behind all the components of the design. > More broadly, these documents need to have a clearer philosophical position > as to what their goals are. In particular, these documents should make it > clear how what they are doing differs from security protocols that work > at higher layers of the protocol stack. It would seem sensible to think > that a protocol at this IP layer should ONLY worry about security between > hosts, and let protocols at higher layers take care of security between > end-users or their applications. That isn't the goal. > Bringing in users and userids to this protocol risks great confusion > and muddled systems. Users and userids are NOT in this protocol. The requirement is much simpler than that and has several good justifications. > 3.4 USE OF MD5 > > The language in [AH, section 4] says "If a block-oriented authentication > algorithm (e.g. MD5 or MD4) is in use and the IP packet is not an integral > number of blocks, the authentication data calculation is performed using > zero bytes at the end to pad the length out to an integral number of blocks > [Riv92]." > > This is VERY confused, since MD5 (and MD4) are byte-oriented algorithms > that are specified to normally take variable-length byte-strings as input. > It is not necessary (and may even be dangerous) for the user to supply his > own padding! The examples were perhaps bad, but MACs in the general case may be block oriented. > 3.5 AUDIT LOGS > > In [AH, page 9] and other places, it is stated that the system "MUST > record the authentication failure in the system log or audit log." > > Given the rate at which bad packets can be delivered to a system by a > malicious adversary, it may not be too hard for the adversary to fill > up the disk of a complying implementation with the audit log. I think > the "MUST" should be downgraded to "SHOULD". The requirement is prehaps inapropriate. > 4. CONCLUSIONS > > I feel that the proposed protocols are not sufficiently worked out to > allow proceedings with them as a proposed standard. 1) We are attempting to proceed with them as a draft standard. 2) a proposed or draft standard is not a standard. Perry From: smb@research.att.com To: rivest@theory.lcs.mit.edu (Ron Rivest) Subject: Re: Some comments on IPSEC proposals Date: Fri, 30 Jun 95 18:54:15 EDT 3.3 HOST-ORIENTED vs USER-ORIENTED KEYING In [SA, section 4.4] it is stated that "support for user-oriented keying SHOULD be present in all IP implementations". Since "users" as such are not named principals at the IP protocol level, we are getting into strange territory here. It is not clear what "support for user-oriented keying" means. Does this merely mean that each user can be associated with a separate SPI, or does it mean that the host system must support secure multi-user processing somehow (e.g., so one user can not read another user's key by probing memory addresses assigned to the other user)? If I send encrypted traffice to an SPI that is associated with a particular user, what am I guaranteed about the security of that traffic from other users on the same host as the receiver? If nothing is guaranteed, why have this feature? The entire discussion on user-oriented keying seems confused (or at least confusing). This capability ought to be more carefully described, or dropped. I'm tempted to recommend just dropping it. Without going into any of your other points, this one is specifically designed to counter an attack I found a few months ago. There are a few slides in ftp://ftp.research.att.com/dist/smb/hostpair.ps that might be useful; the net, though, is that if mutually hostile users share the same key, confidentiality can often be breached by replay or cut-and-paste attacks. The former threat is by reuse of the port number later in time; the latter by taking advantage of CBC mode's self-healing properties. There are a bunch of email messages in the archives discussing this, but much of the discussion took place at the last IETF meeting in April (which is when I came up with the attack). --Steve Bellovin Date: Sun, 2 Jul 95 18:16:40 GMT From: "William Allen Simpson" To: ietf@CNRI.Reston.VA.US Subject: Re: Last Call: IPSEC drafts -> Proposed Standards (In the hope that the ietf list mail loop is now fixed, and eliminating IESG and IPSEC since relevant persons are already members of this list.) Gentlefolk, Thank you for your kind remarks. However, other comments were not appropriate to this process. Many are directed at a different community. This is a protocol design, not a critical analysis or mathematical thesis. As a protocol design, only those elements are included which are needed to define interoperable packet formats and resulting implementations. It is intended to be much easier for implementors to read the protocol specification than a mathematical treatise. It is not appropriate for our community to reference unpublished material. Indeed, it would be quite surprising if a draft most recently updated in April would have had the prescience to reference material from conferences in May. My usual practice is not to include material less than a year old, awaiting peer review. Surely other forums will provide plenty of publication opportunity for many future competing analyses in a variety of formats. It would have been more helpful if comments had not been based on a third party's comments, instead of the drafts themselves. Actually having _read_ the most recent drafts would have lent credibility. I agree that certain concepts could be described more clearly or be better organized. I attempted this in _my_ series of alternate drafts. However, the "powers that be" chose other drafts, which are adequate to provide the basis for a "Proposed Standard", and will be updated in the future. If you have better ideas, contribute the wording or write competing drafts of your own! Keyed hashing functions are _not_ a new concept for authenticity and integrity. They have been used for decades in such media as databases, ATM cards, and as long ago as telegraphy. The reference to a recent paper as their basis was completely laughable. Commercial vendors have been using them since the '70s. The IETF has widely deployed keyed MD2, MD4 and MD5 since '92 in PPP and SNMP, and the initial design drafts are several years older. The repeated plaint is that more time is needed to further analyse the protocols, or that the protocols need more layering in order that futher analysis would be simplified. I refer these persons to the "Perfect Security" Research Group of the IRTF, who have been so successful at completing work in the area. This is the IETF, with emphasis on the E. The specific criticisms of MD5 in particular are that certain known (or possibly only chosen) texts may match in 2**64 tries. No other attack has been found, although some have been hypothesized. Do we need to discuss how _big_ a number 2**64 is yet again? I take personal affront that most of those posting say their ideas have been "ignored". I have over 250K of private messages with these persons, and 3 MB of the WG list -- this year alone! I specifically refer Mr. Rogaway to my private message to him of April 30, 1995 regarding his posting, which was also sent to the IESG. Finally, these armchair "experts" are requested to apply their efforts to actual cryptanalysis. These protocols have been deployed and running for over 2 years. Please come back when you have successfully intercepted and cracked the daily traffic between Phil Karn's home and office, and periodic traffic between me and my clients. Bill.Simpson@um.cc.umich.edu Key fingerprint = 2E 07 23 03 C5 62 70 D3 59 B1 4F 5E 1D C2 C1 A2 Date: Sun, 2 Jul 1995 12:35:07 +0800 From: Phil Rogaway To: rivest@theory.lcs.mit.edu Subject: Re: Phil-the-snake Hi Ron, I did rewrite one of the drafts completely: the one on cbc-encryption. That's what Paul Lambert (the apparently powerless co-chair) advised me to do when I told him that I felt the drafts needed to be rewritten, not just have some editing here and there. But nothing happened; the official draft didn't change, and there was no discussion of switching to the new draft. Maybe instead of posting this out as a new (alternative) Internet Draft I should have sent the text to the editors. This way they could have adopted the new draft while leaving their own names on top. Just a couple days ago Hugo has done the same thing (ie. write a counter-proposal) for the MD5 MAC document. I think Hugo will have better luck, mainly becuase he is changing the mechanism to something close but more secure. Hugo has also been more politically astute, being careful not to come across as too critical of the organization's work. Phil