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

Re: Fwd: Use of Keyed MD5



Dear Ran --

Following are some comments on the attached note, per Russ Housley's 
request. Please copy me on any reply, as I am not on the ipsec list.

     Folks,
     
     It is NOT accurate to state that a "vulnerability" was discussed
     by the Security Directorate.  I mentioned that Russ Housely had sent me an 
     email expressing concern about the use of MD5, nothing more. To my 
     knowledge (and I have mostly been in the loop), there is no known 
     vulnerability.  It is true that MD5 was designed as a message digest 
     function and not for cryptographic authentication in the manner becoming 
     commonplace within the IETF.  I believe that an Informational RFC on the 
     use of keyed MD5 for authentication is
     a good idea and I think one is likely to appear.
     
     The only statements I've seen have been of the form that
     
     (1) if no length field is present at a fixed location,
     then appending attacks might be possible
     (Both IPv4 and IPv6 have length fields in fixed locations)
     
Agreed.
     
     (2) use of prepend-only might not be not desirable with IP because,
     in the words of Eric Rains, "This has the effect that a large block of bits 
     at the beginning of the data fed to the digester [i.e. algorithm] will 
     likely be the same for every packet involved in a communication, with the 
     exception of the payload length."
     
Good point, but note that a weakness in MD5 found this way --- say two messages 
with the same digest, starting with the same bits --- would imply a weakness in 
MD5 without the special conditions just noted. So, if MD5 is strong, including 
common bits at the beginning of a message shouldn't affect security.
     
     However, this is not a problem as long as we believe that it is not 
     computationally feasible to invert the particular algorithm (in our case 
     MD5) and determine the secret key.  I am not aware
     of any work that would lead us to believe that it is computationally 
     feasible to invert MD5.  Further, the work of Joe Touch indicates that MD5 
     might be hard to parallelise, so the existence of systems such as the 
     Connection Machine are less of a factor wrt computational feasibility.
     
     (3) Both prepending and appending the secret key significantly
     increases the entropy of the result of the hash.  It can also be 
     significantly more expensive to compute the hash because one
     cannot cache the appended computation.  Prepended keys can enable a system 
     to precompute (once) the initial part of the computation and thereby 
     possibly speed up the processing of packets.  Given the experimental 
     evidence from Hilarie Orman, this is a serious issue to consider.
     
I'm not sure I agree with either part of this point, though I'm open to 
correction. The entropy (uncertainty) of the hash depends only on the number of 
secret bits. The number of secret bits is the same whether the key is appended, 
prepended or both.

As far as speed, I would not expect any precomputation to be possible, unless 
the key is 512 bits or longer, since MD5 processes in 512-bit blocks.

Another approach is to hash the message first, and then hash the concatenation 
of the hash and the key. This avoids the need for any special structure in the 
message, and is only a little more work than the other proposals.

Keep in mind that MD5 wasn't designed with message authentication in mind, so 
all of these approaches need to be examined very carefully. (As opposed to 
digital signatures, where one can assume prima facie that MD5 is suitable for 
hashing a message before a private-key operation is applied.)

I believe this is the ENTIRE dataset on this matter.  If people have specific 
     detailed comments, suggestions, or data that they are willing to backup on 
     this list, then please present it so that the group can consider it.
     
     Best Regards,
     
     Ran
     atkinson@itd.nrl.navy.mil

-- Burt Kaliski
RSA Laboratories