Encryption in the Global Data Plane

Eric Allman, Swarm Lab, U.C. Berkeley

This is a working document, more musing and request for comment than tutorial.  Nothing herein is definitive.


Need reasonable efficiency.  Implies not doing public key operations on a per-record basis, which in turn means using symmetric keys across multiple records.

Need to handle revocation.

How to retroactively grant permission?  This is the flip side of revocation: you want a new reader to be able to read data already written.  Simple if you share the secret keys around, harder if you do not.

Two major options: might have key pairs associated with readers, and the writer grants permission to specific readers, versus sharing the secret key with all readers.  Either way there are key management issues, but they are different.  This discussion attempts to discuss both options.


Assumption: most of the Writing and Reading operations are amenable to caching.  These algorithm overviews do not include caching to keep things simple.


Creating a Log L

  1. Create a (symmetric) key K
  2. Create a key pair (Sr1, Pr1) [only if sharing secret key]
  3. Encrypt K with Pi, i ∈ { self, r1, r2 ...}, self is your own key, and ri are readers [only one if sharing secret key]
  4. Create Generational Log GL unique to this log L
  5. Write EPi(K) ∀i to GL (this is generation GL:1)


  1. Writer reads GL:g from GL, where GL:g is the last entry in GL
  2. Use Sself to decrypt K from GL:g
  3. Use K to encrypt data
  4. Prepend generation number g (unencrypted) before writing encrypted data EK(m)

Reading (Normal Case)

  1. Reader reads datum X and extracts generation number g
  2. Look up GL:g from GL
  3. See if we have a secret key SrN that will decrypt one of the encrypted copies of K; if not, fail (but see Problem Case below)
  4. Decrypt remainder of datum with K


Revocation looks very similar to creation.

  1. Create new symmetric key K′
  2. Create new key pair (S′r1, P′r1) [only if sharing secret key]
  3. Encrypt K′ with Pself, Pr1, Pr2... (need not be the same set of readers)
  4. Encrypt old key K with new key K′
  5. Write encrypted K and EPi(K) ∀i to GL (this creates a new generation)
  6. Start using K′ as K

Reading (Problem Case)

This could be because you have no access, or you do but you have to read backwards through generations to find the K you need for the record.

  1. Reader reads datum and extracts g from datum, reads GL,g from GL, but does not have a valid secret key to decrypt it
  2. Read GL,n from GL where n is the most recent generation
  3. If no access to that generation, give up (means your access has been denied)
  4. Use that access to decrypt K
  5. For k ∈ {n–1, n–2, ... i}, use Kk+1 to decrypt Kk
  6. Stop when you find a valid S

Security Analysis/Discussion/Questions

Once a reader has access to any point in the log, they have access to all points prior.  This could be mitigated by not including EK′(K) in new GL records, but then granting backward access would be hard.

If each reader had its own key pair, then this looks like an ACL.  "Reader" here could mean "application", "user", "administrative domain", or something else.  Alternatively, each log could have its own key pair, which would mean that somehow that secret key SL has to be distributed to all possible readers, and revocation becomes a matter of changing SL as well as K.  The encryption key pair should probably not be the same one used for signing.

This description ignores the step of signing the updates to GL.  Clearly GL will need a key pair of its own, and it's not clear if that might be shared with the original log L.

If secret keys are are being created per log and distributed around, they need to be encrypted themselves; at some point there has to be a decryption key not held on disk in encrypted form or the game is over.  Q: could TPM help us here?