Subject: comments on nsec3-01

From: Samuel Weiler <[email-masked]>
Date: Thu, 24 Feb 2005 00:37:39 -0500 (EST)

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

Executive summary: While I don't like the inclusion of opt-in, I like
most of the technical substance in this doc.  That said, the text has
some rough edges, and I'm still worried about how to change salts and
hash functions.

Technical summary (someone tell me if I get any of this wrong,
please):  At the San Diego IETF last August, I did a presentation
comparing NSEC2 (from Ben Laurie) to DNSNR (from Roy Arends).  I
described four differences between the protocols: hash iterations, the
authoritative-only bit (a.k.a. opt-in), a null hash function
(plaintext names), and the choice of what gets hashed.  The first
three I described as options -- they were compatible with both
protocols.  This proposal uses hash iterations and the
authoritative-only bit (opt-in) but does not define a null hash
function.  This proposal hashes the entire owner name (as NSEC2 had
originally proposed) and adds NSEC3 RRs at all empty non-terminals (a
new innovation that should help with wildcard proofs).

That presentation also identified several problems common to both
documents.  This new proposal seems to address the wildcard handling
issues and it makes progress on handling hash collisions.  I still
worry about changing hashes/salts.

Details (with asterisks on especially interesting items):

Sections 2 and 2.1.1 were very hard to read, 2.1.1 especially.  Please
rework them.

Section 2: rather than cite (just?) 2308, (also?) cite -records.

** 2.1.2 Discarding NSEC3 RRs w/ unknown hashes sounds very, very bad.
** If you simply discard them, then presumably you can't do validation
** of negative answers in that zone (can anyone say "attack vector"?).
** One (perhaps bad) option is to tie the NSEC3 hash algorithm to the
** zone's DS message digest algorithm, since we already know how to
** handle unsupported algorithms in the DS.  But since a zone could
** have multiple DS's (with different hash algorithms), but not
** multiple NSEC3 chains (presumably), this doesn't sound so good.
** Can we just declare "this is the NSEC3 hash function" and not
** parameterize it?

2.2  Citation for RFC3597 ([5]) doesn't exist.

Section 3.  Adding NSEC RRs at names with no other RRs is a protocol
change and should probably be more vigorously flagged as such (as in:
"changes section xxx of -records by...").

** Section 5 is remarkably clear.  I wish there were similar sections
** telling resolvers how to deal with NSEC3's and telling servers when
** to include them -- both with very explicit instructions.

Section 6.1.1: I'm uneasy with this paragraph:
   The only possible mitigation is to either not use this method,
   hence proving existence or absence of unsigned delegations, or
   signing the delegated zone, changing the unsigned delegation into a
   signed delegation.
It's not the signing of the child that mitigates the attack, it's the
signing of the delegation, whether or not there's a DS.

Section 6.2: This doesn't sounds quite right: "... an RR must be shown
for the closest encloser, and non-existence must be shown for all
enclosers that could be closer."  Ed?

Section 6.4: the 2^80 number depends on SHA1.  Say that.

Section 6.4.1: for the second paragraph (really dealing with
collisions), suggest a specific server behavior when it needs to prove
the non-existence of something and can't.  Should it make up an RR
set?  Give a REFUSED?

Section 6.4.3: hash truncation.  Are you describing a technique you
expect to be used?  Are you expecting truncation to be recognized
automatically?  Or do you need a new hash identifier for each
truncation?  If recognized automatically, more text is needed.

IANA: What's the criteria for assignment?  "Reserved" won't cut it --
see 2434bis.  Standards Action might be appropriate.  What's
experimental (also in section 2.1.2)?  (Is it "private use"?)
Describe it or drop it.  The presentation format in section 2.2 allows
for the "name of the hash" to appear.  If that's to be retained, the
names/mnemonics need to be in the registry.  All that said, if we
can't find a wat to change hash functions, maybe we should just drop
the parameterization entirely, as discussed above re: section 2.1.2.

