Subject: NSEC3 Issue 23: dealing with unknown hashes

From: Roy Arends <[email-masked]>
Date: Fri, 25 Aug 2006 00:00:18 +0200

NSEC3 Issue 23:

(see also http://www.nsec3.org/cgi-bin/trac.cgi/ticket/45 )

If a validator ignores an NSEC3 resource record because it contains an 
unknown hash algorithm and subsequently treat a dnssec/nsec3 response as 
'unsigned', the validator must check that the NSEC3 record came from the 
proper zone.
 
This check needs to be done to avoid a replay of some arbitrary NSEC3 with 

an unknown hash algorithm, that happens to be signed with a key that the 
validator trusts. A successful replay can lead to a downgrade attack. 
 
The ownername of the NSEC3 record contains the hash value, prepended to 
the zone name. Since we want the NSEC3 record to be future proof, we have 
to allow digests to be longer than the maximum label size, and so, a 
future hash algorithm might have a digest that is presented over multiple 
labels.
 
We can therefor not safely assume that the first label contains the hash 
value, and the rest of the name is the zone name.
 
So, we need to find a way to discover the zone that the NSEC3 is from.

We have several approaches for this, described here in no particular 
order:
 
1) it is possible to calculate the number of labels that contains the hash 

from the hash length field. 
 
The hash length field contains the length of the hash of the Next Hashed 
Owner Name field. This length is in octets. The following formula 
determines the amount of labels used for the hash, and indicates that the 
rest of the labels contain the zone.
 
Let L be the value of the hash length field
 
Then labelcount = 1+((L*8)/315)

This approach assumes that all hash outputs for this single (unknown) 
algorithm have the same length, since the hash length field applies to the 

Next Hashed Ownername, not to the Owner Name of the NSEC3 record. Hence, 
an Identity Hash function, a function with variable length output, can not 

be easily defined this way.

2) it is possible to use the Signer's Name field of the RRSIG record that 
accompanies this NSEC3 record. The drawback is that the validator, while 
checking the applicability of the NSEC3 record, must have knowledge of the 

RRSIG at that stage. Note that the validator _has_ to check the validity 
of the signature anyway if it decides to treat a response as insecure due 
to an unknown hash algorithm. 
 
3) Add a 'Zone labels field' to the rdata field that indicates of how many 

labels the zone consists of, and hence, use that as a mask for the 
ownername of the NSEC3 record to determine the zone name. The drawback 
here is that the NSEC3 rdata is changed Yet Again. 

4) drop the 'unknown hash' methodology alltogether. This means that if an 
unknown hash is encountered, it is discarded. When the validator tries to 
validate the response, it ignores unknown hash NSEC3's and will treat the 
response as bogus. The drawback is that it will be hard to introduce new 
hash algorithms, unknown to a deployed base. The penalty is that zones 
using this new hash algorithm will be treated as bogus, thus 
unresolveable, for the deployed base.
 
5) truncate all hash outputs over 315 bits to 315 bits so it will always 
fit in a single label. The drawback here is that the 2nd-preimage 
resistance of a hash function is then restricted to 2^315, and thus less 
futureproof.

Note, the number 315 is the amount of significant bits of a base32 decoded 

maximum length label (5 * 63)

--
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: Mark Andrews <[email-masked]>
Date: Fri, 25 Aug 2006 10:50:41 +1000

> unresolveable, for the deployed base.

	Not really.  We just specify that if you want to use the new hash
	algorithm then you need to use specific key algorithms. 
  
> maximum length label (5 * 63)

	280 is the maximum number of bits that can be base32 encoded into
	a single label.  63/8 => 7 base32 blocks, 7*5*8 => 280 bits.
 
  6) Remove algorithm agility.

--
ISC Training!  October 16-20, 2006, in the San Francisco Bay Area,
covering topics from DNS to DHCP.  Email [email-masked].
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Roy Arends <[email-masked]>
Date: Fri, 25 Aug 2006 10:10:52 +0200

>    algorithm then you need to use specific key algorithms. 

When a new hash-algorithm is introduced, it might be because an old 
hash-algorithm is broken. In that case, a new key-algorithm must be used 
as well, if the signing used that same broken hash-algorithm. So this 
makes sense. 
Furthermore we already understand the semantics of this, it is similar to 
rolling from NSEC to NSEC3. 

