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.

Issues

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.

Operations

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

Nomenclature:

K = symmetric key
P = public key
S = secret key
E^K(m), D^K(m) = encrypt or decrypt m using key K (also applies to P and S; E^K ≡ D^K for symmetric keys K)
L = a log
G_L = corresponding generational log (to store key information)
G_L:g = information corresponding to generation g

Creating a Log L

Create a (symmetric) key K
Create a key pair (S_r1, P_r1) [only if sharing secret key]
Encrypt K with P_i, i ∈ { self, r₁, r₂ ...}, self is your own key, and r_i are readers [only one if sharing secret key]
Create Generational Log G_L unique to this log L
Write E^P_i(K) ∀i to G_L (this is generation G_L:1)

Writing

Writer reads G_L:g from G_L, where G_L:g is the last entry in G_L
Use S_self to decrypt K from G_L:g
Use K to encrypt data
Prepend generation number g (unencrypted) before writing encrypted data E_K(m)

Reading (Normal Case)

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

Revocation

Revocation looks very similar to creation.

Create new symmetric key K′
Create new key pair (S′_r1, P′_r1) [only if sharing secret key]
Encrypt K′ with P_self, P_r1, P_r2... (need not be the same set of readers)
Encrypt old key K with new key K′
Write encrypted K and E^P_i(K) ∀i to G_L (this creates a new generation)
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.

Reader reads datum and extracts g from datum, reads G_L,g from G_L, but does not have a valid secret key to decrypt it
Read G_L,n from G_L where n is the most recent generation
If no access to that generation, give up (means your access has been denied)
Use that access to decrypt K
For k ∈ {n–1, n–2, ... i}, use K_k+1 to decrypt K_k
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 E^K′(K) in new G_L 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 S_L has to be distributed to all possible readers, and revocation becomes a matter of changing S_L 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 G_L. Clearly G_L 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?