Security considerations: "...in any case, [a dictonary] attack could
also be used directly against the name server..." is misleading.
NSEC3 enables an off-line dictonary attack, which is faster, less
dectable, and less susceptible to counter-measures than an on-line
attack.

** Security considerations: suggests changing salt, but how?  Section
** 2.1.5 requires identical salt values throughout the zone.  Can you
** change salts without going insecure?  How?

Security considerations: "If [hash collisions occur], it will be
impossible to prove the non-existence of the colliding domain" doesn't
sound quite right.

Security considerations: needs to discuss the risks of opt-in.  6.1.1
does much of it, but there should at least be a pointer here, if not a
repeat of the discussion.  May want to look at the text from David's
opt-in draft.

Remove sections 10 (duplicates 1.2) & 11

--
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: Thu, 24 Feb 2005 06:37:25 +0000

Responding to non-editorial points for now. I'll edit the document tomorrow.

> some rough edges, and I'm still worried about how to change salts and

As discussed, opt-in is optional, and can be removed at the WG's 
discretion. I don't like it much either, but since it impacts the spec 
it seemed wise to include it, at this point.

> worry about changing hashes/salts.

I still don't understand what your concern is. Any individual NSEC3 
record works standalone with its own hash/salt/iterations. The owner of 
a zone must be sure to have a complete set for any particular 
combination of hash/salt/iterations, or there could be queries it could 
not respond to, but it doesn't actually matter if a client receives part 
of the response from one set and part from another, since each 
individual NSEC3 record denies a particular RR, and that RR is denied 
whichever set it comes from (not that I can see how this can happen 
anyway, but guessing at your concern).

> ** of negative answers in that zone (can anyone say "attack vector"?).

How can this be used as an attack? NSEC3s must be signed, so an attacker 
is not at liberty to choose the hash.

> ** Can we just declare "this is the NSEC3 hash function" and not

Then we'd have to roll the whole protocol to change the hash function, 
which sounds even less good.

> NSEC3 enables an off-line dictonary attack, which is faster,

I would dispute that it is necessarily faster - that was the point of 
having iterations. I would agree with "might be faster".

> less dectable, and less susceptible to counter-measures than an on-line
> attack.

One of our entry-points to the whole NSEC++ discussion was that there 
are no plausible counter-measures.

> ** change salts without going insecure?  How?

You would have to change the salt for the whole zone, and see above. But 
hash collisions are a distraction. In practice they will not occur.

> impossible to prove the non-existence of the colliding domain" doesn't

It sounds right to me. What do you think is wrong?

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: Ben Laurie <[email-masked]>
Date: Thu, 24 Feb 2005 13:13:32 +0000

> Sections 2 and 2.1.1 were very hard to read, 2.1.1 especially.  Please

I think this'll have to wait for discussion about exactly what is unclear.

> Section 2: rather than cite (just?) 2308, (also?) cite -records.

Where, exactly? Would 1.1 be more appropriate?

> 2.2  Citation for RFC3597 ([5]) doesn't exist.

Fixed.

> signing of the delegation, whether or not there's a DS.

Agreed, fixed. Of course, this relates to opt-in, hence the confusion.

I note that the other case is also wrong. Proving absence of unsigned 
delegations does not prevent the fabrication of such delegations. I am 
also fixing that. This strikes me as an argument against opt-in.

> enclosers that could be closer."  Ed?

What doesn't sound right about this? It seems correct to me.

> Section 6.4: the 2^80 number depends on SHA1.  Say that.

Fixed (and made more general).

> the non-existence of something and can't.  Should it make up an RR

You know, this obsession with collisions is really getting quite silly. 
If you want to follow it to its logical conclusion, then we are going to 
have to rework all the signature stuff in DNSSEC, too, since they are 
equally vulnerable to hash collisions (and with substantially worse 
consequences, too). Do you really want to go down that path?

