Subject: Re: comments on nsec3-01

From: Roy Arends <[email-masked]>
Date: Tue, 1 Mar 2005 13:50:19 +0100 (CET)

On Mon, 28 Feb 2005, Samuel Weiler wrote:

> Think about this from the perspective of a zone owner: "if I sign my
> zone using new NSEC3 hash algorithm 42, many/most resolvers will
> discard the NSEC3's, resulting in validation failures in my zone --
> among other things, unsecure delegations FROM my zone will vanish,
> since resolvers discard the NSEC3's needed to prove that they're
> unsecure".  And none of this requires an attacker -- this is what
> happens with well-behaved validators using the algorithm your doc
> describes.  That's a pretty strong disincentive to use any new
> algorithm.

> > > If you can't change the algorithm with some grace, I think
> > > parameterizing it is misleading and adds unnecessary complexity.
> >
> > I don't believe you've demonstrated that inability.
>
> And I believe this document hasn't even postulated, much less
> demonstrated, an ability to gracefully roll them.

Samuel, Ben,

The issue of changing algorithms, or changing any parameter for that
matter, becomes a problem when the behaviour of this change is not
properly documented. Specific behavior falls into two classes: if the new
parameter value is known: behave accordingly. If value is unknown, follow
the path of least destruction.

Firstly, lets agree that changing the hash-function field value inside the
NSEC3 requires re-signing the record. If an adversary changes the
hash-function field value without re-signing, the verification of the
RR will fail, and will be noticed by the validating resolver. Lets
call this state 'failed signature verification'. Essentially, the
validation process will end here, if all sources are exhausted, further,
the resolver process will end here as well, since it has encountered a
fatal error.

Secondly, lets agree that an RR with a hash-function field value unknown
to the resolver, though with a proper signature, will be verified
successfully. Lets call this state 'unknown NSEC3 hash function'. The
validation process will ignore this NSEC3, and therefor can't proof (non)
existence. The resolver process will end here as well, since it has
encountered a fatal error.

Basically, there are three mayor effects:

1) negative responses (i.e. no such name, no such type) will deem invalid.
(for argument sake, this includes responses due to wildcard expansions).

2) positive responses can be replaced by any negative response from the
same zone. Because the hash-function is not known, QNAME can not be
checked against the interval.

3) the status of delegation points is unknown, since the interval of the
related NSEC3 RR can not be checked, hence, the DS bit status is not
valid.

The most destructive action an adversary can mount at this point is a
denial of service.

In contrast: When rolling DS 'digest type', multiple field values
can exist in a single RRset, as long as one value is known.

It is not possible to have multiple NSEC3 RRs with different
'hash-function' values in a single NSEC3 RRset, since hashing a name using
different functions, leads to different hashed owner names.

Indeed, there is no easy way to roll NSEC3 hash-functions, and no way to
safely include multiple forms of denial in a response. Therefor, the
question 'why parameterize hash-functions' is valid.

The benefits in parameterizing the hash-function inside NSEC3 as
opposed to create a NSEC_SHA1 and NSEC_SHA256 (have a NSEC type per
function) are ephemeral when there are just 2 values defined, and the rest
is coined 'unknown'. There are benefits when there is a manifold of
known hash-functions defined.

Roy

--
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: "Olaf M. Kolkman" <[email-masked]>
Date: Tue, 1 Mar 2005 14:52:37 +0100

Samuel Weiler:
> This reminds me of a discussion from 1.5 years ago:
>  http://ops.ietf.org/lists/namedroppers/namedroppers.2003/msg01539.html
>  http://ops.ietf.org/lists/namedroppers/namedroppers.2003/msg01773.html

I think the essential difference between the threat in that thread and
the threat in this thread is that one could do an attack by stripping
the RRSIGs with known algorithms and insert RRSIGs with unknown
algorithms, which would go unnoticed as the RRSIGs are not signed.

An attacker cannot simply insert the '42-Hash" since the NSEC3 RR will
need to cary a valid signature.

-- Olaf

---------------------------------| Olaf M. Kolkman
---------------------------------| RIPE NCC
---------------------------------| JID: olaf at jabber.secret-wg.org

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Mar 2005 14:23:11 +0000

> question 'why parameterize hash-functions' is valid.

It seems to me that it would be fine to include multiple responses, one 
per desired hash. During introduction of a new hash type, return both 
the old and new types. If size of response is an issue, I guess the 
client would have to indicate which version on NSEC3 it supported.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"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: "Olaf M. Kolkman" <[email-masked]>
Date: Tue, 1 Mar 2005 17:33:14 +0100

On Tue, 01 Mar 2005 14:23:11 +0000
Ben Laurie <[email-masked]> wrote:

> During introduction of a new hash type, return both 

How can one be sure that one of those responses is not stripped from
the answer? They are not covered by one signature since they have
diffent ownernames. What is the the concequence of stripping?

