[Dnssec-deployment] Barbie sez: "Algorithm rollovers are HARD!"

Michael Sinatra michael at rancid.berkeley.edu
Mon Aug 16 02:07:29 EDT 2010

Part of the issue that comes up when deciding with which algorithm to 
initially sign your zone is the difficulty of algorithm rollovers.  I 
have pointed this out elsewhere, but I am seeing it again as I undertake 
an exercise to try think about how I would roll the algorithm for 
berkeley.edu and all of its subzones from RSASHA1 to RSASHA512.

The steps that I would take in doing this (I came up with these on my 
own, but also validated them against Scott Rose's paper: 

1. Generate KSK and ZSK with new algorithm.

2. Sign zone with existing KSK/ZSK algorithm and new KSK/ZSK algorithm 
(accordingly, there will be four RRSIGs for the DNSKEY RRSet and two 
RSSIGs for all other RRSets, which are signed by the respective ZSKs only).

3. Install new DS records in parent.

4. Remove old DS records from parent (I think Scott may have forgotten 
this step in his paper).  I don't think you have to wait a for the usual 
TTL+propagation delay (for the DSSet) for this because any new client 
that grabs the DSSet from the parent will validate with the new algo and 
any one that has the old DSSet cached will still be able to validate. 
You will, however, have to wait for the TTL+propagation delay of the 
DNSKEY RRSet, so that clients will have removed the old DNSKEY RRSet 
from their caches.

5. AFTER waiting TTL+propagation delay of the DSSet, DNSKEYs with old 
algorithm can be "safely" removed.

The problem is that this method can lead to validation failures and zone 
bogusity if not done exactly right.  The reason is to accommodate those 
implementations that enforce (probably correctly) a strict 
interpretation of the last paragraph of section 2.2 of RFC 4035:

    "There MUST be an RRSIG for each RRset using at least one DNSKEY of
    each algorithm in the zone apex DNSKEY RRset.  The apex DNSKEY RRset
    itself MUST be signed by each algorithm appearing in the DS RRset
    located at the delegating parent (if any)."

Here's the wrinkle: Although I can remove all algo 5 DS records in the 
parent, as long as I have an algo 5 DNSKEY in the DNSKEY RRSet, I MUST 
continue to sign with algo 5 (using, of course, one of the algo 5 keys 
in that DNSKEY RRSet).  Moreover, clients who have cached the DNSKEY 
records WILL experience validation failures until TTL+propagation delay 
after you remove the algo 5 DNSKEYs, *if* you stop signing with those 
keys when you remove them.  I have verified this with such an 
implementation (unbound 1.4.6, which strictly enforces RFC 4035 section 

The irony is that RFC 4035 section 2.2 is designed to prevent algorithm 
downgrade attacks, but it also makes *upgrading* algorithms more difficult.

The answer is to continue signing with the algo 5 keys but not include 
them in the DNSKEY RRSet.  This shouldn't cause problems, since new 
clients will only see the algo 10 DS records and associated DNSKEYs, and 
the multiple RRSIGs don't violate the other parts of section 2.2 AS LONG 
AS there is at least one RRSIG whose signing key's public counterpart 
exists in the zone apex DNSKEY RRSet (which it does in this example). 
Having additional RRSIGs shouldn't be a problem as long as one matches 
one of the DNSKEYs and there are only algo 10 DNSKEYs in the DNSKEY RRSet.

Whew!  So what this means is that my #5 should be rewritten as:

5. AFTER waiting TTL+propagation delay of the DSSet, DNSKEYs with old 
algorithm can be "safely" removed from zone DNSKEY RRSet, but zone will 
still need to be signed with recently-removed keys.

6. AFTER waiting TTL+propagation delay of the DNSKEY RRSet, zone can 
then be signed only with the new algorithm.  The old private keys can be 
discarded.  Administrators may want to lower the TTLs of the DNSKEY 
RRSet in order to minimize the time between steps 5 and 6.

I wonder if folks have thoughts on this, and if anyone knows of a howto 
that has clarified these issues.  The logic here is exactly the opposite 
of a ZSK rollover, where keys are present but aren't signing anything, 
and it requires a bit more coordination than a typical KSK rollover 
because you have to keep signing with the old algorithm to deal with 
cached DNSKEY RRSets.  Do any of the automated management tools support 
this type of rollover?  (I use zkt and it does not--you have to do a lot 
of manual work and shim scripting to make this happen gracefully.)

I think the moral of the story is "the more algorithm rollovers you can 
avoid, the better."


More information about the Dnssec-deployment mailing list