GID Mail Exchange From April 2008

This is an excerpt from a mail thread on our protoGENI development mailing list. Believe it or not, the original discussion was much longer!

Date: Thu, 3 Apr 2008 11:03:40 -0600
From: Robert P Ricci <ricci@cs.utah.edu>
Subject: Re: GGIDs

Thus spake Leigh Stoller on Thu, Apr 03, 2008 at 08:00:55AM -0700:
> The downside is that generating a new public key for a user changes  
> their GID, which I think we want to be static, not dynamic (my  
> identity this week is different then this week). Not sure that is a  
> good idea.

Ah, this highlights a decision that I guess we have not made explicitly:

If a GID is a 'secure' function (ie. hash) of a public key, this has the
nice property that it is basically self-certifying, in the sense that if
I present you with my GID, my public key, and some thing that's a
function of my private key (ie. I encrypt a challenge you send to me),
then I've proven that I have the private key that goes with the GID,
because you can check that the GID is a function of the public key.

The downside, as you point out, is that I have to change my GID if I
want to use a new (ie. if someone might have stolen my old private key.)

If the GID is just some string of bits, UUID-like, then we don;t have
this downside, but it is no longer self-certifying, and we have all  
kinds of potential problems with holes allowing people to steal each   
other's GIDs.

The arch group has not really made up its mind on this point either, I
think.

> >So, I think a credential *might* need a UUID or something like it so 
> >that we can refer to it (ie. to revoke it), but I don't think that  
> >needs
> >to be a GID, and doesn't need a public key to go with it.
> 
> The inconsistency makes me nervous, but I have to give it more  
> thought before I really have an opinion.

Basically, a GID is about authentication, so I don't think that an
object (credential) that is about authorization needs one (of its own).

From: Leigh Stoller <stoller@flux.utah.edu>
Subject: Re: GGIDs
Date: Sat, 5 Apr 2008 06:55:00 -0700

>If a GID is a 'secure' function (ie. hash) of a public key, this    
>has the
>nice property that it is basically self-certifying, in the sense      
>that if
>I present you with my GID, my public key, and some thing that's a
>function of my private key (ie. I encrypt a challenge you send to me),
>then I've proven that I have the private key that goes with the GID,
>because you can check that the GID is a function of the public key.

Yes, but where in protogeni is this authentication going to be
required, if we are using x509 based ssl authentication, and
credentials to indicate permissions? Also, I think the ssl stuff has
a challenge/response option, but I have to check that to be sure.

Date: Sat, 5 Apr 2008 21:34:40 -0600
From: Robert P Ricci <ricci@cs.utah.edu>
Subject: Re: GGIDs

Thus spake Leigh Stoller on Sat, Apr 05, 2008 at 06:55:00AM -0700:
> >If a GID is a 'secure' function (ie. hash) of a public key, this  
> >has the
> >nice property that it is basically self-certifying, in the sense  
> >that if
> >I present you with my GID, my public key, and some thing that's a
> >function of my private key (ie. I encrypt a challenge you send to me),
> >then I've proven that I have the private key that goes with the GID,
> >because you can check that the GID is a function of the public key.
> 
> Yes, but where in protogeni is this authentication going to be  
> required, if we are using x509 based ssl authentication,

You'll need to authenticate (at least at a session level) every time you
want to make a call that's part of the GENI API. Doing so will, as you
say, use x509, but the point of that certificate is basically to prove
that you have the right to use a particular GID (which will need to be
embedded in the certificate in some way, possibly in the CN).

> and  
> credentials to indicate permissions?

Right, but the credential will be something like 'GID 42 is allowed to
call DestroySliver() on slice foo, component bar', and in order to use
it, you need to prove you are the person with GID 42 (see above).

> >If the GID is just some string of bits, UUID-like, then we don;t have
> >this downside, but it is no longer self-certifying, and we have all   
> >kinds of potential problems with holes allowing people to steal each
> >other's GIDs.
> 
> ^GWhy is stealing GIDs an issue, if all they represent is a person's  
> public key?

Sorry, I was imprecise. Steal as in impersonate you. You're right, in
either case, you don't need to keep the GID itself secret.

