Subject: Re: Logical inconsistencies in draft-ietf-dnsext-tsig-md5-deprecated-00.txt

From: Francis Dupont <[email-masked]>
Date: Mon, 07 Jul 2008 17:23:05 +0200

In your previous mail you wrote:

   Greetings again. The logic in this document is kind of a mess.

=> I understand the situation is very frustrating for a cryptographer...

   It says, in essence:
   
   a) MD5 turns out to be weaker than expected for a hash
   
=> note the consequences are important, not this fact by itself.

   b) therefore it should be deprecated and HMAC-SHA1 be mandatory
   
=> HMAC-SHA1 and HMAC-SHA256 are already mandatory (cf RFC 4635).

   The first statement is certainly true, but irrelevant, because TSIG 
   uses HMAC-MD5, not MD5. As the draft admits, there are no known 
   attacks on HMAC-MD5. To the best of my knowledge, there have been no 
   papers published even hinting at it.
   
=> I fully agree, this is why the draft explains the real reason of
the deprecation of HMAC-MD5 is not a security issue but an operational
issue which is based on a not-yet-proved assumption about HMAC-MD5
weakness. So a) doesn't imply b) but the consequences of a), even
not well-founded, imply the first part of b).

   The second statement is short-sighted. The document talks about the 
   desire to have algorithms that can be used in systems that are 
   validated with FIPS 140 for NIST in the US.

=> yes, there are some environments where you have no choice about
what the crypto module includes. You can believe it is limited, etc,
but when it is in the regulations you must apply the term "no choice"
has a real meaning.

   However, NIST has already 
   said that SHA-1 will be deprecated in about 2.5 years; see 
   <http://csrc.nist.gov/groups/ST/hash/statement.html>.

=> I prefer <http://csrc.nist.gov/groups/ST/hash/policy.html>
which is clearer about the use.

   So making SHA-1 mandatory based on wanting to use FIPS algorithms
   is also not a good idea.

=> s/making/keeping/. There is a good reason to keep SHA-1 is the
mandatory to support algorithms: I am afraid many old implementations
propose only MD5 and SHA-1, so to deprecate both HMAC-MD5 and HMAC-SHA1
should lead to more operational issues than to do nothing.

   Getting rid of TSIG-HMAC-MD5 for NIST-related reasons would 
   also require us to get rid of TSIG-HMAC-SHA1, either now or in 2.5 
   years from now.
   
=> I've tried to get more years but making HMAC-SHA256 recommended.
Note:
 - this is new as no algorithm was recommended before.
 - it is not based on cryptography because as far as I know nobody
 has a recognized argument showing that HMAC-SHA256 is stronger than
 HMAC-SHA1.
But I agree in the long term HMAC-SHA1 should be deprecated too...

   If the only reason for this draft to exist is to deprecate 
   TSIG-HMAC-MD5, then it seems like vast overkill. Instead, a better 
   idea is a simple one-page draft that takes TSIG-HMAC-MD5 from 
   mandatory to optional. That draft doesn't need any questionable 
   cryptography or discussion of NIST.
   
=> in the previous version in the RFC 4635 table HMAC-MD5 was moved
from mandatory to optional but a comment asked to move it to
deprecated. BTW the only defined requirement levels are "mandatory"
(MUST implement) and "not mandatory" (MAY implement), so it is just
a matter of choice of words...

If we come back to the draft in the 4 sub targets:
 - 1 is about IANA registry;
 - 2 is exactly what we are talking: move HMAC-MD5 to not mandatory;
 - 3 is about TKEY and as it uses directly MD5 for keying material
  derivation I believe you should agree SHA-256 is a better choice;
 - 4 is the (new) recommendation for HMAC-SHA256.
Is something wrong here?

Regards

[email-masked]

PS: my own target is to provide a DNS tool implementing TSIG, TKEY, etc,
which both uses a FIPS 140-2 crypto module in the FIPS mode, and is
"RFC compliant". Today it is not possible because HMAC-MD5 is mandatory
to support and TKEY specs written last century...

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 7 Jul 2008 11:57:53 -0700

At 5:23 PM +0200 7/7/08, Francis Dupont wrote:
>weakness.

Not only has a weakness in HMAC-MD5 not been proven, *it hasn't even 
been proposed*, at least in the cryptographic literature I have seen. 
I may have missed it, of course. Please note that the HMAC 
construction has been studied and written about extensively. If it 
was weak for hashes that have weakened collision resistance, that 
would probably be noted by now.

>deprecated.

I don't see that in RFC 4635. I only see it as mandatory. Could you 
quote the section you are referring to?

