NSEC3 zone signing support

[asannes]

Motivation

I wanted to test NSEC3 zone signing and found sign_zone in dns/dnssec.py:

def sign_zone(
...
        if nsec3:
            raise NotImplementedError("Signing with NSEC3 not yet implemented")
	else:
            ...
            return _sign_zone_nsec(zone, _txn, _rrset_signer)

And I was thinking I could make a go at implementing it, this being my first
try at a contribution to dnspython I figured I would outline my approach
first before wasting your time on a PR that might be going in the wrong
direction. From what I can see, all the bits need is in the dnspython code base already.

Describe the solution you'd like.

I want to make a functional NSEC3 signing implementation.

From what I can see, it would basically be implementing in the dnssec.py
file (after _sign_zone_nsec):

def _sign_zone_nsec3(
    zone: dns.zone.Zone,
    txn: dns.transaction.Transaction,
    nsec3param: NSEC3PARAM,
    rrset_signer: RRsetSigner | None = None,
) -> None:
    """NSEC3 zone signer"""

Re-using rrset_signer to sign the rrset and creating the NSEC3 name chains
as described in https://datatracker.ietf.org/doc/html/rfc5155#section-7.1:

1.  Select the hash algorithm and the values for salt and iterations.

This is what nsec3param contains (slots = ["algorithm", "flags", "iterations",
"salt"]).

2.  For each unique original owner name in the zone add an NSEC3 RR.
       *  If Opt-Out is being used, owner names of unsigned delegations
          MAY be excluded.

       *  The owner name of the NSEC3 RR is the hash of the original
          owner name, prepended as a single label to the zone name.

       *  The Next Hashed Owner Name field is left blank for the moment.

       *  If Opt-Out is being used, set the Opt-Out bit to one.

       *  For collision detection purposes, optionally keep track of the
          original owner name with the NSEC3 RR.

       *  Additionally, for collision detection purposes, optionally
          create an additional NSEC3 RR corresponding to the original
          owner name with the asterisk label prepended (i.e., as if a
          wildcard existed as a child of this owner name) and keep track
          of this original owner name.  Mark this NSEC3 RR as temporary.

The Opt-Out flag in nsec3param.flags first bit, this enables opt-out for not
secured delegations (ns, but no ds). If we want to support opt-out.

We go through all the names, we filter out not secured delegations, sign the
rdatasets, and create hashed names with nsec3_hash(). To handle collisions we
store the hash to a dict[hash str, list[name str]]. Or maybe we could just
add the types into the list up front?

The last point, is about wildcard collisions, we could defer it to the end
and iterate all the names pre-pending wildcards and seeing if there is any
collisions before creating the NSEC3 records, and raise a Nsec3Collision
exception?

3.  For each RRSet at the original owner name, set the corresponding bit in the Type Bit Maps field.  

In _sign_zone_nsec() this is done later in _txn_add_nsec(), should we try to keep it as
equal as possible?

4.  If the difference in number of labels between the apex and the      
    original owner name is greater than 1, additional NSEC3 RRs need    
    to be added for every empty non-terminal between the apex and the   
    original owner name.  This process may generate NSEC3 RRs with      
    duplicate hashed owner names.  Optionally, for collision            
    detection, track the original owner names of these NSEC3 RRs and    
    create temporary NSEC3 RRs for wildcard collisions in a similar     
    fashion to step 1.   

This should probably be solved while iterating, if there are more than one
label between the zone and the record we generate all hashes. We must then
allow to not find any rdatasets in the zone and just have the mandatory
RRSIG type set in the bitmap for it. If there is added other names for this
with data they should combine just fine.

5. Sort the set of NSEC3 RRs into hash order. 

This should be be possible by using the result of sort(hased_names.keys()) as created the steps
above.

6.  Combine NSEC3 RRs with identical hashed owner names by replacing    
    them with a single NSEC3 RR with the Type Bit Maps field            
    consisting of the union of the types represented by the set of      
    NSEC3 RRs.  If the original owner name was tracked, then            
    collisions may be detected when combining, as all of the matching   
    NSEC3 RRs should have the same original owner name.  Discard any    
    possible temporary NSEC3 RRs.

7.  In each NSEC3 RR, insert the next hashed owner name by using the    
    value of the next NSEC3 RR in hash order.  The next hashed owner    
    name of the last NSEC3 RR in the zone contains the value of the     
    hashed owner name of the first NSEC3 RR in the hash order.

The sorted list of hashed names next should be next_hash = sorted_hashes[(i + 1) % len(sorted_hashes)]. And if we have something similar to _sign_zone_nsec(),
say _sign_zone_nsec3() that takes that as a parameter and can lookup all the
rdatasets for the name to create the bitmap.

8.  Finally, add an NSEC3PARAM RR with the same Hash Algorithm,         
    Iterations, and Salt fields to the zone apex.  

Just add the NSEC3PARAM provided signed.

   If a hash collision is detected, then a new salt has to be chosen,
   and the signing process restarted.

An open question is what to do with illegal collisions between non-existant
wildcards covering real names. In the signing process it says that we should
restart with a new salt, but since nsec3param is given as a parameter, should we
throw an exception or should we randomly generate a salt and try again?

And, as it is not recommended for small and medium zone sizes, should we even support opt out?

[rthalley]

I will have to read your plan again tomorrow as I don't have enough brainpower for NSEC3 today. But, some thoughts for now... This is a difficult first dnspython project as NSEC3 is very unpleasant. NSEC3 is really only applicable if you are running a gTLD; other use cases are much better served by NSEC or by Compact Denial of Existence (RFC 9824). Do you have a use case for this, or are you proposing it because you think dnspython should be complete? You should also read RFC 9276 as modern usage doesn't need a salt or a non-zero iteration count, and using them may cause validations to fail. Please think carefully about testing as really good test coverage is needed due to NSEC3's complexity.

[asannes]

Thank you for taking a look!

My main motivation was to remove a dependency on a not maintained signing-tool for our offline zone generation.
And since we depend on dnspython anyway, it would be nice to not introduce any new dependency.

NSEC3 applies for my use-case because it protects against zone enumeration and is what is set up today.

RFC 9824 is absolutely something that we would like, but the support from the name server software we use today does not support it.

RFC 9276 have good points, I do not think I would touch anything that would alter the defaults of NSEC3PARAM in dnspython, but it should be pointed to in the documentation. And it does not tell us what to do in case of an illegal collision between *.onerecord.example.com and someotherrecordwithsamehash.example.com. That would cause us perhaps to do one iteration (or just raise an exception, if we find it unlikely enough).

The test cases that comes to mind:

• RRSIGs are still applied to all the correct rdatasets
• ordering of chain, maybe just hard-code a signing with inception/expiration/key set to something so it is easier to test
• how combining rdatasets to bitmap works
• how collisions are handled, but I would not know how to reproduce
• how unsecured delegations are handled when opt-out is set

First iteration running, basically copying _sign_zone_nsec() and adding nsec3 record and chains.

def _sign_zone_nsec3(
    zone: dns.zone.Zone,
    txn: dns.transaction.Transaction,
    nsec3param: NSEC3PARAM,
    rrset_signer: RRsetSigner | None = None,
) -> None:
    """
    NSEC3 zone signer


    """
    rrsig_ttl = zone.get_soa(txn).minimum

    def _hash_to_binary(hashed_name: str) -> bytes:
        """Convert hashed name to binary format"""
        return base64.b32decode(hashed_name.upper().translate(b32_hex_to_normal).encode())

    def _txn_add_nsec3(
                    hashed_name: str,
                    names: list[str],
                    next_hashed_name: str,
    ) -> None:
        """Add NSEC3 RR"""
        next_hashed_name_binary = _hash_to_binary(next_hashed_name)

        types = set([dns.rdatatype.RRSIG])
        for name in names:
            _node = txn.get_node(name)
            if _node:
                types |= set([rdataset.rdtype for rdataset in _node.rdatasets])

        windows = NSEC3Bitmap.from_rdtypes(list(types))
        nsec3_rrset = dns.rrset.from_rdata(
            dns.name.from_text(hashed_name, origin=zone.origin),
            rrsig_ttl,
            NSEC3(
                rdclass=zone.rdclass,
                rdtype=dns.rdatatype.RdataType.NSEC3,
                next=next_hashed_name_binary,
                windows=windows,
                algorithm=nsec3param.algorithm,
                flags=nsec3param.flags,
                iterations=nsec3param.iterations,
                salt=nsec3param.salt,
            ),
        )
        txn.add(nsec3_rrset)
        if rrset_signer:
            rrset_signer(txn, nsec3_rrset)

    def _add_hashed_name(name: dns.name.Name) -> None:
        """Add a hashed name to the hashed_names dictionary"""
        absolute_name = name.derelativize(origin=zone.origin)
        hashed_name = nsec3_hash(
            absolute_name, nsec3param.salt, nsec3param.iterations, nsec3param.algorithm,
        )
        if hashed_name not in hashed_names:
            hashed_names[hashed_name] = []
        hashed_names[hashed_name].append(name)

    # Add NSEC3PARAM to the zone
    nsec3param_rrset = dns.rrset.from_rdata(
        zone.origin,0,nsec3param,
    )
    txn.add(nsec3param_rrset)
    if rrset_signer:
        rrset_signer(txn, nsec3param_rrset)

    # TODO: Add NSEC3PARAM.OPTOUT or something?
    opt_out = (nsec3param.flags & 1) == 1
    delegation = None
    hashed_names = {} # dict<str, list<str>>()
    for name in sorted(txn.iterate_names()):
        if delegation and name.is_subdomain(delegation):
            # names below delegations are not secure
            continue
        elif txn.get(name, dns.rdatatype.NS) and name != zone.origin:
            # inside delegation
            delegation = name
        else:
            # outside delegation
            delegation = None

        if rrset_signer:
            node = txn.get_node(name)
            if node:
                for rdataset in node.rdatasets:
                    if rdataset.rdtype == dns.rdatatype.RRSIG:
                        # do not sign RRSIGs
                        continue
                    elif delegation and rdataset.rdtype != dns.rdatatype.DS:
                        # do not sign delegations except DS records
                        continue
                    else:
                        rrset = dns.rrset.from_rdata(name, rdataset.ttl, *rdataset)
                        rrset_signer(txn, rrset)

        # do not add NSEC3 RRs for unsecured delegations
        if not delegation or not opt_out or txn.get(name, dns.rdatatype.DS):
            _add_hashed_name(name)

    # TODO: Collision detection, raise a new exception or re-use something that exists?

    # Iterate through sorted hashed to create NSEC3 chain (binary and hashed name has the same lexicographical order)
    sorted_hashed_names = sorted(hashed_names.keys())
    for index, hashed_name in enumerate(sorted_hashed_names):
        next_hashed_name = sorted_hashed_names[(index + 1) % len(sorted_hashed_names)]
        names = hashed_names[hashed_name]
        _txn_add_nsec3(hashed_name, names, next_hashed_name)

[asannes]

Did some more iterations on it and tested it with other tools, just going to finish up the tests and I will make a PR that will make it easier to evaluate it than here.