Subject: Re: NSEC3 Issue 9: Potential DoS on Resolvers

From: Sam Weiler <[email-masked]>
Date: Fri, 17 Mar 2006 16:55:51 -0500 (EST)

On Fri, 24 Feb 2006, Ben Laurie wrote:

>> Another related attack is actually not for people forging NSEC3
>> records and returning them to an attacker, but is actually much worse:
>
> Forgery is not an issue, since the signature won't check.

This suggests that it may be wisest to check the signature BEFORE 
performing a large number of hash iterations to see if the NSEC3 
record is applicable to the query (or, even, for which name it might 
be applicable).  This does go against the common wisdom of "make sure 
the record, if it validates, would matter", so it probably worth 
calling out.

But going back to the original question:

> 1.  Should an upper limit be specified in the standard?

No.  It seems reasonable to me for any given resolver to independently 
say "I'll never do more than X hash iterations -- any zone using NSEC3 
with >X hash iterations will be treated as insecure".  Those 
decisions, which need not be made in any coordinated fashion, won't 
break the net.  A resolver could even do more subtle things like "I 
won't do more than N iterations UNLESS I've seen at least 50 NSEC3 
records from that zone with at least that number of iterations set 
during the last month" or "I won't do more than N iterations per 
second -- any queries that would exceed that threshhold will be 
treated as insecure".  These local decisions of what authentication 
data to ignore will happen anyway, with few ill effects.

I'm fine with giving a recommendation to support a certain mimimun 
number, but I don't think we need to go any further.

-- Sam

--
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: Ben Laurie <[email-masked]>
Date: Sat, 18 Mar 2006 10:16:53 +0000

Sam Weiler wrote:
> performing a large number of hash iterations to see if the NSEC3 record
> is applicable to the query (or, even, for which name it might be
> applicable).  This does go against the common wisdom of "make sure the
> record, if it validates, would matter", so it probably worth calling out.
> 
> with >X hash iterations will be treated as insecure".  Those decisions,
> which need not be made in any coordinated fashion, won't break the net. 
> A resolver could even do more subtle things like "I won't do more than N
> iterations UNLESS I've seen at least 50 NSEC3 records from that zone
> with at least that number of iterations set during the last month" or "I
> won't do more than N iterations per second -- any queries that would
> exceed that threshhold will be treated as insecure".  These local
> decisions of what authentication data to ignore will happen anyway, with
> few ill effects.
> 

The consequence of such a recommendation is that no public zone will be
able to set their iterations higher, and so it will effectively be an
upper limit.

Which still leaves us with the question: what should that minimum number be?

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Ben Laurie <[email-masked]>
Date: Sat, 18 Mar 2006 10:24:58 +0000

> record, if it validates, would matter", so it probably worth calling out.

I have added this to our issue tracker.

---

From: Sam Weiler <[email-masked]>
Date: Mon, 20 Mar 2006 20:17:20 -0500 (EST)

On Sat, 18 Mar 2006, Ben Laurie wrote:

> The consequence of such a recommendation is that no public zone will 
> be able to set their iterations higher, and so it will effectively 
> be an upper limit.

Why wouldn't a public zone be able to set their iterations higher?

Your statement sounds remarkably like "no public zone will be able to 
use a new hash or crypto algorithm", which I certainly hope is 
untrue.

Sure, some resolvers won't be able to validate answers from a zone 
using "too many" iterations, but they should still be able to see the 
zone.  Likewise, an NSEC-only resolver won't be able to validate 
answers from an NSEC3 zone, and BIND 9.3.x won't be able to validate a 
zone signed with the CryptSam cipher suite.  But these are limitations 
on what a resolver is able to do, not what a zone is able to do.  If a 
zone owner wants the largest number of resolvers to be able to 
validate his zone, he can use NSEC-classic.  If he's using NSEC3 at 
all, clearly he has a different priority.  Using more iterations is a 
similar choice.

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Tue, 21 Mar 2006 06:28:12 +0000

Sam Weiler wrote:
>> be able to set their iterations higher, and so it will effectively be
>> an upper limit.
> 
> use a new hash or crypto algorithm", which I certainly hope is untrue.
> 
> Sure, some resolvers won't be able to validate answers from a zone using
> "too many" iterations, but they should still be able to see the zone. 
> Likewise, an NSEC-only resolver won't be able to validate answers from
> an NSEC3 zone, and BIND 9.3.x won't be able to validate a zone signed
> with the CryptSam cipher suite.  But these are limitations on what a
> resolver is able to do, not what a zone is able to do.  If a zone owner
> wants the largest number of resolvers to be able to validate his zone,
> he can use NSEC-classic.  If he's using NSEC3 at all, clearly he has a
> different priority.  Using more iterations is a similar choice.

There is no knob I can turn in a resolver that will make it understand a
new hash algorithm, in sharp contrast to number of iterations, so I
totally don't buy this analogy.

-- 
http://www.links.org/

---

From: Sam Weiler <[email-masked]>
Date: Tue, 21 Mar 2006 08:44:51 -0500 (EST)

>> use a new hash or crypto algorithm", which I certainly hope is untrue.
...
> totally don't buy this analogy.

Whether or not you "buy" the analogy, you could at least have the good 
grace to answer the direct question: why wouldn't a public zone be 
able to set their iterations higher?

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Tue, 21 Mar 2006 22:08:48 +0000

Sam Weiler wrote:
> grace to answer the direct question: why wouldn't a public zone be able
> to set their iterations higher?

You already answered it - because then some NSEC3-aware resolvers would
be unable to validate answers from the zone.

