Key management/rotation VS a different key for everything

[Christopher Lemmer Webber]

I've been encountering two things that I think are both important
points, and individually seem true, but feel in conflict to me:

- People have a hard time managing their keys, and sometimes they do
need to rotate them and update them and etc. This is true for key
loss but *especially* for cryptographic algorithms weakening. How
common is it for servers to be littered with 1024 bit ssh keys that
are lying around? If there was a nice way for people to update their
keys and push that updated version out to the wild, that would be
great. (In fact, this is exactly what DIDs are trying to solve,
and even have a social recovery system so even accidental key loss
can in theory be recovered from.) In this case, keys would probably
not be directly embedded, but have some sort of "indirection pointer"
so that an update can happen.

- On the other hand, there seems to be an ocap mantra that is, don't
use a key for more than one thing. If you can have a different key
for each separate service you interact with, etc, that would be
great. Also, don't tie ocap certificates to an object's identity,
but to some *specific key* (and if you can bundle it with the
certificate, that's probably even better).

Here's the problem: key management is hard enough when you have 1-3
keys. Even with a working DID ecosystem, it's some amount of cost to
register and upate a DID (not large for a few, but not nothing, and
it could be a lot if you had thousands of keys). Worse yet, in an
ideal ocap system you really wouldn't be paying close attention to
purpose of which key is for what because those would be being spawned
for you behind the scenes. Figuring out how to update all of them
could be very hard.

Does anyone have thoughts on this? How do we deal with it? Do people
generally agree that both of these points are valid, but that they are
hard to reconcile? Or am I missing something?

[Alan Karp]

You probably don't need to update the one-off keys that you associate with capabilities; you can use a process similar to the OAuth refresh token flow when one of these keys expires. However, you may have keys that you use when asking for a capability (the ones you want to "push out into the wild").  These keys are often long-lived and associated with you.  One way to manage refreshing these keys is to use two with different expiration dates on each request.  When one expires, the other one is sufficient to certify the new one.  

--------------
Alan Kar

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To post to this group, send email to cap-...@googlegroups.com.
Visit this group at https://groups.google.com/group/cap-talk.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87y3ds4hob.fsf%40dustycloud.org.
For more options, visit https://groups.google.com/d/optout.

[Mark Miller]

Alan, I think you misunderstand Chris' point. Alice needs to be able to hold many persistent caps to outside things, where these cap's representations are not obviously related to Alice's identity. However, any cryptographic aspect of her external representation needs to be refreshed.

Chris, am I better capturing your concern?

To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/CANpA1Z3JGCXhC%2BnrA7RMVr_%3DRUjXc-3f5Yaaj8Spt0%3DVWp2cFg%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

  Cheers,
  --MarkM

[Christopher Lemmer Webber]

Mark Miller writes:

> Alan, I think you misunderstand Chris' point. Alice needs to be able to
> hold many persistent caps to outside things, where these cap's
> representations are not obviously related to Alice's identity. However, any
> cryptographic aspect of her external representation needs to be refreshed.
>
> Chris, am I better capturing your concern?

Maybe, but I think I'm getting confused. I feel like this matches the
cap lore I've heard, that Alice's ocaps *shouldn't* have to match her
identity, and that's justifiable for privacy but also because we don't
want to be identity-centric. But I'm getting confused so I'm going to
try to work it through.

I do think Alan was trying to express a workflow but I didn't fully
understand it so I can't tell if it addresses this or not. Maybe a
familiar example would help.

- (A)lice has a capability to access her account at (B)ank.
- This capability is tied to a key Alice has, let's call it
(K0).
- Time has passed, Alice needs to replace K0 because either she lost
her old computer and wants to be safe, or maybe K0's cryptographic
suite is not as strong as it once was.
- We'll also assume Alice also has capabilities accesssing a wide range
of (O)ther services... in fact, let's call them (O1-O1000).

Now let's diverge scenarios:

- Alice uses (K0) for lots of services... she has individual capability
certificates issued for O1-1000 but they all use K0.
- Pros: Alice can update K0 in a single place and all of her services
are now also updated. She can invoke her capabilities for B and
also invoke O1-1000 and it's fine.
- Cons: We can express a much broader risk for that key being
compromised, (though she does use different certificates for each,
so Alice's programs are less likely to be subject to confused
deputy problems I believe, but the security risk of key compromise
is still high).

- Alice uses totally different keys for each service. K0 is used for
B, K1-1000 are used for O1-1000.
- Pros: A compromise of one key doesn't affect a compromise of
others.

It also may better support anonymnity, and may lead
to less systems accidentally "paying attention" to Alice's
identity, which could lead to confused deputy problems if
mis-implemented and Alice's identity becomes the source of
authority rather than possession of a valid ocap on invocation.

- Cons: We have to remember to update all those keys somehow,
and have a mechanism for doing so that isn't expensive.

Alan, it sounded like the workflow you suggested was the following:

- Have each capability indeed be linked to a one-off key that
expires.
- But also include in the capability, or maybe the one-off key, a way
to specify how to exchange the capability for a new one, pointing at
a different key?

I don't understand how this would be done, but I am trying to think
through it.

- Say the capability was tied to a specific one-off key, but the
refresh is on the capability, and Alice has some kind of "refresh
key" that, I think you say, is longer lived. Would Alice sign a
request for a new ocap from the Bank with her "refresh key", and hope
the Bank is willing to issue her a new ocap then? This seems like a
new refresh protocol, and it sounds tricky to figure out how to put
in ocap-ld, but maybe we could do it. But it also seems like it
wouldn't work for delegated ocaps. If Alice delegated a capability
to her Bank to Carol, what happens to the ocap Carol now holds
when Alice's key expires? How does she refresh that? It doesn't
seem like she can.

(Come to think of it, Carol may also be hosed in that scenario even
if Alice used the same key for everything but Alice's key got
rotated. Alice could surely invoke her certificate to the Bank with
her new key, but it seems like the delegation would break here too,
because if the cert chain was signed with Alice's old key, even
if she rotated it, we can't trust this old cert that Carol has.
Argh, my brain is breaking!)

- Say the key itself is refreshed. How do we present that this key is
refreshed? Do we present a certificate chain including the old key
and the new key at invocation time? That could maybe work but it's
a lot of extra paperwork to show up with on every invocation! :)

