/src/bind9/lib/dns/keymgr.c

Source
/*
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
 *
 * SPDX-License-Identifier: MPL-2.0
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

/*! \file */

#include <inttypes.h>
#include <stdbool.h>
#include <stdlib.h>
#include <unistd.h>

#include <isc/buffer.h>
#include <isc/dir.h>
#include <isc/log.h>
#include <isc/mem.h>
#include <isc/result.h>
#include <isc/string.h>
#include <isc/time.h>
#include <isc/util.h>

#include <dns/dnssec.h>
#include <dns/kasp.h>
#include <dns/keymgr.h>
#include <dns/keyvalues.h>

#include <dst/dst.h>

/*
 * Set key state to `target` state and change last changed
 * to `time`, only if key state has not been set before.
 */
#define INITIALIZE_STATE(key, state, timing, target, time)                     \
  do {                                                                   \
    dst_key_state_t s;                                             \
    char keystr[DST_KEY_FORMATSIZE];                               \
    if (dst_key_getstate((key), (state), &s) == ISC_R_NOTFOUND) {  \
      dst_key_setstate((key), (state), (target));            \
      dst_key_settime((key), (timing), time);                \
                                                                               \
      if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {              \
        dst_key_format((key), keystr, sizeof(keystr)); \
        isc_log_write(                                 \
          DNS_LOGCATEGORY_DNSSEC,                \
          DNS_LOGMODULE_DNSSEC,                  \
          ISC_LOG_DEBUG(3),                      \
          "keymgr: DNSKEY %s (%s) initialize "   \
          "%s state to %s (policy %s)",          \
          keystr, keymgr_keyrole(key),           \
          keystatetags[state],                   \
          keystatestrings[target],               \
          dns_kasp_getname(kasp));               \
      }                                                      \
    }                                                              \
  } while (0)

/* Shorter keywords for better readability. */
#define HIDDEN      DST_KEY_STATE_HIDDEN
#define RUMOURED    DST_KEY_STATE_RUMOURED
#define OMNIPRESENT DST_KEY_STATE_OMNIPRESENT
#define UNRETENTIVE DST_KEY_STATE_UNRETENTIVE
#define NA      DST_KEY_STATE_NA

/* Quickly get key state timing metadata. */
static int keystatetimes[] = { DST_TIME_DNSKEY, DST_TIME_ZRRSIG,
             DST_TIME_KRRSIG, DST_TIME_DS };
#define NUM_KEYSTATES (int)ARRAY_SIZE(keystatetimes)

/* Readable key state types and values. */
static const char *keystatetags[NUM_KEYSTATES] = { "DNSKEY", "ZRRSIG", "KRRSIG",
               "DS" };
static const char *keystatestrings[] = { "HIDDEN", "RUMOURED", "OMNIPRESENT",
           "UNRETENTIVE" };

static void
log_key_overflow(dst_key_t *key, const char *what) {
  char keystr[DST_KEY_FORMATSIZE];
  dst_key_format(key, keystr, sizeof(keystr));
  isc_log_write(
    DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC, ISC_LOG_WARNING,
    "keymgr: DNSKEY %s (%s) calculation overflowed", keystr, what);
}

/*
 * Print key role.
 *
 */
static const char *
keymgr_keyrole(dst_key_t *key) {
  bool ksk = false, zsk = false;
  isc_result_t result;
  result = dst_key_getbool(key, DST_BOOL_KSK, &ksk);
  if (result != ISC_R_SUCCESS) {
    return "UNKNOWN";
  }
  result = dst_key_getbool(key, DST_BOOL_ZSK, &zsk);
  if (result != ISC_R_SUCCESS) {
    return "UNKNOWN";
  }
  if (ksk && zsk) {
    return "CSK";
  } else if (ksk) {
    return "KSK";
  } else if (zsk) {
    return "ZSK";
  }
  return "NOSIGN";
}

/*
 * Set the remove time on key given its retire time.
 *
 */
static void
keymgr_settime_remove(dns_dnsseckey_t *key, dns_kasp_t *kasp) {
  isc_stdtime_t retire = 0, remove = 0, ksk_remove = 0, zsk_remove = 0;
  bool zsk = false, ksk = false;
  isc_result_t result;

  REQUIRE(key != NULL);
  REQUIRE(key->key != NULL);

  result = dst_key_gettime(key->key, DST_TIME_INACTIVE, &retire);
  if (result != ISC_R_SUCCESS) {
    return;
  }

  result = dst_key_getbool(key->key, DST_BOOL_ZSK, &zsk);
  if (result == ISC_R_SUCCESS && zsk) {
    dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
    /* ZSK: Iret = Dsgn + Dprp + TTLsig */
    zsk_remove =
      retire + ttlsig + dns_kasp_zonepropagationdelay(kasp) +
      dns_kasp_retiresafety(kasp) + dns_kasp_signdelay(kasp);
  }
  result = dst_key_getbool(key->key, DST_BOOL_KSK, &ksk);
  if (result == ISC_R_SUCCESS && ksk) {
    /* KSK: Iret = DprpP + TTLds */
    ksk_remove = retire + dns_kasp_dsttl(kasp) +
           dns_kasp_parentpropagationdelay(kasp) +
           dns_kasp_retiresafety(kasp);
  }

  remove = ISC_MAX(ksk_remove, zsk_remove);
  dst_key_settime(key->key, DST_TIME_DELETE, remove);
}

/*
 * Set the SyncPublish time (when the DS may be submitted to the parent).
 *
 */
void
dns_keymgr_settime_syncpublish(dst_key_t *key, dns_kasp_t *kasp, bool first) {
  isc_stdtime_t published, syncpublish;
  bool ksk = false;
  isc_result_t result;

  REQUIRE(key != NULL);

  result = dst_key_gettime(key, DST_TIME_PUBLISH, &published);
  if (result != ISC_R_SUCCESS) {
    return;
  }

  result = dst_key_getbool(key, DST_BOOL_KSK, &ksk);
  if (result != ISC_R_SUCCESS || !ksk) {
    return;
  }

  syncpublish = published + dst_key_getttl(key) +
          dns_kasp_zonepropagationdelay(kasp) +
          dns_kasp_publishsafety(kasp);
  if (first) {
    /* Also need to wait until the signatures are omnipresent. */
    isc_stdtime_t zrrsig_present;
    dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
    zrrsig_present = published + ttlsig +
         dns_kasp_zonepropagationdelay(kasp);
    if (zrrsig_present > syncpublish) {
      syncpublish = zrrsig_present;
    }
  }
  dst_key_settime(key, DST_TIME_SYNCPUBLISH, syncpublish);

  uint32_t lifetime = 0;
  result = dst_key_getnum(key, DST_NUM_LIFETIME, &lifetime);
  if (result == ISC_R_SUCCESS && lifetime > 0) {
    dst_key_settime(key, DST_TIME_SYNCDELETE,
        syncpublish + lifetime);
  }
}

/*
 * Calculate prepublication time of a successor key of 'key'.
 * This function can have side effects:
 * 1. If there is no active time set, which would be super weird, set it now.
 * 2. If there is no published time set, also super weird, set it now.
 * 3. If there is no syncpublished time set, set it now.
 * 4. If the lifetime is not set, it will be set now.
 * 5. If there should be a retire time and it is not set, it will be set now.
 * 6. The removed time is adjusted accordingly.
 *
 * This returns when the successor key needs to be published in the zone.
 * A special value of 0 means there is no need for a successor.
 *
 */
static isc_stdtime_t
keymgr_prepublication_time(dns_dnsseckey_t *key, dns_kasp_t *kasp,
         uint32_t lifetime, isc_stdtime_t now) {
  isc_result_t result;
  isc_stdtime_t active, retire, pub, prepub;
  bool zsk = false, ksk = false;

  REQUIRE(key != NULL);
  REQUIRE(key->key != NULL);

  active = 0;
  pub = 0;
  retire = 0;

  /*
   * An active key must have publish and activate timing
   * metadata.
   */
  result = dst_key_gettime(key->key, DST_TIME_ACTIVATE, &active);
  if (result != ISC_R_SUCCESS) {
    /* Super weird, but if it happens, set it to now. */
    dst_key_settime(key->key, DST_TIME_ACTIVATE, now);
    active = now;
  }
  result = dst_key_gettime(key->key, DST_TIME_PUBLISH, &pub);
  if (result != ISC_R_SUCCESS) {
    /* Super weird, but if it happens, set it to now. */
    dst_key_settime(key->key, DST_TIME_PUBLISH, now);
    pub = now;
  }

  /*
   * To calculate phase out times ("Retired", "Removed", ...),
   * the key lifetime is required.
   */
  uint32_t klifetime = 0;
  result = dst_key_getnum(key->key, DST_NUM_LIFETIME, &klifetime);
  if (result != ISC_R_SUCCESS) {
    dst_key_setnum(key->key, DST_NUM_LIFETIME, lifetime);
    klifetime = lifetime;
  }

  /*
   * Calculate prepublication time.
   */
  prepub = dst_key_getttl(key->key) + dns_kasp_publishsafety(kasp) +
     dns_kasp_zonepropagationdelay(kasp);
  result = dst_key_getbool(key->key, DST_BOOL_KSK, &ksk);
  if (result == ISC_R_SUCCESS && ksk) {
    isc_stdtime_t syncpub;

    /*
     * Set PublishCDS if not set.
     */
    result = dst_key_gettime(key->key, DST_TIME_SYNCPUBLISH,
           &syncpub);
    if (result != ISC_R_SUCCESS) {
      uint32_t tag;
      isc_stdtime_t syncpub1, syncpub2;

      syncpub1 = pub + prepub;
      syncpub2 = 0;
      result = dst_key_getnum(key->key, DST_NUM_PREDECESSOR,
            &tag);
      if (result != ISC_R_SUCCESS) {
        /*
         * No predecessor, wait for zone to be
         * completely signed.
         */
        dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp,
                       true);
        syncpub2 = pub + ttlsig +
             dns_kasp_zonepropagationdelay(kasp);
      }

      syncpub = ISC_MAX(syncpub1, syncpub2);
      dst_key_settime(key->key, DST_TIME_SYNCPUBLISH,
          syncpub);
      if (klifetime > 0) {
        dst_key_settime(key->key, DST_TIME_SYNCDELETE,
            syncpub + klifetime);
      }
    }
  }

  /*
   * Not sure what to do when dst_key_getbool() fails here.  Extending
   * the prepublication time anyway is arguably the safest thing to do,
   * so ignore the result code.
   */
  (void)dst_key_getbool(key->key, DST_BOOL_ZSK, &zsk);

  result = dst_key_gettime(key->key, DST_TIME_INACTIVE, &retire);
  if (result != ISC_R_SUCCESS) {
    if (klifetime == 0) {
      /*
       * No inactive time and no lifetime,
       * so no need to start a rollover.
       */
      return 0;
    }

    if (ckd_add(&retire, active, klifetime)) {
      log_key_overflow(key->key, "retire");
      retire = UINT32_MAX;
    }
    dst_key_settime(key->key, DST_TIME_INACTIVE, retire);
  }

  /*
   * Update remove time.
   */
  keymgr_settime_remove(key, kasp);

  /*
   * Publish successor 'prepub' time before the 'retire' time of 'key'.
   */
  if (prepub > retire) {
    /* We should have already prepublished the new key. */
    return now;
  }
  return retire - prepub;
}

static void
keymgr_key_retire(dns_dnsseckey_t *key, dns_kasp_t *kasp, uint8_t opts,
      isc_stdtime_t now) {
  char keystr[DST_KEY_FORMATSIZE];
  isc_result_t result;
  isc_stdtime_t retire;
  dst_key_state_t s;
  bool ksk = false, zsk = false;

  REQUIRE(key != NULL);
  REQUIRE(key->key != NULL);

  dst_key_format(key->key, keystr, sizeof(keystr));

  result = dst_key_getstate(key->key, DST_KEY_GOAL, &s);
  INSIST(result == ISC_R_SUCCESS);

  if (dns_kasp_manualmode(kasp) &&
      (opts & DNS_KEYMGRATTR_FORCESTEP) == 0 && s != HIDDEN)
  {
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_INFO,
            "keymgr-manual-mode: block retire DNSKEY "
            "%s (%s)",
            keystr, keymgr_keyrole(key->key));
    return;
  } else {
    /* This key wants to retire and hide in a corner. */
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_INFO, "keymgr: retire DNSKEY %s (%s)",
            keystr, keymgr_keyrole(key->key));

    dst_key_setstate(key->key, DST_KEY_GOAL, HIDDEN);
  }

  /*
   * This key may not have key states set yet. Pretend as if they are
   * in the OMNIPRESENT state.
   */
  result = dst_key_gettime(key->key, DST_TIME_INACTIVE, &retire);
  if (result != ISC_R_SUCCESS || (retire > now)) {
    dst_key_settime(key->key, DST_TIME_INACTIVE, now);
  }
  keymgr_settime_remove(key, kasp);

  if (dst_key_getstate(key->key, DST_KEY_DNSKEY, &s) != ISC_R_SUCCESS) {
    dst_key_setstate(key->key, DST_KEY_DNSKEY, OMNIPRESENT);
    dst_key_settime(key->key, DST_TIME_DNSKEY, now);
  }

  result = dst_key_getbool(key->key, DST_BOOL_KSK, &ksk);
  if (result == ISC_R_SUCCESS && ksk) {
    if (dst_key_getstate(key->key, DST_KEY_KRRSIG, &s) !=
        ISC_R_SUCCESS)
    {
      dst_key_setstate(key->key, DST_KEY_KRRSIG, OMNIPRESENT);
      dst_key_settime(key->key, DST_TIME_KRRSIG, now);
    }
    if (dst_key_getstate(key->key, DST_KEY_DS, &s) != ISC_R_SUCCESS)
    {
      dst_key_setstate(key->key, DST_KEY_DS, OMNIPRESENT);
      dst_key_settime(key->key, DST_TIME_DS, now);
    }
  }
  result = dst_key_getbool(key->key, DST_BOOL_ZSK, &zsk);
  if (result == ISC_R_SUCCESS && zsk) {
    if (dst_key_getstate(key->key, DST_KEY_ZRRSIG, &s) !=
        ISC_R_SUCCESS)
    {
      dst_key_setstate(key->key, DST_KEY_ZRRSIG, OMNIPRESENT);
      dst_key_settime(key->key, DST_TIME_ZRRSIG, now);
    }
  }
}

