[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