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

IP Authentication using Keyed MD5 / The ESP DES-CBC Transform



Ref:  Your note of Mon, 3 Jul 1995 18:53:13 +0200

I agree with most of Bart Preneel's comments (some clarifications
are brought below). In particular, I do not see any significant
conflict between what Bart says and what I have written in my draft
and companion notes.
My conclusions are the same as I already presented ("Never underestimate
the power of repetition" says an old proverb...), namely:

The key-pad-text-key mode of keyed-MD5 in draft-krawczyk-keyed-md5-txt.00
is the result of adapting the analytical work of BCK to the constraints:

1) do not modify MD5 code
2) do not slow down MD5 performance
3) keep simple keying rules

The relaxation of any of these constraints can produce a more secure
proposal in the sense of better matching the BCK analysis and/or having
potentially better heuristic security.

It is up to this WG to decide whether this is desirable or not.
(Please speak up!). I, as a cryptographer, will always support
going to the (plausibly) more secure solutions. However, in this WG
the system and performance considerations are of prime importance
and trade-offs and compromise are behind any decision made.

Again, as said several times, we will eventually need a faster transform,
and more secure transforms. The work many of us are carrying in analysis
and design of these transforms will hopefully bring a better solution.
But, in any case, the choice of an interim default for the authentication
transform cannot wait until we have enough confidence in new solutions.

I want to make one point that was not mentioned before but is significant
If you use an encryption function that is broken 5 years from now,
any adversary that recorded today's traffic will be able to read
your information then (of course, it depends on the kind of information
the attacker gathered and the nature of the encryption breaking).
However, an authentication function which is broken in the future
has no implication on the security of past traffic. This consideration
makes it easier to go towards some system/security trade-offs
for the authentication function in spite of potential weaknesses.
Of course, one shouldn't gratuitly sacrifice security, and most
importantly one has to be ready to replace the authentication function
as soon significant evidence against the security of the transform is
found. This is why modularity and support (upon negotiation) of
alternative functions is of prime importance for the proposed standard.

I believe that the keyed-MD5 function specified in the current drafts
will be replaced *before* this becomes a final standard. The only
reason for my draft is to "optimize" the choice from the security
point of view without paying any additional price in performance,
complexity, etc.

Here is a list of possible improvements depending on how much of
the above constraints are relaxed:

* With a minimal complexity addition to keying: have "independent"
  prepended and appended keys (i.e., K1, pad, text, K2, where K1 and
  K2 may be derived from a common 128-bit key using standard techniques)

* A minimal change in MD5 code: do not use prepend and/or append keys
  to text but rather use the keys to replace the fixed MD5 IV (key-ed
  IV approach). Define the function to be: MD5_K1(MD5_K2(text))
  (which was my original preferred proposal).
  Note: MD5_K stands for MD5 with IV=K.

* If some slow-down of MD5 is accceptable (and somewhat more complex
  change to MD5 code) then the Preneel-Van Oorschot recommendation
  of keying the MD5 rounds can be incorporated.

And when we'll eventually come with better performance/security
transforms we'll replace any of the above.

Note: One change that will not pay with any system penalty (actually, has
some bandwidth advantage) and applies to any of the avove variants
is to reduce the size of the MAC output as Bart proposes.
I do not see right now a conflict of that choice with our analysis,
however, I have not personally given much thought to this issue.

Appended are some direct comments on Bart's note. (In what follows
Bart's note is indented and incomplete)
 > ======================================================================

 > Some comments on Keyed-MD5 for Message Authentication
 > and on the ESP DES-CBC Transform
 >
 > Bart Preneel
 >
 > THE PSEUDO-RANDOMNESS ASSUMPTION
 >
 > A first remark is that while the collision resistance of MD4 and
 > MD5 has been analyzed, no one has ever published any results regarding
 > an evaluation to verify whether MD5# is actually a pseudo-random function.
 > Both properties (collision resistance of MD5 and pseudo-randomness of
 > MD5#) are independent, i.e., either of them can be present without the
 > other one. A related observation has been made in [Roe et al.].

Bart is absolutely correct here. Unfortunately, all of the work on
iterated one-way hash function from design to  further
cryptanalytical work concentrated solely in the (known-IV) collision
resistance aspect. As I pointed out in my sketch this is
an aspect which does not follow from a function being a good MAC neither
guarantees the quality of MAC. In order to be able to analyze these
functions as a MAC one needs to gain a better understanding of
necessary and sufficient conditions of a compression function to
produce a good MAC. BCK and PV are a first step in this direction.
(And definitely not the final one!)

 >
 > Second, weaknesses have been found in the compression function of
 > MD5, and recent work on MD4 [Vaudenay] and RIPEMD [Dobbertin] suggests
 > that the internal structure of these hash functions could be used to
 > find collisions faster than by a brute force birthday attack
 > (2^{64} operations).  It is not clear what the implications of this
 > are on the pseudo-randomness of MD5#, but it seems quite plausible that
 > the internal structure of these functions can be exploited in an attack
 > as well.
 >
 > Note that in [Krawczyk2] it is stated that "everybody uses these functions
A minor correction: I didn't say that "evrybody uses", though I said
it is used "everywhere" (quotes included) to mean that is quite common
to find that use of these functions these days.

 > [MD5, SHA] to generate (pseudo) random keys": while it is true that this
 > is based on the pseudo-randomness of MD5#, it should be noted that when
 > MD5 is used for key derivation, an attacker has much less input-output
 > pairs available, which makes statistical attacks infeasible.

In reality, our analysis shows that the significant parameter for the
pseudorandomness quality of the compression function depends on
information gained by an adversary by quering the function only once
(on average).

 >
 > In view of the above it would appear more secure (or at least prudent) to
 > key not only the beginning and the end of the hashing process, but also the
 > compression function as done in MD5-MAC. In this way, the MAC is more
 > robust against weaknesses of the underlying hash function. By keeping
 > the modification as simple as possible, it is highly unlikely that new
 > vulnerabilities are introduced. While both the scheme proposed by
 > Krawczyk and MD5-MAC use a key as IV, the introduction of a secret key
 > in the compression function is a major difference between both schemes.

I have no idea how to qualify/quantify  this "major difference",
but as I said I will support that change, if the slow down it carries
is accepted by the WG.

 >
 > CBC-MAC
 >
 > In [Roe et al.], it is proposed to make DES based CBC-MAC the default algorithm.
 > We do not support this proposal for the following reasons:

I agree with Bart. Attacks in the order of 2^32 messages are not
acceptable for a general purpose MAC (which will be used in many
differennt scenarios). Moreover, I want to make clear a point
which is a fundamental conclusion of the Birthday attacks on MAC:
even going to triple-DES will not improve against these attacks
as far as the output is (as in CBC-DES) 64 bits!!

Hugo