/* Update lifetime and retire and remove time accordingly. */
static void
keymgr_key_update_lifetime(dns_dnsseckey_t *key, dns_kasp_t *kasp,
         isc_stdtime_t now, uint32_t lifetime) {
  uint32_t l;
  dst_key_state_t g = HIDDEN;
  isc_result_t r;

  (void)dst_key_getstate(key->key, DST_KEY_GOAL, &g);
  r = dst_key_getnum(key->key, DST_NUM_LIFETIME, &l);
  /* Initialize lifetime. */
  if (r != ISC_R_SUCCESS) {
    dst_key_setnum(key->key, DST_NUM_LIFETIME, lifetime);
    l = lifetime - 1;
  }
  /* Skip keys that are still hidden or already retiring. */
  if (g != OMNIPRESENT) {
    return;
  }
  /* Update lifetime and timing metadata. */
  if (l != lifetime) {
    dst_key_setnum(key->key, DST_NUM_LIFETIME, lifetime);
    if (lifetime > 0) {
      uint32_t a = now;
      uint32_t inactive;
      (void)dst_key_gettime(key->key, DST_TIME_ACTIVATE, &a);
      if (ckd_add(&inactive, a, lifetime)) {
        log_key_overflow(key->key, "inactive");
        inactive = UINT32_MAX;
      }
      dst_key_settime(key->key, DST_TIME_INACTIVE, inactive);
      keymgr_settime_remove(key, kasp);
    } else {
      dst_key_unsettime(key->key, DST_TIME_INACTIVE);
      dst_key_unsettime(key->key, DST_TIME_DELETE);
      dst_key_unsettime(key->key, DST_TIME_SYNCDELETE);
    }
  }
}

static bool
keymgr_keyid_conflict(dst_key_t *newkey, uint16_t min, uint16_t max,
          dns_dnsseckeylist_t *keys) {
  uint16_t id = dst_key_id(newkey);
  uint32_t rid = dst_key_rid(newkey);
  uint32_t alg = dst_key_alg(newkey);

  if (id < min || id > max) {
    return true;
  }
  if (rid < min || rid > max) {
    return true;
  }

  ISC_LIST_FOREACH(*keys, dkey, link) {
    if (dst_key_alg(dkey->key) != alg) {
      continue;
    }
    if (dst_key_id(dkey->key) == id ||
        dst_key_rid(dkey->key) == id ||
        dst_key_id(dkey->key) == rid ||
        dst_key_rid(dkey->key) == rid)
    {
      return true;
    }
  }
  return false;
}

/*
 * Create a new key for 'origin' given the kasp key configuration 'kkey'.
 * This will check for key id collisions with keys in 'keylist'.
 * The created key will be stored in 'dst_key'.
 *
 */
static isc_result_t
keymgr_createkey(dns_kasp_key_t *kkey, const dns_name_t *origin,
     dns_kasp_t *kasp, dns_rdataclass_t rdclass, isc_mem_t *mctx,
     const char *keydir, dns_dnsseckeylist_t *keylist,
     isc_stdtime_t now, dns_dnsseckeylist_t *newkeys,
     dst_key_t **dst_key) {
  isc_result_t result = ISC_R_SUCCESS;
  bool conflict = false;
  int flags = DNS_KEYOWNER_ZONE;
  dst_key_t *newkey = NULL;
  uint32_t alg = dns_kasp_key_algorithm(kkey);
  dns_keystore_t *keystore = dns_kasp_key_keystore(kkey);
  const char *dir = NULL;
  int size = dns_kasp_key_size(kkey);
  dns_dnsseckeylist_t keykeys;

  ISC_LIST_INIT(keykeys);

  if (dns_kasp_key_ksk(kkey)) {
    flags |= DNS_KEYFLAG_KSK;
  }

  /*
   * We also need to check against K* files for KEYs.
   */
  result = dns_dnssec_findmatchingkeys(origin, NULL, keydir, NULL, now,
               true, mctx, &keykeys);
  if (result != ISC_R_SUCCESS && result != ISC_R_NOTFOUND) {
    goto cleanup;
  }

  do {
    if (keystore == NULL) {
      CHECK(dst_key_generate(origin, alg, size, 0, flags,
                 DNS_KEYPROTO_DNSSEC, rdclass,
                 NULL, mctx, &newkey, NULL));
    } else {
      CHECK(dns_keystore_keygen(
        keystore, origin, dns_kasp_getname(kasp),
        rdclass, mctx, alg, size, flags, &newkey));
    }

    /* Key collision? */
    conflict = keymgr_keyid_conflict(newkey, kkey->tag_min,
             kkey->tag_max, keylist);
    if (!conflict) {
      conflict = keymgr_keyid_conflict(
        newkey, kkey->tag_min, kkey->tag_max, &keykeys);
    }
    if (!conflict) {
      conflict = keymgr_keyid_conflict(
        newkey, kkey->tag_min, kkey->tag_max, newkeys);
    }
    if (conflict) {
      /* Try again. */
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_WARNING,
              "keymgr: key collision id %d",
              dst_key_id(newkey));
      dst_key_free(&newkey);
    }
  } while (conflict);

  INSIST(!conflict);
  dst_key_setnum(newkey, DST_NUM_LIFETIME, dns_kasp_key_lifetime(kkey));
  dst_key_setbool(newkey, DST_BOOL_KSK, dns_kasp_key_ksk(kkey));
  dst_key_setbool(newkey, DST_BOOL_ZSK, dns_kasp_key_zsk(kkey));

  dir = dns_keystore_directory(keystore, keydir);
  if (dir != NULL) {
    dst_key_setdirectory(newkey, dir);
  }
  *dst_key = newkey;
  result = ISC_R_SUCCESS;

cleanup:
  while (!ISC_LIST_EMPTY(keykeys)) {
    dns_dnsseckey_t *key = ISC_LIST_HEAD(keykeys);
    ISC_LIST_UNLINK(keykeys, key, link);
    dns_dnsseckey_destroy(mctx, &key);
  }
  return result;
}

/*
 * Return the desired state for this record 'type'.  The desired state depends
 * on whether the key wants to be active, or wants to retire.  This implements
 * the edges of our state machine:
 *
 *            ---->  OMNIPRESENT  ----
 *            |                      |
 *            |                     \|/
 *
 *        RUMOURED     <---->   UNRETENTIVE
 *
 *           /|\                     |
 *            |                      |
 *            ----     HIDDEN    <----
 *
 * A key that wants to be active eventually wants to have its record types
 * in the OMNIPRESENT state (that is, all resolvers that know about these
 * type of records know about these records specifically).
 *
 * A key that wants to be retired eventually wants to have its record types
 * in the HIDDEN state (that is, all resolvers that know about these type
 * of records specifically don't know about these records).
 *
 */
static dst_key_state_t
keymgr_desiredstate(dns_dnsseckey_t *key, dst_key_state_t state) {
  dst_key_state_t goal;

  if (dst_key_getstate(key->key, DST_KEY_GOAL, &goal) != ISC_R_SUCCESS) {
    /* No goal? No movement. */
    return state;
  }

  if (goal == HIDDEN) {
    switch (state) {
    case RUMOURED:
    case OMNIPRESENT:
      return UNRETENTIVE;
    case HIDDEN:
    case UNRETENTIVE:
      return HIDDEN;
    default:
      return state;
    }
  } else if (goal == OMNIPRESENT) {
    switch (state) {
    case RUMOURED:
    case OMNIPRESENT:
      return OMNIPRESENT;
    case HIDDEN:
    case UNRETENTIVE:
      return RUMOURED;
    default:
      return state;
    }
  }

  /* Unknown goal. */
  return state;
}

/*
 * Check if 'key' matches specific 'states'.
 * A state in 'states' that is NA matches any state.
 * A state in 'states' that is HIDDEN also matches if the state is not set.
 * If 'next_state' is set (not NA), we are pretending as if record 'type' of
 * 'subject' key already transitioned to the 'next state'.
 *
 */
static bool
keymgr_key_match_state(const dst_key_t *key, const dst_key_t *subject, int type,
           dst_key_state_t next_state,
           dst_key_state_t states[NUM_KEYSTATES]) {
  REQUIRE(key != NULL);

  for (int i = 0; i < NUM_KEYSTATES; i++) {
    dst_key_state_t state;
    if (states[i] == NA) {
      continue;
    }
    if (next_state != NA && i == type &&
        dst_key_alg(key) == dst_key_alg(subject) &&
        dst_key_id(key) == dst_key_id(subject))
    {
      /* Check next state rather than current state. */
      state = next_state;
    } else if (dst_key_getstate(key, i, &state) != ISC_R_SUCCESS) {
      /* This is fine only if expected state is HIDDEN. */
      if (states[i] != HIDDEN) {
        return false;
      }
      continue;
    }
    if (state != states[i]) {
      return false;
    }
  }
  /* Match. */
  return true;
}

/*
 * Key d directly depends on k if d is the direct predecessor of k.
 */
static bool
keymgr_direct_dep(dst_key_t *d, dst_key_t *k) {
  uint32_t s, p;

  if (dst_key_getnum(d, DST_NUM_SUCCESSOR, &s) != ISC_R_SUCCESS) {
    return false;
  }
  if (dst_key_getnum(k, DST_NUM_PREDECESSOR, &p) != ISC_R_SUCCESS) {
    return false;
  }
  return dst_key_id(d) == p && dst_key_id(k) == s;
}

/*
 * Determine which key (if any) has a dependency on k.
 */
static bool
keymgr_dep(dst_key_t *k, dns_dnsseckeylist_t *keyring, uint32_t *dep) {
  ISC_LIST_FOREACH(*keyring, d, link) {
    /*
     * Check if k is a direct successor of d, e.g. d depends on k.
     */
    if (keymgr_direct_dep(d->key, k)) {
      dst_key_state_t hidden[NUM_KEYSTATES] = {
        HIDDEN, HIDDEN, HIDDEN, HIDDEN
      };
      if (keymgr_key_match_state(d->key, k, NA, NA, hidden)) {
        continue;
      }

      SET_IF_NOT_NULL(dep, dst_key_id(d->key));
      return true;
    }
  }
  return false;
}

/*
 * Check if a 'z' is a successor of 'x'.
 * This implements Equation(2) of "Flexible and Robust Key Rollover".
 */
static bool
keymgr_key_is_successor(dst_key_t *x, dst_key_t *z, dst_key_t *key, int type,
      dst_key_state_t next_state,
      dns_dnsseckeylist_t *keyring) {
  uint32_t dep_x;
  uint32_t dep_z;

  /*
   * The successor relation requires that the predecessor key must not
   * have any other keys relying on it. In other words, there must be
   * nothing depending on x.
   */
  if (keymgr_dep(x, keyring, &dep_x)) {
    return false;
  }

  /*
   * If there is no keys relying on key z, then z is not a successor.
   */
  if (!keymgr_dep(z, keyring, &dep_z)) {
    return false;
  }

  /*
   * x depends on z, thus key z is a direct successor of key x.
   */
  if (dst_key_id(x) == dep_z) {
    return true;
  }

  /*
   * It is possible to roll keys faster than the time required to finish
   * the rollover procedure. For example, consider the keys x, y, z.
   * Key x is currently published and is going to be replaced by y. The
   * DNSKEY for x is removed from the zone and at the same moment the
   * DNSKEY for y is introduced. Key y is a direct dependency for key x
   * and is therefore the successor of x. However, before the new DNSKEY
   * has been propagated, key z will replace key y. The DNSKEY for y is
   * removed and moves into the same state as key x. Key y now directly
   * depends on key z, and key z will be a new successor key for x.
   */
  dst_key_state_t zst[NUM_KEYSTATES] = { NA, NA, NA, NA };
  for (int i = 0; i < NUM_KEYSTATES; i++) {
    dst_key_state_t state;
    if (dst_key_getstate(z, i, &state) != ISC_R_SUCCESS) {
      continue;
    }
    zst[i] = state;
  }

  ISC_LIST_FOREACH(*keyring, y, link) {
    if (dst_key_id(y->key) == dst_key_id(z)) {
      continue;
    }

    if (dst_key_id(y->key) != dep_z) {
      continue;
    }
    /*
     * This is another key y, that depends on key z. It may be
     * part of the successor relation if the key states match
     * those of key z.
     */

    if (keymgr_key_match_state(y->key, key, type, next_state, zst))
    {
      /*
       * If y is a successor of x, then z is also a
       * successor of x.
       */
      return keymgr_key_is_successor(x, y->key, key, type,
                   next_state, keyring);
    }
  }

  return false;
}

/*
 * Check if a key exists in 'keyring' that matches 'states'.
 *
 * If 'match_algorithms', the key must also match the algorithm of 'key'.
 * If 'next_state' is not NA, we are actually looking for a key as if
 *   'key' already transitioned to the next state.
 * If 'check_successor', we also want to make sure there is a successor
 *   relationship with the found key that matches 'states2'.
 */