How do you distinguish between a situation where a validator only
receives the newest of the two algoritms (the one that it knows about
being stripped) and the situation that only a new algorithm NSEC3 is
served?

Although parts of the answer are popping up in this thread, I still
fail to see the complete picture. (And I have not even tried to bend
my mind around a situation where one of the two has a DS bit set and
the other did not).

On the client signaling which version of NSEC3 it supports; that may
not be trivial since there might be all kind of forwarders/caches in
between that need to deal with this. Im not saying its impossible but
its not very appealing to go into that direction.

-- Olaf

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Mar 2005 17:46:59 +0000

> diffent ownernames. What is the the concequence of stripping?

If the stripped answer is the only one the client understands, then the 
consequence is the same as preventing delivery of the answer at all. 
That is, I don't believe this introduces any kind of interesting 
vulnerability in that respect, since an attacker can always eat your 
responses anyway.

> being stripped) and the situation that only a new algorithm NSEC3 is

Why would you want to?

> its not very appealing to go into that direction.

True enough.

Cheers,

Ben.

---

From: Samuel Weiler <[email-masked]>
Date: Tue, 1 Mar 2005 14:23:41 -0500 (EST)

On Tue, 1 Mar 2005, Ben Laurie wrote:

> If size of response is an issue, I guess the

Don't go there.

Think about caching.  Think about the difficulties we've had with
signalling up the resolver chain (the DO bit, for one).

Don't go there.

-- Sam

---

From: Samuel Weiler <[email-masked]>
Date: Tue, 1 Mar 2005 14:28:27 -0500 (EST)

> need to cary a valid signature.

Absolutely correct -- sorry I didn't state that as clearly in my
messages.

This leads me to think that if we give zones a choice of what hashes
to use that includes future expansion space, then it's important to
signal what hash is in zone when the zone is entered.  We could pick
from algorithm signaling, DS hash signaling, a new DS record, or
perhaps other ideas doucmented in -trans, but that signalling needs to
happen at the zone cut.

(The case of possibly including multiple NSEC3's is a different beast,
as Olaf pointed out later in this thread.)

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Mar 2005 21:24:37 +0000

> signalling up the resolver chain (the DO bit, for one).

I am more than happy not to go there :-)

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Wed, 2 Mar 2005 11:43:49 +0100

> vulnerability in that respect, since an attacker can always eat your 

Iff stripping has prevention of delivery as only concequence I am with
you. That would be a vulnarability one can live with.

> > being stripped) and the situation that only a new algorithm NSEC3 is

That question was related to the first question. If there are
concequences, other than prevention of delivery (DOS) how would you
understand that you are under attack or that you are served with
genuine data?

One of the many questions I have is what should be the default
behavior in case you do not understand the new hash algorithm. Should
you treat the answer as non secure?

I am also affraid there might be interference between algorithm roll
and the opt-in part of the proposal. What should a validator do if it
receives an answer with an unknown hash algorithm and the "A" flag
set? The validator can not tell that the delegation NS RR that has
been returned is actually part of the opt-in span and is therefore
supposed to be non-secured. In other words if one spoofs an NSEC3 RR
with an unknown hashing algorithm and a valid RRSIG (which was
obtained from a random query) into the query stream one can make a
zone that was previously secure unsecured and then spoof answers from
that zone.  (I am affraid I'm a little to dense here).

As an alternative approach. Lets try to enumerate the possible answers
a resolver may expect and see what the possible choices are.

In all cases we asume that the NSEC3 spans the "hashed qname" for
which an NXDOMAIN is returned and that the NSEC3 RR is validated with
an RRSIG.

For means of notation.  NSEC3(a,0) means an NSEC3 record with hash
algorithm an that the "A" flag is clear. NSEC3(z,1) means the NSEC3 rr
uses hash algorithm 'z' and the "A" flag is set (hence its "OPT-IN").

Algorithms a,b are understood by the validators and algorithm z,y are
not.

What does the resolver do if the following is returned and what are the
vulnarabilities in these cases.

situation         Returned
   1               NSEC3(a,0)     
   2               NSEC3(a,1)
   3               NSEC3(a,0),NSEC3(b,1)    Two different owner names both span
                                            the QNAME one is with opt-in one
                                            without.

   4              NSEC3(a,0),NSEC3(z,0)
   5              NSEC3(a,1),NSEC3(z,0)
   6              NSEC3(a,0),NSEC3(z,1)
   7              NSEC3(a,1),NSEC3(z,1)

   8              NSEC3(a,1),NSEC3(a,0)    These have the same owner name
                                           should this be outlawed?

   9              NSEC3(z,0)

   10             NSEC3(z,1)

I think that we have to go over these corner cases and spell out if
there are vulnarabilities. I think that we can safely assume that
NSEC3(z) records can not be injected since they will need to be
signed. That is a somewhat different situation from what we had with
the key degradation attack.

--Olaf

---

From: Ben Laurie <[email-masked]>
Date: Wed, 02 Mar 2005 15:08:20 +0000

> you treat the answer as non secure?

The answer is non secure, so it would be slightly insane to treat it any 
other way.

However, I do not believe it is well-defined what we mean when we say 
"treat the answer as non-secure". This seems to me to be tied in with 
the questions related to resolvers, APIs and user interaction that have 
been consistently punted every time I've seen them discussed. Having a 
clear idea of what is meant by this seems to me to be vital to 
understanding the threats, if any.

> that zone.  (I am affraid I'm a little to dense here).

Again, I don't see how this is different from preventing the delivery of 
NSEC3 RRs at all.

> the key degradation attack.

I guess sitting down for an hour or two in minneapolis and going over 
these would be useful. Just to be clear, there appear to be two 
different issues which are being addressed here:

a) Hash function rollover

b) Inconsistent opt-in responses (which are presumably only of interest 
if a zone is switching to or from opt-in - otherwise the zone is just 
plain broken).

