How to rotate VRF key

[arlolra]

The policies are protocol specific, and don't really have anything to do with the underlying data structures, do they?

Further, it seems undesirable to be storing the VRF key in the policies, and relying on only extracting the public key when serializing. In practice, that means many copies of secret material stored in memory / on disk.

What's worse is that usually rotating keys means that you can safely destroy the previous key material. However, in order to support lookups in previous epochs, we need to keep those keys around indefinitely.

For now, I think maybe the PAD struct should gain an vrfKey vrf.PrivateKey field and policies should move to protocol, and become an opaque blob ([]byte) in the PAD.

Somewhat related to #47

[vqhuy]

Aligning VRF key and signing key makes a lot of sense to me, but how will vrf.PrivateKeys be handled in protocol?

[arlolra]

how will vrf.PrivateKeys be handled in protocol?

Can you clarify what you're asking? For now, we won't have a mechanism to rotate the vrf key.

[vqhuy]

For now, we won't have a mechanism to rotate the vrf key.

OK. My question was about how would we store vrf keys in protocol, but your statement answered it.

[arlolra]

Yeah, see the third paragraph about what rotating would even mean, given the consequences.

[vqhuy]

Since we'll also support prior history verification in #106, it probably means we also have to support key lookup in epoch without time limitation?

[masomel]

probably means we also have to support key lookup in epoch without time limitation?

What do you mean by "without time limitation"?

[vqhuy]

I meant something like "you are not allowed to look up for key older than 1 month". I remember that is what we discussed in our previous meeting, right?

[masomel]

I meant something like "you are not allowed to look up for key older than 1 month". I remember that is what we discussed in our previous meeting, right?

Gotcha. Yeah, I wasn't sure if we had come to an agreement during our last meeting since we haven't figured out a scheme for rotating the VRF key. But I think you're right, that if we support prior history verification, lookups at any time in the past should also be possible.

[vqhuy]

I wasn't sure if we had come to an agreement during our last meeting

I think we haven't had it yet.

[vqhuy]

A possible way is using an HKDF, if we support lookups at any time in the past:

• The server generates a MasterVRFKey
• The new VRF key is derived as VRFPrivateKey_t = HKDF(t, MasterVRFKey, "CONIKS_VRF", PrivateKeySize), with t is the epoch we rotate the key, started from 0.
• The server also needs to maintain an array of rotated epochs or salts (which is t).

Do you think it works? /cc @arlolra @masomel @Liamsi

Answer: No, see: https://github.com/coniks-sys/coniks-go/issues/120#issuecomment-284938420

[arlolra]

I'm not sure what that scheme buys us since the master key, as you've defined it, can't be destroyed.

[vqhuy]

We always need to maintain at least one private key, right? Then we just need to keep only the master key, instead of multiple keys.

[arlolra]

But if previous keys can be derived at any time, you haven't really rotated anything.

[masomel]

Could the server maintain a history tree or hash chain of the VRF public keys? This would at least solve the problem of supporting lookups in past epochs. The only reason why the server needs to keep the old private keys around is in order to recover from a crash by reconstructing the old trees, no?

[arlolra]

VRF public keys are stored in the policies, so they're available already.

The private keys are required because lookups use them to compute the private indices.

[masomel]

The private keys are required because lookups use them to compute the private indices.

Derp, right. I've been doing some research on secure private key storage, and most recommendations I've seen so far either use a separate physical server or store the private keys on tamper-evident hardware, neither of which are good options for us since we need to be able to access the private keys efficiently and on-demand.

In practice, how frequently do we expect to be rotating the VRF key? I'm wondering if the best we can do is store the VRF private keys encrypted on disk? This really just defers key management, and if the disk encryption key is compromised, the VRF keys are compromised as well. But if we find ourselves in that situation, there might not be a way around doing a completely clean start of the key server anyway, in which case we end up losing access to all keys and history anyway.

[vqhuy]

The main purpose of this (thanks to @arlolra for explaining this to me) is: we cannot (or at least there is currently a conflict) support past lookups at any time and also support key rotating. Because, rotating keys means that you can safely destroy the previous key material. We need to figure out how to reconcile those two.

I think how to securely store the private keys (VRF keys, signing key, or even TLS keys) is another issue, but Arlo and Ismail might certainly have some experience on this.

[masomel]

The main purpose of this (thanks to @arlolra for explaining this to me) is: we cannot (or at least there is currently a conflict) support past lookups at any time and also support key rotating. Because, rotating keys means that you can safely destroy the previous key material. We need to figure out how to reconcile those two.

I understand this issue completely... I understand that in the normal case, we'd want to destroy old key material once we've rotated any key, which is of course an issue if we want to support past lookups. But we need to support past lookups for the security of the users, which is why my suggested solution is finding a way to keep the old keys. These aren't separate issues, I believe finding a way to store the VRF private keys could be a solution to this problem.

[vqhuy]

These aren't separate issues, I believe finding a way to store the VRF private keys could be a solution to this problem.

Yeah, that seems to make sense to me. And sorry for misunderstanding your comment and being hasty :(

[masomel]

No problem! I don't think I was super clear before either, so that's my bad :( I'm glad we understand each other now :)

[masomel]

You're right, though, @arlolra and @Liamsi might have some experience with securely storing private keys, so I'd like to hear what they think. Like I said above, maybe storing the keys is a bad idea, but I don't have a better solution right now.

[arlolra]

But we need to support past lookups for the security of the users, which is why my suggested solution is finding a way to keep the old keys.

We should also be thinking about to what extent that needs to be true and looking for ways to remove that property from the system. I imagine even an honest administrator can lose keys.

[masomel]

We should also be thinking about to what extent that needs to be true and looking for ways to remove that property from the system. I imagine even an honest administrator can lose keys.

We certainly need this property for monitoring, and we kind of want it for registration as well if a client wants to ensure that the name wasn't registered at any point in time before. We can possibly compromise on the registration, but we definitely need to be able to catch up on missed epochs. But maybe we don't need to keep stale keys around if nobody is looking really far back in history.

An honest admin can certainly lose keys, so I'm not 100% sold on the idea of keeping them around either. OTOH, we need to figure out private key management for the signing key and the TLS key either way, so it could make sense to use the same solution for the VRF keys being kept. An alternative to keeping VRF keys around would be to keep an internal map of names to (index, epoch) pairs. This way, the server wouldn't have to recompute the index on the fly upon a lookup. But I really would prefer to avoid this.

[liamsi]

We should also be thinking about to what extent that needs to be true and looking for ways to remove that property from the system. I imagine even an honest administrator can lose keys.

I absolutely agree on this. Let's first focus on finding a solution to get rid of needing to keep the old key around.