static bool
keymgr_key_exists_with_state(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key,
           int type, dst_key_state_t next_state,
           dst_key_state_t states[NUM_KEYSTATES],
           dst_key_state_t states2[NUM_KEYSTATES],
           bool check_successor, bool match_algorithms) {
  ISC_LIST_FOREACH(*keyring, dkey, link) {
    if (match_algorithms &&
        (dst_key_alg(dkey->key) != dst_key_alg(key->key)))
    {
      continue;
    }

    if (!keymgr_key_match_state(dkey->key, key->key, type,
              next_state, states))
    {
      continue;
    }

    /* Found a match. */
    if (!check_successor) {
      return true;
    }

    /*
     * We have to make sure that the key we are checking, also
     * has a successor relationship with another key.
     */
    ISC_LIST_FOREACH(*keyring, skey, link) {
      if (skey == dkey) {
        continue;
      }

      if (!keymgr_key_match_state(skey->key, key->key, type,
                next_state, states2))
      {
        continue;
      }

      /*
       * Found a possible successor, check.
       */
      if (keymgr_key_is_successor(dkey->key, skey->key,
                key->key, type, next_state,
                keyring))
      {
        return true;
      }
    }
  }
  /* No match. */
  return false;
}

/*
 * Check if a key has a successor.
 */
static bool
keymgr_key_has_successor(dns_dnsseckey_t *predecessor,
       dns_dnsseckeylist_t *keyring) {
  ISC_LIST_FOREACH(*keyring, successor, link) {
    if (keymgr_direct_dep(predecessor->key, successor->key)) {
      return true;
    }
  }
  return false;
}

/*
 * Check if all keys have their DS hidden.  If not, then there must be at
 * least one key with an OMNIPRESENT DNSKEY.
 *
 * If 'next_state' is not NA, we are actually looking for a key as if
 *   'key' already transitioned to the next state.
 * If 'match_algorithms', only consider keys with same algorithm of 'key'.
 *
 */
static bool
keymgr_ds_hidden_or_chained(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key,
          int type, dst_key_state_t next_state,
          bool match_algorithms, bool must_be_hidden) {
  /* (3e) */
  dst_key_state_t dnskey_chained[NUM_KEYSTATES] = { OMNIPRESENT, NA,
                OMNIPRESENT, NA };
  dst_key_state_t ds_hidden[NUM_KEYSTATES] = { NA, NA, NA, HIDDEN };
  /* successor n/a */
  dst_key_state_t na[NUM_KEYSTATES] = { NA, NA, NA, NA };

  ISC_LIST_FOREACH(*keyring, dkey, link) {
    if (match_algorithms &&
        (dst_key_alg(dkey->key) != dst_key_alg(key->key)))
    {
      continue;
    }

    if (keymgr_key_match_state(dkey->key, key->key, type,
             next_state, ds_hidden))
    {
      /* This key has its DS hidden. */
      continue;
    }

    if (must_be_hidden) {
      return false;
    }

    /*
     * This key does not have its DS hidden. There must be at
     * least one key with the same algorithm that provides a
     * chain of trust (can be this key).
     */
    if (keymgr_key_match_state(dkey->key, key->key, type,
             next_state, dnskey_chained))
    {
      /* This DNSKEY and KRRSIG are OMNIPRESENT. */
      continue;
    }

    /*
     * Perhaps another key provides a chain of trust.
     */
    dnskey_chained[DST_KEY_DS] = OMNIPRESENT;
    if (!keymgr_key_exists_with_state(keyring, key, type,
              next_state, dnskey_chained,
              na, false, match_algorithms))
    {
      /* There is no chain of trust. */
      return false;
    }
  }
  /* All good. */
  return true;
}

/*
 * Check if all keys have their DNSKEY hidden.  If not, then there must be at
 * least one key with an OMNIPRESENT ZRRSIG.
 *
 * If 'next_state' is not NA, we are actually looking for a key as if
 *   'key' already transitioned to the next state.
 * If 'match_algorithms', only consider keys with same algorithm of 'key'.
 *
 */
static bool
keymgr_dnskey_hidden_or_chained(dns_dnsseckeylist_t *keyring,
        dns_dnsseckey_t *key, int type,
        dst_key_state_t next_state,
        bool match_algorithms) {
  /* (3i) */
  dst_key_state_t rrsig_chained[NUM_KEYSTATES] = { OMNIPRESENT,
               OMNIPRESENT, NA, NA };
  dst_key_state_t dnskey_hidden[NUM_KEYSTATES] = { HIDDEN, NA, NA, NA };
  /* successor n/a */
  dst_key_state_t na[NUM_KEYSTATES] = { NA, NA, NA, NA };

  ISC_LIST_FOREACH(*keyring, dkey, link) {
    if (match_algorithms &&
        (dst_key_alg(dkey->key) != dst_key_alg(key->key)))
    {
      continue;
    }

    if (keymgr_key_match_state(dkey->key, key->key, type,
             next_state, dnskey_hidden))
    {
      /* This key has its DNSKEY hidden. */
      continue;
    }

    /*
     * This key does not have its DNSKEY hidden. There must be at
     * least one key with the same algorithm that has its RRSIG
     * records OMNIPRESENT.
     */
    (void)dst_key_getstate(dkey->key, DST_KEY_DNSKEY,
               &rrsig_chained[DST_KEY_DNSKEY]);
    if (!keymgr_key_exists_with_state(keyring, key, type,
              next_state, rrsig_chained, na,
              false, match_algorithms))
    {
      /* There is no chain of trust. */
      return false;
    }
  }
  /* All good. */
  return true;
}

/*
 * Check for existence of DS.
 *
 */
static bool
keymgr_have_ds(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key, int type,
         dst_key_state_t next_state, uint8_t opts) {
  /* (3a) */
  dst_key_state_t states[2][NUM_KEYSTATES] = {
    /* DNSKEY, ZRRSIG, KRRSIG, DS */
    { NA, NA, NA, OMNIPRESENT }, /* DS present */
    { NA, NA, NA, RUMOURED }     /* DS introducing */
  };
  /* successor n/a */
  dst_key_state_t na[NUM_KEYSTATES] = { NA, NA, NA, NA };

  /*
   * Equation (3a):
   * There is a key with the DS in either RUMOURD or OMNIPRESENT state.
   */
  return keymgr_key_exists_with_state(keyring, key, type, next_state,
              states[0], na, false, false) ||
         keymgr_key_exists_with_state(keyring, key, type, next_state,
              states[1], na, false, false) ||
         ((opts & DNS_KEYMGRATTR_S2I) != 0 &&
    keymgr_key_exists_with_state(keyring, key, type, next_state, na,
               na, false, false));
}

/*
 * Check for existence of DNSKEY, or at least a good DNSKEY state.
 * See equations what are good DNSKEY states.
 *
 */
static bool
keymgr_have_dnskey(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key, int type,
       dst_key_state_t next_state) {
  dst_key_state_t states[9][NUM_KEYSTATES] = {
    /* DNSKEY,     ZRRSIG, KRRSIG,      DS */
    { OMNIPRESENT, NA, OMNIPRESENT, OMNIPRESENT }, /* (3b) */

    { OMNIPRESENT, NA, OMNIPRESENT, UNRETENTIVE }, /* (3c)p */
    { OMNIPRESENT, NA, OMNIPRESENT, RUMOURED },    /* (3c)s */

    { UNRETENTIVE, NA, UNRETENTIVE, OMNIPRESENT }, /* (3d)p */
    { OMNIPRESENT, NA, UNRETENTIVE, OMNIPRESENT }, /* (3d)p */
    { UNRETENTIVE, NA, OMNIPRESENT, OMNIPRESENT }, /* (3d)p */
    { RUMOURED, NA, RUMOURED, OMNIPRESENT },       /* (3d)s */
    { OMNIPRESENT, NA, RUMOURED, OMNIPRESENT },    /* (3d)s */
    { RUMOURED, NA, OMNIPRESENT, OMNIPRESENT },    /* (3d)s */
  };
  /* successor n/a */
  dst_key_state_t na[NUM_KEYSTATES] = { NA, NA, NA, NA };

  return
    /*
     * Equation (3b):
     * There is a key with the same algorithm with its DNSKEY,
     * KRRSIG and DS records in OMNIPRESENT state.
     */
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[0], na, false, true) ||
    /*
     * Equation (3c):
     * There are two or more keys with an OMNIPRESENT DNSKEY and
     * the DS records get swapped.  These keys must be in a
     * successor relation.
     */
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[1], states[2], true,
               true) ||
    /*
     * Equation (3d):
     * There are two or more keys with an OMNIPRESENT DS and
     * the DNSKEY records and its KRRSIG records get swapped.
     * These keys must be in a successor relation.  Since the
     * state for DNSKEY and KRRSIG move independently, we have
     * to check all combinations for DNSKEY and KRRSIG in
     * OMNIPRESENT/UNRETENTIVE state for the predecessor, and
     * OMNIPRESENT/RUMOURED state for the successor.
     */
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[3], states[6], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[3], states[7], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[3], states[8], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[4], states[6], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[4], states[7], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[4], states[8], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[5], states[6], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[5], states[7], true,
               true) ||
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[5], states[8], true,
               true) ||
    /*
     * Equation (3e):
     * The key may be in any state as long as all keys have their
     * DS HIDDEN, or when their DS is not HIDDEN, there must be a
     * key with its DS in the same state and its DNSKEY omnipresent.
     * In other words, if a DS record for the same algorithm is
     * is still available to some validators, there must be a
     * chain of trust for those validators.
     */
    keymgr_ds_hidden_or_chained(keyring, key, type, next_state,
              true, false);
}

/*
 * Check for existence of RRSIG (zsk), or a good RRSIG state.
 * See equations what are good RRSIG states.
 *
 */
static bool
keymgr_have_rrsig(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key, int type,
      dst_key_state_t next_state) {
  dst_key_state_t states[11][NUM_KEYSTATES] = {
    /* DNSKEY,     ZRRSIG,      KRRSIG, DS */
    { OMNIPRESENT, OMNIPRESENT, NA, NA }, /* (3f) */
    { UNRETENTIVE, OMNIPRESENT, NA, NA }, /* (3g)p */
    { RUMOURED, OMNIPRESENT, NA, NA },    /* (3g)s */
    { OMNIPRESENT, UNRETENTIVE, NA, NA }, /* (3h)p */
    { OMNIPRESENT, RUMOURED, NA, NA },    /* (3h)s */
  };
  /* successor n/a */
  dst_key_state_t na[NUM_KEYSTATES] = { NA, NA, NA, NA };

  return
    /*
     * If all DS records are hidden than this rule can be ignored.
     */
    keymgr_ds_hidden_or_chained(keyring, key, type, next_state,
              true, true) ||
    /*
     * Equation (3f):
     * There is a key with the same algorithm with its DNSKEY and
     * ZRRSIG records in OMNIPRESENT state.
     */
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[0], na, false, true) ||
    /*
     * Equation (3g):
     * There are two or more keys with OMNIPRESENT ZRRSIG
     * records and the DNSKEY records get swapped.  These keys
     * must be in a successor relation.
     */
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[1], states[2], true,
               true) ||
    /*
     * Equation (3h):
     * There are two or more keys with an OMNIPRESENT DNSKEY
     * and the ZRRSIG records get swapped.  These keys must be in
     * a successor relation.
     */
    keymgr_key_exists_with_state(keyring, key, type, next_state,
               states[3], states[4], true,
               true) ||
    /*
     * Equation (3i):
     * If no DNSKEYs are published, the state of the signatures is
     * irrelevant.  In case a DNSKEY is published however, there
     * must be a path that can be validated from there.
     */
    keymgr_dnskey_hidden_or_chained(keyring, key, type, next_state,
            true);
}

/*
 * Check if a transition in the state machine is allowed by the policy.
 * This means when we do rollovers, we want to follow the rules of the
 * 1. Pre-publish rollover method (in case of a ZSK)
 *    - First introduce the DNSKEY record.
 *    - Only if the DNSKEY record is OMNIPRESENT, introduce ZRRSIG records.
 *
 * 2. Double-KSK rollover method (in case of a KSK)
 *    - First introduce the DNSKEY record, as well as the KRRSIG records.
 *    - Only if the DNSKEY record is OMNIPRESENT, suggest to introduce the DS.
 */
static bool
keymgr_policy_approval(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key,
           int type, dst_key_state_t next) {
  dst_key_state_t dnskeystate = HIDDEN;
  dst_key_state_t ksk_present[NUM_KEYSTATES] = { OMNIPRESENT, NA,
                   OMNIPRESENT,
                   OMNIPRESENT };
  dst_key_state_t ds_rumoured[NUM_KEYSTATES] = { OMNIPRESENT, NA,
                   OMNIPRESENT, RUMOURED };
  dst_key_state_t ds_retired[NUM_KEYSTATES] = { OMNIPRESENT, NA,
                  OMNIPRESENT,
                  UNRETENTIVE };
  dst_key_state_t ksk_rumoured[NUM_KEYSTATES] = { RUMOURED, NA, NA,
              OMNIPRESENT };
  dst_key_state_t ksk_retired[NUM_KEYSTATES] = { UNRETENTIVE, NA, NA,
                   OMNIPRESENT };
  /* successor n/a */
  dst_key_state_t na[NUM_KEYSTATES] = { NA, NA, NA, NA };

  if (next != RUMOURED) {
    /*
     * Local policy only adds an extra barrier on transitions to
     * the RUMOURED state.
     */
    return true;
  }

  switch (type) {
  case DST_KEY_DNSKEY:
    /* No restrictions. */
    return true;
  case DST_KEY_ZRRSIG:
    /* Make sure the DNSKEY record is OMNIPRESENT. */
    (void)dst_key_getstate(key->key, DST_KEY_DNSKEY, &dnskeystate);
    if (dnskeystate == OMNIPRESENT) {
      return true;
    }
    /*
     * Or are we introducing a new key for this algorithm? Because
     * in that case allow publishing the RRSIG records before the
     * DNSKEY.
     */
    return !(keymgr_key_exists_with_state(keyring, key, type, next,
                  ksk_present, na, false,
                  true) ||
       keymgr_key_exists_with_state(keyring, key, type, next,
                  ds_retired, ds_rumoured,
                  true, true) ||
       keymgr_key_exists_with_state(keyring, key, type, next,
                  ksk_retired, ksk_rumoured,
                  true, true));
  case DST_KEY_KRRSIG:
    /* Only introduce if the DNSKEY is also introduced. */
    (void)dst_key_getstate(key->key, DST_KEY_DNSKEY, &dnskeystate);
    return dnskeystate != HIDDEN;
  case DST_KEY_DS:
    /* Make sure the DNSKEY record is OMNIPRESENT. */
    (void)dst_key_getstate(key->key, DST_KEY_DNSKEY, &dnskeystate);
    return dnskeystate == OMNIPRESENT;
  default:
    return false;
  }
}