>BTW the only defined requirement levels are "mandatory"

It is probably inappropriate to change the terminology when updating 
a document. The term "not mandatory" does not appear in RFC 4635.

Further, if you mean to say "not mandatory" in your draft, why do you 
instead say:

              | Deprecated        | HMAC-MD5.SIG-ALG.REG.INT |

>  - 1 is about IANA registry;

Yes.

>  - 2 is exactly what we are talking: move HMAC-MD5 to not mandatory;

Then say that.

>   derivation I believe you should agree SHA-256 is a better choice;

Please don't put words in my mouth. I don't agree that SHA-256 is 
better than MD5 for TKEY keying material. What attack do you see with 
MD5 for keying material in TKEY.

>  - 4 is the (new) recommendation for HMAC-SHA256.

Fine.

>to support and TKEY specs written last century...

So, your crypto module in FIPS mode will not be "RFC compliant": so 
what? There are lots of examples of IETF protocols that have that 
property; IKEv1 comes to mind. Your entire app can be RFC compliant 
and still have a crypto module that can be FIPS validated.

--Paul Hoffman, Director
--VPN Consortium

---

From: Florian Weimer <[email-masked]>
Date: Tue, 08 Jul 2008 13:06:44 +0200

> been proposed*, at least in the cryptographic literature I have

HMAC-MD5 is technically broken because MD5 is broken.  In addition to
that, there are somewhat plausible attack scenarios involving chosen
plaintexts in the DNS context, and the "evil twins" nature of the
current MD5 attacks[1] is probably not an obstacle in this
application.

I don't know why anyone hasn't published anything on HMAC-MD5.
Perhaps because it's rather obvious that chosen-plaintext attacks can
be successful.  On the other hand, Wang et al.'s work doesn't give any
insight into how to recover the underlying key.

[1] I think there are even better attacks now which move away from the
  "evil twins" concept, involving exchanged randomly-looking garbage
  blocks in a different part of the message which compensate for an
  arbitrary edit in some other part (where both versions are
  meaningful and not high-entropy gibberish).
-- 
Florian Weimer                <[email-masked]>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstraße 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 8 Jul 2008 08:07:15 -0700

At 1:06 PM +0200 7/8/08, Florian Weimer wrote:
>HMAC-MD5 is technically broken because MD5 is broken.

Please define what you mean by "technically". The well-received 
paper, <http://eprint.iacr.org/2006/043> seems to disagree with this 
statement

>I don't know why anyone hasn't published anything on HMAC-MD5.

That is simply untrue. The article above explicitly talks about HMAC-MD5.

--Paul Hoffman, Director
--VPN Consortium

---

From: Florian Weimer <[email-masked]>
Date: Tue, 08 Jul 2008 17:25:46 +0200

* Paul Hoffman:

> Please define what you mean by "technically". The well-received paper,
> <http://eprint.iacr.org/2006/043> seems to disagree with this
> statement

The problem is that the traditional threat model for MACs simply does
not consider chosen-plaintext attacks.

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 8 Jul 2008 12:39:10 -0700

>not consider chosen-plaintext attacks.

If you thing that is a problem with the paper in question, you should 
take that to the author of the paper. It is a well-received paper by 
a leader in the crypto community. Given the construction of HMACs, 
and the conclusion of the paper that the collision-resistance of the 
underlying hash function is actually not needed for the security 
proof, asserting that chosen-plaintext attacks are somehow relevant 
would certainly need a fair amount of supporting evidence.

--Paul Hoffman, Director
--VPN Consortium

---

From: Francis Dupont <[email-masked]>
Date: Wed, 09 Jul 2008 00:02:41 +0200

=> in the cryptographic literature proposed == proved (or it is not
good cryptographic literature). I think we agree.

   >from mandatory to optional but a comment asked to move it to
   
=> in the previon version of the I-D (published with my name before
it became a WG item).

=> draft-dupont-dnsext-tsig-md5-deprecated-00.txt should be still
available in the I-D repository.

   
=> the RFC 4635 doesn't define the requirement levels, again
a comment asked to fix this.

   
=> I am open to any idea as soon as there is a consensus about it.

   Yes.

   Then say that.

   
=> I can see two issues, one operational (MD5 has to be available),
one mixed operational/security (a hash producing more bits works better
with longer keys). BTW there is no cryptographic analysis of the
derivation formula, it just seems to totally stupid...

   Fine.

   what?

=> it is not "mine" crypto module but mine application using a third
party crypto module. Perhaps I am influenced by the "Graceful Avoidance
of of non-FIPS Algorithms" of
http://www.openssl.org/docs/fips/UserGuide-1.1.1.pdf (:-)?
   