Imagine this. Someone from the testbed project in Emulab makes you a
GID, which is a UUID, and let's say it's 42. You now get a certificate
that says 'Emulab/testbed says GID 42 belongs to the person with this
public key', and you use that to authenticate yourself to a CM, since
you hold the private key that goes with that public key.

But now, project bar on Emulab decides it wants to impersonate you, so
it makes a new certificate that says 'Emulab/bar says GID belongs to the
person with this other public key', then presents GID and the new
certificate to a CM. There's no way at all to tell which one is the
'real you'.

Now, when there is only a single trusted entity issuing GIDs and the
associated certificates, we don't really have to worry about this. So,
we *might* be able to get away with it for the prototype, but it's
definitely not an option for GENI itself.

Making the GID a hash of your public key fixes this, because when
project bar goes to generate the bogus certificate, one of two things    
will happen:
1) The public key it includes will not hash to the GID, so it'll be
    obvious that it's a bogus certificate
2) It will use your actual public key, in which case, it won't know the 
    private key, so the bogus certificate will do no good (if it did
    know your private key, there would be no point in generating a new
    certificate)

From: Leigh Stoller <stoller@flux.utah.edu>
Subject: Re: GGIDs
Date: Sun, 6 Apr 2008 05:53:54 -0700

>You'll need to authenticate (at least at a session level) every  
>time you
>want to make a call that's part of the GENI API. Doing so will, as you
>say, use x509, but the point of that certificate is basically to prove
>that you have the right to use a particular GID (which will need to be
>embedded in the certificate in some way, possibly in the CN).


Right, my thought (and current impl) was that the CN is the UUID with
a serial number extension (12345678,1) to indicate the precise
certificate. Helpful when considering certificate revocation; the
serial number has to match the serial number of the certificate, and
what is on record as being a valid certificate(s) for that user.

>Right, but the credential will be something like 'GID 42 is allowed to
>call DestroySliver() on slice foo, component bar', and in order to use
>it, you need to prove you are the person with GID 42 (see above).


Yes, and when I authenticate using my certificate, its CN says
UUID,serial, where the UUID must match what is in the credentials. I
could not have authenticated if I did not have the private key for
this certificate.

>Imagine this. Someone from the testbed project in Emulab makes you a
>GID, which is a UUID, and let's say it's 42. You now get a certificate
>that says 'Emulab/testbed says GID 42 belongs to the person with this
>public key', and you use that to authenticate yourself to a CM, since
>you hold the private key that goes with that public key.
>
>But now, project bar on Emulab decides it wants to impersonate you, so
>it makes a new certificate that says 'Emulab/bar says GID belongs  
>to the
>person with this other public key', then presents GID and the new
>certificate to a CM. There's no way at all to tell which one is the 
>'real you'.

Just to make sure, I was under the impression that identity
certificates can only be made by trusted entities, not mere users,
and so those certificates always chain back to a trusted root.

>Now, when there is only a single trusted entity issuing GIDs and the
>associated certificates, we don't really have to worry about this. So,
>we *might* be able to get away with it for the prototype, but it's
>definitely not an option for GENI itself.

Right, but the model I had in mind was that we trusted CMs and that 
we had those root certificates in our certificate cache (or we use a
real CA).

>Making the GID a hash of your public key fixes this, because when
>project bar goes to generate the bogus certificate, one of two things
>will happen:
>1) The public key it includes will not hash to the GID, so it'll be  
>    obvious that it's a bogus certificate
>2) It will use your actual public key, in which case, it won't know  
>the
>    private key, so the bogus certificate will do no good (if it did  
>    know your private key, there would be no point in generating a new
>    certificate)

Correct, but I did not think this was a problem. See above.

Date: Mon, 7 Apr 2008 11:33:44 -0600
From: Robert P Ricci <ricci@cs.utah.edu>
Subject: Re: GGIDs

> Yes, and when I authenticate using my certificate, its CN says  
> UUID,serial, where the UUID must match what is in the credentials. I  
> could not have authenticated if I did not have the private key for  
> this certificate.

