< draft-ietf-dnsext-nsec3-03.txt   draft-ietf-dnsext-nsec3-04.txt >
Network Working Group B. Laurie Network Working Group B. Laurie
Internet-Draft G. Sisson Internet-Draft G. Sisson
Expires: April 26, 2006 Nominet Expires: August 5, 2006 R. Arends
R. Arends Nominet
Telematica Instituut February 2006
October 23, 2005
DNSSEC Hash Authenticated Denial of Existence DNSSEC Hash Authenticated Denial of Existence
draft-ietf-dnsext-nsec3-03 draft-ietf-dnsext-nsec3-04
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 36 skipping to change at page 1, line 35
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on April 26, 2006. This Internet-Draft will expire on August 5, 2006.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2006).
Abstract Abstract
The DNS Security Extensions introduces the NSEC resource record for The DNS Security Extensions introduces the NSEC resource record for
authenticated denial of existence. This document introduces a new authenticated denial of existence. This document introduces a new
resource record as an alternative to NSEC that provides measures resource record as an alternative to NSEC that provides measures
against zone enumeration and allows for gradual expansion of against zone enumeration and allows for gradual expansion of
delegation-centric zones. delegation-centric zones.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Reserved Words . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Reserved Words . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
2. NSEC versus NSEC3 . . . . . . . . . . . . . . . . . . . . . . 5 2. NSEC versus NSEC3 . . . . . . . . . . . . . . . . . . . . . . 5
3. The NSEC3 Resource Record . . . . . . . . . . . . . . . . . . 5 3. The NSEC3 Resource Record . . . . . . . . . . . . . . . . . . 5
3.1. NSEC3 RDATA Wire Format . . . . . . . . . . . . . . . . . 6 3.1. NSEC3 RDATA Wire Format . . . . . . . . . . . . . . . . . 6
3.1.1. The Opt-In Flag Field . . . . . . . . . . . . . . . . 6 3.1.1. The Hash Function Field . . . . . . . . . . . . . . . 6
3.1.2. The Hash Function Field . . . . . . . . . . . . . . . 7 3.1.2. The Opt-In Flag Field . . . . . . . . . . . . . . . . 7
3.1.3. The Iterations Field . . . . . . . . . . . . . . . . . 8 3.1.3. The Iterations Field . . . . . . . . . . . . . . . . . 8
3.1.4. The Salt Length Field . . . . . . . . . . . . . . . . 8 3.1.4. The Salt Length Field . . . . . . . . . . . . . . . . 8
3.1.5. The Salt Field . . . . . . . . . . . . . . . . . . . . 8 3.1.5. The Salt Field . . . . . . . . . . . . . . . . . . . . 8
3.1.6. The Next Hashed Ownername Field . . . . . . . . . . . 8 3.1.6. The Next Hashed Ownername Field . . . . . . . . . . . 9
3.1.7. The Type Bit Maps Field . . . . . . . . . . . . . . . 9 3.1.7. The Type Bit Maps Field . . . . . . . . . . . . . . . 9
3.2. The NSEC3 RR Presentation Format . . . . . . . . . . . . . 10 3.2. The NSEC3 RR Presentation Format . . . . . . . . . . . . . 10
4. Creating Additional NSEC3 RRs for Empty Non-Terminals . . . . 10 4. Creating Additional NSEC3 RRs for Empty Non-Terminals . . . . 11
5. Calculation of the Hash . . . . . . . . . . . . . . . . . . . 11 5. Calculation of the Hash . . . . . . . . . . . . . . . . . . . 11
6. Including NSEC3 RRs in a Zone . . . . . . . . . . . . . . . . 11 6. Including NSEC3 RRs in a Zone . . . . . . . . . . . . . . . . 11
7. Responding to NSEC3 Queries . . . . . . . . . . . . . . . . . 12 7. Responding to NSEC3 Queries . . . . . . . . . . . . . . . . . 12
8. Special Considerations . . . . . . . . . . . . . . . . . . . . 13 8. Special Considerations . . . . . . . . . . . . . . . . . . . . 13
8.1. Proving Nonexistence . . . . . . . . . . . . . . . . . . . 13 8.1. Proving Nonexistence . . . . . . . . . . . . . . . . . . . 13
8.2. Salting . . . . . . . . . . . . . . . . . . . . . . . . . 14 8.2. Salting . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.3. Hash Collision . . . . . . . . . . . . . . . . . . . . . . 14 8.3. Iterations . . . . . . . . . . . . . . . . . . . . . . . . 15
8.3.1. Avoiding Hash Collisions during generation . . . . . . 15 8.4. Hash Collision . . . . . . . . . . . . . . . . . . . . . . 16
8.3.2. Second Preimage Requirement Analysis . . . . . . . . . 15 8.4.1. Avoiding Hash Collisions during generation . . . . . . 16
8.3.3. Possible Hash Value Truncation Method . . . . . . . . 15 8.4.2. Second Preimage Requirement Analysis . . . . . . . . . 16
8.3.4. Server Response to a Run-time Collision . . . . . . . 16 8.4.3. Possible Hash Value Truncation Method . . . . . . . . 17
9. Performance Considerations . . . . . . . . . . . . . . . . . . 16 8.4.4. Server Response to a Run-time Collision . . . . . . . 17
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 8.4.5. Parameters that Cover the Zone . . . . . . . . . . . . 18
11. Security Considerations . . . . . . . . . . . . . . . . . . . 17 9. Performance Considerations . . . . . . . . . . . . . . . . . . 18
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
12.1. Normative References . . . . . . . . . . . . . . . . . . . 19 11. Security Considerations . . . . . . . . . . . . . . . . . . . 18
12.2. Informative References . . . . . . . . . . . . . . . . . . 20 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
12.1. Normative References . . . . . . . . . . . . . . . . . . . 21
12.2. Informative References . . . . . . . . . . . . . . . . . . 22
Editorial Comments . . . . . . . . . . . . . . . . . . . . . . . . Editorial Comments . . . . . . . . . . . . . . . . . . . . . . . .
Appendix A. Example Zone . . . . . . . . . . . . . . . . . . . . 20 Appendix A. Example Zone . . . . . . . . . . . . . . . . . . . . 22
Appendix B. Example Responses . . . . . . . . . . . . . . . . . . 25 Appendix B. Example Responses . . . . . . . . . . . . . . . . . . 27
B.1. answer . . . . . . . . . . . . . . . . . . . . . . . . . . 25 B.1. answer . . . . . . . . . . . . . . . . . . . . . . . . . . 27
B.1.1. Authenticating the Example DNSKEY RRset . . . . . . . 27 B.1.1. Authenticating the Example DNSKEY RRset . . . . . . . 29
B.2. Name Error . . . . . . . . . . . . . . . . . . . . . . . . 28 B.2. Name Error . . . . . . . . . . . . . . . . . . . . . . . . 30
B.3. No Data Error . . . . . . . . . . . . . . . . . . . . . . 30 B.3. No Data Error . . . . . . . . . . . . . . . . . . . . . . 32
B.3.1. No Data Error, Empty Non-Terminal . . . . . . . . . . 31 B.3.1. No Data Error, Empty Non-Terminal . . . . . . . . . . 33
B.4. Referral to Signed Zone . . . . . . . . . . . . . . . . . 32 B.4. Referral to Signed Zone . . . . . . . . . . . . . . . . . 34
B.5. Referral to Unsigned Zone using the Opt-In Flag . . . . . 33 B.5. Referral to Unsigned Zone using the Opt-In Flag . . . . . 35
B.6. Wildcard Expansion . . . . . . . . . . . . . . . . . . . . 34 B.6. Wildcard Expansion . . . . . . . . . . . . . . . . . . . . 36
B.7. Wildcard No Data Error . . . . . . . . . . . . . . . . . . 36 B.7. Wildcard No Data Error . . . . . . . . . . . . . . . . . . 38
B.8. DS Child Zone No Data Error . . . . . . . . . . . . . . . 37 B.8. DS Child Zone No Data Error . . . . . . . . . . . . . . . 39
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 41
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 39 Intellectual Property and Copyright Statements . . . . . . . . . . 42
Intellectual Property and Copyright Statements . . . . . . . . . . 40
1. Introduction 1. Introduction
1.1. Rationale 1.1. Rationale
The DNS Security Extensions included the NSEC RR to provide The DNS Security Extensions included the NSEC RR to provide
authenticated denial of existence. Though the NSEC RR meets the authenticated denial of existence. Though the NSEC RR meets the
requirements for authenticated denial of existence, it introduced a requirements for authenticated denial of existence, it introduced a
side-effect in that the contents of a zone can be enumerated. This side-effect in that the contents of a zone can be enumerated. This
property introduces undesired policy issues. property introduces undesired policy issues.
skipping to change at page 5, line 13 skipping to change at page 5, line 13
the domains within a zone, is known as "zone enumeration". Zone the domains within a zone, is known as "zone enumeration". Zone
enumeration was not practical prior to the introduction of DNSSEC. enumeration was not practical prior to the introduction of DNSSEC.
In this document the term "original ownername" refers to a standard In this document the term "original ownername" refers to a standard
ownername. Because this proposal uses the result of a hash function ownername. Because this proposal uses the result of a hash function
over the original (unmodified) ownername, this result is referred to over the original (unmodified) ownername, this result is referred to
as "hashed ownername". as "hashed ownername".
"Hash order" means the order in which hashed ownernames are arranged "Hash order" means the order in which hashed ownernames are arranged
according to their numerical value, treating the leftmost (lowest according to their numerical value, treating the leftmost (lowest
numbered) octet as the most significant octet. Note that this numbered) octet as the most significant octet. Note that this is the
differs from the canonical ordering specified in RFC 4034 [4]. same as the canonical ordering specified in RFC 4034 [4].
An "empty non-terminal" is a domain name that owns no resource An "empty non-terminal" is a domain name that owns no resource
records but has subdomains that do. records but has subdomains that do.
The "closest encloser" of a (nonexistent) domain name is the longest The "closest encloser" of a (nonexistent) domain name is the longest
domain name, including empty non-terminals, that matches the domain name, including empty non-terminals, that matches the
rightmost part of the nonexistent domain name. rightmost part of the nonexistent domain name.
"Base32 encoding" is "Base 32 Encoding with Extended Hex Alphabet" as "Base32 encoding" is "Base 32 Encoding with Extended Hex Alphabet" as
specified in 3548-bis [15]. specified in RFC 3548bis [15].
2. NSEC versus NSEC3 2. NSEC versus NSEC3
This document does NOT obsolete the NSEC record, but gives an This document does NOT obsolete the NSEC record, but gives an
alternative for authenticated denial of existence. NSEC and NSEC3 alternative for authenticated denial of existence. NSEC and NSEC3
RRs can not co-exist in a zone. See draft-vixie-dnssec-ter [14] for RRs can not co-exist in a zone. See draft-vixie-dnssec-ter [14] for
a signaling mechanism to allow for graceful transition towards NSEC3. a signaling mechanism to allow for graceful transition towards NSEC3.
3. The NSEC3 Resource Record 3. The NSEC3 Resource Record
skipping to change at page 6, line 31 skipping to change at page 6, line 31
The NSEC3 RR SHOULD have the same TTL value as the SOA minimum TTL The NSEC3 RR SHOULD have the same TTL value as the SOA minimum TTL
field. This is in the spirit of negative caching [8]. field. This is in the spirit of negative caching [8].
3.1. NSEC3 RDATA Wire Format 3.1. NSEC3 RDATA Wire Format
The RDATA of the NSEC3 RR is as shown below: The RDATA of the NSEC3 RR is as shown below:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|O|Hash Function| Iterations | | Hash Function |O| Iterations |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Salt Length | Salt / | Salt Length | Salt /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ Next Hashed Ownername / / Next Hashed Ownername /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ Type Bit Maps / / Type Bit Maps /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
"O" is the Opt-In Flag field. "O" is the Opt-In Flag field.
3.1.1. The Opt-In Flag Field 3.1.1. The Hash Function Field
The Hash Function field identifies the cryptographic hash function
used to construct the hash-value.
The values are as defined for the DS record (see RFC 3658 [10]).
On reception, a resolver MUST ignore an NSEC3 RR with an unknown hash
function value.
3.1.2. The Opt-In Flag Field
The Opt-In Flag field indicates whether this NSEC3 RR covers unsigned The Opt-In Flag field indicates whether this NSEC3 RR covers unsigned
delegations. delegations.
In DNSSEC, NS RRsets at delegation points are not signed, and may be In DNSSEC, NS RRsets at delegation points are not signed, and may be
accompanied by a DS record. The security status of the subzone is accompanied by a DS record. The security status of the subzone is
determined by the presence or absence of the DS RRset, determined by the presence or absence of the DS RRset,
cryptographically proven by the NSEC record or the signed DS RRset. cryptographically proven by the NSEC record or the signed DS RRset.
The presence of the Opt-In flag expands this definition by allowing The presence of the Opt-In flag expands this definition by allowing
insecure delegations to exist within an otherwise signed zone without insecure delegations to exist within an otherwise signed zone without
skipping to change at page 7, line 47 skipping to change at page 8, line 11
o A non Opt-In NSEC3 type is identified by an Opt-In Flag field o A non Opt-In NSEC3 type is identified by an Opt-In Flag field
value of 0. value of 0.
and, and,
o An Opt-In NSEC3 record does not assert the non-existence of a hash o An Opt-In NSEC3 record does not assert the non-existence of a hash
ownername between its ownername and next hashed ownername, ownername between its ownername and next hashed ownername,
although it does assert that any hashed name in this span MUST be although it does assert that any hashed name in this span MUST be
of an insecure delegation. of an insecure delegation.
o An Opt-In NSEC3 record does assert the (non)existence of RRsets o An Opt-In NSEC3 record does assert the (non)existence of RRsets
with the same hashed owner name. with the same hashed owner name.
3.1.2. The Hash Function Field
The Hash Function field identifies the cryptographic hash function
used to construct the hash-value.
The values are as defined for the DS record (see RFC 3658 [10]).
[Comment.1]
On reception, a resolver MUST ignore an NSEC3 RR with an unknown hash
function value.
3.1.3. The Iterations Field 3.1.3. The Iterations Field
The Iterations field defines the number of times the hash has been The Iterations field defines the number of times the hash has been
iterated. More iterations results in greater resiliency of the hash iterated. More iterations results in greater resiliency of the hash
value against dictionary attacks, but at a higher cost for both the value against dictionary attacks, but at a higher cost for both the
server and resolver. See Section 5 for details of this field's use. server and resolver. See Section 5 for details of this field's use.
Iterations make an attack more costly by making the hash computation
more computationally intensive, e.g. by iterating the hash function a
number of times.
When generating a few hashes this performance loss will not be a
problem, as a validator can handle a delay of a few milliseconds.
But when doing a dictionary attack it will also multiply the attack
workload by a factor, which is a problem for the attacker.
3.1.4. The Salt Length Field 3.1.4. The Salt Length Field
The salt length field defines the length of the salt in octets. The salt length field defines the length of the salt in octets.
3.1.5. The Salt Field 3.1.5. The Salt Field
The Salt field is not present when the Salt Length Field has a value The Salt field is not present when the Salt Length Field has a value
of 0. of 0.
The Salt field is appended to the original ownername before hashing The Salt field is appended to the original ownername before hashing
in order to defend against precalculated dictionary attacks. See in order to defend against precalculated dictionary attacks. See
Section 5 for details on how the salt is used. Section 5 for details on how the salt is used.
Salt is used to make dictionary attacks using precomputation more
costly. A dictionary can only be computed after the attacker has the
salt, hence a new salt means that the dictionary has to be
regenerated with the new salt.
There MUST be a complete set of NSEC3 records covering the entire There MUST be a complete set of NSEC3 records covering the entire
zone that use the same salt value. The requirement exists so that, zone that use the same salt value. The requirement exists so that,
given any qname within a zone, a single covering NSEC3 rrset may be given any qname within a zone, at least one covering NSEC3 RRset may
found. While it may be theoretically possible to produce a set of be found. While it may be theoretically possible to produce a set of
NSEC3s that use different salts that cover the entire zone, it is NSEC3s that use different salts that cover the entire zone, it is
computationally infeasible to generate such a set. See Section 8.2 computationally infeasible to generate such a set. See Section 8.2
for further discussion. for further discussion.
The salt value SHOULD be changed from time to time - this is to The salt value SHOULD be changed from time to time - this is to
prevent the use of a precomputed dictionary to reduce the cost of prevent the use of a precomputed dictionary to reduce the cost of
enumeration. enumeration.
3.1.6. The Next Hashed Ownername Field 3.1.6. The Next Hashed Ownername Field
The Next Hashed Ownername field contains the next hashed ownername in The Next Hashed Ownername field contains the next hashed ownername in
hash order. That is, given the set of all hashed owernames, the Next hash order. That is, given the set of all hashed owernames, the Next
Hashed Ownername contains the hash value that immediately follows the Hashed Ownername contains the hash value that immediately follows the
owner hash value for the given NSEC3 record. The value of the Next owner hash value for the given NSEC3 record. The value of the Next
Hashed Ownername Field in the last NSEC3 record in the zone is the Hashed Ownername Field in the last NSEC3 record in the zone is the
same as the ownername of the first NSEC3 RR in the zone in hash same as the ownername of the first NSEC3 RR in the zone in hash
order. order.
Hashed ownernames of glue RRsets MUST NOT be listed in the Next Hashed ownernames of glue RRsets MUST NOT be listed in the Next
Hashed Ownername unless at least one authoritative RRset exists at Hashed Ownername unless at least one authoritative RRset exists at
the same ownername. Hashed ownernames of delegation NS rrsets MUST the same ownername. Hashed ownernames of delegation NS RRsets MUST
be listed if the Opt-In bit is clear. be listed if the Opt-In bit is clear.
Note that the Next Hashed Ownername field is not encoded, unlike the Note that the Next Hashed Ownername field is not encoded, unlike the
NSEC3 RR's ownername. It is the unmodified binary hash value. It NSEC3 RR's ownername. It is the unmodified binary hash value. It
does not include the name of the containing zone. does not include the name of the containing zone.
The length of this field is the length of the hash value produced by The length of this field is the length of the hash value produced by
the hash function selected by the Hash Function field. the hash function selected by the Hash Function field.
3.1.7. The Type Bit Maps Field 3.1.7. The Type Bit Maps Field
skipping to change at page 11, line 7 skipping to change at page 11, line 20
by a wildcard, it is necessary to prove the existence of its closest by a wildcard, it is necessary to prove the existence of its closest
encloser. A closest encloser might be an empty non-terminal. encloser. A closest encloser might be an empty non-terminal.
Additional NSEC3 RRs are generated for empty non-terminals. These Additional NSEC3 RRs are generated for empty non-terminals. These
additional NSEC3 RRs are identical in format to NSEC3 RRs that cover additional NSEC3 RRs are identical in format to NSEC3 RRs that cover
existing RRs in the zone except that their type-maps only indicated existing RRs in the zone except that their type-maps only indicated
the existence of an NSEC3 RRset and an RRSIG RRset. the existence of an NSEC3 RRset and an RRSIG RRset.
This relaxes the requirement in Section 2.3 of RFC4035 that NSEC RRs This relaxes the requirement in Section 2.3 of RFC4035 that NSEC RRs
not appear at names that did not exist before the zone was signed. not appear at names that did not exist before the zone was signed.
[Comment.2] [Comment.1]
5. Calculation of the Hash 5. Calculation of the Hash
Define H(x) to be the hash of x using the hash function selected by Define H(x) to be the hash of x using the hash function selected by
the NSEC3 record and || to indicate concatenation. Then define: the NSEC3 record and || to indicate concatenation. Then define:
IH(salt,x,0)=H(x || salt) IH(salt,x,0)=H(x || salt)
IH(salt,x,k)=H(IH(salt,x,k-1) || salt) if k > 0 IH(salt,x,k)=H(IH(salt,x,k-1) || salt) if k > 0
skipping to change at page 12, line 6 skipping to change at page 12, line 20
Each empty non-terminal MUST have an NSEC3 record. Each empty non-terminal MUST have an NSEC3 record.
The TTL value for any NSEC3 RR SHOULD be the same as the minimum TTL The TTL value for any NSEC3 RR SHOULD be the same as the minimum TTL
value field in the zone SOA RR. value field in the zone SOA RR.
The type bitmap of every NSEC3 resource record in a signed zone MUST The type bitmap of every NSEC3 resource record in a signed zone MUST
indicate the presence of both the NSEC3 RR type itself and its indicate the presence of both the NSEC3 RR type itself and its
corresponding RRSIG RR type. corresponding RRSIG RR type.
The following steps describe the proper construction of NSEC3 The following steps describe the proper construction of NSEC3
records. [Comment.3] records. [Comment.2]
1. For each unique original ownername in the zone, add an NSEC3 1. For each unique original ownername in the zone, add an NSEC3
RRset. If Opt-In is being used, ownernames of unsigned RRset. If Opt-In is being used, ownernames of unsigned
delegations may be excluded, but must be considered for empty- delegations may be excluded, but must be considered for empty-
non-terminals. The ownername of the NSEC3 RR is the hashed non-terminals. The ownername of the NSEC3 RR is the hashed
equivalent of the original owner name, prepended to the zone equivalent of the original owner name, prepended to the zone
name. The Next Hashed Ownername field is left blank for the name. The Next Hashed Ownername field is left blank for the
moment. If Opt-In is being used, set the Opt-In bit to one. moment. If Opt-In is being used, set the Opt-In bit to one.
2. For each RRset at the original owner name, set the corresponding 2. For each RRset at the original owner name, set the corresponding
bit in the type bit map. bit in the type bit map.
3. If the difference in number of labels between the apex and the 3. If the difference in number of labels between the apex and the
skipping to change at page 12, line 33 skipping to change at page 12, line 47
5. Combine NSEC3 RRs with identical hashed ownernames by replacing 5. Combine NSEC3 RRs with identical hashed ownernames by replacing
with a single NSEC3 RR with the type map consisting of the union with a single NSEC3 RR with the type map consisting of the union
of the types represented by the set of NSEC3 RRs. of the types represented by the set of NSEC3 RRs.
6. In each NSEC3 RR, insert the Next Hashed Ownername by using the 6. In each NSEC3 RR, insert the Next Hashed Ownername by using the
value of the next NSEC3 RR in hash order. The Next Hashed value of the next NSEC3 RR in hash order. The Next Hashed
Ownername of the last NSEC3 in the zone contains the value of the Ownername of the last NSEC3 in the zone contains the value of the
hashed ownername of the first NSEC3 in the hash order. hashed ownername of the first NSEC3 in the hash order.
7. Responding to NSEC3 Queries 7. Responding to NSEC3 Queries
Since NSEC3 records do not correspond to names that exist within the Since NSEC3 ownernames are not represented in the NSEC3 chain like
zone, there is the potential for confusion when responding to queries other zone ownernames, direct queries for NSEC3 ownernames present a
that have the QTYPE set to NSEC3 (or ANY). In order to avoid special case.
creating an infinite recursion, there is only one consistent way to
respond to NSEC3 queries, and that is to act as if the NSEC3 record
did not exist.
So, if presented with a query where QTYPE is NSEC3 and QNAME is a The special case arises when the following are all true:
name that exists in the zone with an RRTYPE other than NSEC3, then o The QNAME equals an existing NSEC3 ownername, and
the responder should deny the existence of the NSEC3 RRSet and prove o There are no other record types that exist at QNAME, and
it with an NSEC3 record corresponding to the hash of the QNAME (which o The QTYPE does not equal NSEC3.
will, of course, exist), as usual. These conditions describe a particular case: the answer should be a
NOERROR/NODATA response, but there is no NSEC3 RRset for H(QNAME) to
include in the authority section.
If the QTYPE is NSEC3 and QNAME is a name that only exists by virtue However, the NSEC3 RRset with ownername equal to QNAME is able to
of an NSEC3 record at that name, then the response should be an prove its own existence. Thus, when answering this query, the
NXDOMAIN with appropriate NSEC3 records as proof. authoritative server MUST include the NSEC3 RRset whose ownername
equals QNAME. This RRset proves that QNAME is an existing name with
types NSEC3 and RRSIG. The authoritative server MUST also include
the NSEC3 RRset that covers the hash of QNAME. This RRset proves
that no other types exist.
When validating a NOERROR/NODATA response, validators MUST check for
a NSEC3 RRset with ownername equals to QNAME, and MUST accept that
(validated) NSEC3 RRset as proof that QNAME exists. The validator
MUST also check for an NSEC3 RRset that covers the hash of QNAME as
proof that QTYPE doesn't exist.
Other cases where the QNAME equals an existing NSEC3 ownername may be
answered normally.
8. Special Considerations 8. Special Considerations
The following paragraphs clarify specific behaviour explain special The following paragraphs clarify specific behaviour explain special
considerations for implementations. considerations for implementations.
8.1. Proving Nonexistence 8.1. Proving Nonexistence
If a wildcard resource record appears in a zone, its asterisk label If a wildcard resource record appears in a zone, its asterisk label
is treated as a literal symbol and is treated in the same way as any is treated as a literal symbol and is treated in the same way as any
skipping to change at page 14, line 12 skipping to change at page 14, line 38
the resolver to be denied by one of the returned NSEC3s, since, by the resolver to be denied by one of the returned NSEC3s, since, by
definition, all these names exist and so cannot appear within the definition, all these names exist and so cannot appear within the
range covered by an NSEC3. Note, however, that the first name that range covered by an NSEC3. Note, however, that the first name that
the resolver tries MUST be the apex of the zone, since names above the resolver tries MUST be the apex of the zone, since names above
the apex could be denied by one of the returned NSEC3s. the apex could be denied by one of the returned NSEC3s.
8.2. Salting 8.2. Salting
Augmenting original ownernames with salt before hashing increases the Augmenting original ownernames with salt before hashing increases the
cost of a dictionary of pre-generated hash-values. For every bit of cost of a dictionary of pre-generated hash-values. For every bit of
salt, the cost of the dictionary doubles. The NSEC3 RR can use a salt, the cost of a precomputed dictionary doubles (because there
maximum of 2040 bits (255 octets) of salt, multiplying the cost by must be an entry for each word combined with each possible salt
2^2040. value). The NSEC3 RR can use a maximum of 2040 bits (255 octets) of
salt, multiplying the cost by 2^2040. This means that an attacker
must, in practice, recompute the dictionary each time the salt is
changed.
There MUST be a complete set of NSEC3s for the zone using the same There MUST be at least one complete set of NSEC3s for the zone using
salt value. the same salt value.
The salt SHOULD be changed periodically to prevent precomputation The salt SHOULD be changed periodically to prevent precomputation
using a single salt. It is RECOMMENDED that the salt be changed for using a single salt. It is RECOMMENDED that the salt be changed for
every resigning. every resigning.
Note that this could cause a resolver to see records with different Note that this could cause a resolver to see records with different
salt values for the same zone. This is harmless, since each record salt values for the same zone. This is harmless, since each record
stands alone (that is, it denies the set of ownernames whose hashes, stands alone (that is, it denies the set of ownernames whose hashes,
using the salt in the NSEC3 record, fall between the two hashes in using the salt in the NSEC3 record, fall between the two hashes in
the NSEC3 record) - it is only the server that needs a complete set the NSEC3 record) - it is only the server that needs a complete set
skipping to change at page 14, line 43 skipping to change at page 15, line 25
able to consistently find covering NSEC3 RRs, the authoritative able to consistently find covering NSEC3 RRs, the authoritative
server MUST choose a single set of parameters (algorithm, salt, and server MUST choose a single set of parameters (algorithm, salt, and
iterations) to use when selecting NSEC3s. In the absence of any iterations) to use when selecting NSEC3s. In the absence of any
other metadata, the server does this by using the parameters from the other metadata, the server does this by using the parameters from the
zone apex NSEC3, recognizable by the presence of the SOA bit in the zone apex NSEC3, recognizable by the presence of the SOA bit in the
type map. If there is more than one NSEC3 record that meets this type map. If there is more than one NSEC3 record that meets this
description, then the server may arbitrarily choose one. Because of description, then the server may arbitrarily choose one. Because of
this, if there is a zone apex NSEC3 RR within a zone, it MUST be part this, if there is a zone apex NSEC3 RR within a zone, it MUST be part
of a complete NSEC3 set. Conversely, if there exists an incomplete of a complete NSEC3 set. Conversely, if there exists an incomplete
set of NSEC3 RRs using the same parameters within a zone, there MUST set of NSEC3 RRs using the same parameters within a zone, there MUST
NOT be an NSEC3 RR with the SOA bit set present. NOT be an NSEC3 RR using those parameters with the SOA bit set.
8.3. Hash Collision 8.3. Iterations
Setting the number of iterations used allows the zone owner to choose
the cost of computing a hash, and so the cost of generating a
dictionary. Note that this is distinct from the effect of salt,
which prevents the use of a single precomputed dictionary for all
time.
Obviously the number of iterations also affects the zone owner's cost
of signing the zone as well as the verifiers cost of verifying the
zone. We therefore impose an upper limit on the number of
iterations. We base this on the number of iterations that
approximately doubles the cost of signing the zone.
A zone owner MUST NOT use a value higher than shown in the table
below for iterations. A resolver MAY treat a response with a higher
value as bogus.
+--------------+------------+
| RSA Key Size | Iterations |
+--------------+------------+
| 1024 | 3,000 |
| 2048 | 20,000 |
| 4096 | 150,000 |
+--------------+------------+
+--------------+------------+
| DSA Key Size | Iterations |
+--------------+------------+
| 1024 | 1,500 |
| 2048 | 5,000 |
+--------------+------------+
This table is based on 150,000 SHA-1's per second, 50 RSA signs per
second for 1024 bit keys, 7 signs per second for 2048 bit keys, 1
sign per second for 4096 bit keys, 100 DSA signs per second for 1024
bit keys and 30 signs per second for 2048 bit keys.
Note that since RSA verifications are 10-100 times faster than
signatures (depending on key size), in the case of RSA the legal
values of iterations can substantially increase the cost of
verification.
8.4. Hash Collision
Hash collisions occur when different messages have the same hash Hash collisions occur when different messages have the same hash
value. The expected number of domain names needed to give a 1 in 2 value. The expected number of domain names needed to give a 1 in 2
chance of a single collision is about 2^(n/2) for a hash of length n chance of a single collision is about 2^(n/2) for a hash of length n
bits (i.e. 2^80 for SHA-1). Though this probability is extremely bits (i.e. 2^80 for SHA-1). Though this probability is extremely
low, the following paragraphs deal with avoiding collisions and low, the following paragraphs deal with avoiding collisions and
assessing possible damage in the event of an attack using hash assessing possible damage in the event of an attack using hash
collisions. collisions.
8.3.1. Avoiding Hash Collisions during generation 8.4.1. Avoiding Hash Collisions during generation
During generation of NSEC3 RRs, hash values are supposedly unique. During generation of NSEC3 RRs, hash values are supposedly unique.
In the (academic) case of a collision occurring, an alternative salt In the (academic) case of a collision occurring, an alternative salt
MUST be chosen and all hash values MUST be regenerated. MUST be chosen and all hash values MUST be regenerated.
8.3.2. Second Preimage Requirement Analysis 8.4.2. Second Preimage Requirement Analysis
A cryptographic hash function has a second-preimage resistance A cryptographic hash function has a second-preimage resistance
property. The second-preimage resistance property means that it is property. The second-preimage resistance property means that it is
computationally infeasible to find another message with the same hash computationally infeasible to find another message with the same hash
value as a given message, i.e. given preimage X, to find a second value as a given message, i.e. given preimage X, to find a second
preimage X' != X such that hash(X) = hash(X'). The work factor for preimage X' != X such that hash(X) = hash(X'). The work factor for
finding a second preimage is of the order of 2^160 for SHA-1. To finding a second preimage is of the order of 2^160 for SHA-1. To
mount an attack using an existing NSEC3 RR, an adversary needs to mount an attack using an existing NSEC3 RR, an adversary needs to
find a second preimage. find a second preimage.
Assuming an adversary is capable of mounting such an extreme attack, Assuming an adversary is capable of mounting such an extreme attack,
the actual damage is that a response message can be generated which the actual damage is that a response message can be generated which
claims that a certain QNAME (i.e. the second pre-image) does exist, claims that a certain QNAME (i.e. the second pre-image) does exist,
while in reality QNAME does not exist (a false positive), which will while in reality QNAME does not exist (a false positive), which will
either cause a security aware resolver to re-query for the non- either cause a security aware resolver to re-query for the non-
existent name, or to fail the initial query. Note that the adversary existent name, or to fail the initial query. Note that the adversary
can't mount this attack on an existing name but only on a name that can't mount this attack on an existing name but only on a name that
the adversary can't choose and does not yet exist. the adversary can't choose and does not yet exist.
8.3.3. Possible Hash Value Truncation Method 8.4.3. Possible Hash Value Truncation Method
The previous sections outlined the low probability and low impact of The previous sections outlined the low probability and low impact of
a second-preimage attack. When impact and probability are low, while a second-preimage attack. When impact and probability are low, while
space in a DNS message is costly, truncation is tempting. Truncation space in a DNS message is costly, truncation is tempting. Truncation
might be considered to allow for shorter ownernames and rdata for might be considered to allow for shorter ownernames and rdata for
hashed labels. In general, if a cryptographic hash is truncated to n hashed labels. In general, if a cryptographic hash is truncated to n
bits, then the expected number of domains required to give a 1 in 2 bits, then the expected number of domains required to give a 1 in 2
probability of a single collision is approximately 2^(n/2) and the probability of a single collision is approximately 2^(n/2) and the
work factor to produce a second preimage is 2^n. work factor to produce a second preimage is 2^n.
skipping to change at page 16, line 18 skipping to change at page 17, line 42
and limited space in DNS messages, the balance between truncation and limited space in DNS messages, the balance between truncation
profit and collision damage may be determined by local policy. Of profit and collision damage may be determined by local policy. Of
course, the size of the corresponding RRSIG RR is not reduced, so course, the size of the corresponding RRSIG RR is not reduced, so
truncation is of limited benefit. truncation is of limited benefit.
Truncation could be signaled simply by reducing the length of the Truncation could be signaled simply by reducing the length of the
first label in the ownername. Note that there would have to be a first label in the ownername. Note that there would have to be a
corresponding reduction in the length of the Next Hashed Ownername corresponding reduction in the length of the Next Hashed Ownername
field. field.
8.3.4. Server Response to a Run-time Collision 8.4.4. Server Response to a Run-time Collision
In the astronomically unlikely event that a server is unable to prove In the astronomically unlikely event that a server is unable to prove
nonexistence because the hash of the name that does not exist nonexistence because the hash of the name that does not exist
collides with a name that does exist, the server is obviously broken, collides with a name that does exist, the server is obviously broken,
and should, therefore, return a response with an RCODE of 2 (server and should, therefore, return a response with an RCODE of 2 (server
failure). failure).
8.4.5. Parameters that Cover the Zone
Secondary servers (and perhaps other entities) need to reliably
determine which NSEC3 parameters (that is, hash, salt and iterations)
are present at every hashed ownername, in order to be able to choose
an appropriate set of NSEC3 records for negative responses. This is
indicated by the parameters at the apex: any set of parameters that
is used in an NSEC3 record whose original ownername is the apex of
the zone MUST be present throughout the zone.
A method to determine which NSEC3 in a complete chain corresponds to
the apex is to look for a NSEC3 RRset which has the SOA bit set in
the RDATA bit type maps field.
9. Performance Considerations 9. Performance Considerations
Iterated hashes imposes a performance penalty on both authoritative Iterated hashes impose a performance penalty on both authoritative
servers and resolvers. Therefore, the number of iterations should be servers and resolvers. Therefore, the number of iterations should be
carefully chosen. In particular it should be noted that a high value carefully chosen. In particular it should be noted that a high value
for iterations gives an attacker a very good denial of service for iterations gives an attacker a very good denial of service
attack, since the attacker need not bother to verify the results of attack, since the attacker need not bother to verify the results of
their queries, and hence has no performance penalty of his own. their queries, and hence has no performance penalty of his own.
On the other hand, nameservers with low query rates and limited On the other hand, nameservers with low query rates and limited
bandwidth are already subject to a bandwidth based denial of service bandwidth are already subject to a bandwidth based denial of service
attack, since responses are typically an order of magnitude larger attack, since responses are typically an order of magnitude larger
than queries, and hence these servers may choose a high value of than queries, and hence these servers may choose a high value of
skipping to change at page 17, line 38 skipping to change at page 19, line 31
Walking the NSEC3 RRs will reveal the total number of records in the Walking the NSEC3 RRs will reveal the total number of records in the
zone, and also what types they are. This could be mitigated by zone, and also what types they are. This could be mitigated by
adding dummy entries, but certainly an upper limit can always be adding dummy entries, but certainly an upper limit can always be
found. found.
Hash collisions may occur. If they do, it will be impossible to Hash collisions may occur. If they do, it will be impossible to
prove the non-existence of the colliding domain - however, this is prove the non-existence of the colliding domain - however, this is
fantastically unlikely, and, in any case, DNSSEC already relies on fantastically unlikely, and, in any case, DNSSEC already relies on
SHA-1 to not collide. SHA-1 to not collide.
Responses to queries where QNAME equals an NSEC3 ownername that has
no other types may be undetectably changed from a NOERROR/NODATA
response to a NAME ERROR response.
The Opt-In Flag (O) allows for unsigned names, in the form of The Opt-In Flag (O) allows for unsigned names, in the form of
delegations to unsigned subzones, to exist within an otherwise signed delegations to unsigned subzones, to exist within an otherwise signed
zone. All unsigned names are, by definition, insecure, and their zone. All unsigned names are, by definition, insecure, and their
validity or existence cannot by cryptographically proven. validity or existence cannot by cryptographically proven.
In general: In general:
Records with unsigned names (whether existing or not) suffer from Records with unsigned names (whether existing or not) suffer from
the same vulnerabilities as records in an unsigned zone. These the same vulnerabilities as records in an unsigned zone. These
vulnerabilities are described in more detail in [16] (note in vulnerabilities are described in more detail in [16] (note in
particular sections 2.3, "Name Games" and 2.6, "Authenticated particular sections 2.3, "Name Games" and 2.6, "Authenticated
skipping to change at page 20, line 19 skipping to change at page 22, line 19
[15] Josefsson, Ed., S,., "The Base16, Base32, and Base64 Data [15] Josefsson, Ed., S,., "The Base16, Base32, and Base64 Data
Encodings.", draft-josefsson-rfc3548bis-00 (work in progress), Encodings.", draft-josefsson-rfc3548bis-00 (work in progress),
October 2005. October 2005.
[16] Atkins, D. and R. Austein, "Threat Analysis of the Domain Name [16] Atkins, D. and R. Austein, "Threat Analysis of the Domain Name
System (DNS)", RFC 3833, August 2004. System (DNS)", RFC 3833, August 2004.
Editorial Comments Editorial Comments
[Comment.1] This is an inconsistency in the document -- this [Comment.1] Although, strictly speaking, the names *did* exist.
document both refers to the RFC and proceeds to define
its own registry. Furthermore, it only allocates 7 bits
for this value, where DS allocates 8.
[Comment.2] Although, strictly speaking, the names *did* exist.
[Comment.3] Note that this method makes it impossible to detect [Comment.2] Note that this method makes it impossible to detect
(extremely unlikely) hash collisions. (extremely unlikely) hash collisions.
Appendix A. Example Zone Appendix A. Example Zone
This is a zone showing its NSEC3 records. They can also be used as This is a zone showing its NSEC3 records. They can also be used as
test vectors for the hash algorithm. test vectors for the hash algorithm.
The data in the example zone is currently broken, as it uses a The data in the example zone is currently broken, as it uses a
different base32 alphabet. This shall be fixed in the next release. different base32 alphabet. This shall be fixed in the next release.
skipping to change at page 39, line 20 skipping to change at page 41, line 20
London W3 7LR London W3 7LR
England England
Phone: +44 (20) 8735 0686 Phone: +44 (20) 8735 0686
Email: ben@algroup.co.uk Email: ben@algroup.co.uk
Geoffrey Sisson Geoffrey Sisson
Nominet Nominet
Roy Arends Roy Arends
Telematica Instituut Nominet
Brouwerijstraat 1
7523 XC Enschede
The Netherlands
Phone: +31 (53) 485 0485
Email: roy.arends@telin.nl
Intellectual Property Statement Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be on the procedures with respect to rights in RFC documents can be
skipping to change at page 40, line 41 skipping to change at page 42, line 41
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement Copyright Statement
Copyright (C) The Internet Society (2005). This document is subject Copyright (C) The Internet Society (2006). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights. except as set forth therein, the authors retain all their rights.
Acknowledgment Acknowledgment
Funding for the RFC Editor function is currently provided by the Funding for the RFC Editor function is currently provided by the
Internet Society. Internet Society.
 End of changes. 38 change blocks. 
99 lines changed or deleted 176 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/