Subject: [dnsext] bootstrapping using a quorum of witnesses

From: Tony Finch <[email-masked]>
Date: Tue, 1 Feb 2011 20:48:09 +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  <[email-masked]>  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.
_______________________________________________
dnsext mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsext

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 1 Feb 2011 23:18:44 -0500

That is along the lines of where I was thinking. It may even be possible to
make it work with less organization, possibly self-assembling.

So the starting point I thought of was that a Large Router Vendor (LRV)
decides to use its own existing offline root key maintain signatures over
the ICANN KSK.

ICANN have published a CSR so it should be relatively easy to generate an
X.509v3 cross certificate for the ICANN KSK. Why use X.509 here? Well
because that allows us to use the code that we already have to service other
equipment. It allows us to specify an expiry date for the cross certificate
- I would suggest one to two years. Also it allows said LRV to avoid
liability issues that I will come to in a moment.

The LRV then publishes the cross certificate at a specified point in their
DNS tree that is a subdomain that they have reserved for this purpose and is
specific to that particular root.

So this might be:

root2009.lrv.biz  CERT ..... blah

If people are willing to write code we could achieve the same thing in pure
DNSSEC. But that would require code to be written to use the existing HSM to
sign DNS records. There would also be some more architectural options.

This is the minimal cheap and cheerful approach. Essentially all that LRV
has done is to replace the ICANN root with themselves. However they are
publishing the cross cert in a public place.

So what happens if Small Router Vendor now comes along and looks at this
scheme and says 'hey, I can free ride on LRV's scheme'. Which originally had
me thinking in terms of putting a practices statement in the certificate or
possibly going so far as to assert copyright in the embedded root key.

To make this scheme worthwhile is is necessary for LRV to spend an
equivalent amount of care etc. in management of their root. They should be
using key sharing, separation of duties etc (to see how it is done read a
certain large CA's CPS that has the whole scheme explained in all the detail
anyone would ever need).

Then I thought that maybe the bug is a feature and that maybe hooking into
LRV alone is not going to meet the needs of SRV after all. They have no more
control over LRV than they have over ICANN. In fact they have rather less
assurance as LRV might decide to issue a firmware update and phase out their
root.

So one model would be for SRV to contract to have someone manage a root for
them in an outsourced model. Which is feasible, but not inexpensive. And the
cumulative duplication of effort is really not worthwhile.

A better model would be for there to be an established standard for this
scheme and for SRV to embed multiple roots and employ a quorum scheme.

The main advantage to LRV is that the concentration of risk is gone and thus
the potential third party liability. They might still want to have some form
of contractual arrangement with the relying party vendors. But the
possibility of unilateral default is gone and with it the liability.
Moreover since the LRV cannot successfully default, there is no incentive
for them to attempt to do so or for someone to attempt to coerce them -
unless they can coerce a quorum of roots.

A second advantage to LRV is that it frequently grows by acquiring SRVs.
Having them use compatible protocol approaches will ease their legacy
maintenance headache.

So now we have arrived at a position where LRV is doing the work but SRV is
actually giving a better assurance to their customers, their equipment is
can only be compromised through multiple failures while LRVs is vulnerable
to a single failure.

So LRV would probably end up employing the same quorum scheme, either with
peers or with some number of specialist providers of outsourced crypto
management.

So now we have a scheme that is independent of any single point of control.
The only question being the circumstances in which the signers would
legitimately sign something other than the current ICANN root KSK.

The point here is not that ICANN would want to default, but that it might be
coerced. The practices they are using are tamper-evident, not absolutely
tamper proof. If we take away the possibility that a coercion attempt would
succeed, we take away the incentive for a rational person to attempt to do
so.

What I like about this scheme is that we can start building the technical
infrastructure without having to first construct a social-political
construct. It In fact I would prefer to avoid creating any such construct
that might be misinterpreted as a 'New World Order' type organization.

The same technical infrastructure can be used to support a quorum of one out
of one to n out of m. And there is the option for the ultimate customer to
choose their own quorum points.

-- 
Website: http://hallambaker.com/
_______________________________________________
dnsext mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsext

---

From: Tony Finch <[email-masked]>
Date: Wed, 2 Feb 2011 08:38:58 +0000

On 2 Feb 2011, at 04:18, Phillip Hallam-Baker <[email-masked]> wrote:

I'm glad you think my sheme is reasonably plausible. I'm not sure your idea of a self-assembling committee of witnesses is likely to happen. It seems to me that more deliberate setup will be faster and more likely to succeed. But it requires politics which isn't my area...

> So now we have a scheme that is independent of any single point of control. The only question being the circumstances in which the signers would legitimately sign something other than the current ICANN root KSK. 

The same question applies to the root server operators' relationship with ICANN...

Tony.