Subject: [DNSOP] algorithm rollover use cases (was: Signed TLD status)

From: Matthijs Mekking <[email-masked]>
Date: Thu, 30 Sep 2010 15:03:13 +0200

Hi,

On the dnssec-deployment list, the Signed TLD status thread [1] evolved
into a discussion how algorithm rollover works in specific use cases. My
feeling is that this discussion belongs to DNSOP and so I want to share
my conclusions here.

The algorithm rollover logic is described in
draft-ietf-dnsop-rfc4641bis-04. Please take a look at the table in
section 4.1.5. This is the case where you have a ZSK/KSK split and 5011
is not in place. The background information for this [2] convinces me
that these steps ensure that the chain of trust stays in tact:

Step 2 (New RRSIGs) is needed to propagate the signatures created with
the new algorithm to the caches. If you do not do that, it might happen
that the resolver picks up the new DNSKEY RRset (with the new algorithm
included), but still have the old list of signatures stored.

Step 3 (New DNSKEY) can be performed if the old signatures are expired
from the caches.

Step 4 (Exchange DS) can be performed if the old keyset is expired from
the caches.

Step 5 (Remove DNSKEY) can be done if the old DS RRset is expired from
the caches. We still need to publish the signatures of both algorithms,
because the intermediate keyset may still be in the caches. A fresh
query for zone data must thus be accompanied with signatures of both
algorithms, since it may be verified with the cached keyset.

Step 6 (Remove RRSIGs) can be done if the intermediate keyset is expired
from the caches.

Life is great.

Now there are other use cases:
a) Single Type Signing Scheme Algorithm Rollover
b) Trust Anchor Algorithm Rollover (5011 may be used)
c) Both a) and b).

a) Single Type Signing Scheme Algorithm Rollover
If you have one key that acts both as ZSK and KSK, you reduce the size
of the DNSKEY set. Just remove all DNSKEY_Z_* records from the table in
section 4.1.5 and replace all RRSIG_Z_* with RRSIG_K_*. No hard stuff here.

b) Trust Anchor Algorithm Rollover
When rolling a trust anchor to a different algorithm, you should be
aware of the possible use of 5011. Before removing the deprecated
algorithm KSK, it should be revoked first. This may cause a problem for
a validating resolver.

Take a look at the table in section 4.1.5 in the 4641bis document again.
After Step 4 (Exchange DS) we need an additional step 4a (Revoke DNSKEY):

- -------------------------------
4b Revoke DNSKEY
- -------------------------------
Parent:
 -----------(SOA)------------->
 ----------------------------->
 ----------------------------->
 ----------------------------->

Child:
SOA3
RRSIG_Z_1(SOA3)
RRSIG_Z_2(SOA3)

DNSKEY_K_1_REVOKED
DNSKEY_Z_1
DNSKEY_K_2
DNSKEY_Z_2
RRSIG_K_1_REVOKED(DNSKEY)
RRSIG_K_2(DNSKEY)
- -------------------------------

Non-aware 5011 resolvers will handle DNSKEY_K_1_REVOKED the same as
DNSKEY_K_1, since they do not know about the REVOKED bit.
5011-aware resolvers will remove DNSKEY_K_1 from the set of trust
anchors. That is okay, since they have already added DNSKEY_K_2 as the
new trust anchor. Thus, 2 is the only signaled algorithm by now. That
means, we only need RRSIG_K_2(DNSKEY) to authenticate the DNSKEY RRset,
and we still are compliant with section 2.2 from RFC 4035: There must be
a RRSIG for each RRset using at least one DNSKEY of each algorithm in
the zone apex DNSKEY RRset.

After that, we can continue with step 5 (Remove DNSKEY) just like
described as above. Actually, the added complexity to algorithm rollover
due to 5011 is equal to the added complexity due to 5011 in KSK
rollover. That sounds about right.