/*
 * Check if a transition in the state machine is DNSSEC safe.
 * This implements Equation(1) of "Flexible and Robust Key Rollover".
 *
 */
static bool
keymgr_transition_allowed(dns_dnsseckeylist_t *keyring, dns_dnsseckey_t *key,
        int type, dst_key_state_t next_state, uint8_t opts) {
  bool rule1a, rule1b, rule2a, rule2b, rule3a, rule3b;
  rule1a = keymgr_have_ds(keyring, key, type, NA, opts);
  rule1b = keymgr_have_ds(keyring, key, type, next_state, opts);
  rule2a = keymgr_have_dnskey(keyring, key, type, NA);
  rule2b = keymgr_have_dnskey(keyring, key, type, next_state);
  rule3a = keymgr_have_rrsig(keyring, key, type, NA);
  rule3b = keymgr_have_rrsig(keyring, key, type, next_state);

  /* Debug logging. */
  if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
    char keystr[DST_KEY_FORMATSIZE];
    dst_key_format(key->key, keystr, sizeof(keystr));
    isc_log_write(
      DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
      ISC_LOG_DEBUG(1),
      "keymgr: dnssec evaluation of %s %s record %s: "
      "rule1=(~%s or %s) rule2=(~%s or %s) "
      "rule3=(~%s or %s)",
      keymgr_keyrole(key->key), keystr, keystatetags[type],
      rule1a ? "true" : "false", rule1b ? "true" : "false",
      rule2a ? "true" : "false", rule2b ? "true" : "false",
      rule3a ? "true" : "false", rule3b ? "true" : "false");
  }

  /*
   * Rule checking:
   * First check the current situation: if the rule check fails,
   * we allow the transition to attempt to move us out of the
   * invalid state.  If the rule check passes, also check if
   * the next state is also still a valid situation.
   */
  char keystr2[DST_KEY_FORMATSIZE];
  dst_key_format(key->key, keystr2, sizeof(keystr2));

  /*
   * Rule 1: There must be a DS at all times.
   */
  if (!rule1a && !rule1b && next_state == UNRETENTIVE) {
    return false;
  }
  /*
   * Rule 2: There must be a DNSKEY at all times.  Again, first
   * check the current situation, then assess the next state.
   */
  if (!rule2a && !rule2b && next_state == UNRETENTIVE) {
    return false;
  }
  /*
   * Rule 3: There must be RRSIG records at all times. Again,
   * first check the current situation, then assess the next
   * state.
   */
  if (!rule3a && !rule3b && next_state == UNRETENTIVE) {
    return false;
  }

  return (!rule1a || rule1b) && (!rule2a || rule2b) &&
         (!rule3a || rule3b);
}

/*
 * Calculate the time when it is safe to do the next transition.
 *
 */
static void
keymgr_transition_time(dns_dnsseckey_t *key, int type,
           dst_key_state_t next_state, dns_kasp_t *kasp,
           isc_stdtime_t now, isc_stdtime_t *when) {
  isc_result_t result;
  isc_stdtime_t lastchange, dstime, sigtime, nexttime = now;
  dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
  uint32_t dsstate, sigstate, signdelay = 0;

  /*
   * No need to wait if we move things into an uncertain state.
   */
  if (next_state == RUMOURED || next_state == UNRETENTIVE) {
    *when = now;
    return;
  }

  result = dst_key_gettime(key->key, keystatetimes[type], &lastchange);
  if (result != ISC_R_SUCCESS) {
    /* No last change, for safety purposes let's set it to now. */
    dst_key_settime(key->key, keystatetimes[type], now);
    lastchange = now;
  }

  switch (type) {
  case DST_KEY_DNSKEY:
  case DST_KEY_KRRSIG:
    switch (next_state) {
    case OMNIPRESENT:
      /*
       * RFC 7583: The publication interval (Ipub) is the
       * amount of time that must elapse after the
       * publication of a DNSKEY (plus RRSIG (KSK)) before
       * it can be assumed that any resolvers that have the
       * relevant RRset cached have a copy of the new
       * information.  This is the sum of the propagation
       * delay (Dprp) and the DNSKEY TTL (TTLkey).  This
       * translates to zone-propagation-delay + dnskey-ttl.
       * We will also add the publish-safety interval.
       */
      nexttime = lastchange + dst_key_getttl(key->key) +
           dns_kasp_zonepropagationdelay(kasp) +
           dns_kasp_publishsafety(kasp);
      break;
    case HIDDEN:
      /*
       * Same as OMNIPRESENT but without the publish-safety
       * interval.
       */
      nexttime = lastchange + dst_key_getttl(key->key) +
           dns_kasp_zonepropagationdelay(kasp);
      break;
    default:
      nexttime = now;
      break;
    }
    break;
  case DST_KEY_ZRRSIG:
    switch (next_state) {
    case OMNIPRESENT:
    case HIDDEN:
      /* Was there a full sign? */
      sigstate = (next_state == HIDDEN) ? DST_TIME_SIGDELETE
                : DST_TIME_SIGPUBLISH;
      result = dst_key_gettime(key->key, sigstate, &sigtime);
      if (result == ISC_R_SUCCESS && sigtime <= now) {
        signdelay = 0;
      } else {
        sigtime = lastchange;
        signdelay = dns_kasp_signdelay(kasp);
      }

      /*
       * RFC 7583: The retire interval (Iret) is the amount
       * of time that must elapse after a DNSKEY or
       * associated data enters the retire state for any
       * dependent information (RRSIG ZSK) to be purged from
       * validating resolver caches.  This is defined as:
       *
       *     Iret = Dsgn + Dprp + TTLsig
       *
       * Where Dsgn is the Dsgn is the delay needed to
       * ensure that all existing RRsets have been re-signed
       * with the new key, Dprp is the propagation delay and
       * TTLsig is the maximum TTL of all zone RRSIG
       * records.  This translates to:
       *
       *     Dsgn + zone-propagation-delay + max-zone-ttl.
       */
      nexttime = sigtime + ttlsig +
           dns_kasp_zonepropagationdelay(kasp);
      /*
       * Only add the sign delay Dsgn and retire-safety if
       * there is an actual predecessor or successor key.
       */
      uint32_t tag;
      result = dst_key_getnum(key->key, DST_NUM_PREDECESSOR,
            &tag);
      if (result != ISC_R_SUCCESS) {
        result = dst_key_getnum(
          key->key, DST_NUM_SUCCESSOR, &tag);
      }
      if (result == ISC_R_SUCCESS) {
        nexttime += signdelay +
              dns_kasp_retiresafety(kasp);
      }
      break;
    default:
      nexttime = now;
      break;
    }
    break;
  case DST_KEY_DS:
    switch (next_state) {
    /*
     * RFC 7583: The successor DS record is published in
     * the parent zone and after the registration delay
     * (Dreg), the time taken after the DS record has been
     * submitted to the parent zone manager for it to be
     * placed in the zone.  Key N (the predecessor) must
     * remain in the zone until any caches that contain a
     * copy of the DS RRset have a copy containing the new
     * DS record. This interval is the retire interval
     * (Iret), given by:
     *
     *      Iret = DprpP + TTLds
     *
     * This translates to:
     *
     *      parent-propagation-delay + parent-ds-ttl.
     */
    case OMNIPRESENT:
    case HIDDEN:
      /* Make sure DS has been seen in/withdrawn from the
       * parent. */
      dsstate = next_state == HIDDEN ? DST_TIME_DSDELETE
                   : DST_TIME_DSPUBLISH;
      result = dst_key_gettime(key->key, dsstate, &dstime);
      if (result != ISC_R_SUCCESS || dstime > now) {
        /* Not yet, try again in an hour. */
        nexttime = now + 3600;
      } else {
        nexttime =
          dstime + dns_kasp_dsttl(kasp) +
          dns_kasp_parentpropagationdelay(kasp);
        /*
         * Only add the retire-safety if there is an
         * actual predecessor or successor key.
         */
        uint32_t tag;
        result = dst_key_getnum(
          key->key, DST_NUM_PREDECESSOR, &tag);
        if (result != ISC_R_SUCCESS) {
          result = dst_key_getnum(
            key->key, DST_NUM_SUCCESSOR,
            &tag);
        }
        if (result == ISC_R_SUCCESS) {
          nexttime += dns_kasp_retiresafety(kasp);
        }
      }
      break;
    default:
      nexttime = now;
      break;
    }
    break;
  default:
    UNREACHABLE();
    break;
  }

  *when = nexttime;
}

/*
 * Update keys.
 * This implements Algorithm (1) of "Flexible and Robust Key Rollover".
 *
 */
static isc_result_t
keymgr_update(dns_dnsseckeylist_t *keyring, dns_kasp_t *kasp, isc_stdtime_t now,
        isc_stdtime_t *nexttime, uint8_t opts) {
  isc_result_t result = DNS_R_UNCHANGED;
  bool changed;
  bool force = ((opts & DNS_KEYMGRATTR_FORCESTEP) != 0);

  /* Repeat until nothing changed. */
transition:
  changed = false;

  /* For all keys in the zone. */
  ISC_LIST_FOREACH(*keyring, dkey, link) {
    char keystr[DST_KEY_FORMATSIZE];
    dst_key_format(dkey->key, keystr, sizeof(keystr));

    if (dkey->purge) {
      /* Skip purged keys. */
      continue;
    }

    /* For all records related to this key. */
    for (int i = 0; i < NUM_KEYSTATES; i++) {
      isc_stdtime_t when;
      dst_key_state_t state, next_state;

      if (dst_key_getstate(dkey->key, i, &state) ==
          ISC_R_NOTFOUND)
      {
        /*
         * This record type is not applicable for this
         * key, continue to the next record type.
         */
        continue;
      }

      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: examine %s %s type %s "
              "in state %s",
              keymgr_keyrole(dkey->key), keystr,
              keystatetags[i], keystatestrings[state]);

      /* Get the desired next state. */
      next_state = keymgr_desiredstate(dkey, state);
      if (state == next_state) {
        /*
         * This record is in a stable state.
         * No change needed, continue with the next
         * record type.
         */
        isc_log_write(DNS_LOGCATEGORY_DNSSEC,
                DNS_LOGMODULE_DNSSEC,
                ISC_LOG_DEBUG(1),
                "keymgr: %s %s type %s in "
                "stable state %s",
                keymgr_keyrole(dkey->key), keystr,
                keystatetags[i],
                keystatestrings[state]);
        continue;
      }

      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: can we transition %s %s type %s "
              "state %s to state %s?",
              keymgr_keyrole(dkey->key), keystr,
              keystatetags[i], keystatestrings[state],
              keystatestrings[next_state]);

      /* Is the transition allowed according to policy? */
      if (!keymgr_policy_approval(keyring, dkey, i,
                next_state))
      {
        /* No, please respect rollover methods. */
        isc_log_write(
          DNS_LOGCATEGORY_DNSSEC,
          DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
          "keymgr: policy says no to %s %s type "
          "%s "
          "state %s to state %s",
          keymgr_keyrole(dkey->key), keystr,
          keystatetags[i], keystatestrings[state],
          keystatestrings[next_state]);

        continue;
      }

      /* Is the transition DNSSEC safe? */
      if (!keymgr_transition_allowed(keyring, dkey, i,
                   next_state, opts))
      {
        /* No, this would make the zone bogus. */
        isc_log_write(
          DNS_LOGCATEGORY_DNSSEC,
          DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
          "keymgr: dnssec says no to %s %s type "
          "%s "
          "state %s to state %s",
          keymgr_keyrole(dkey->key), keystr,
          keystatetags[i], keystatestrings[state],
          keystatestrings[next_state]);
        continue;
      }

      /* Is it time to make the transition? */
      when = now;
      keymgr_transition_time(dkey, i, next_state, kasp, now,
                 &when);
      if (when > now) {
        /* Not yet. */
        isc_log_write(
          DNS_LOGCATEGORY_DNSSEC,
          DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
          "keymgr: time says no to %s %s type %s "
          "state %s to state %s (wait %u "
          "seconds)",
          keymgr_keyrole(dkey->key), keystr,
          keystatetags[i], keystatestrings[state],
          keystatestrings[next_state],
          when - now);
        if (*nexttime == 0 || *nexttime > when) {
          *nexttime = when;
        }
        continue;
      }

      /*
       * Are we allowed to make the transition automatically?
       */
      if (next_state != OMNIPRESENT && next_state != HIDDEN) {
        if (dns_kasp_manualmode(kasp) && !force) {
          isc_log_write(
            DNS_LOGCATEGORY_DNSSEC,
            DNS_LOGMODULE_DNSSEC,
            ISC_LOG_INFO,
            "keymgr-manual-mode: block "
            "transition "
            "%s %s type %s "
            "state %s to state %s",
            keymgr_keyrole(dkey->key),
            keystr, keystatetags[i],
            keystatestrings[state],
            keystatestrings[next_state]);
          continue;
        }
      }

      /* It is safe to make the transition. */
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: transition %s %s type %s "
              "state %s to state %s!",
              keymgr_keyrole(dkey->key), keystr,
              keystatetags[i], keystatestrings[state],
              keystatestrings[next_state]);

      dst_key_setstate(dkey->key, i, next_state);
      dst_key_settime(dkey->key, keystatetimes[i], now);
      INSIST(dst_key_ismodified(dkey->key));
      changed = true;
    }
  }

  /* We changed something, continue processing. */
  if (changed) {
    result = ISC_R_SUCCESS;
    /* No longer force for the next run */
    force = false;
    goto transition;
  }

  return result;
}

