Subject: [dnsext] Increasing hash collision resilience

From: Florian Weimer <[email-masked]>
Date: Mon, 18 May 2009 09:54:27 +0200

Currently, DNSSEC is rather exposed to near-state-of-the-art collision
attacks when the signature on DS records is computed.  (This data
comes from a potential attacker.  Other signatures cover self-created
data and are thus not subject to current attacks, except for
signatures on externally submitted zone contents, but this can be
addressed by delegation.)

In order to counter these attacks, it's possible (and recommended) to
prefix the signed document with a nonce.  Currently, there is no good
way to do this.  However, it would be posssible to put this nonce into
a DS record with the Digest Type 0, Key Tag 0, which is currently
reserved.

Is there interest in a draft which sets aside Digest Type 0 for this
purpose?  Any other Digest Type doesn't work because
attacker-controlled data might sort in front of it.

No change in authoritative reservers, resolvers, or validators are
required beyond relaxation of overly restrict checks on DNSSEC Digest
Types.  Only zone signers need to be updated to generate the nonces.

-- 
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

--
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: Florian Weimer <[email-masked]>
Date: Mon, 18 May 2009 14:56:58 +0200

* Florian Weimer:

> attacks when the signature on DS records is computed.

I've been asked privately how such an attack would be carried out.
The attack sketched below is analogous to the one by Lenstra et al.
on MD5 CAs.

Suppose that ORG. is signed using DNSSEC, and you want to attack
EXAMPLE.ORG., that is, get a valid signature on a DS RRset for
EXAMPLE.ORG. which contains hashes of keys you control.

We haven't got a second preimage attack, so we cannot use the original
EXAMPLE.ORG. DS RRset and attack it directly.  Instead, we generate
our own key pair, and create two DS RRsets which hash to the same
value.  The second RRset is for a domain different from EXAMPLE.ORG.
(the name does not matter, as long as it is available for
registration), and both RRsets are stuffed with additional DS RRs,
ignored by validators, to obtain a collision.  We request a signed
delegation for the second domai nname from the .ORG. zone operator,
and thanks to the collision, it is also valid for EXAMPLE.ORG.  (It's
probably necessary to register several domains in parallel because
there is some uncertainty in the validity period of the RRSIG record.)

Right now, this is rather theoretical because a sufficiently potent
attack for SHA-1 has not been published.  However, it is widely
believed that such attacks are just around the corner.

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 18 May 2009 07:05:02 -0700

At 2:56 PM +0200 5/18/09, Florian Weimer wrote:
>attack for SHA-1 has not been published. 

Correct. In fact, not a single actual collision for SHA-1 has been published.

>However, it is widely

Could you point to some references on that? I have not heard anyone in the crypto community saying that. Of course, it depends on what you mean by "just around the corner".

I do *not* support the use of randomized hashing for DNSSEC; the use of already-defined better hash algorithms (SHA-256) is a much better option.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Aki Tuomi" <[email-masked]>
Date: Mon, 18 May 2009 17:32:43 +0300

> -----Original Message-----
> From: [email-masked] [mailto:owner-
> [email-masked]] On Behalf Of Paul Hoffman
> Sent: Monday, May 18, 2009 5:05 PM
> To: Florian Weimer; [email-masked]
> Subject: Re: [dnsext] Increasing hash collision resilience
> 
> Could you point to some references on that? I have not heard anyone in
> the crypto community saying that. Of course, it depends on what you
> mean by "just around the corner".
> 
> I do *not* support the use of randomized hashing for DNSSEC; the use of
> already-defined better hash algorithms (SHA-256) is a much better
> option.
> 
> --Paul Hoffman, Director
> --VPN Consortium
> 

I wonder if use of SHA-256 will only postpone the problem, unless the 
algorithm is sufficiently different.

---
Aki Tuomi
TDC Oy

h�{.n�+���zwZ��,j��v�y�覗������-��"z��"�a{
+v�칻�&ފv��x%zX�y�-�鞲Ơzױ��ɪ܆+ކ�i��)�'�~���X����jg���iz�?

---

From: Edward Lewis <[email-masked]>
Date: Mon, 18 May 2009 11:09:29 -0400

>algorithm is sufficiently different.

All that cryptography ever does is "postpone the problem" - hopefully 
long enough that a successful attack no longer matters. ;)

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis
NeuStar                    You can leave a voice message at +1-571-434-5468

Getting everything you want is easy if you don't want much.

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 18 May 2009 08:32:39 -0700

>algorithm is sufficiently different.

For some value of "postpone", yes. However, watching the research on MD5 and SHA-1, it appears that the length of the hash output has a *huge* effect on finding differential paths, much less finding useful ones.

The argument for randomized hashing is that you don't need to worry about reductions in collision resistance. Two arguments against randomized hashing are that it relies on the unpredictability of the salt added and it adds one more place for interoperability to fail. That is, we are weighing a cryptographic principle against operational issues. I strongly tend towards having as few operational requirements as possible.

--Paul Hoffman, Director
--VPN Consortium

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 18 May 2009 09:02:44 -0700

