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

re:MD5 for authentication article in RSA's "CryptoBytes"

Ref:  Your note of Wed, 5 Jul 1995 15:05:00 -0400 (attached)

Paul,

What are you concluding from your remarks below?
If you see that as an indication that the functions proposed in
[kaliski95] are weak I disagree. (Not that I am claiming that these
functions must be good, but, in my opinion, your arguments below show
no real weaknesses of these schemes).
More details below:

 >
 > In message "MD5 for authentication article in RSA's "CryptoBytes"",
 > 'perry@imsi.com' writes:
 >
 > >There is a new RSADSI newsletter called "CryptoBytes". One of their
 > >articles in the fist issue is about use of MD5 for authentication.
 > >
 > >Perry
 >
 > Note there is a comment related to this in [crypto95],
 > at the end of section 4.3:
 >
 >    Three MD5-based MAC proposals for the IPSEC
 >    working group are made in [kaliski95]:
 >    one is the envelope method with
 >    $K_1=K_2$ and $k_1=128$ ($K_1$ is padded to a complete block),
 >    the other two are
 >    $MAC(x) = h( K_1  || h( K_2  || x))$ and
 >    $MAC(x) = h( K_1  || h( K_1  || x))$.
 >    It is suggested that the best known attack on
 >    these schemes requires $2^{64}$ chosen messages;
 >    however, Proposition 4 shows that $2^{56.5}$ known text-MAC
 >    pairs are sufficient (if $s=2^{16}$).

As I already explained in past notes when the appended key in the envelope
method is not padded but mixed with data, the attack is *strictly speaking*
a *chosen* message attack. Moreover, I would not call an attack assuming
common trailing blocks in the queried messages a *known* message attack.

This is mainly a semantical issue with not much contents in the case
of 128-bit output functions as MD5. Indeed, when I communicated this
attack to Kaliski and Robshaw (the authors in [kaliski95]),
I saw little value in making the precise distinction in the chosen vs
semi-chosen vs known-message attacks (there is even place for a "semi-known"
category here) when in any case:

       * all of these attacks *require* to be applicable to maintain *
       * the *same* key for MAC-ing 2^73 bits of information !!!     *

This is true also in the $2^{56.5}$ attack (that in addition requires
4Mb of common trailing information in all queried messages).

The attacks are unrealistic anyway. Moreover, they do not imply by
themselves any further weaknesses of these constructions.
These attacks are applicable to any of the proposed constructions
even if you use a perfectly random compression function!

(Things are *very* different when you move from 2^64 to 2^32 as is the case
of DES-MAC-CBC)

 >    Also, the second scheme is vulnerable to the
 >    divide and conquer attack described above.

That is true. But what is the conclusion?. In any case no one is claiming
an effective key length of more than 128 bits. Notice that [kaliski95]
explicitly says that these two keys could be derived from a single 128-bit key.

Hugo

 >
 > [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).
 >    {ftp: ftp.esat.kuleuven.ac.be, directory pub/COSIC/preneel}
 >
 > [kaliski95] B. Kaliski, M. Robshaw, ``Message authentication with MD5,''
 >    CryptoBytes (RSA Laboratories Technical Newsletter),
 >    Vol.1, No.1, Spring 1995, pp.5--8.
 >
 >
 > Paul Van Oorschot.
 >
 >