void
dns_keymgr_key_init(dns_dnsseckey_t *key, dns_kasp_t *kasp, isc_stdtime_t now,
        bool csk) {
  bool ksk, zsk;
  isc_result_t result;
  isc_stdtime_t active = 0, pub = 0, syncpub = 0, retire = 0, remove = 0;
  dst_key_state_t dnskey_state = HIDDEN;
  dst_key_state_t ds_state = HIDDEN;
  dst_key_state_t zrrsig_state = HIDDEN;
  dst_key_state_t goal_state = HIDDEN;

  REQUIRE(key != NULL);
  REQUIRE(key->key != NULL);

  /* Initialize role. */
  result = dst_key_getbool(key->key, DST_BOOL_KSK, &ksk);
  if (result != ISC_R_SUCCESS) {
    ksk = ((dst_key_flags(key->key) & DNS_KEYFLAG_KSK) != 0);
    dst_key_setbool(key->key, DST_BOOL_KSK, ksk || csk);
  }
  result = dst_key_getbool(key->key, DST_BOOL_ZSK, &zsk);
  if (result != ISC_R_SUCCESS) {
    zsk = ((dst_key_flags(key->key) & DNS_KEYFLAG_KSK) == 0);
    dst_key_setbool(key->key, DST_BOOL_ZSK, zsk || csk);
  }

  /* Get time metadata. */
  result = dst_key_gettime(key->key, DST_TIME_ACTIVATE, &active);
  if (active <= now && result == ISC_R_SUCCESS) {
    dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
    ttlsig += dns_kasp_zonepropagationdelay(kasp);
    if ((active + ttlsig) <= now) {
      zrrsig_state = OMNIPRESENT;
    } else {
      zrrsig_state = RUMOURED;
    }
    goal_state = OMNIPRESENT;
  }
  result = dst_key_gettime(key->key, DST_TIME_PUBLISH, &pub);
  if (pub <= now && result == ISC_R_SUCCESS) {
    dns_ttl_t key_ttl = dst_key_getttl(key->key);
    key_ttl += dns_kasp_zonepropagationdelay(kasp);
    if ((pub + key_ttl) <= now) {
      dnskey_state = OMNIPRESENT;
    } else {
      dnskey_state = RUMOURED;
    }
    goal_state = OMNIPRESENT;
  }
  result = dst_key_gettime(key->key, DST_TIME_SYNCPUBLISH, &syncpub);
  if (syncpub <= now && result == ISC_R_SUCCESS) {
    dns_ttl_t ds_ttl = dns_kasp_dsttl(kasp);
    ds_ttl += dns_kasp_parentpropagationdelay(kasp);
    if ((syncpub + ds_ttl) <= now) {
      ds_state = OMNIPRESENT;
    } else {
      ds_state = RUMOURED;
    }
    goal_state = OMNIPRESENT;
  }
  result = dst_key_gettime(key->key, DST_TIME_INACTIVE, &retire);
  if (retire <= now && result == ISC_R_SUCCESS) {
    dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
    ttlsig += dns_kasp_zonepropagationdelay(kasp);
    if ((retire + ttlsig) <= now) {
      zrrsig_state = HIDDEN;
    } else {
      zrrsig_state = UNRETENTIVE;
    }
    ds_state = UNRETENTIVE;
    goal_state = HIDDEN;
  }
  result = dst_key_gettime(key->key, DST_TIME_DELETE, &remove);
  if (remove <= now && result == ISC_R_SUCCESS) {
    dns_ttl_t key_ttl = dst_key_getttl(key->key);
    key_ttl += dns_kasp_zonepropagationdelay(kasp);
    if ((remove + key_ttl) <= now) {
      dnskey_state = HIDDEN;
    } else {
      dnskey_state = UNRETENTIVE;
    }
    zrrsig_state = HIDDEN;
    ds_state = HIDDEN;
    goal_state = HIDDEN;
  }

  /* Set goal if not already set. */
  if (dst_key_getstate(key->key, DST_KEY_GOAL, &goal_state) !=
      ISC_R_SUCCESS)
  {
    dst_key_setstate(key->key, DST_KEY_GOAL, goal_state);
  }

  /* Set key states for all keys that do not have them. */
  INITIALIZE_STATE(key->key, DST_KEY_DNSKEY, DST_TIME_DNSKEY,
       dnskey_state, now);
  if (ksk || csk) {
    INITIALIZE_STATE(key->key, DST_KEY_KRRSIG, DST_TIME_KRRSIG,
         dnskey_state, now);
    INITIALIZE_STATE(key->key, DST_KEY_DS, DST_TIME_DS, ds_state,
         now);
  }
  if (zsk || csk) {
    INITIALIZE_STATE(key->key, DST_KEY_ZRRSIG, DST_TIME_ZRRSIG,
         zrrsig_state, now);
  }
}

static isc_result_t
keymgr_key_rollover(dns_kasp_key_t *kaspkey, dns_dnsseckey_t *active_key,
        dns_dnsseckeylist_t *keyring, dns_dnsseckeylist_t *newkeys,
        const dns_name_t *origin, dns_rdataclass_t rdclass,
        dns_kasp_t *kasp, const char *keydir, uint32_t lifetime,
        uint8_t opts, isc_stdtime_t now, isc_stdtime_t *nexttime,
        isc_mem_t *mctx) {
  char keystr[DST_KEY_FORMATSIZE];
  char namestr[DNS_NAME_FORMATSIZE];
  isc_stdtime_t retire = 0, active = 0, prepub = 0;
  dns_dnsseckey_t *new_key = NULL;
  dst_key_t *dst_key = NULL;
  bool keycreated = false;

  /* Do we need to create a successor for the active key? */
  if (active_key != NULL) {
    if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
      dst_key_format(active_key->key, keystr, sizeof(keystr));
      isc_log_write(
        DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
        ISC_LOG_DEBUG(1),
        "keymgr: DNSKEY %s (%s) is active in policy %s",
        keystr, keymgr_keyrole(active_key->key),
        dns_kasp_getname(kasp));
    }

    /*
     * Calculate when the successor needs to be published
     * in the zone.
     */
    prepub = keymgr_prepublication_time(active_key, kasp, lifetime,
                now);
    if (prepub > now) {
      if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
        dst_key_format(active_key->key, keystr,
                 sizeof(keystr));
        isc_log_write(
          DNS_LOGCATEGORY_DNSSEC,
          DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
          "keymgr: new successor needed for "
          "DNSKEY %s (%s) (policy %s) in %u "
          "seconds",
          keystr, keymgr_keyrole(active_key->key),
          dns_kasp_getname(kasp), prepub - now);
      }
    }
    if (prepub == 0 || prepub > now) {
      /* No need to start rollover now. */
      if (*nexttime == 0 || prepub < *nexttime) {
        if (prepub > 0) {
          *nexttime = prepub;
        }
      }
      return ISC_R_SUCCESS;
    }

    if (keymgr_key_has_successor(active_key, keyring)) {
      /* Key already has successor. */
      if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
        dst_key_format(active_key->key, keystr,
                 sizeof(keystr));
        isc_log_write(
          DNS_LOGCATEGORY_DNSSEC,
          DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
          "keymgr: key DNSKEY %s (%s) (policy "
          "%s) already has successor",
          keystr, keymgr_keyrole(active_key->key),
          dns_kasp_getname(kasp));
      }
      return ISC_R_SUCCESS;
    }

    if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
      dst_key_format(active_key->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: need successor for DNSKEY %s "
              "(%s) (policy %s)",
              keystr, keymgr_keyrole(active_key->key),
              dns_kasp_getname(kasp));
    }

    /*
     * If rollover is not allowed, warn.
     */
    if ((opts & DNS_KEYMGRATTR_NOROLL) != 0) {
      dst_key_format(active_key->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_WARNING,
              "keymgr: DNSKEY %s (%s) is offline in "
              "policy %s, cannot start rollover",
              keystr, keymgr_keyrole(active_key->key),
              dns_kasp_getname(kasp));
      return ISC_R_SUCCESS;
    }
  } else if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
    dns_name_format(origin, namestr, sizeof(namestr));
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_DEBUG(1),
            "keymgr: no active key found for %s (policy %s)",
            namestr, dns_kasp_getname(kasp));
  }

  /* It is time to do key rollover, we need a new key. */

  /*
   * Check if there is a key available in pool because keys
   * may have been pregenerated with dnssec-keygen.
   */
  ISC_LIST_FOREACH(*keyring, candidate, link) {
    if (dns_kasp_key_match(kaspkey, candidate) &&
        dst_key_is_unused(candidate->key))
    {
      /* Found a candidate in keyring. */
      new_key = candidate;
      break;
    }
  }

  if (dns_kasp_manualmode(kasp) && (opts & DNS_KEYMGRATTR_FORCESTEP) == 0)
  {
    if (active_key != NULL && new_key != NULL) {
      char keystr2[DST_KEY_FORMATSIZE];
      dst_key_format(active_key->key, keystr, sizeof(keystr));
      dst_key_format(new_key->key, keystr2, sizeof(keystr2));
      dns_name_format(origin, namestr, sizeof(namestr));
      isc_log_write(
        DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
        ISC_LOG_INFO,
        "keymgr-manual-mode: block %s rollover for key "
        "%s to key %s (policy %s)",
        keymgr_keyrole(active_key->key), keystr,
        keystr2, dns_kasp_getname(kasp));
    } else if (active_key != NULL) {
      dst_key_format(active_key->key, keystr, sizeof(keystr));
      dns_name_format(origin, namestr, sizeof(namestr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
              "keymgr-manual-mode: block %s rollover "
              "for key %s (policy %s)",
              keymgr_keyrole(active_key->key), keystr,
              dns_kasp_getname(kasp));
    } else if (new_key != NULL) {
      dst_key_format(new_key->key, keystr, sizeof(keystr));
      dns_name_format(origin, namestr, sizeof(namestr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
              "keymgr-manual-mode: block %s "
              "introduction %s (policy %s)",
              keymgr_keyrole(new_key->key), keystr,
              dns_kasp_getname(kasp));
    } else {
      dns_name_format(origin, namestr, sizeof(namestr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
              "keymgr-manual-mode: block new key "
              "generation for zone %s (policy %s)",
              namestr, dns_kasp_getname(kasp));
    }
    return ISC_R_SUCCESS;
  }

  if (new_key == NULL) {
    /* No key available in keyring, create a new one. */
    bool csk = (dns_kasp_key_ksk(kaspkey) &&
          dns_kasp_key_zsk(kaspkey));

    isc_result_t result = keymgr_createkey(
      kaspkey, origin, kasp, rdclass, mctx, keydir, keyring,
      now, newkeys, &dst_key);
    if (result != ISC_R_SUCCESS) {
      return result;
    }
    dst_key_setttl(dst_key, dns_kasp_dnskeyttl(kasp));
    dst_key_settime(dst_key, DST_TIME_CREATED, now);
    dns_dnsseckey_create(mctx, &dst_key, &new_key);
    dns_keymgr_key_init(new_key, kasp, now, csk);
    keycreated = true;
  }
  dst_key_setnum(new_key->key, DST_NUM_LIFETIME, lifetime);

  /* Got a key. */
  if (active_key == NULL) {
    /*
     * If there is no active key found yet for this kasp
     * key configuration, immediately make this key active.
     */
    dst_key_settime(new_key->key, DST_TIME_PUBLISH, now);
    dst_key_settime(new_key->key, DST_TIME_ACTIVATE, now);
    dns_keymgr_settime_syncpublish(new_key->key, kasp, true);
    active = now;
  } else {
    /*
     * This is a successor.  Mark the relationship.
     */
    isc_stdtime_t created;
    (void)dst_key_gettime(new_key->key, DST_TIME_CREATED, &created);

    dst_key_setnum(new_key->key, DST_NUM_PREDECESSOR,
             dst_key_id(active_key->key));
    dst_key_setnum(active_key->key, DST_NUM_SUCCESSOR,
             dst_key_id(new_key->key));
    (void)dst_key_gettime(active_key->key, DST_TIME_INACTIVE,
              &retire);
    active = retire;

    /*
     * If prepublication time and/or retire time are
     * in the past (before the new key was created), use
     * creation time as published and active time,
     * effectively immediately making the key active.
     */
    if (prepub < created) {
      active += (created - prepub);
      prepub = created;
    }
    if (active < created) {
      active = created;
    }
    dst_key_settime(new_key->key, DST_TIME_PUBLISH, prepub);
    dst_key_settime(new_key->key, DST_TIME_ACTIVATE, active);
    dns_keymgr_settime_syncpublish(new_key->key, kasp, false);

    /*
     * Retire predecessor.
     */
    dst_key_setstate(active_key->key, DST_KEY_GOAL, HIDDEN);
  }

  /* This key wants to be present. */
  dst_key_setstate(new_key->key, DST_KEY_GOAL, OMNIPRESENT);

  /* Do we need to set retire time? */
  if (lifetime > 0) {
    uint32_t inactive;

    if (ckd_add(&inactive, active, lifetime)) {
      log_key_overflow(new_key->key, "inactive");
      inactive = UINT32_MAX;
    }
    dst_key_settime(new_key->key, DST_TIME_INACTIVE, inactive);
    keymgr_settime_remove(new_key, kasp);
  }

  /* Append dnsseckey to list of new keys. */
  dns_dnssec_get_hints(new_key, now);
  new_key->source = dns_keysource_repository;
  INSIST(!new_key->legacy);
  if (keycreated) {
    ISC_LIST_APPEND(*newkeys, new_key, link);
  }

  /* Logging. */
  dst_key_format(new_key->key, keystr, sizeof(keystr));
  isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
          ISC_LOG_INFO, "keymgr: DNSKEY %s (%s) %s for policy %s",
          keystr, keymgr_keyrole(new_key->key),
          keycreated ? "created" : "selected",
          dns_kasp_getname(kasp));
  return ISC_R_SUCCESS;
}

bool
dns_keymgr_key_may_be_purged(const dst_key_t *key, uint32_t after,
           isc_stdtime_t now) {
  bool ksk = false;
  bool zsk = false;
  dst_key_state_t hidden[NUM_KEYSTATES] = { HIDDEN, NA, NA, NA };
  isc_stdtime_t lastchange = 0;

  char keystr[DST_KEY_FORMATSIZE];
  dst_key_format(key, keystr, sizeof(keystr));

  /* If 'purge-keys' is disabled, always retain keys. */
  if (after == 0) {
    return false;
  }

  /* Don't purge keys with goal OMNIPRESENT */
  if (dst_key_goal(key) == OMNIPRESENT) {
    return false;
  }

  /* Don't purge unused keys. */
  if (dst_key_is_unused(key)) {
    return false;
  }

  /* If this key is completely HIDDEN it may be purged. */
  (void)dst_key_getbool(key, DST_BOOL_KSK, &ksk);
  (void)dst_key_getbool(key, DST_BOOL_ZSK, &zsk);
  if (ksk) {
    hidden[DST_KEY_KRRSIG] = HIDDEN;
    hidden[DST_KEY_DS] = HIDDEN;
  }
  if (zsk) {
    hidden[DST_KEY_ZRRSIG] = HIDDEN;
  }
  if (!keymgr_key_match_state(key, key, 0, NA, hidden)) {
    return false;
  }

  /*
   * Check 'purge-keys' interval. If the interval has passed since
   * the last key change, it may be purged.
   */
  for (int i = 0; i < NUM_KEYSTATES; i++) {
    isc_stdtime_t change = 0;
    (void)dst_key_gettime(key, keystatetimes[i], &change);
    if (change > lastchange) {
      lastchange = change;
    }
  }

  return (lastchange + after) < now;
}

static void
keymgr_purge_keyfile(dst_key_t *key, int type) {
  isc_result_t result;
  isc_buffer_t fileb;
  char filename[NAME_MAX];

  /*
   * Make the filename.
   */
  isc_buffer_init(&fileb, filename, sizeof(filename));
  result = dst_key_buildfilename(key, type, dst_key_directory(key),
               &fileb);
  if (result != ISC_R_SUCCESS) {
    char keystr[DST_KEY_FORMATSIZE];
    dst_key_format(key, keystr, sizeof(keystr));
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_WARNING,
            "keymgr: failed to purge DNSKEY %s (%s): cannot "
            "build filename (%s)",
            keystr, keymgr_keyrole(key),
            isc_result_totext(result));
    return;
  }

  if (unlink(filename) < 0) {
    char keystr[DST_KEY_FORMATSIZE];
    dst_key_format(key, keystr, sizeof(keystr));
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_WARNING,
            "keymgr: failed to purge DNSKEY %s (%s): unlink "
            "'%s' failed",
            keystr, keymgr_keyrole(key), filename);
  }
}