but, until we have a clear idea of what action we might take depending 
on our assessment of the security of the zone, it is difficult to be 
clear what, if any, vulnerabilities arise from the above situations.

In particular, the state where we can can't get an answer to a query 
seems to me to be not interestingly different from the state where we 
get an answer we don't understand (whether through intervention or 
simply because we're out of sync, version-wise), but perhaps someone has 
a threat model where these are different - do they?

Cheers,

Ben.

---

From: Alex Bligh <[email-masked]>
Date: Wed, 02 Mar 2005 16:19:43 +0000

--On 02 March 2005 15:08 +0000 Ben Laurie <[email-masked]> wrote:

> "treat the answer as non-secure". This seems to me to be tied in with the
> questions related to resolvers, APIs and user interaction that have been
> consistently punted every time I've seen them discussed. Having a clear
> idea of what is meant by this seems to me to be vital to understanding
> the threats, if any.

Call me naive or avoiding the question, but isn't the answer here
that the API / application treats it exactly how it would have treated
it if the zone were unsigned.

So some apps might chose to proceed, some might display a warning, some
might not highlight the browser bar in yellow and proceed anyway.

IE I don't understand why at APPLICATION level this adds any more of
a third state than is already necessary to provide backward compatibility
with vanilla DNS. If applications do not want to provide such backward
compatibility, they necessary reject unsigned replies, whether that's
an opt-in "I can't tell give you a signed denial of existence" or
a vanilla DNS NXDOMAIN. If they want to treat unsigned replies as
if they were signed, fine. If they want to treat them "a third way",
also fine.

Alex

---

From: Ben Laurie <[email-masked]>
Date: Wed, 02 Mar 2005 17:11:53 +0000

> if they were signed, fine. If they want to treat them "a third way",

That's certainly a plausible argument for how APIs might work :-)

If everyone can agree that that's how it should work, then we have a 
basis for proceeding.

Cheers,

Ben.

---

From: Florian Weimer <[email-masked]>
Date: Tue, 29 Mar 2005 20:05:19 +0200

* Roy Arends:

> I've just submitted draft-ietf-dnsext-nsec3-01 and am hereby solliciting
> comments.

In the Performance Considerations, you could mention that the hashed
labels decrease performance of some access methods (e.g. B-trees) due
to poor locality.

I'm not sure if there are any relevant applications which are affected
by this (mine doesn't qualify as relevant, and I don't plan to store
NSEC3 records, either).

---

From: Ben Laurie <[email-masked]>
Date: Wed, 30 Mar 2005 06:19:40 +0100

> labels decrease performance of some access methods (e.g. B-trees) due

? I don't understand this comment - B-trees shouldn't be affected by the 
distribution of the data (not entirely sure what you mean by "locality" 
in this context, though).

---

From: Samuel Weiler <[email-masked]>
Date: Wed, 30 Mar 2005 01:31:12 -0500 (EST)

> in this context, though).

Presumably: when answering a query for a non-existing name, an
authoritative server must first look for the exact match, then for the
span containing the hash of the QNAME.  With NSEC-classic, the QNAME
and the NSEC covering it can be found remarkably close to one another
in the sorted zone.  When using a B-tree keyed on the name, presumably
the search for the closest predecessor is shorter than starting over
at the root at the tree.

With NSEC3, the QNAME and the NSEC3 covering hash(QNAME) are generally
not adjacent in the sorted zone, so a server storing the zone as a
B-tree would need to do two full searches.

This doesn't seem like a big deal to me, but I just spent the
afternoon hanging around with academic cryptographer types who were
dismissing 3-10x growth in message size and computational load as "Oh,
it's just some constant factor".

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Wed, 30 Mar 2005 10:35:06 +0100

> B-tree would need to do two full searches.

Obviously if one is going to search by the hash, then one would 
construct an index using the hash, which would be around as efficient as 
an index of names (at least, it would be using B-trees).

Cheers,

Ben.