Incidentally, 6.4.2 deals with the case you described, not 6.4.1. But 
I'm personally in favour of deleting all mention of collisions beyond 
specifying that hash functions should resist them.

> truncation?  If recognized automatically, more text is needed.

No, I've updated the text to reflect this.

> the parameterization entirely, as discussed above re: section 2.1.2.

Since I've added the null function back, this is not an option. I leave 
it to the WG to decide what action is needed to allocate a new hash 
function.

> dectable, and less susceptible to counter-measures than an on-line

Text modified somewhat.

> impossible to prove the non-existence of the colliding domain" doesn't

This seems correct to me - what problem do you see?

BTW, Alex Bligh did point out a way to completely resolve this - in the 
event of a collision, one presents NSEC3 records with the identity hash 
function instead. I would suggest we do NOT specify this, because it's a 
good deal of work for implementers to handle a case that will almost 
certainly never occur and is computationally infeasible to ever test(!). 
Plus it substantially increases the size and signing cost of the zone.

> repeat of the discussion.  May want to look at the text from David's

Perhaps we should simply refer to the opt-in draft, since all we're 
doing is adding support for it.

> Remove sections 10 (duplicates 1.2) & 11

Done.

Cheers,

Ben.

---

From: Alex Bligh <[email-masked]>
Date: Thu, 24 Feb 2005 14:04:32 +0000

> Plus it substantially increases the size and signing cost of the zone.

Firstly, I agree with your comment about hash collisions taking up
an inordinate amount of unnecessary conversations.

That being said, in partial defense of my own suggestion above, I'd
make the following points:
1. It certainly should not be a MUST or a SHOULD requirement, but I would
   have thought a MAY specification is reasonable (indicating it is a
   possible option), as there may be some implementers who are worried
   about hash collisions more than we are. It would be reasonable to
   say MUST either (a) use alternate non-colliding hash such as the
   identity hash which is guaranteed never to collide, OR (b) [specify
   default behaviour - REFUSED, SERVERR whatever].
2. It is not computationally infeasible to test because one can generate
   (for this purpose) a deliberately weak hash function (for instance take
   the octets as groups of 32 bit words and XOR them together). If we
   are that concerned about it, given we probably want to do
   interoperability testing for multiple hash functions, it might be
   that specifying this (as an optional hash) is a good idea anyway.
3. If it is optional, the argument about it being a lot of work falls.
   Ditto the argument about increasing size and signing cost of zone. Only
   the ultra-cautious/paranoid (you pick which!) bear the cost.
4. Such a scheme would permit the use of very truncated hashes as alternate
   hash functions, where one is prepared to accept the possibility
   of the occasional collision (and thus the occasional adjacent name
   being discovered) AND additional signing complexity
   in order to minimize on-wire data (if bandwidth rather than CPU is
   the problem). I figure you can truncate the zone hash to something
   like 2logN bits (where N is number of items in zone) and keep the
   expected value of the number of collisions smaller than 2 (but you
   would HAVE to handle the case where collisions do exist if you are
   doing this by doing an identity sign as well). That's a noticeable
   on-wire saving.

But no, I'm not that fussed about it.

Alex

---

From: David Blacka <[email-masked]>
Date: Thu, 24 Feb 2005 18:01:38 -0500

> also fixing that. This strikes me as an argument against opt-in.

Opt-In explicitly doesn't prove the absence of unsigned delegations. 
That was the point.  That you can fabricate unsigned delegations in an 
opt-in signed zone is very well understood.  Because this strikes some 
as an argument against opt-in is why opt-in is always *optional*.

> doing is adding support for it.

You could refer to it, but keep in mind that the opt-in document is 
heading for the Experimental track, not PS.

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

---

From: Samuel Weiler <[email-masked]>
Date: Sat, 26 Feb 2005 14:23:53 -0500 (EST)

> anyway, but guessing at your concern).