static bool
dst_key_doublematch(dns_dnsseckey_t *key, dns_kasp_t *kasp) {
  int matches = 0;

  ISC_LIST_FOREACH(dns_kasp_keys(kasp), kkey, link) {
    if (dns_kasp_key_match(kkey, key)) {
      matches++;
    }
  }
  return matches > 1;
}

static void
keymgr_zrrsig(dns_dnsseckeylist_t *keyring, isc_stdtime_t now) {
  ISC_LIST_FOREACH(*keyring, dkey, link) {
    isc_result_t result;
    bool zsk = false;
    dst_key_state_t state;

    result = dst_key_getbool(dkey->key, DST_BOOL_ZSK, &zsk);
    if (result != ISC_R_SUCCESS || !zsk) {
      continue;
    }

    result = dst_key_getstate(dkey->key, DST_KEY_ZRRSIG, &state);
    if (result == ISC_R_SUCCESS) {
      if (state == RUMOURED) {
        dst_key_settime(dkey->key, DST_TIME_SIGPUBLISH,
            now);
      } else if (state == UNRETENTIVE) {
        dst_key_settime(dkey->key, DST_TIME_SIGDELETE,
            now);
      }
    }
  }
}

/*
 * Examine 'keys' and match 'kasp' policy.
 *
 */
isc_result_t
dns_keymgr_run(const dns_name_t *origin, dns_rdataclass_t rdclass,
         isc_mem_t *mctx, dns_dnsseckeylist_t *keyring,
         dns_dnsseckeylist_t *dnskeys, const char *keydir,
         dns_kasp_t *kasp, uint8_t opts, isc_stdtime_t now,
         isc_stdtime_t *nexttime) {
  isc_result_t result = DNS_R_UNCHANGED;
  dns_dnsseckeylist_t newkeys;
  int numkeys = 0;
  int options = (DST_TYPE_PRIVATE | DST_TYPE_PUBLIC | DST_TYPE_STATE);
  char keystr[DST_KEY_FORMATSIZE];

  REQUIRE(dns_name_isvalid(origin));
  REQUIRE(mctx != NULL);
  REQUIRE(keyring != NULL);
  REQUIRE(DNS_KASP_VALID(kasp));

  ISC_LIST_INIT(newkeys);

  *nexttime = 0;

  /* Debug logging: what keys are available in the keyring? */
  if (isc_log_wouldlog(ISC_LOG_DEBUG(1))) {
    if (ISC_LIST_EMPTY(*keyring)) {
      char namebuf[DNS_NAME_FORMATSIZE];
      dns_name_format(origin, namebuf, sizeof(namebuf));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: keyring empty (zone %s policy "
              "%s)",
              namebuf, dns_kasp_getname(kasp));
    }

    ISC_LIST_FOREACH(*keyring, dkey, link) {
      dst_key_format(dkey->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: keyring: %s (policy %s)", keystr,
              dns_kasp_getname(kasp));
    }
    ISC_LIST_FOREACH(*dnskeys, dkey, link) {
      dst_key_format(dkey->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(1),
              "keymgr: dnskeys: %s (policy %s)", keystr,
              dns_kasp_getname(kasp));
    }
  }

  ISC_LIST_FOREACH(*dnskeys, dkey, link) {
    numkeys++;
  }

  /* Do we need to remove keys? */
  ISC_LIST_FOREACH(*keyring, dkey, link) {
    bool found_match = false;

    dns_keymgr_key_init(dkey, kasp, now, numkeys == 1);

    ISC_LIST_FOREACH(dns_kasp_keys(kasp), kkey, link) {
      if (dns_kasp_key_match(kkey, dkey)) {
        found_match = true;
        break;
      }
    }

    /* No match, so retire unwanted retire key. */
    if (!found_match) {
      keymgr_key_retire(dkey, kasp, opts, now);
    }

    /* Check purge-keys interval. */
    if (dns_keymgr_key_may_be_purged(dkey->key,
             dns_kasp_purgekeys(kasp), now))
    {
      dst_key_format(dkey->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
              "keymgr: purge DNSKEY %s (%s) according "
              "to policy %s",
              keystr, keymgr_keyrole(dkey->key),
              dns_kasp_getname(kasp));

      keymgr_purge_keyfile(dkey->key, DST_TYPE_PUBLIC);
      keymgr_purge_keyfile(dkey->key, DST_TYPE_PRIVATE);
      keymgr_purge_keyfile(dkey->key, DST_TYPE_STATE);
      dkey->purge = true;
    }
  }

  /* Create keys according to the policy, if come in short. */
  ISC_LIST_FOREACH(dns_kasp_keys(kasp), kkey, link) {
    uint32_t lifetime = dns_kasp_key_lifetime(kkey);
    dns_dnsseckey_t *active_key = NULL;

    /* Do we have keys available for this kasp key? */
    ISC_LIST_FOREACH(*keyring, dkey, link) {
      if (dns_kasp_key_match(kkey, dkey)) {
        /* Found a match. */
        dst_key_format(dkey->key, keystr,
                 sizeof(keystr));
        isc_log_write(DNS_LOGCATEGORY_DNSSEC,
                DNS_LOGMODULE_DNSSEC,
                ISC_LOG_DEBUG(1),
                "keymgr: DNSKEY %s (%s) matches "
                "policy %s",
                keystr, keymgr_keyrole(dkey->key),
                dns_kasp_getname(kasp));

        /* Update lifetime if changed. */
        keymgr_key_update_lifetime(dkey, kasp, now,
                 lifetime);

        if (active_key) {
          /* We already have an active key that
           * matches the kasp policy.
           */
          if (!dst_key_is_unused(dkey->key) &&
              !dst_key_doublematch(dkey, kasp) &&
              (dst_key_goal(dkey->key) ==
               OMNIPRESENT) &&
              !keymgr_dep(dkey->key, keyring,
              NULL) &&
              !keymgr_dep(active_key->key,
              keyring, NULL))
          {
            /*
             * Multiple signing keys match
             * the kasp key configuration.
             * Retire excess keys in use.
             */
            keymgr_key_retire(dkey, kasp,
                  opts, now);
          }
          continue;
        }

        /*
         * Save the matched key only if it is active
         * or desires to be active.
         */
        if (dst_key_goal(dkey->key) == OMNIPRESENT ||
            dst_key_is_active(dkey->key, now))
        {
          active_key = dkey;
        }
      }
    }

    if (active_key == NULL) {
      /*
       * We didn't found an active key, perhaps the .private
       * key file is offline. If so, we don't want to create
       * a successor key. Check if we have an appropriate
       * state file.
       */
      ISC_LIST_FOREACH(*dnskeys, dnskey, link) {
        if (dns_kasp_key_match(kkey, dnskey)) {
          /* Found a match. */
          dst_key_format(dnskey->key, keystr,
                   sizeof(keystr));
          isc_log_write(
            DNS_LOGCATEGORY_DNSSEC,
            DNS_LOGMODULE_DNSSEC,
            ISC_LOG_DEBUG(1),
            "keymgr: DNSKEY %s (%s) "
            "offline, policy %s",
            keystr,
            keymgr_keyrole(dnskey->key),
            dns_kasp_getname(kasp));
          opts |= DNS_KEYMGRATTR_NOROLL;
          active_key = dnskey;
          break;
        }
      }
    }

    /* See if this key requires a rollover. */
    CHECK(keymgr_key_rollover(kkey, active_key, keyring, &newkeys,
            origin, rdclass, kasp, keydir,
            lifetime, opts, now, nexttime, mctx));

    opts &= ~DNS_KEYMGRATTR_NOROLL;
  }

  /* Walked all kasp key configurations.  Append new keys. */
  if (!ISC_LIST_EMPTY(newkeys)) {
    ISC_LIST_APPENDLIST(*keyring, newkeys, link);
  }

  /*
   * If the policy has an empty key list, this means the zone is going
   * back to unsigned.
   */
  if (dns_kasp_keylist_empty(kasp)) {
    opts |= DNS_KEYMGRATTR_S2I;
  }

  /* In case of a full sign, store ZRRSIGPublish/ZRRSIGDelete. */
  if ((opts & DNS_KEYMGRATTR_FULLSIGN) != 0) {
    keymgr_zrrsig(keyring, now);
  }

  /* Read to update key states. */
  isc_result_t retval = keymgr_update(keyring, kasp, now, nexttime, opts);

  /* Store key states and update hints. */
  ISC_LIST_FOREACH(*keyring, dkey, link) {
    bool modified = dst_key_ismodified(dkey->key);
    if (dst_key_getttl(dkey->key) != dns_kasp_dnskeyttl(kasp)) {
      dst_key_setttl(dkey->key, dns_kasp_dnskeyttl(kasp));
      modified = true;
      retval = ISC_R_SUCCESS;
    }
    if (modified && !dkey->purge) {
      const char *directory = dst_key_directory(dkey->key);
      if (directory == NULL) {
        directory = ".";
      }

      dns_dnssec_get_hints(dkey, now);
      CHECK(dst_key_tofile(dkey->key, options, directory));
      dst_key_setmodified(dkey->key, false);

      if (!isc_log_wouldlog(ISC_LOG_DEBUG(3))) {
        continue;
      }
      dst_key_format(dkey->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(3),
              "keymgr: DNSKEY %s (%s) "
              "saved to directory %s, policy %s",
              keystr, keymgr_keyrole(dkey->key),
              directory, dns_kasp_getname(kasp));
    }
    dst_key_setmodified(dkey->key, false);
  }

  result = retval;

cleanup:
  if (result != ISC_R_SUCCESS) {
    ISC_LIST_FOREACH(newkeys, newkey, link) {
      ISC_LIST_UNLINK(newkeys, newkey, link);
      INSIST(newkey->key != NULL);
      dst_key_free(&newkey->key);
      dns_dnsseckey_destroy(mctx, &newkey);
    }
  }

  if (isc_log_wouldlog(ISC_LOG_DEBUG(3))) {
    char namebuf[DNS_NAME_FORMATSIZE];
    dns_name_format(origin, namebuf, sizeof(namebuf));
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_DEBUG(3), "keymgr: %s done", namebuf);
  }
  return result;
}