One thing seems clear to me from the above: If A has an ocap to B, and A
delegates to C, if A rotates the key, it doesn't seem like the ocap
delegated to C survives... since it's signed with A's old key, we can't
trust it any more! (If the old key really was compromised, a bad actor
could always issue "old delgated certs".)

Sorry, I realize this is complicated, and hopefully I'm not making it
even more complicated with my exploration! I appreciate the help in
thinking this through!

>> <https://groups.google.com/d/msgid/cap-talk/CANpA1Z3JGCXhC%2BnrA7RMVr_%3DRUjXc-3f5Yaaj8Spt0%3DVWp2cFg%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .

[Kevin Reid]

(no quotes because I'm giving my thoughts on the topic rather than responding to any particular post)

I think that a "full-fledged" capability system — that is, one which provides for all needs which will come up in using it at scale and for a long time — must include standard provisions to help manage them effectively rather than leaving it up to individual users' and application designers' actions to be fully thoughtful.

The straightforward approach as I see it is that there should be an operation — at the capability platform level, applicable to any capability rather than being application-specific — which means "please issue me a new capability exactly like this one except with fresh cryptographic features". Note specifically that this is no different from the normal case of sending a message and getting a response whose value is a capability, so it has no new cryptographic implications. (In platforms which support generic creation of facets (restricted copies of a capability) that are not just locally-implemented proxy objects, this might be the same operation as that but with no-op parameters.)

Given that we have this operation, a question is how the old cryptographically-weak capability is revoked. An obvious option would be that the refresh operation implicitly does it, but this might not suit some applications if a single capability has multiple holders who all want to update. In general, this depends on the capability platform's approach to revocation; some have 'revoke' as an operation on every capability; some reject this in the name of not allowing one client to deny service to others. If every capability has a revoke operation then each holder can revoke the one it has stopped using; if not, then the host of the target of the capability can decide to give up and stop implementing the old version once some standard refresh period has expired.

The other half of this story, besides providing the exchange operation, is that the capability platform should allow automatically exchanging capabilities while the holder of the capability does not need to do anything — transparently substituting the contents of the entry in your c-list, basically. (This implies that capabilities are not held as bits in application-specific data storage, but that is also good for other reasons, such as not leaking caps in bulk data backups/debug logs, and auditing what capabilities you hold.)

Note that in the above I have said nothing whatsoever about identities or keys. This is because I think it is clarifying and important to stick to the fundamental ocap model as much as possible — and also because I don't completely understand certificate-based cap systems. And insofar as I can't treat them as distributed ocap systems implemented on unspecified cryptographic facilities (possibly with additional features enabled by the certificates), that's a bug.

[Justin Cormack]

On 31 July 2018 at 15:13, Kevin Reid <kpr...@switchb.org> wrote:
> I think that a "full-fledged" capability system — that is, one which
> provides for all needs which will come up in using it at scale and for a
> long time — must include standard provisions to help manage them effectively
> rather than leaving it up to individual users' and application designers'
> actions to be fully thoughtful.

Absolutely. This is somewhat specific to the use case of course.

> The straightforward approach as I see it is that there should be an
> operation — at the capability platform level, applicable to any capability
> rather than being application-specific — which means "please issue me a new
> capability exactly like this one except with fresh cryptographic features".
> Note specifically that this is no different from the normal case of sending
> a message and getting a response whose value is a capability, so it has no
> new cryptographic implications.

This is not that useful if a capability has been compromised though as anyone
who stole the capability can get a nice fresh one potentially. It is
fine if you want
to update your algorithm or key strength but this does not happen very often. So
I think you may need a refresh route that involves going back to get
the capability
from where you got the original one from.

My domain of interest is service to service communication for
microservices where
there are at least some assumptions that processes can be relatively short lived
and can be recreated so I am looking at some form of rolling update as one case
at least, but there wil be some longer lived capabilities even so.

> Note that in the above I have said nothing whatsoever about identities or
> keys. This is because I think it is clarifying and important to stick to the
> fundamental ocap model as much as possible — and also because I don't
> completely understand certificate-based cap systems. And insofar as I can't
> treat them as distributed ocap systems implemented on unspecified
> cryptographic facilities (possibly with additional features enabled by the
> certificates), that's a bug.

Because certificates are non transferable (unless you transfer private
keys...) they
do seem a poor fit for capabilities, you would have to do some sort of
chaining for
each transfer which seems not very scalable.

Justin

[Kevin Reid]

On Tue, Jul 31, 2018 at 8:10 PM Justin Cormack <jus...@specialbusservice.com> wrote:

On 31 July 2018 at 15:13, Kevin Reid <kpr...@switchb.org> wrote:
> The straightforward approach as I see it is that there should be an
> operation — at the capability platform level, applicable to any capability
> rather than being application-specific — which means "please issue me a new
> capability exactly like this one except with fresh cryptographic features".
> Note specifically that this is no different from the normal case of sending
> a message and getting a response whose value is a capability, so it has no
> new cryptographic implications.

This is not that useful if a capability has been compromised though as anyone
who stole the capability can get a nice fresh one potentially.

That's a different problem than I was solving. In this one, there must be some degree of application-specific code as what is a reasonable policy for revoking capabilities depends on the application. It might share some of the same infrastructure, though!

 

It is fine if you want to update your algorithm or key strength but this does not happen very often.

Here's another use case that is also infrequent but maybe more often than crypto upgrades, at least in some types of systems: telling clients "in the future please contact me at this new address". The same protocol can be used for both.

 

So I think you may need a refresh route that involves going back to get the capability from where you got the original one from.

In a capability system, you get capabilities from capabilities which you got from capabilities … — to think of there being an original capability which it makes sense to go back to is, in my opinion, a mistake, because it leads to your capability systems being necessarily small and bootstrapped from non-capability systems, which inhibits your ability to do actual capability design.

[Matt Rice]

On Tue, Jul 31, 2018 at 8:50 PM, Kevin Reid <kpr...@switchb.org> wrote:

>> So I think you may need a refresh route that involves going back to get
>> the capability from where you got the original one from.
>
> In a capability system, you get capabilities from capabilities which you got
> from capabilities … — to think of there being an original capability which
> it makes sense to go back to is, in my opinion, a mistake, because it leads
> to your capability systems being necessarily small and bootstrapped from
> non-capability systems, which inhibits your ability to do actual capability
> design.

Perhaps its quibbling over the definition of capability, but we can
take the sealer/unsealer pattern
as a case where the unsealer absent the box gives no authority, and
the box absent the unsealer gives no authority,
essentially a primitive form of rights amplification where 2 benign
objects are brought together to form a capability...

I guess you could define such a benign object as carrying 'potential
authority', but it does carry a sense of origin of capabilities,
while adhering to capability patterns... *shrug*

[Kevin Reid]

On Tue, Jul 31, 2018 at 11:14 PM Matt Rice <rat...@gmail.com> wrote:

On Tue, Jul 31, 2018 at 8:50 PM, Kevin Reid <kpr...@switchb.org> wrote:
> In a capability system, you get capabilities from capabilities which you got
> from capabilities … — to think of there being an original capability which
> it makes sense to go back to is, in my opinion, a mistake, because it leads
> to your capability systems being necessarily small and bootstrapped from
> non-capability systems, which inhibits your ability to do actual capability
> design.

Perhaps its quibbling over the definition of capability, but we can
take the sealer/unsealer pattern
as a case where the unsealer absent the box gives no authority, and
the box absent the unsealer gives no authority,
essentially a primitive form of rights amplification where 2 benign
objects are brought together to form a capability...

I'm not sure I understand your point, if you're intending to disagree with me. I don't mean to claim that "where you got a capability from" is not a thing to ever take into account. I say that it is a bad idea to design a system that, in order to function, needs to periodically look all the way back to something which is not a capability introduction, which is what I took "going back to get the capability from where you got the original one from" to mean.

(Unless you are specifically intending to design a hybrid or legacy-compatibility system.)

[Alan Karp]

Apparently, my response to Chris's original email was too terse.  Hence, the tl;dr that follows

Alice will have sets of keys for different purposes.  This thread has focused on the keys associated with capabilities.  In addition, Alice will have keys that she uses to get those capabilities.  I believe these are the ones Chris says you want to "push out into the wild."  For example, Alice may have one key pair known to her employer that she uses to get her "employee endowment," the initial set of capabilities she needs to do her job.  She may have another one associated with a government agency that she presents to a bank to get the capability to open a new account.  While such keys are often associated with Alice as a person for audit purposes, others need not be.  For example, that government agency could certify that a given key pair is associated with someone over 18, which Alice can use to get a capability to her favorite adult web site.  Managing these keys is easy if they have a single "audience," to use the OAuth term, such as Alice's employer, or nearly impossible, as with the government agency or a certificate authority.  I'll assume we know how to manage and update these key pairs, even though we don't.  The point is that whatever key Alice used to get a capability, she can often use when she needs to get the same capability issued to a different key.

First, some basics.  In a certificate-based capability system, each capability is issued to a specific public key, and a request using it is valid only if the entire request, including the capability certificate, is signed by the corresponding private key.  Delegation is done by creating a new certificate containing the delegator's certificate, and the new delegation certificate is valid only if it signed by the private key corresponding to the public key in the delegator's certificate and delegates a subset of the rights in the delegator's certificate.  Anyone holding the private key corresponding to a public key on the delegation chain can revoke all descendants by sending a revocation request signed by that private key to the object designated by the capability.  Using one-off key pairs for delegation makes it less likely that a given capability will be used by more than one object, but it's not forbidden.

Now on to key management.  First, let's ignore key compromise and worry about expiration or wanting to use stronger crypto.  If a given key pair has not yet expired, Alice should be able to invoke a reissue(new public key) method on the object designated in the delegation certificate (not the target object unless this is the root certificate).  Reissuing a capability should not by default revoke the old one, but Alice can do that explicitly if she wants.  

Say that Alice has delegated a capability to Bob.  When Alice changes her one-off key and chooses to revoke delegations from her old one, Bob's attempt to use his delegation will be rejected.  The first thing Bob's system should try is to invoke the reissue() method in the delegation certificate.  If Alice revoked due to a key change, the reissue() method can return a new capability to Bob.  Note that Alice need not be online for this refresh to work; Alice could have designated some persistent service to handle reissue() requests.  This procedure is very similar to the OAuth refresh token flow.

I'll respond to specific comments on this thread separately.

--------------
Alan Karp

[Matt Rice]

Not really trying to disagree, except to point towards an oddity where the
"capabilities from capabilities from capabilities" turtles all the way
down aspect
is not entirely clear cut.

However i should say I seem to agree with your statement, In Keykos,
for instance
the factory creator, attesting that a factory cap is a factory created
by itself,
does not really carry a back edge to it's origin which one can follow.
Rather it requires them to hold separately the original creator.

[Alan Karp]

(Replying to specific comments in this thread)

Christopher Lemmer Webber Mon, Jul 30, 6:08 PM wrote:

- Alice uses (K0) for lots of services... she has individual capability

   certificates issued for O1-1000 but they all use K0.

   - Pros: Alice can update K0 in a single place and all of her services

     are now also updated.  She can invoke her capabilities for B and

     also invoke O1-1000 and it's fine.

That doesn't work in my approach, since each capability Alice has explicitly includes the public key K0.  It sounds like you are using a level of indirection to point to the key the capability is issued to.  But that doesn't work for the reason you point out in 

   (Come to think of it, Carol may also be hosed in that scenario even

   if Alice used the same key for everything but Alice's key got

   rotated.  Alice could surely invoke her certificate to the Bank with

   her new key, but it seems like the delegation would break here too,

   because if the cert chain was signed with Alice's old key, even

   if she rotated it, we can't trust this old cert that Carol has.

   Argh, my brain is breaking!)

Kevin Reid via googlegroups.com Tue, Jul 31, 7:14 AM wrote: to cap-talk

I think that a "full-fledged" capability system — that is, one which provides for all needs which will come up in using it at scale and for a long time — must include standard provisions to help manage them effectively rather than leaving it up to individual users' and application designers' actions to be fully thoughtful.

I agree wholeheartedly with Kevin's remarks in this email.  Did my tl;dr message capture what you suggest?

Justin Cormack <jus...@specialbusservice.com> Tue, Jul 31, 8:10 PM wrote:

This is not that useful if a capability has been compromised though as anyone

who stole the capability can get a nice fresh one potentially. It is fine if you want

to update your algorithm or key strength but this does not happen very often. So

I think you may need a refresh route that involves going back to get the capability

from where you got the original one from.

Key compromise it tough.  First, you have to know it happened, then you have to have have a recovery mechanism.  Going back to the "push into the wild" capabilities, those you used to get your initial set of capabilities, might be the only solution.

Because certificates are non transferable (unless you transfer private keys...) they

do seem a poor fit for capabilities, you would have to do some sort of

chaining for each transfer which seems not very scalable.

Actually, that's the way it works in SPKI, E-speak, Zebra Copy, and Macaroons.  Our experience with E-speak is that most delegation chains are short, no longer than 10 and never as long as 100.  Since each delegation certificate is order 1 KB, that's not overwhelming.

Kevin Reid via googlegroups.com 9:01 AM

I'm not sure I understand your point, if you're intending to disagree with me. I don't mean to claim that "where you got a capability from" is not a thing to ever take into account. I say that it is a bad idea to design a system that, in order to function, needs to periodically look all the way back to something which is not a capability introduction, which is what I took "going back to get the capability from where you got the original one from" to mean.

But that might be the only solution in the case of key compromise.

--------------
Alan Karp

[Tony Arcieri]

Random thoughts on this:

"Key management/rotation VS a different key for everything" is not a dichotomy. You can use separate keys for everything and also continuously rotate them. See the GCP Encryption at Reset design for an example:

https://cloud.google.com/security/encryption-at-rest/

The problems this post seems to be describing seem to stem from the capabilities-as-keys model, which is well-known not to live up to OCap's ideals.

As an alternative, manage all keys through a KMS, and retain capabilities that let you get the latest DEK for a particular item. This also means revocation works, even on data hierarchies. You may have stashed a DEK, but in the meantime the system re-encrypted the data behind your back and discarded the old ciphertext. Now you need to present your original capability to the KMS again to get the current DEK.

It does make the KMS an online dependency, but that seems to be par for the course, both for OCap and for KMS systems in general.

[Justin Cormack]

On 1 August 2018 at 21:32, Tony Arcieri <bas...@gmail.com> wrote:
> The problems this post seems to be describing seem to stem from the
> capabilities-as-keys model, which is well-known not to live up to OCap's
> ideals.

Is it well known? References? Most of the articles I found were very
early before
things were practical.

> As an alternative, manage all keys through a KMS, and retain capabilities
> that let you get the latest DEK for a particular item. This also means
> revocation works, even on data hierarchies. You may have stashed a DEK, but
> in the meantime the system re-encrypted the data behind your back and
> discarded the old ciphertext. Now you need to present your original
> capability to the KMS again to get the current DEK.

Look after your keys better and add some indirection does seem helpful...

Justin

[Tony Arcieri]

On Wed, Aug 1, 2018 at 5:13 PM Justin Cormack <jus...@specialbusservice.com> wrote:

On 1 August 2018 at 21:32, Tony Arcieri <bas...@gmail.com> wrote:
> The problems this post seems to be describing seem to stem from the
> capabilities-as-keys model, which is well-known not to live up to OCap's
> ideals.

Is it well known? References? Most of the articles I found were very
early before
things were practical.

See: http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf 

--

Tony Arcieri

[Christopher Lemmer Webber]

I'm not sure what this has to do with caps-as-certificates being like
caps-as-keys. Certificate ocaps don't have the problems described in
that section afaict. They're revokeale, and the extent that the
confinement myth applies is no more than an actor ocap approach afaict.

Could you elaborate specifically on the problems mentioned with
caps-as-keys and how they relate to the discussions here about
certificate ocaps? I'm not seeing it.

[Christopher Lemmer Webber]

Sorry, I see now that the section on SPKI certificates being like
caps-as-keys might address it. I haven't digested fully yet how it
applies to ocap-ld. I'm giving this another read and trying to do so.
I was quite new to ocaps the first time I read this paper.