Regards

---

From: Francis Dupont <[email-masked]>
Date: Wed, 09 Jul 2008 14:07:13 +0200

The well-received paper, <http://eprint.iacr.org/2006/043>

=> if you think it should be a good idea to add a reference to this paper,
just ask. IMHO we should avoid the I-D be used to FUD HMAC-MD5, and
further HMAC-SHA1...

Thanks

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 9 Jul 2008 07:09:49 -0700

>just ask. IMHO we should avoid the I-D be used to FUD HMAC-MD5, and

There is no need to reference the paper if we don't try to pretend 
that HMAC-MD5 has any actual problems.

--Paul Hoffman, Director
--VPN Consortium

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 9 Jul 2008 09:56:38 -0700

The following is a proposed rewording. This is the proposal for the 
*entire* document. Note the title and document name are changed to 
correctly reflect the content.

--Pal Hoffman

         Status Change for HMAC-MD5 in DNS TSIG Resource Records
            draft-ietf-dnsext-tsig-hmac-md5-optional-00.txt

Abstract

    This document changes the status of the use of HMAC-MD5 as
    an algorithm for the TSIG (secret key transaction authentication)
    resource record in the DNS (domain name system) from mandatory
    to optional.

1.  Introduction

    The secret key transaction authentication for DNS (TSIG, [RFC2845])
    was defined with the HMAC-MD5 [RFC2104] cryptographic algorithm.
    [RFC4635] defines new TSIG algorithms based on the HMACs using
    the SHA family of hash algorithms.

    This document changes the requirements status of HMAC-MD5 from
    mandatory to optional.

2.  Requirments Status

     RFC 4635 has the requirements statuses listed as:

       Mandatory      HMAC-MD5.SIG-ALG.REG.INT
       Optional       gss-tsig
       Mandatory      hmac-sha1
       Optional       hmac-sha224
       Mandatory      hmac-sha256
       Optional       hamc-sha384
       Optional       hmac-sha512

     Upon adoption of this document, those statuses change to:

       Optional       HMAC-MD5.SIG-ALG.REG.INT
       Optional       gss-tsig
       Mandatory      hmac-sha1
       Optional       hmac-sha224
       Mandatory      hmac-sha256
       Optional       hamc-sha384
       Optional       hmac-sha512

3.  Security Considerations

    The HMAC-MD5 algorithm protects the secret key with 128 bits of
    effective strength. Environments that need more than this level
    of security, or where the HMAC-MD5 algorithm is not allowed, can
    use the HMAC-SHA1 or HMAC-SHA256 algorithms, both of which are
    mandatory to implement for this specification.

8.  References

8.1.  Normative References

    [RFC2845]  Vixie, P., Gudmundsson, O., Eastlake, D., and B.
               Wellington, "Secret Key Transaction Authentication for DNS
               (TSIG)", RFC 2845, May 2000.

    [RFC4635]  Eastlake, D., "HMAC SHA TSIG Algorithm Identifiers",
               RFC 4635, August 2006.

8.2.  Informative References

    [RFC2104]  Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
               Hashing for Message Authentication", RFC 2104,
               February 1997.

[Boilerplate]

---

From: Florian Weimer <[email-masked]>
Date: Thu, 10 Jul 2008 14:46:24 +0200

>>not consider chosen-plaintext attacks.

I think this is still true, but ...

> take that to the author of the paper. It is a well-received paper by a
> leader in the crypto community. Given the construction of HMACs, and
> the conclusion of the paper that the collision-resistance of the

... I was mistaken about the strength of the MD5 attacks published so
far.  D'oh!

Given that, I agree that it deprecating HMAC-MD5 is premature, but the
three octets "MD5" are unfortunately tainted forever.

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 10 Jul 2008 07:57:50 -0700

>... I was mistaken about the strength of the MD5 attacks published so

It is not the strength: it is the type of protection. If you need 
collision-resistance, you can probably safely assume that MD5 is too 
weak for anything, and getting weaker all the time. If you need 
preimage strength, MD5 is still untouched at 128 bits, and there 
haven't even been strong hints of any preimage weakness even though, 
post-Wang, there has been a huge amount of effort by people who want 
to be the first to show an attack.

>three octets "MD5" are unfortunately tainted forever.

Not if we don't spread the FUD. It's really not that hard. Hashes 
have three properties (there are actually two types of preimages), 
and only one has been found weak in MD5 and SHA1. Things that don't 
use that property are not affected by the weakness of the property.

--Paul Hoffman, Director
--VPN Consortium