Remember:  The ideal use of cryptography is about postponing the  
problem until the opponent is able to either build a quantum computer  
or has a few cubic parsecs of sci-fi nanotech.

---

From: Ólafur Guðmundsson /DNSEXT chair <[email-masked]>
Date: Mon, 18 May 2009 12:41:36 -0400

The concerns that SHA-1 would become vulnerable before new generation of
hash algorithms become available was the reason for the WG to rush RFC4509
through. http://www.ietf.org/rfc/rfc4509.txt

The message to everyone should be.
         - Only list DS with digest algorithm =2
         - or list both digest algorithm 1 and 2

The problem is that some DS records in many cases will be submitted by children
and the children need to be educated to use digest 2.

Is it time to change the status of SHA-1 in the registry from "MANDATORY"
to "Not recommended" or "Obsolete"?
http://www.iana.org/assignments/ds-rr-types/ds-rr-types.xhtml

We need an RFC do make that change.

Cryptographic security is a race between complexity, ingenuity,
computational power and desire, there are no winners only innocent
bystanders get inconvenienced.

         Olafur

---

From: Alex Bligh <[email-masked]>
Date: Mon, 18 May 2009 17:33:58 +0100

--On 18 May 2009 07:05:02 -0700 Paul Hoffman <[email-masked]> wrote:

> already-defined better hash algorithms (SHA-256) is a much better option.

Assuming that Florian's suggestion was not to mandate use of a nonce now,
but merely to consider permitting it by adopting a draft that would
document how a reserved type code could be used for this, I don't
really see the harm. What is the harm you see?

As a wider point, this may be my IETF process naivety, but it seems
to me that there might be too high a threshold in this group in getting
a draft adopted as a w/g draft for discussion. As I understand it,
adopting a draft for discussion does not imply support (let alone
unconditional support) for supporting it at last call stage. This
result risks shutting down potentially viable ideas before they have
had the chance to even be properly considered or explained. I appreciate
this may be the result of the w/g charter.

Florian's proposal seems an ideal example of this. Yes, using SHA-256
is going to be "better" than SHA-1 in defeating SHA-1 preimage/collision
attacks, but on the other hand it would appear (if I understand it
right) to offer a means of expanding the life of *any* hash that
is in the position SHA-1 is now (i.e. next most easy to find
a preimage/collision attack). We don't know that's the case, because
I haven't had the benefit of Florian writing up a draft, but it seems
to me too early to say it is valueless. If this is right, it could
be used to extend the life of SHA-256 similarly.

--
Alex Bligh

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 18 May 2009 10:32:54 -0700

>really see the harm. What is the harm you see?

Yet another option with semantics that only make sense to security weenies like us. "Hey, there is this new option and the RFC says it might be safer than SHA-256". "If it's safer than SHA-256, we had better use it. Turn it on." "Do we have a good unpredictable source of randomness?" "Yeah, sure, I think."

>this may be the result of the w/g charter.

I think the five-person rule is reasonable. What number would you propose instead?

>a preimage/collision attack).

Correct. In fact, randomized hashing can be used with MD5 to make MD5-with-randomized-hashing provably more secure than our current use of SHA-1. (Yes, I threw that in just to show how confusing this all can be; it's true, nonetheless.)

> We don't know that's the case, because

I didn't say "valueless", I said that I thought that the other solutions were better than his proposed solution. I have said that in the similar discussion in the PKIX WG. If all we care about is "strongest crypto", randomized hashing helps. If we care about its operational use, I think it hurts.

--Paul Hoffman, Director
--VPN Consortium

---

From: Andrew Sullivan <[email-masked]>
Date: Mon, 18 May 2009 14:10:40 -0400

On Mon, May 18, 2009 at 05:33:58PM +0100, Alex Bligh wrote:

> unconditional support) for supporting it at last call stage.

Olafur posted a point of order on that very issue just the other day.
Our five-reviewer limit is a requirement that we actually have five
people who will complete the WG's commitment to review the document if
and when it comes up for WGLC.  It in no way implies that the document
will in fact proceed from the WG to the IESG, because we can't
possibly know whether all the reviewers will be willing to say, "Yes
this is a good idea."  And, frankly, if we can't find 5 people who are
willing to review a document and say it's a good idea, then I am
perfectly happy concluding that it is not ready for publication as a
product of the WG.

The reason we need to get commitment of five people to do the review
in the first place is because, historically, we have had a problem
with the WG agreeing to take on work, but then not completing review
of the draft.  The result is that we end up with frustrated editors
who can't get their drafts out the door for want of review.  

None of this is to say that I-Ds that haven't actually been adopted by
the WG are off-topic for this list.  If an I-D has something to say
about the DNS and it's not already being worked on elsewhere, don't
hesitate to bring it up here.  Similarly, calls to participate in
other WGs because there are DNS implications "over there" are quite
reasonable.

A

-- 
Andrew Sullivan
[email-masked]
Shinkuro, Inc.

---

From: Alex Bligh <[email-masked]>
Date: Mon, 18 May 2009 19:10:25 +0100