Then the doc needs to say that, including specific instructions to
validators to treat each NSEC3 individually (for instance, you might
have one NSEC3 proving no exact match using hash1 and one proving no
wildcard with hash2).

The doc currently requires that the salt be the same throughout the
zone, which suggests (perhaps incorrectly) that the above doesn't
work.

> is not at liberty to choose the hash.

If a new (relatively unknown) hash is in use, the attacker can replay
it with interesting results.

Imagine a zone using NSEC3 with a previously-unknown hash algorithm
(type 42).  A validator that doesn't understand hash type 42 can still
process positive answers from that zone and set the ad bit for them.
What happens when that same validator (that doesn't understand hash
42) gets a nonexistence proof from the zone?  Following the above
rules, it discards the NSEC3.  What does it do now?  Treat validation
as having failed?  That would make it very dangerous to use new hash
algorithms.  Treat the zone as insecure (at least for non-existence
answers)?  That looks like the only safe option, given the 'discard'
directive.

Now imagine a man-in-the-middle.  In response to a query for an
existing RR in the zone, the attacker synthesizes a nonexistence proof
using ANY of the NSEC3 RR's from the zone.  The validator can't tell
the difference between this and the second situation above -- the
attacker has just spoofed away real names.  Wouldn't it be better to
know the zone was insecure when you first enter it rather than have
this "somewhat secure" state?

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

> which sounds even less good.

If you can't change the algorithm with some grace, I think
parameterizing it is misleading and adds unnecessary complexity.

> having iterations. I would agree with "might be faster".

Fair enough.

> It sounds right to me. What do you think is wrong?

There are at least two ways to read this.  Having looked again, I
suspect you meant: if the hash of an existing name and that of a
non-existing name collide, it will be impossible to prove the
non-existence of the non-existing name.

Another way to read it is: if the hashes of two EXISTING names
collide, if will be impossible to prove the non-existence of either.
(Which is the whole point, right?).  In that case (of two exisitng
owner names colliding), given the rules about including the superset
of types in the bitmap, it might or might not be impossible to prove
the non-existence of some RR types at those names.  If the set of
types at both names is the same, there shouldn't be issues.  Hence my
(somewhat frivolous) suggestion that one response would be to
synthesize bogus records to match the bitmap.  Or, in the case of a
non-existing name colliding, synthesizing bogus RR's at the
(previously non-existing) QNAME to match the NSEC3.

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Sat, 26 Feb 2005 22:15:12 +0000

> zone, which suggests (perhaps incorrectly) that the above doesn't

That is a requirement on the zone, to enable it to answer all queries.

> this "somewhat secure" state?

Would it? So long as I'm getting answers I can rely on, why do I care 
that I might get answers I can't? If I get an answer I can't understand, 
then I know that I can't understand it, so what's the big deal? An 
attacker can always deny me any answer at all, so the easy answer is to 
treat all incomprehensible answers as no answer.

> parameterizing it is misleading and adds unnecessary complexity.

I don't believe you've demonstrated that inability.

> non-existence of the non-existing name.

Yes.

> (previously non-existing) QNAME to match the NSEC3.

I'll agree these are frivolous.

---

From: Alex Bligh <[email-masked]>
Date: Sun, 27 Feb 2005 11:32:15 +0000

--On 26 February 2005 14:23 -0500 Samuel Weiler <[email-masked]> wrote:

> (Which is the whole point, right?).

Such a circumstance can be trivially avoided at signing time by choice
of salt.

Alex

---

From: Samuel Weiler <[email-masked]>
Date: Mon, 28 Feb 2005 15:11:24 -0500 (EST)

> >>>** of negative answers in that zone (can anyone say "attack vector"?).

I made a leap to "there could be an attack" by assuming a behavior
(treat the zone as unsecure) that differs from what the doc seems to
describe now.  Going back to the doc as it is now:

> > algorithms.  [Discussion of an alternative behavior removed.]
...
> treat all incomprehensible answers as no answer.

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.

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

-- Sam