Both a) and b).
You cannot easily use 5011 in a Single Type Signing Scheme. In section
2.1, RFC 5011 states:

   Once the resolver sees the REVOKE bit, it MUST
   NOT use this key as a trust anchor or for any other purpose except to
   validate the RRSIG it signed over the DNSKEY RRSet specifically for
   the purpose of validating the revocation.

This means that if we revoke DNSKEY_KSK_1, we cannot use it to validate
its signatures over non-DNSKEY RRsets. Thus, those RRsets should be
signed with a shadow key, DNSKEY_ZSK_1, during the algorithm rollover.
This shadow key can be introduced at the same time the signatures are
pre-published, in step 2 (new RRSIGs). The shadow key must be removed at
the same time the revoked KSK_1 is removed from the zone.

I have provided tables for all the three use cases:

  a) Single Type Signing Scheme Algorithm Rollover
  ----------------------------------------------------------------
   1 Initial            2 New RRSIGS         3 New DNSKEY
  ----------------------------------------------------------------
   Parent:
    SOA0                 -------------- ( SOA ) -------------->
    RRSIG_par(SOA)       ------------------------------------->
    DS_K_1               ------------------------------------->
    RRSIG_par(DS_K_1)    ------------------------------------->

   Child:
    SOA0                 SOA1                 SOA2
    RRSIG_K_1(SOA)       RRSIG_K_1(SOA)       RRSIG_K_1(SOA)
                         RRSIG_K_2(SOA)       RRSIG_K_2(SOA)

    DNSKEY_K_1           DNSKEY_K_1           DNSKEY_K_1
    RRSIG_K_1(DNSKEY)    RRSIG_K_1(DNSKEY)    DNSKEY_K_2
                         RRSIG_K_2(DNSKEY)    RRSIG_K_1(DNSKEY)
                                              RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------
   4 Exchange DS         5 Remove DNSKEY      6 Remove RRSIGS
   ----------------------------------------------------------------
   Parent:
    SOA1                 -------------( SOA )---------------->
    RRSIG_par(SOA)       ------------------------------------->
    DS_K_2               ------------------------------------->
    RRSIG_par(DS_K_2)    ------------------------------------->

   Child:
    ---- (SOA2 ) --->    SOA3                 SOA4
    ---------------->    RRSIG_K_1(SOA)       RRSIG_K_2(SOA)
    ---------------->    RRSIG_K_2(SOA)

    ---------------->    DNSKEY_K_2           DNSKEY_K_2
    ---------------->    RRSIG_K_1(DNSKEY)    RRSIG_K_2(DNSKEY)
    ---------------->    RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------

  b) Trust Anchor Algorithm Rollover (5011 may be used)
  ----------------------------------------------------------------
   1 Initial            2 New RRSIGS         3 New DNSKEY
  ----------------------------------------------------------------
   Parent:
    SOA0                 -------------- ( SOA ) -------------->
    RRSIG_par(SOA)       ------------------------------------->
    DS_K_1               ------------------------------------->
    RRSIG_par(DS_K_1)    ------------------------------------->

   Child:
    SOA0                 SOA1                 SOA2
    RRSIG_Z_1(SOA)       RRSIG_Z_1(SOA)       RRSIG_Z_1(SOA)
                         RRSIG_Z_2(SOA)       RRSIG_Z_2(SOA)

    DNSKEY_K_1           DNSKEY_K_1           DNSKEY_K_1
    DNSKEY_Z_1           DNSKEY_Z_1           DNSKEY_Z_1
    RRSIG_K_1(DNSKEY)    RRSIG_K_1(DNSKEY)    DNSKEY_K_2
                         RRSIG_K_2(DNSKEY)    DNSKEY_Z_2
                                              RRSIG_K_1(DNSKEY)
                                              RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------
   4 Exchange DS         4b Revoke DNSKEY     5 Remove DNSKEY
   ----------------------------------------------------------------
   Parent:
    SOA1                 -------------( SOA )---------------->
    RRSIG_par(SOA)       ------------------------------------->
    DS_K_2               ------------------------------------->
    RRSIG_par(DS_K_2)    ------------------------------------->

   Child:
    ---- (SOA2 ) --->    SOA3                 SOA4
    ---------------->    RRSIG_Z_1(SOA)       RRSIG_Z_2(SOA)
    ---------------->    RRSIG_Z_2(SOA)

    ---------------->    DNSKEY_K_1_REVOKED   DNSKEY_K_2
    ---------------->    DNSKEY_Z_1           DNSKEY_Z_2
    ---------------->    DNSKEY_K_2           RRSIG_K_2(DNSKEY)
    ---------------->    DNSKEY_Z_2
    ---------------->    RRSIG_K_1_REVOKED(DNSKEY)
    ---------------->    RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------
   6 Remove RRSIGS
   ----------------------------------------------------------------
   Parent:
    --------------( SOA )---------------->
    ------------------------------------->
    ------------------------------------->
    ------------------------------------->

   Child:
    SOA5
    RRSIG_Z_2(SOA5)

    DNSKEY_K_2
    DNSKEY_Z_2
    RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------

  c) Both a) and b)
  ----------------------------------------------------------------
   1 Initial            2 New RRSIGS         3 New DNSKEY
  ----------------------------------------------------------------
   Parent:
    SOA0                 -------------- ( SOA ) -------------->
    RRSIG_par(SOA)       ------------------------------------->
    DS_K_1               ------------------------------------->
    RRSIG_par(DS_K_1)    ------------------------------------->

   Child:
    SOA0                 SOA1                 SOA2
    RRSIG_K_1(SOA)       RRSIG_Z_1(SOA)       RRSIG_Z_1(SOA)
                         RRSIG_Z_2(SOA)       RRSIG_K_2(SOA)

    DNSKEY_K_1           DNSKEY_K_1           DNSKEY_K_1
    RRSIG_K_1(DNSKEY)    DNSKEY_Z_1           DNSKEY_Z_1
                         RRSIG_K_1(DNSKEY)    DNSKEY_K_2
                         RRSIG_K_2(DNSKEY)    RRSIG_K_1(DNSKEY)
                                              RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------
   4 Exchange DS         4b Revoke DNSKEY     5 Remove DNSKEY
   ----------------------------------------------------------------
   Parent:
    SOA1                 -------------( SOA )---------------->
    RRSIG_par(SOA)       ------------------------------------->
    DS_K_2               ------------------------------------->
    RRSIG_par(DS_K_2)    ------------------------------------->

   Child:
    ---- (SOA2 ) --->    SOA3                 SOA4
    ---------------->    RRSIG_Z_1(SOA)       RRSIG_Z_2(SOA)
    ---------------->    RRSIG_Z_2(SOA)

    ---------------->    DNSKEY_K_1_REVOKED   DNSKEY_K_2
    ---------------->    DNSKEY_Z_1           RRSIG_K_2(DNSKEY)
    ---------------->    DNSKEY_K_2
    ---------------->    RRSIG_K_1_REVOKED(DNSKEY)
    ---------------->    RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------
   6 Remove RRSIGS
   ----------------------------------------------------------------
   Parent:
    --------------( SOA )---------------->
    ------------------------------------->
    ------------------------------------->
    ------------------------------------->

   Child:
    SOA5
    RRSIG_K_2(SOA5)

    DNSKEY_K_2
    RRSIG_K_2(DNSKEY)
   ----------------------------------------------------------------

References:

[1]
http://dnssec-deployment.org/pipermail/dnssec-deployment/2010-September/004392.html

[2]
http://www.internetdagarna.se/arkiv/2008/www.internetdagarna.se/images/stories/doc/13_DNSSEC_Key_maintenance.pdf

---

From: Matthijs Mekking <[email-masked]>
Date: Thu, 30 Sep 2010 15:13:37 +0200

Minor clarification in the final table (thanks Wouter). RRSIG_Z_2 in
step 4b and 5 should be RRSIG_K_2.

Matthijs