--On 18 May 2009 10:32:54 -0700 Paul Hoffman <[email-masked]> wrote:

> "If it's safer than SHA-256, we had better use it. Turn it on." "Do we
> have a good unpredictable source of randomness?" "Yeah, sure, I think."

If not, do we not have larger problems?

> I think the five-person rule is reasonable. What number would you propose

I was not necessarily proposing a change to the five person rule. My
observation (and as I say, it may be down to IETF process naivety on my
part) was that perhaps people were expressing views against adoption at an
early stage which would preclude a proper evaluation of an idea which is at
least worth evaluating. This wasn't meant as a criticism of you in
particular, Paul, in any way; the same issue came up with EDNS ping where
someone (I forget who) volunteered to review the draft on the explicit
basis that this didn't indicate support for it (and it was reasonably
obvious it wasn't their favourite idea) but thought that at least it should
be properly evaluated.

--
Alex Bligh

---

From: "Jeffrey A. Williams" <[email-masked]>
Date: Mon, 18 May 2009 12:29:19 -0700

Florian and all,

  Good suggestion.

> Types.  Only zone signers need to be updated to generate the nonces.

Regards,

Spokesman for INEGroup LLA. - (Over 284k members/stakeholders strong!)
"Obedience of the law is the greatest freedom" -
   Abraham Lincoln
"YES WE CAN!"  Barack ( Berry ) Obama

"Credit should go with the performance of duty and not with what is
very often the accident of glory" - Theodore Roosevelt

"If the probability be called P; the injury, L; and the burden, B;
liability depends upon whether B is less than L multiplied by
P: i.e., whether B is less than PL."
United States v. Carroll Towing  (159 F.2d 169 [2d Cir. 1947]
===============================================================
Updated 1/26/04
CSO/DIR. Internet Network Eng. SR. Eng. Network data security IDNS.
div. of Information Network Eng.  INEG. INC.
ABA member in good standing member ID 01257402 E-Mail
[email-masked]
My Phone: 214-244-4827

---

From: "Jeffrey A. Williams" <[email-masked]>
Date: Mon, 18 May 2009 13:04:48 -0700

Paul and all

  Agreed with your conclusion.  However what is not necessarly
"Published" is not necessarly not occuring.

Regards,

---

From: Florian Weimer <[email-masked]>
Date: Tue, 19 May 2009 09:58:50 +0200

* Ólafur Guðmundsson:

> The problem is that some DS records in many cases will be submitted
> by children and the children need to be educated to use digest 2.

The value of the Digest Type does not matter.  (If the zone signer
demands proof for the DS records in the form of DNSKEYs, it's unlikely
that we'll see an attack during the next couple of years, neither for
SHA-1 or SHA-256.)

To address the issue with unchecked DS records submitted by untrusted
parties, you need to switch to a different hashing algorithm in RRSIG
signatures.  draft-ietf-dnsext-dnssec-rsasha256-13 still hasn't been
published as an RFC.  And general availability is two to three years
away.

> http://www.iana.org/assignments/ds-rr-types/ds-rr-types.xhtml

This action would have to target the DNSSEC Algorithm Types registry,
but such a step seems rather premature at this stage.  Incorporating
it into draft-ietf-dnsext-dnssec-rsasha256-13 is probably not a good
idea because it would delay its publication even further.

---

From: Olafur Gudmundsson <[email-masked]>
Date: Tue, 19 May 2009 08:23:37 -0400

<no-hat>

>that we'll see an attack during the next couple of years, neither for

How is this a practical attack?
The attacker has only part of the input to the signature under his/her
control.
Parent signs the DS record and selects timer values[1] of the RRSIG.
         Signature Interception, Signature Expire, TTL.

Once a target DS signature is generated the attacker has only the
"effective" life signature to play with, trying to
create a collision signature. If parent is using predictable timing
values the attacker still has to submit the "attack DS set" during a
one second window to have a good chance to get the right signature values.

>idea because it would delay its publication even further.

The attack you are describing is available against all RR types (DS is just
most attractive one). Thus if a fix is needed that should protect all
types not just one.

A better solution is to recommend that when signing records the
timer values be randomly picked from a range for example:
         sig init                [curr time-256..curr_time]
         sig expire      [lifetime-3600..curr_time+3600]
         TTL             [standard_TTL-1024..standard_TTL+1024]

This has no protocol implications.

         Olafur

---

From: Francis Dupont <[email-masked]>
Date: Thu, 21 May 2009 15:45:25 +0200

In your previous mail you wrote:

=> as the requirement is about implementation "OPTIONAL" should be
enough. But if one believes it is the right time to introduce
a requirement about usage then "not recommended" seems right.

=> looking for an editor (:-)?

Regards

[email-masked]

PS: note the document should specify implementations SHOULD provide
a (per-domain) configuration flag to refuse SHA-1 only DS RRsets.
PPS: we should check too if deployed DNSSEC implementations support
SHA-256 DS RRs (IMHO it is the case but it is an opinion, not the
result of some research/poll/etc).