Your statement that a zone choosing to use NSEC3 at all would mean that
some resolvers couldn't validate the zone doesn't strike me as
motivation for increasing the number of resolvers that can't.

As we all know, some zones _cannot_ deploy NSEC. I see no point in
beating that dead horse further.

-- 
http://www.links.org/

---

From: David Blacka <[email-masked]>
Date: Tue, 21 Mar 2006 22:08:48 -0600

> motivation for increasing the number of resolvers that can't.

To try and salvage some use out of this thread, I thought I would  
point out that the real point that Sam has raised is that "too many  
iterations" should cause the validator to treat the response as  
INSECURE rather than BOGUS as the draft currently states.

This certainly makes the consequences of setting the iterations too  
high more palatable, so I think it should be considered.

--
David Blacka    <[email-masked]>
Sr. Engineer    VeriSign Applied Research

---

From: Sam Weiler <[email-masked]>
Date: Wed, 22 Mar 2006 00:16:27 -0500 (EST)

> INSECURE rather than BOGUS as the draft currently states.

Thanks for the help, David.

This inspired me to think of one minor downgrade opportunity...

If 1) a zone were to have multiple NSEC3 chains, perhaps because it 
was in the middle of rolling between NSEC3 parameters, or perhaps 
because it wanted to use different sets of NSEC3 parameters for 
different names, and 2) one of those NSEC3 chains used "too many 
iterations" (noting that "too many iterations" may be a 
resolver-specific number) and one those NSEC3 chains used "few 
iterations" (meaning that a given resolver can validate it)...

Then, even if the zone was using entirely "few iteration" NSEC3's for 
most names, an attacker could take one of the "too many iteration" 
NSEC3's and replay it in response to a query which might normally be 
answered with a "few iteration" NSEC3, causing that answer to be 
marked as insecure (since the resolver can't tell if the NSEC3 is 
applicable to that particular query or not).

In other words, if you have ANY "too many iteration" NSEC3's in the 
zone, your entire zone might be treated as insecure (just as if all of 
the NSEC3's used "too many iterations").

All in all, this doesn't worry me.  If a zone has multiple NSEC3 
chains, it's likely in the middle of a transition.  And if some of 
those NSEC3's use "too many iterations", then some resolvers will not 
have been able to validate the old zone (if rolling from "too many") 
or will not be able to validate the new zone (if rolling to "too 
many"), anyway.

This doesn't seem like a failure mode we need to do special 
engineering for.  But we should probably mention it in the security 
considerations section.

-- Sam

---

From: Sam Weiler <[email-masked]>
Date: Wed, 22 Mar 2006 00:20:23 -0500 (EST)

On Tue, 21 Mar 2006, Ben Laurie wrote:

> Your statement that a zone choosing to use NSEC3 at all would mean 
> that some resolvers couldn't validate the zone doesn't strike me as 

I'm now lost.  In what context do you think we were talking about 
"increasing the number of resolvers that can't [validate the zone]" 
and what is it you think we were proposing that that would have the 
effect of "increasing the number of resolvers that can't [validate the 
zone]"?

-- Sam

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Wed, 22 Mar 2006 13:02:43 -0600

On Mar 21, 2006, at 4:08 PM, Ben Laurie wrote:

> that

<no-hats>

During the WG meeting you mentioned that the number of iterations  
(section 8.3) could be increased sometime in the future.

So what happens when at some time X the number of iterations  
'allowed' will be increased. There is no (specified) way for a NSEC3  
aware resolver to become aware of the increased allowed number of  
iterations. A zone owner will not know if and/or when the set of  
resolvers has been updated to comply with the new number of  
iterations. Which would mean that in practice a zone owner will not  
be able to upgrade.

I therefore think that you will not be able to change the number of  
iterations field.

You could say that the number of iterations can be increased when you  
introduce new key or hash algorithms but that probably only work for  
algorithms that MUST be supported.

While skimming the ID again I did not find any text suggesting that  
the number of iterations may or should be modified in the future. I  
propose not to add such text and live with the fact that you will not  
be able to modify the costs once you set the numbers in 8.3. You may  
want to add text to the security section expanding on that.

Not sure,

--Olaf

-----------------------------------------------------------
Olaf M. Kolkman
NLnet Labs
http://www.nlnetlabs.nl/

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Wed, 22 Mar 2006 14:24:54 -0600

> (section 8.3) could be increased sometime in the future.

When I wrote this message I had not seens David's remark yet. The  
"treat as INSECURE" is a good solution to this as well. Good thinking!

--Olaf

---

From: Ben Laurie <[email-masked]>
Date: Sun, 26 Mar 2006 11:40:24 +0100

Olaf M. Kolkman wrote:
> So what happens when at some time X the number of iterations 'allowed'
> will be increased. There is no (specified) way for a NSEC3 aware
> resolver to become aware of the increased allowed number of iterations.
> A zone owner will not know if and/or when the set of resolvers has been
> updated to comply with the new number of iterations. Which would mean
> that in practice a zone owner will not be able to upgrade.
> 
> While skimming the ID again I did not find any text suggesting that the
> number of iterations may or should be modified in the future. I propose
> not to add such text and live with the fact that you will not be able to
> modify the costs once you set the numbers in 8.3. You may want to add
> text to the security section expanding on that.

That sounds fine to me. Obviously when we're all in our graves someone
can change our mind for us by writing a new RFC.

One thing that did occur to me, though, is that we might want to relate
maximum number of iterations to verification cost rather than signing cost.

Cheers,

Ben.