Ben Laurie blathering

Revocation Transparency and Sovereign Keys

In line with Certificate Transparency (note, updated version, 2.1a), we’ve been thinking about how to do something similar for revocation. Not because we have any particular plan but because as soon as we mention CT, people always say “what about revocation?”. Which is, admittedly, in a bit of a pickle, and it isn’t at all obvious how to fix it. But however its fixed, we think its a good idea to have transparency – for everyone to be assured that they are seeing revocation state that is the same as everyone else is seeing, and for revocations to be auditable – just as we think certificate issuance should be.

So, we’re quite excited that recently we came up with not one, but two, mechanisms. One of them (Sparse Merkle Trees) even appears to be novel. There’s a brief write-up here.

Also, it turns out, Sparse Merkle Trees can be used to solve a problem that has been bugging me with Sovereign Keys since day one. The issue is that in SK the relying party needs to trust mirrors to tell it what the current status of any particular domain is (i.e. what the current key is), because the only other way to be sure is to download the entire database, which will be many gigabytes long. Using Sparse Merkle Trees plus a CT-like append-only log (as described in the RT document), this is no longer the case. Instead, we can generate a sparse tree containing leaves corresponding to the hashes of domain names. The value stored at the leaf is the domain’s current key (or whatever we want to store there). The sparse tree allows us to verify efficiently that we are, indeed, seeing the latest version, and the append-only log prevents abuse of the change mechanism to make temporary changes shown only to a subset of relying parties.

1 Comment

  1. Nice :-) This construction reminds me a bit of the hashlife quadtree, which relies on shared subtrees for efficiency.

    Comment by Tony Finch — 11 Sep 2012 @ 18:21

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress