[dnsext] bootstrapping using a quorum of witnesses

Tony Finch <dot@dotat.at> Tue, 01 February 2011 20:44 UTC

Return-Path: <fanf2@hermes.cam.ac.uk>
X-Original-To: dnsext@core3.amsl.com
Delivered-To: dnsext@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 003663A6C7A; Tue, 1 Feb 2011 12:44:54 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.857
X-Spam-Level:
X-Spam-Status: No, score=-4.857 tagged_above=-999 required=5 tests=[AWL=1.742, BAYES_00=-2.599, RCVD_IN_DNSWL_MED=-4]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZKkG6QawcOlm; Tue, 1 Feb 2011 12:44:52 -0800 (PST)
Received: from ppsw-50.csi.cam.ac.uk (ppsw-50.csi.cam.ac.uk [131.111.8.150]) by core3.amsl.com (Postfix) with ESMTP id 479683A6C5E; Tue, 1 Feb 2011 12:44:52 -0800 (PST)
X-Cam-AntiVirus: no malware found
X-Cam-SpamDetails: not scanned
X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/
Received: from hermes-1.csi.cam.ac.uk ([131.111.8.51]:45583) by ppsw-50.csi.cam.ac.uk (smtp.hermes.cam.ac.uk [131.111.8.157]:25) with esmtpa (EXTERNAL:fanf2) id 1PkN8z-0006v0-sK (Exim 4.72) (return-path <fanf2@hermes.cam.ac.uk>); Tue, 01 Feb 2011 20:48:09 +0000
Received: from fanf2 (helo=localhost) by hermes-1.csi.cam.ac.uk (hermes.cam.ac.uk) with local-esmtp id 1PkN8z-00045E-Qi (Exim 4.67) (return-path <fanf2@hermes.cam.ac.uk>); Tue, 01 Feb 2011 20:48:09 +0000
Date: Tue, 1 Feb 2011 20:48:09 +0000
From: Tony Finch <dot@dotat.at>
X-X-Sender: fanf2@hermes-1.csi.cam.ac.uk
To: dnsop@ietf.org, dnsext@ietf.org
Message-ID: <alpine.LSU.2.00.1102012018420.3329@hermes-1.csi.cam.ac.uk>
User-Agent: Alpine 2.00 (LSU 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: Tony Finch <fanf2@hermes.cam.ac.uk>
Subject: [dnsext] bootstrapping using a quorum of witnesses
X-BeenThere: dnsext@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: DNS Extensions working group discussion list <dnsext.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/dnsext>, <mailto:dnsext-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/dnsext>
List-Post: <mailto:dnsext@ietf.org>
List-Help: <mailto:dnsext-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dnsext>, <mailto:dnsext-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 01 Feb 2011 20:44:54 -0000

Here is a sketch of a scheme for establishing trust in the root KSK based
on a group of less-trusted cryptographic "witnesses", without a single
point of failure.

It is designed to survive a reasonable amount of cryptographic,
operational, and organizational attrition, so that it should be possible
for a ten-year-old validator to successfully and securely bootstrap. Think
of a fifteen-year-old root hints file, which still after all that time
contains eight valid root server IP addresses: enough to bootstrap.

Phillip Hallam-Baker and John Bashinski have recently hinted at something
like this, though I thought up this scheme a few months ago.

* Witnesses

There is a group of about a dozen root trust anchor witnesses. They are
selected from interested parties such as root server operators, TLD
operators, DNS registries, RIRs, software and hardware vendors, etc. They
have diverse software, hardware, crypto algorithms, operations, locations,
politics, etc. There is no need for anyone to trust any single one of them
nor to trust all of them.

* Witness signatures

Periodically (quarterly, perhaps) the witnesses all sign each others'
public keys and the root public key(s). They also sign a digest of the
previous witness signature set to form a historical link, and other
metadata to associate each key with its owner. These mutual signatures
form a proof that all witnesses agree that these are the current keys.

* Interaction with root zone

There is no coupling between the witnesses and root zone operations,
except that witness signing ceremonies must be timed so that validators
can reliably obtain a valid root KSK from the witness zones across a root
KSK rollover.

* Witness zones

Each witness maintains a well-known DNS zone in which that witness
publishes their copy of all historical witness signatures from all
witnesses. This zone's KSK is the witness's current key. (Details of the
format TBD.)

* Key lifetime

We do not require any very long-lived or standby keys: the only keys not
in active oprerational use are historical bootstrap keys whose private
parts have been destroyed. The remaining risk is that these old keys might
fall to crypographic attack; however if the witnesses have reasonable key
and algorithm rolling schedules and the attacks aren't catastrophic, this
vulnerability will only affect validators bootsrapping of very old
(compromised) data. Sufficiently diverse witnesses can also reduce this
vulnerability.

* Bootstrap data

A validator's bootstrap data comprises a list of witness zones and their
keys. This is operationally similar to the root name server hints, in that
moderately stale data doesn't matter.

* Staleness

There are three kinds of change to the set of witness keys.

 - planned key and/or algorithm rollovers

 - deletion of a witness key

 - introduction of a new witness

Deletion and introduction are expected to be fairly rare. (cf. root
server changes.)

* Rollover

There is a mechanism (details TBD) to indicate in the series of witness
signature sets that a witness performed a planned rollover and destroyed
the old key's private part. A bootstrapping validator uses this
information to update its idea of that witness's key while tracing the
chain of witness signature sets.

* Deletion

There is a mechanism (details TBD) to indicate in the series of witness
signature sets that a key was deleted because of loss or compromise or
because the key's owner ceased to act as a witness for some other reason.
Deletion requires agreement by the other witnesses but does not require
action from the deleted witness. A bootstrapping validator does not trust
any witness that it observes to have been deleted.

* Introduction

New witnesses can be added (again details TBD). A bootstrapping validator
ignores witnesses that were not included in its bootstrap data. Validators
will normally ship with an up-to-date list of witnesses.

If an organization wishes to continue its role as a witness after its key
has been deleted from the set (and if the other witnesses agree!), it must
be re-introduced as a new witness.

* Bootstrap actions

A validator traces the chain of witness signature sets in a witness zone.
In each signature set it verifies all the signatures of the witnesses in
its bootstrap data. Witnesses' keys are updated as necessary by rollover
information. Witnesses that the validator observes to have been deleted
according to this zone are excluded from the entire validation process.
The most recent signature set must have a quorum of valid signatures.

The validator repeats this process for each witness zone until a quorum of
the zones has a record of exactly the same valid chain of witness
signature sets. If it fails to find a quorum it cannot bootstrap.

The size of the quorum is chosen to balance security against resilience in
the face of stale bootstrap data.

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
HUMBER THAMES DOVER WIGHT PORTLAND: NORTH BACKING WEST OR NORTHWEST, 5 TO 7,
DECREASING 4 OR 5, OCCASIONALLY 6 LATER IN HUMBER AND THAMES. MODERATE OR
ROUGH. RAIN THEN FAIR. GOOD.