Right, so this basically boils down to: is it possible to have two valid 
certificates for the same GID? See below.

> Just to make sure, I was under the impression that identity  
> certificates can only be made by trusted entities, not mere users,  
> and so those certificates always chain back to a trusted root.

These entities might correspond to projects or institutions. While it's
not 'just anybody', it might include project heads, and while we do have
to trust them, I don't know if we really want to trust them this much -
in the current Emulab model, a badly-behaved project head can only cause
problems for people in their project, but this would open things up and 
allow them to impersonate anyone from any project, including possibly 
people with special (ie. admin) privs.

> Right, but the model I had in mind was that we trusted CMs and that   
> we had those root certificates in our certificate cache (or we use a  
> real CA).
   
I'm not sure what level of 'trust' we really need to put in CMs - other  
than that they will do their job. I guess you are talking about trusting
them to verify users properly?

> Correct, but I did not think this was a problem. See above.

Making the UUID a hash of the public key is not the only way to solve
this problem - it would seem that you could probably construct it in
such a way that it could be validated along with the certificate chain.  
But I will have to think more about this.

From: Leigh Stoller <stoller@flux.utah.edu>
Subject: Re: GGIDs
Date: Mon, 7 Apr 2008 11:23:20 -0700

So it boils down to two points then? 1) If "anyone" can issue
identity certificates then impersonation does become a problem and 2)
can a person have more then one identity certificate.

Sounds like #1 is yes. Complicates things, since revoking or issuing a
new identity certificate invalidates any credentials/tickets in play,
if the GID is a hash of the public key. Right?

#2 is an open question.

Date: Mon, 7 Apr 2008 15:02:27 -0600
From: Robert P Ricci <ricci@cs.utah.edu>
Subject: Re: GGIDs

What about this - what if we construct the GID in such a way that it's
bound to the public keys of all the authoress that signed it, up to the 
root?  

It might look like this: take the public keys for the chain of
authorities, back up to the root, in order, and concatenate them.
(Notice I did *not* include public key of the user we are creating.)
Then, use that at the first N bits of the GID, with the remaining M bits
selected by the 'last hop' authority (ie. set them randomly or    
sequentially.)

The interesting property here is that an authenticating entity (ie. CM),
as it traces back the certificate chain, can do the same process of
concatenating and hashing the authorities' public keys, and can thus
check that the first N bits of the GID were constructed correctly. This 
means that an authority cannot generate a certificate for a GID that   
looks as if it 'belongs' to another authority. But it doesn't tie the
GID to the holder's own public key - the authority that issued that GID
can issue as many certificates as it wants for that GID. So, it can give
the owner of the GID more than one (ie. if the first is compromised),  
and if it misbehaves, the worst it can do is issue certificates for the
GIDs it itself has created.

Note that we should look around for some existing cryptographic
primitive that looks like this, since making up your own crypto/security
is never a good idea...

Some other properties of this system:
If a user's private key is compromised, their issuing authority can revoke
    their old certificate and issue a new one for the same GID
If you want to get a new certificate from a new authority (ie. your GID
    came from your intuition, and you moved, or you need a new
    certificate and the project that originally issued your is defunct or
    you are no longer a member), you need a new GID. This was not true
    of either of the other schemes, and may be the biggest downside 
Users cannot make and distribute their own certificates, like we do with
    ssh keys, but I think we have given that up anyway

Date: Mon, 14 Apr 2008 09:25:58 -0600
From: Robert P Ricci <ricci@cs.utah.edu>
Subject: Re: GGIDs

Thus spake Leigh Stoller on Sat, Apr 12, 2008 at 06:34:53AM -0700:
> Okay, given one of these GIDs, how do we verify it? I have a hash,  
> that was generated by concatenating a bunch of public keys and  
> hashing that (or maybe a hash of a concatenation of hashes of public  
> keys).

The idea is that the certificate chain contains the public key for each
authority, so you just concatenate them, hash, and compare that to the
first N bits of the GID.

> There is the authentication process (to a service) and then the  
> verification of credentials that reference a GID.

This would be part of authentication. I guess we could do something
similar with credentials, hadn't thought that far yet.