Open Stack

TL;DR: improving the crypto exchanges to address the issues raised :-)

Read below.

On Thu, 2013-04-25 at 16:51 -0400, Simo Sorce wrote:
> On Thu, 2013-04-25 at 15:16 -0400, Eric Windisch wrote:
> > One use-case I see this proposal failing to address is with cross-cell
> > and cross-project messaging. 
> 
> At the moment it is not directly addressed, but I haven't seen
> addressing handling certificate trust and revocation checking in the
> public key scheme which has the same challenges.
> 
> > The cross-cell messaging is a legitimate concern and probably where
> > some of this security is most desperately needed. Your present design
> > seems to require a single, global service to drive communication and
> > authority for all cells.
> 
> If I have to argue on the spot I can tell that cross-cell keys can be
> easily handled through intra key server communication when the 2 peers
> are in different cells.
> 
> If you look at how keys are generated only one peer key is used to do
> derivation, so if the key is not on a specific server all you need is a
> call to the trusted peer-key server to obtain the necessary keys and
> hand them back to the client.
> 
> This is made up on the spot and will need more consideration but I do
> not see it as an obstacle, and certainly not incompatible with the
> current scheme, just an additional extension.
> 
> > Secondly, cross-project messaging is a concern for the Ceilometer
> > team. This is presently contentious amongst the RPC users and
> > maintainers, and a matter of active discussion.  However, should that
> > we seek to support this, it should be considered. Presently, all
> > projects communicate via AMQP through a single control_exchange.
> > ZeroMQ messaging happen over a unique TCP port per project. The
> > messaging is clearly delineated, split between the projects.
> > 
> > In our proposed PKI model, this isn't a huge deal, because we can have
> > a keyserver per project, per cell, or per project per cell. There will
> > be devils in the details of implementing it,
> 
> At least as hard as with the shared-secret solution.
> 
> You have the same problem of trust between clients and the key server
> and inter-domain/project/cell/server trust between different key
> servers. 
> 
> >  surely, but it isn't against the architectural design. If
> > communicating to another project or cell, we can make the code reach
> > into the right keyserver.
> 
> Same with a shared key solution, why do you think you can't there ?
> 
> >   However, your proposal requires a tight coupling of peers / services
> > that introduces complexity around scale that is not presently
> > addressed. 
> 
> I do not see a difference in the complexity, care to share some details
> about why you think it is more complex ?

Ok I have been thinking about the issues raised here for the best part
of the last 12 hours :-)
As well as the following one:

On Thu, 2013-04-25 at 12:52 -0400, Eric Windisch wrote:
> I've read through this and had a discussion with Simo on IRC for
> clarity, before posting.
> 
> It isn't a terrible proposal. My biggest concerns are the following,
> as pertains to signing-only:
> 
> 1) Keyserver lookups on both sides, not just one-sided, on signing.
> 2) Practical requirement for the matchmaker for signing, even for
> AMQP.
> 
> On the encryption side, PKI has the same requirements, but using
> slower algorithms. If we accept that the typical use-case will be
> message signing, then we may prefer to optimize for that, not for
> encryption. Perhaps we could figure out a middle-ground here with a
> single sender-side lookup and a token from the keyserver? That might
> be a slippery slope.


And I have a few ideas to improve the scheme I proposed.
I will ignore point 2 above here because I think we can used group keys,
however we can improve on the design and have short lived ones.


This is a quite long description, and I may have made errors (either in
transcribing the mechanism or even in the logic!) so if something
doesn't check out feel absolutely free to point it out, it's rather
complex stuff so any question is a good question!



So let's proceed in order.

1) Double lookups on both sides.
This is solvable by simply following a bit more the Needham-Schroeder
model. I initially tried to keep things a simple as possible, but it is
evident the cost is concerning so let's explore a slightly more complex
model that have very desirable properties.

Let's look at the communication pattern for sending a message, assuming
none of the actors have talked to each other in a while.

S is the key server.
Ex() means Encrypt with key of X
A wants to send a message to B and sign it

Current proposal:

1. A -> S [Please give me SEK for A -> B]
2. S -> A [Here your SEK]
3. A -> B [signed message]
4. B -> S [Please give me SEK for A -> B]
5. S -> B [Here your SEK]
now B validates the message.

We can cut down steps 4 and 5 by simply sending back in 2 a copy of the
SEK encrypted with B's key so that the pattern becomes:

1. A -> S [Please give me SEK for A -> B]
2. S -> A [Here your SEK and btw here is Eb(SEK)]
3. A -> B [signed message, sends along Eb(SEK)]
now B takes Eb(SEK), unencrypts it and uses SEK to validate the message

This cuts down the 2 lookups per pair problem. The communication between
A and S or between A and B is not more complex, the total number of
encryption/decryption in the system does not change.

There are also 3 neat advantages using this amended protocol:
1. Multiple Key Servers do not need anymore to have a coherent
Random.Key shared among them. This makes scaling key servers a little
bit easier (big win!).

2. It allows us to use a random salt that differs for every single SEK
request (win!) as we do not need to be able to regenerate the same SEK
in the server anymore (no second query from the receiver). [Even better
see 4) below.]