>    a single label.  63/8 => 7 base32 blocks, 7*5*8 => 280 bits.

yes
 
>   6) Remove algorithm agility.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 25 Aug 2006 12:17:20 +0100

> resistance of a hash function is then restricted to 2^315, and thus less 

Woah, what future is this? The one where every atom in the universe has
2^200 domain names?

-- 
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: Roy Arends <[email-masked]>
Date: Fri, 25 Aug 2006 13:21:23 +0200

> Woah, what future is this? The one where every atom in the universe has

Yes. That future. :-)

Roy

---

From: bert hubert <[email-masked]>
Date: Fri, 25 Aug 2006 13:32:11 +0200

> > Woah, what future is this? The one where every atom in the universe has

Keeping the DNSSEC faith requirers some big leaps of the imagination I think
:-)

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services

---

From: David Blacka <[email-masked]>
Date: Fri, 25 Aug 2006 12:45:40 -0400

> 	algorithm then you need to use specific key algorithms. 

The referred to "'unknown hash' methodology" is to return an INSECURE
result when all of the NSEC3s are using an unknown hash algorithm.  So
dropping means that you would need to do a key algorithm roll (or
equivalent) in order to get the desired behavior.

>   6) Remove algorithm agility.

By this I assume that you are suggesting (as an option) essentially
fixing the hash algorithm field to "1", or removing the hash algorithm
field altogether.  That is, if a new algorithm is desired, then a new RR
 type will have to be defined.  Correct?

-- 
David Blacka                      <[email-masked]>
Sr. Engineer    VeriSign Infrastructure Product Engineering

---

From: Mark Andrews <[email-masked]>
Date: Sat, 26 Aug 2006 07:49:47 +1000

>  type will have to be defined.  Correct?

	Removing the algorithm field.  What happens w.r.t. NSEC3 if the
	hash algorithm ends up being busted? 

	* We can discover the NSEC3 chain.
	* We can spoof NODATA/NXDOMAIN responses that match a NSEC3 hash
	in the zone for a non-existing name.  The WG has already concluded
	that this is not a problem.
	* We cannot spoof data into existance.
	* We cannot spoof a NODATA response where there is data.

	* Speed of light saves us from having all the the potential
	qnames being checked.  Potential qnames still need to be
	tested against the authoritative servers.

	Yes it would reduce the problem space enormously but still not
	enough to be a issue.

	I would still get crypto guys to check my conclusions but I
	believe they are correct.

	So do we need algorithm agility?

	Mark

---

From: Roy Arends <[email-masked]>
Date: Thu, 31 Aug 2006 14:08:30 +0200

Roy Arends wrote on 08/31/2006 01:27:40 PM:

> The nsec3 draft editors have documented approach 4 in the upcoming 
release 
> of the draft. To recap approach 4:
> 
> 4) drop the 'unknown hash' methodology alltogether. 
> 
> This means that if an unknown hash is encountered, it is discarded. When 

> the validator tries to validate the response, it ignores unknown hash 
> NSEC3's and will treat the response as bogus, due to the lack of 
> appropriate NSEC3 records. The drawback is that it will be hard to 
> introduce new hash algorithms, unknown to a deployed base. The penalty 
is 
> that zones using this new hash algorithm will be treated as bogus, thus 
> Furthermore:
> When rolling from a known hash to an unknown hash, we recommend using 
the 
> exact same mechanism as when transitioning from NSEC to NSEC3 to 
overcome 
> the drawback and penalty described above.

to clarify: 'exact same mechanism' refers to using unknown DNSKEY 
signature algorithm, so a validator must treat the data in the response as 
coming from an unsigned zone.

Roy

---

From: Roy Arends <[email-masked]>
Date: Thu, 31 Aug 2006 13:27:40 +0200

The nsec3 draft editors have documented approach 4 in the upcoming release 
of the draft. To recap approach 4:

introduce new hash algorithms, unknown to a deployed base. The penalty is 

Furthermore:

When rolling from a known hash to an unknown hash, we recommend using the 
exact same mechanism as when transitioning from NSEC to NSEC3 to overcome 
the drawback and penalty described above. 

This is not set in stone, but we wanted to have at least one approach 
documented for the upcoming NSEC3 workshop. As always, we need consensus 
to lead us to the least evil way of dealing with unknown hashes, but will 
use this as the default resolution.

Roy Arends
with editor hat^H^H^H safety helmet and pressure suit