Re: [Secdispatch] Controller-IKE

[Tero Kivinen <[e-mail]>]

Benjamin Kaduk writes:
> On Mon, Jul 22, 2019 at 11:13:24AM -0700, Eric Rescorla wrote:
> > David,
> > 
> > At the mic today, you said that C-IKE was 2N complexity rather than N^2
> > complexity in terms of messages. Here's what confuses me.
> > 
> > Just for simplicity, imagine that we do this in two phases: everyone
> > registers their key with the controller and then the controller
> > disseminates them. At this point, the controller has N keys and it needs to
> > send them to N endpoints. If you are able to broadcast to all the nodes at
> > once, then the controller will send N keys, so the total overhead is 2N (N
> > uploads + N downloads). However, if the controller has point to point
> > links, then the controller has to send ~N^2 keys (N-1 keys down N links).
> > So those might be bundled into a single message, but you still have to send
> > N^2 keys. Or am I missing something?

I was pointing out that this is actually N^3 keys you need to
transport if you you start building the network with one node at time.

In the beginning there is only C (controller) and it has no keys. This
was good, but then there was light. Key count over wire 0.

Node 1 came up, sent its key to C and saw this is still good, as there
is nobody for him to talk to. KCOW 1.

Node 2 came up, sent its key to C and C saw that it needs to send the
Node 2's key to Node 1, and Node 1's key to Node 2, it did so. KCOW +=
1 + 2*1 = 4

Node 3 came up, sent its key to C, and C sent other keys it has to
everybody else. KCOW += 1 + 3*2 = 11.

Node n came up, sent its keys to C, and C sent other keys (n-1) it has
to everybody else (n) KCOW += 1 + n*(n-1).

The final count of key count over wire is n + n * (n-1) * (n-1)...

Of course you could remember in C which keys you have already sent
out, so in that case the key count over wire drops down to n + n * (n-1). 

When you compare this to the IKE case, where the node n coming up, it
just needs to send diffie-hellman public keys out for 2 * m times,
where m is the number of nodes it wants to talk. In general cases m <<
n.

Also one node rekeying requires C to send its new key to every n-1
node in the network. In the IKE case rekeying just does sends keys out
2 * m times.

It seems that you assumed that messages between the controller and
node are free, but peer to peer messages between nodes are not. I do
not belive in that. 

> I'm p robably missing something too, but there's a couple potential
> differences from what you describe -- the flow down from the controller to
> the endpoints can be a P2MP flow, and also if the controller knows the
> overlay network, it knows that it only has to send each endpoint (a specific)
> 10 keys for that endpoint to talk to the other endpoints it needs to.  That
> is, each endpoint may not need (or be able to!) store the keys for all N
> endpoints.

The whole idea in the controller IKE seemed to be that m == n-1, i.e.,
each node wants to talk to everybody else, otherwise normal IKE where
nodes bring up SAs when they need it is much more efficient.
-- 
[e-mail]