static isc_result_t
keymgr_checkds(dns_kasp_t *kasp, dns_dnsseckeylist_t *keyring,
         isc_stdtime_t now, isc_stdtime_t when, bool dspublish,
         dns_keytag_t id, unsigned int alg, bool check_id) {
  int options = (DST_TYPE_PRIVATE | DST_TYPE_PUBLIC | DST_TYPE_STATE);
  const char *directory = NULL;
  isc_result_t result;
  dns_dnsseckey_t *ksk_key = NULL;

  REQUIRE(DNS_KASP_VALID(kasp));
  REQUIRE(keyring != NULL);

  ISC_LIST_FOREACH(*keyring, dkey, link) {
    bool ksk = false;

    result = dst_key_getbool(dkey->key, DST_BOOL_KSK, &ksk);
    if (result == ISC_R_SUCCESS && ksk) {
      if (check_id && dst_key_id(dkey->key) != id) {
        continue;
      }
      if (alg > 0 && dst_key_alg(dkey->key) != alg) {
        continue;
      }

      if (ksk_key != NULL) {
        /*
         * Only checkds for one key at a time.
         */
        return DNS_R_TOOMANYKEYS;
      }

      ksk_key = dkey;
    }
  }

  if (ksk_key == NULL) {
    return DNS_R_NOKEYMATCH;
  }

  if (dspublish) {
    dst_key_state_t s;
    dst_key_settime(ksk_key->key, DST_TIME_DSPUBLISH, when);
    result = dst_key_getstate(ksk_key->key, DST_KEY_DS, &s);
    if (result != ISC_R_SUCCESS || s != RUMOURED) {
      dst_key_setstate(ksk_key->key, DST_KEY_DS, RUMOURED);
    }
  } else {
    dst_key_state_t s;
    dst_key_settime(ksk_key->key, DST_TIME_DSDELETE, when);
    result = dst_key_getstate(ksk_key->key, DST_KEY_DS, &s);
    if (result != ISC_R_SUCCESS || s != UNRETENTIVE) {
      dst_key_setstate(ksk_key->key, DST_KEY_DS, UNRETENTIVE);
    }
  }

  if (isc_log_wouldlog(ISC_LOG_NOTICE)) {
    char keystr[DST_KEY_FORMATSIZE];
    char timestr[26]; /* Minimal buf as per ctime_r() spec. */

    dst_key_format(ksk_key->key, keystr, sizeof(keystr));
    isc_stdtime_tostring(when, timestr, sizeof(timestr));
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_NOTICE,
            "keymgr: checkds DS for key %s seen %s at %s",
            keystr, dspublish ? "published" : "withdrawn",
            timestr);
  }

  /* Store key state and update hints. */
  directory = dst_key_directory(ksk_key->key);
  if (directory == NULL) {
    directory = ".";
  }

  dns_dnssec_get_hints(ksk_key, now);
  result = dst_key_tofile(ksk_key->key, options, directory);
  if (result == ISC_R_SUCCESS) {
    dst_key_setmodified(ksk_key->key, false);
  }

  return result;
}

isc_result_t
dns_keymgr_checkds(dns_kasp_t *kasp, dns_dnsseckeylist_t *keyring,
       isc_stdtime_t now, isc_stdtime_t when, bool dspublish) {
  return keymgr_checkds(kasp, keyring, now, when, dspublish, 0, 0, false);
}

isc_result_t
dns_keymgr_checkds_id(dns_kasp_t *kasp, dns_dnsseckeylist_t *keyring,
          isc_stdtime_t now, isc_stdtime_t when, bool dspublish,
          dns_keytag_t id, unsigned int alg) {
  return keymgr_checkds(kasp, keyring, now, when, dspublish, id, alg,
            true);
}

static isc_result_t
keytime_status(dst_key_t *key, isc_stdtime_t now, isc_buffer_t *buf,
         const char *pre, int ks, int kt) {
  char timestr[26]; /* Minimal buf as per ctime_r() spec. */
  isc_result_t result = ISC_R_SUCCESS;
  isc_stdtime_t when = 0;
  dst_key_state_t state = NA;

  CHECK(isc_buffer_printf(buf, "%s", pre));
  (void)dst_key_getstate(key, ks, &state);
  isc_result_t r = dst_key_gettime(key, kt, &when);
  if (state == RUMOURED || state == OMNIPRESENT) {
    CHECK(isc_buffer_printf(buf, "yes - since "));
  } else if (now < when) {
    CHECK(isc_buffer_printf(buf, "no  - scheduled "));
  } else {
    return isc_buffer_printf(buf, "no\n");
  }
  if (r == ISC_R_SUCCESS) {
    isc_stdtime_tostring(when, timestr, sizeof(timestr));
    CHECK(isc_buffer_printf(buf, "%s\n", timestr));
  }

cleanup:
  return result;
}

static isc_result_t
keystate_status(dst_key_t *key, isc_buffer_t *buf, const char *pre, int ks) {
  dst_key_state_t state = NA;
  isc_result_t result = ISC_R_SUCCESS;

  (void)dst_key_getstate(key, ks, &state);
  switch (state) {
  case HIDDEN:
    CHECK(isc_buffer_printf(buf, "  - %shidden\n", pre));
    break;
  case RUMOURED:
    CHECK(isc_buffer_printf(buf, "  - %srumoured\n", pre));
    break;
  case OMNIPRESENT:
    CHECK(isc_buffer_printf(buf, "  - %somnipresent\n", pre));
    break;
  case UNRETENTIVE:
    CHECK(isc_buffer_printf(buf, "  - %sunretentive\n", pre));
    break;
  case NA:
  default:
    /* print nothing */
    break;
  }

cleanup:
  return result;
}

static isc_result_t
rollover_status(dns_dnsseckey_t *dkey, dns_kasp_t *kasp,
    dns_dnsseckeylist_t *keyring, isc_stdtime_t now,
    isc_buffer_t *buf, bool *verbose, bool checkds) {
  isc_result_t result = ISC_R_SUCCESS;
  dst_key_t *key = dkey->key;
  dst_key_state_t goal = HIDDEN;
  dst_key_state_t dnskey = HIDDEN;
  dst_key_state_t zrrsig = HIDDEN;
  dst_key_state_t ds = HIDDEN;
  bool ksk = false;
  bool zsk = false;
  bool log_next_rollover = false;
  int active_state = DST_TIME_ACTIVATE;
  int retire_state = DST_TIME_INACTIVE;

  (void)dst_key_getstate(key, DST_KEY_GOAL, &goal);
  (void)dst_key_getstate(key, DST_KEY_DNSKEY, &dnskey);
  (void)dst_key_getstate(key, DST_KEY_ZRRSIG, &zrrsig);
  (void)dst_key_getstate(key, DST_KEY_DS, &ds);

  // publish status
  CHECK(keytime_status(key, now, buf, "  Published:    ", DST_KEY_DNSKEY,
           DST_TIME_PUBLISH));

  // signing status
  result = dst_key_getbool(key, DST_BOOL_KSK, &ksk);
  if (result == ISC_R_SUCCESS && ksk) {
    CHECK(keytime_status(key, now, buf, "  Key signing:  ",
             DST_KEY_KRRSIG, DST_TIME_PUBLISH));
  }
  result = dst_key_getbool(key, DST_BOOL_ZSK, &zsk);
  if (result == ISC_R_SUCCESS && zsk) {
    CHECK(keytime_status(key, now, buf, "  Zone signing: ",
             DST_KEY_ZRRSIG, DST_TIME_ACTIVATE));
  }

  if (zsk) {
    if (goal == OMNIPRESENT) {
      if (dnskey == HIDDEN && zrrsig == HIDDEN) {
        CHECK(isc_buffer_printf(
          buf, "  Key is created but not "
               "published yet.\n"));
      } else if (dnskey == RUMOURED && zrrsig == HIDDEN) {
        CHECK(isc_buffer_printf(
          buf, "  Key is pre-published.\n"));
      } else if (dnskey == RUMOURED && zrrsig == RUMOURED) {
        CHECK(isc_buffer_printf(buf, "  Introducing "
                   "new key.\n"));
      } else if (dnskey == OMNIPRESENT && zrrsig == HIDDEN) {
        CHECK(isc_buffer_printf(
          buf, "  Key is published, but not yet "
               "signing.\n"));
      } else if (dnskey == OMNIPRESENT && zrrsig == RUMOURED)
      {
        if (keymgr_dep(key, keyring, NULL)) {
          CHECK(isc_buffer_printf(
            buf,
            "  Key is published, waiting "
            "for the zone to be completely "
            "signed with this key.\n"));
        } else {
          CHECK(isc_buffer_printf(
            buf,
            "  Key is published, "
            "introducing signatures.\n"));
        }
      } else if (dnskey == OMNIPRESENT &&
           zrrsig == OMNIPRESENT)
      {
        if (!ksk) {
          log_next_rollover = true;
        }
      } else {
        CHECK(isc_buffer_printf(
          buf, "  Key is in unexpected state, "
               "performing auto-healing.\n"));
        *verbose = true;
      }
    } else if (goal == HIDDEN) {
      if (dnskey == OMNIPRESENT && zrrsig == OMNIPRESENT) {
        if (!ksk) {
          CHECK(isc_buffer_printf(
            buf, "  Key will be retired "
                 "after successor key "
                 "becomes active.\n"));
        }
      } else if (dnskey == OMNIPRESENT &&
           zrrsig == UNRETENTIVE)
      {
        CHECK(isc_buffer_printf(
          buf,
          "  Key is retired, waiting until all "
          "signatures generated with this key "
          "are replaced with successor.\n"));
      } else if (dnskey == OMNIPRESENT && zrrsig == HIDDEN) {
        CHECK(isc_buffer_printf(
          buf, "  Key is retired, no longer "
               "signing the zone.\n"));
      } else if (dnskey == UNRETENTIVE && zrrsig == HIDDEN) {
        CHECK(isc_buffer_printf(buf, "  Key is removed "
                   "from zone.\n"));
      } else if (dnskey == HIDDEN && zrrsig == HIDDEN) {
        CHECK(isc_buffer_printf(
          buf, "  Key is completely hidden "
               "(waiting to be purged).\n"));
      } else {
        CHECK(isc_buffer_printf(
          buf, "  WARNING: Key is in unexpected "
               "state, "
               "performing auto-healing.\n"));
        *verbose = true;
      }
    }
  } else if (ksk) {
    if (goal == OMNIPRESENT) {
      if (dnskey == HIDDEN && ds == HIDDEN) {
        if (!zsk) {
          CHECK(isc_buffer_printf(
            buf, "  Key is created but not "
                 "published yet.\n"));
        }
      } else if (dnskey == RUMOURED && ds == HIDDEN) {
        if (!zsk) {
          CHECK(isc_buffer_printf(
            buf,
            "  Key is pre-published.\n"));
        }
      } else if (dnskey == OMNIPRESENT && ds == HIDDEN) {
        if (keymgr_dep(key, keyring, NULL)) {
          CHECK(isc_buffer_printf(
            buf,
            "  Waiting for the DS to be "
            "submitted to the parent.\n"));
        } else {
          CHECK(isc_buffer_printf(
            buf,
            "  Wait for zone to be fully "
            "signed before submitting the "
            "DS to the parent.\n"));
        }
      } else if (dnskey == OMNIPRESENT && ds == RUMOURED) {
        isc_stdtime_t dstime = now;
        isc_result_t ret = dst_key_gettime(
          key, DST_TIME_DSPUBLISH, &dstime);
        if (ret != ISC_R_SUCCESS || dstime > now) {
          CHECK(isc_buffer_printf(
            buf,
            "  Waiting for the DS to be "
            "published to the parent.\n"));
          if (checkds) {
            CHECK(isc_buffer_printf(
              buf,
              "  checkds is enabled, "
              "BIND will check the "
              "DS RRset "
              "periodically.\n"));
          } else {
            CHECK(isc_buffer_printf(
              buf,
              "  ! Once the DS is in "
              "the parent, run 'rndc "
              "dnssec -checkds -key "
              "%d published' to mark "
              "it as published.\n",
              dst_key_id(key)));
          }
        } else {
          CHECK(isc_buffer_printf(
            buf, "  Waiting TTL period for "
                 "validators to pick up "
                 "the new DS RRset.\n"));
        }
      } else if (dnskey == OMNIPRESENT && ds == OMNIPRESENT) {
        log_next_rollover = true;
        active_state = DST_TIME_PUBLISH;
        retire_state = DST_TIME_DELETE;
      } else {
        CHECK(isc_buffer_printf(
          buf, "  WARNING: Key is in unexpected "
               "state, "
               "performing auto-healing.\n"));
        *verbose = true;
      }
    } else if (goal == HIDDEN) {
      if (dnskey == OMNIPRESENT && ds == OMNIPRESENT) {
        CHECK(isc_buffer_printf(
          buf,
          "  Key will be retired after the DS is "
          "withdrawn from the parent.\n"));
      } else if (dnskey == OMNIPRESENT && ds == UNRETENTIVE) {
        isc_stdtime_t dstime = now;
        isc_result_t ret = dst_key_gettime(
          key, DST_TIME_DSDELETE, &dstime);
        if (ret != ISC_R_SUCCESS || dstime > now) {
          CHECK(isc_buffer_printf(
            buf,
            "  Waiting for the DS to be "
            "removed from the parent.\n"));
          if (checkds) {
            CHECK(isc_buffer_printf(
              buf,
              "  checkds is enabled, "
              "BIND will check the "
              "DS RRset "
              "periodically.\n"));
          } else {
            CHECK(isc_buffer_printf(
              buf,
              "  ! Once the DS is "
              "removed from the "
              "parent, run 'rndc "
              "dnssec -checkds -key "
              "%d withdrawn' to mark "
              "it as withdrawn.\n",
              dst_key_id(key)));
          }
        } else {
          CHECK(isc_buffer_printf(
            buf, "  Waiting TTL period for "
                 "validators to pick up "
                 "the new DS RRset.\n"));
        }
      } else if (dnskey == OMNIPRESENT && ds == HIDDEN) {
        CHECK(isc_buffer_printf(buf, "  Key is removed "
                   "from chain of "
                   "trust.\n"));
      } else if (dnskey == UNRETENTIVE && ds == HIDDEN) {
        if (!zsk) {
          CHECK(isc_buffer_printf(
            buf, "  Key is removed from "
                 "zone.\n"));
        }
      } else if (dnskey == HIDDEN && ds == HIDDEN) {
        if (!zsk) {
          CHECK(isc_buffer_printf(
            buf,
            "  Key is completely hidden "
            "(waiting to be purged).\n"));
        }
      } else {
        CHECK(isc_buffer_printf(
          buf, "  WARNING: Key is in unexpected "
               "state, "
               "performing auto-healing.\n"));
        *verbose = true;
      }
    }
  }

  // rollover status
  if (log_next_rollover) {
    isc_stdtime_t active_time = 0;
    isc_stdtime_t retire_time = 0;
    (void)dst_key_gettime(key, active_state, &active_time);
    result = dst_key_gettime(key, retire_state, &retire_time);
    if (result == ISC_R_SUCCESS) {
      char timestr[26]; /* Minimal buf as per ctime_r() spec.
             */
      if (now < retire_time) {
        CHECK(isc_buffer_printf(buf, "  Next rollover "
                   "scheduled on "));
        retire_time = keymgr_prepublication_time(
          dkey, kasp, retire_time - active_time,
          now);
      } else {
        CHECK(isc_buffer_printf(buf, "  Rollover is "
                   "due since "));
      }
      isc_stdtime_tostring(retire_time, timestr,
               sizeof(timestr));
      CHECK(isc_buffer_printf(buf, "%s\n", timestr));
    } else {
      CHECK(isc_buffer_printf(buf,
            "  No rollover scheduled.\n"));
    }
  }

cleanup:
  return result;
}