3. It allows us to avoid a potential attack on the receiver side I
thought about this night (win!) With the current scheme an attacker can
run a DoS by which it sends many messages to a receiver pretending each
message comes from a different source. This will cause the client to ask
for SEKs from the Key server at a rapid rate consuming key server
resources needlessly. This is especially problematic because you cannot
stop receivers from asking as that's a totally legitimate operation.
Using the new scheme this does not happen anymore as the receiver does
not need to ask for anything, and if a compromised host contacts
directly the key server it can be rate limited or filtered and squashed
as its requests are not legitimate anymore.


4. An additional property of this scheme is that because of (2) we do
not actually need to use A's key and HKDF to derive the SEK, we can
actually decide to use completely random keys generated on the spot as
the SEK pair if we wish. Because we do not need to ever be able to
regenerate a SEK again. So we gain the fact we have now simplified the
SEK generation by removing the need to perform Key Derivation.
We can still do Key Derivation if we see an advantage to it, but we do
not need to.

Also note that Eb(SEK) is actually more than just encrypting the SEK
into a key, the reason is that the receiver must actually be able to
check the SEK used is actually the one for A -> B and not one stolen by
X and used to send messages X -> B

So Eb(SEK) includes both A and B names and the expiration time and the
receiver will check that they all check out.
We have 2 ways to do this:
1. simple direct comparison of strings taken from message metadata.

2. Use just HKDF expansion (w/o extraction) and generate a Random Key
(Rkey) on the key server side and send the Rkey encrypted, leaving the
client to perform the expansion (which requires the correct names and
expiration time to yield the right SEK back).
The new way to compute the SEK now becomes:

SEK = HKDF-Expand(Rkey, Svc.A+'\x00'+Svc.B+'\x00'Exp.Time, Le+Ls)


I have a slight preference for 2 as it makes impossible to 'forget' to
make this check on the receiver. It also decouples completely using any
of the shared keys to derive the SEK because is uses totally random keys
at this point.
So we basically reduce computation on the key server side as we just
need to get a random value and do not need to perform the HKDF
extraction.

Also note that we do not want to send Rkey to the sender but a fully
formed SEK, this way if the sender is compromised it cannot try to
impersonate other services. If we gave the RKey to the sender it would
be able to generate a SEK for any source/expiration combination (the
target is fixed and determined by Eb()), so the receiver would have to
go back to actually explicitly check the source and expiration time
provided do actually match the ones in the message metadata as just
computing the SEK would not be a check in itself anymore.


2) Group messages.
One of the issues here is how to send messages to a group like
scheduler.*, by using EB(SEK) the receiver is none the wiser if key B is
a group key, unless the receiver happens to have access to this key.
however there are 2 big issues with group keys:
1. distribution
2. re-keying in case one actor in the group is compromised

We can solve both of these problems with a short lived key.
Basically each service in a group can be allowed to request the shared
group key from the Key server.
The exchange is very similar to the one used to request a SEK.
When a client asks for a Group key, the server performs a few steps:
1. Verifies the requesting party is actually part of the group it is
asking a key for. The simplest way to validate this is by verifying the
service part of the name of the requester matches the group name and the
group is white listed and allowed to exist.
2. Checks if a recent valid key is available otherwise generates a new
keys and stores it (timestamped with a short expiration time, say a few
hours)
3. Sends the key back encrypted with the requester long term key.
Ea(group.key + expiration)

The receiver caches the group key until the expiration time so that the
receiver performs at most one lookup within the expiration time and we
do not fall back into a 2 lookups per message scheme.

This solves distribution and re-keying.
If any host is compromised the admin will kill the specific host key and
can kill the group key or count on the fact it will expire very shortly.

The group key is ever only used for *receiving* messages, A request to
the key server for a SEK where the source is a group SHOULD be denied.

So a compromised group key can only fake messages that can be sent to
the group but cannot be used to fake messages sent from any other group
member to third parties.


3) Finally let's come to services from different trust zones talking to
each other. Assuming we have S1 as the key server for A and S2 the key
server for B and A wants to send messages to B

The solution for this is a trust relationship between S1 and S2 (shared
key between them). And ACLs that says S1 is allowed to ask any SEK for
targets in S2 (and vice versa unless the trust is unidirectional).


So to send a message from A-> B our communication now becomes only
slightly more complex, but requires no knowledge of this 'trust' from
either A or B which is a win as we can seamlessly add this later.

1. A -> S1 [Please give me SEK for A -> B]
2.1. S1 -> S2 [Please give me SEK for A -> B] (*)
2.2. S2 -> S1 [Here your SEK and btw here is  Eb(SEK)]
2.3. S1 -> A [Here your SEK and btw here is Eb(SEK)]
3. A -> B [signed message, sends along Eb(SEK)]
now B takes Eb(SEK), unencrypts it and uses SEK to validate the message

So the communication now is a little bit slower cross-trust zone but
works just fine and transparently to the sender and the receiver.



(*) Note that S2 does not have A's Key for derivation but that is ok see
subpoint 4 of the first point in this email, where I say SEK can be
totally random. Note also how neither S1 gets to know any secret in zone
S1nor S2 any secret in zone S2, the only secret really is the shared key
between them that represents the trust.


I am going to work over the weekend to change the document to use this
scheme.

As always Feedback is *very* welcome.


Simo.

-- 
Simo Sorce * Red Hat, Inc * New York