isc_result_t
dns_keymgr_status(dns_kasp_t *kasp, dns_dnsseckeylist_t *keyring,
      isc_buffer_t *buf, isc_stdtime_t now, bool verbose,
      bool checkds) {
  isc_result_t result = ISC_R_SUCCESS;

  REQUIRE(DNS_KASP_VALID(kasp));
  REQUIRE(keyring != NULL);
  REQUIRE(buf != NULL);

  ISC_LIST_FOREACH(*keyring, dkey, link) {
    char algstr[DNS_NAME_FORMATSIZE];

    if (dst_key_is_unused(dkey->key)) {
      continue;
    }

    if (!verbose && dst_key_is_hidden(dkey->key)) {
      continue;
    }

    // key data
    dns_secalg_format((dns_secalg_t)dst_key_alg(dkey->key), algstr,
          sizeof(algstr));
    CHECK(isc_buffer_printf(buf, "\n%s %d (%s):\n",
          keymgr_keyrole(dkey->key),
          dst_key_id(dkey->key), algstr));

    // rollover status
    CHECK(rollover_status(dkey, kasp, keyring, now, buf, &verbose,
              checkds));

    if (verbose) {
      // key states
      CHECK(isc_buffer_printf(buf, "  Key states:\n"));

      CHECK(keystate_status(
        dkey->key, buf,
        "goal:           ", DST_KEY_GOAL));
      CHECK(keystate_status(
        dkey->key, buf,
        "dnskey:         ", DST_KEY_DNSKEY));
      CHECK(keystate_status(dkey->key, buf,
                "ds:             ", DST_KEY_DS));
      CHECK(keystate_status(
        dkey->key, buf,
        "zone rrsig:     ", DST_KEY_ZRRSIG));
      CHECK(keystate_status(
        dkey->key, buf,
        "key rrsig:      ", DST_KEY_KRRSIG));
    }
  }

cleanup:
  return result;
}

isc_result_t
dns_keymgr_rollover(dns_kasp_t *kasp, dns_dnsseckeylist_t *keyring,
        isc_stdtime_t now, isc_stdtime_t when, dns_keytag_t id,
        unsigned int algorithm) {
  int options = (DST_TYPE_PRIVATE | DST_TYPE_PUBLIC | DST_TYPE_STATE);
  const char *directory = NULL;
  isc_result_t result;
  dns_dnsseckey_t *key = NULL;
  isc_stdtime_t active, retire, prepub;

  REQUIRE(DNS_KASP_VALID(kasp));
  REQUIRE(keyring != NULL);

  ISC_LIST_FOREACH(*keyring, dkey, link) {
    if (dst_key_id(dkey->key) != id) {
      continue;
    }
    if (algorithm > 0 && dst_key_alg(dkey->key) != algorithm) {
      continue;
    }
    if (key != NULL) {
      /*
       * Only rollover for one key at a time.
       */
      return DNS_R_TOOMANYKEYS;
    }
    key = dkey;
  }

  if (key == NULL) {
    return DNS_R_NOKEYMATCH;
  }

  result = dst_key_gettime(key->key, DST_TIME_ACTIVATE, &active);
  if (result != ISC_R_SUCCESS || active > now) {
    return DNS_R_KEYNOTACTIVE;
  }

  result = dst_key_gettime(key->key, DST_TIME_INACTIVE, &retire);
  if (result != ISC_R_SUCCESS) {
    /**
     * Default to as if this key was not scheduled to
     * become retired, as if it had unlimited lifetime.
     */
    retire = 0;
  }

  /**
   * Usually when is set to now, which is before the scheduled
   * prepublication time, meaning we reduce the lifetime of the
   * key. But in some cases, the lifetime can also be extended.
   * We accept it, but we can return an error here if that
   * turns out to be unintuitive behavior.
   */
  prepub = dst_key_getttl(key->key) + dns_kasp_publishsafety(kasp) +
     dns_kasp_zonepropagationdelay(kasp);
  retire = when + prepub;

  dst_key_settime(key->key, DST_TIME_INACTIVE, retire);

  /* Store key state and update hints. */
  directory = dst_key_directory(key->key);
  if (directory == NULL) {
    directory = ".";
  }

  dns_dnssec_get_hints(key, now);
  result = dst_key_tofile(key->key, options, directory);
  if (result == ISC_R_SUCCESS) {
    dst_key_setmodified(key->key, false);
  }

  return result;
}

isc_result_t
dns_keymgr_offline(const dns_name_t *origin, dns_dnsseckeylist_t *keyring,
       dns_kasp_t *kasp, isc_stdtime_t now,
       isc_stdtime_t *nexttime) {
  isc_result_t result = ISC_R_SUCCESS;
  int options = (DST_TYPE_PRIVATE | DST_TYPE_PUBLIC | DST_TYPE_STATE);
  char keystr[DST_KEY_FORMATSIZE];

  *nexttime = 0;

  /* Store key states and update hints. */
  ISC_LIST_FOREACH(*keyring, dkey, link) {
    bool modified;
    bool ksk = false, zsk = false;
    isc_stdtime_t active = 0, published = 0, inactive = 0,
            remove = 0;
    isc_stdtime_t lastchange = 0, nextchange = 0;
    dst_key_state_t dnskey_state = HIDDEN, zrrsig_state = HIDDEN,
        goal_state = HIDDEN;
    dst_key_state_t current_dnskey = HIDDEN,
        current_zrrsig = HIDDEN, current_goal = HIDDEN;

    (void)dst_key_role(dkey->key, &ksk, &zsk);
    if (ksk || !zsk) {
      continue;
    }

    dns_keymgr_key_init(dkey, kasp, now, false);

    /* Get current metadata */
    CHECK(dst_key_getstate(dkey->key, DST_KEY_DNSKEY,
               &current_dnskey));
    CHECK(dst_key_getstate(dkey->key, DST_KEY_ZRRSIG,
               &current_zrrsig));
    CHECK(dst_key_getstate(dkey->key, DST_KEY_GOAL, &current_goal));
    CHECK(dst_key_gettime(dkey->key, DST_TIME_PUBLISH, &published));
    CHECK(dst_key_gettime(dkey->key, DST_TIME_ACTIVATE, &active));
    (void)dst_key_gettime(dkey->key, DST_TIME_INACTIVE, &inactive);
    (void)dst_key_gettime(dkey->key, DST_TIME_DELETE, &remove);

    /* Determine key states from the metadata. */
    if (active <= now) {
      dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
      ttlsig += dns_kasp_zonepropagationdelay(kasp);
      if ((active + ttlsig) <= now) {
        zrrsig_state = OMNIPRESENT;
      } else {
        zrrsig_state = RUMOURED;
        (void)dst_key_gettime(dkey->key,
                  DST_TIME_ZRRSIG,
                  &lastchange);
        nextchange = lastchange + ttlsig +
               dns_kasp_retiresafety(kasp);
      }
      goal_state = OMNIPRESENT;
    }

    if (published <= now) {
      dns_ttl_t key_ttl = dst_key_getttl(dkey->key);
      key_ttl += dns_kasp_zonepropagationdelay(kasp);
      if ((published + key_ttl) <= now) {
        dnskey_state = OMNIPRESENT;
      } else {
        dnskey_state = RUMOURED;
        (void)dst_key_gettime(dkey->key,
                  DST_TIME_DNSKEY,
                  &lastchange);
        nextchange = lastchange + key_ttl +
               dns_kasp_publishsafety(kasp);
      }
      goal_state = OMNIPRESENT;
    }

    if (inactive > 0 && inactive <= now) {
      dns_ttl_t ttlsig = dns_kasp_zonemaxttl(kasp, true);
      ttlsig += dns_kasp_zonepropagationdelay(kasp);
      if ((inactive + ttlsig) <= now) {
        zrrsig_state = HIDDEN;
      } else {
        zrrsig_state = UNRETENTIVE;
        (void)dst_key_gettime(dkey->key,
                  DST_TIME_ZRRSIG,
                  &lastchange);
        nextchange = lastchange + ttlsig +
               dns_kasp_retiresafety(kasp);
      }
      goal_state = HIDDEN;
    }

    if (remove > 0 && remove <= now) {
      dns_ttl_t key_ttl = dst_key_getttl(dkey->key);
      key_ttl += dns_kasp_zonepropagationdelay(kasp);
      if ((remove + key_ttl) <= now) {
        dnskey_state = HIDDEN;
      } else {
        dnskey_state = UNRETENTIVE;
        (void)dst_key_gettime(dkey->key,
                  DST_TIME_DNSKEY,
                  &lastchange);
        nextchange =
          lastchange + key_ttl +
          dns_kasp_zonepropagationdelay(kasp);
      }
      zrrsig_state = HIDDEN;
      goal_state = HIDDEN;
    }

    if ((*nexttime == 0 || *nexttime > nextchange) &&
        nextchange > 0)
    {
      *nexttime = nextchange;
    }

    /* Update key states if necessary. */
    if (goal_state != current_goal) {
      dst_key_setstate(dkey->key, DST_KEY_GOAL, goal_state);
    }
    if (dnskey_state != current_dnskey) {
      dst_key_setstate(dkey->key, DST_KEY_DNSKEY,
           dnskey_state);
      dst_key_settime(dkey->key, DST_TIME_DNSKEY, now);
    }
    if (zrrsig_state != current_zrrsig) {
      dst_key_setstate(dkey->key, DST_KEY_ZRRSIG,
           zrrsig_state);
      dst_key_settime(dkey->key, DST_TIME_ZRRSIG, now);
      if (zrrsig_state == RUMOURED) {
        dkey->first_sign = true;
      }
    }
    modified = dst_key_ismodified(dkey->key);

    if (modified) {
      const char *directory = dst_key_directory(dkey->key);
      if (directory == NULL) {
        directory = ".";
      }

      dns_dnssec_get_hints(dkey, now);

      CHECK(dst_key_tofile(dkey->key, options, directory));
      dst_key_setmodified(dkey->key, false);

      if (!isc_log_wouldlog(ISC_LOG_DEBUG(3))) {
        continue;
      }
      dst_key_format(dkey->key, keystr, sizeof(keystr));
      isc_log_write(DNS_LOGCATEGORY_DNSSEC,
              DNS_LOGMODULE_DNSSEC, ISC_LOG_DEBUG(3),
              "keymgr: DNSKEY %s (%s) "
              "saved to directory %s, policy %s",
              keystr, keymgr_keyrole(dkey->key),
              directory, dns_kasp_getname(kasp));
    }
    dst_key_setmodified(dkey->key, false);
  }

  result = ISC_R_SUCCESS;

cleanup:
  if (isc_log_wouldlog(ISC_LOG_DEBUG(3))) {
    char namebuf[DNS_NAME_FORMATSIZE];
    dns_name_format(origin, namebuf, sizeof(namebuf));
    isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
            ISC_LOG_DEBUG(3), "keymgr: %s (offline-ksk) done",
            namebuf);
  }
  return result;
}

Coverage Report

Created: 2026-04-05 06:47