Re: [Secdispatch] Controller-IKE

Tero Kivinen <> Mon, 22 July 2019 22:35 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 75E11120094 for <>; Mon, 22 Jul 2019 15:35:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.419
X-Spam-Status: No, score=-3.419 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_NEUTRAL=0.779, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 3QENfRFZq_yA for <>; Mon, 22 Jul 2019 15:35:33 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id D81E912006B for <>; Mon, 22 Jul 2019 15:35:32 -0700 (PDT)
Received: from (localhost []) by (8.15.2/8.15.2) with ESMTPS id x6MMZNti020160 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Tue, 23 Jul 2019 01:35:23 +0300 (EEST)
Received: (from kivinen@localhost) by (8.15.2/8.14.8/Submit) id x6MMZMBI015494; Tue, 23 Jul 2019 01:35:22 +0300 (EEST)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <>
Date: Tue, 23 Jul 2019 01:35:22 +0300
From: Tero Kivinen <>
To: Benjamin Kaduk <>
Cc: Eric Rescorla <>, "secdispatch\" <>, "David Carrel \(carrel\)" <>
In-Reply-To: <>
References: <> <> <> <> <> <> <> <>
X-Mailer: VM 8.2.0b under 25.1.1 (x86_64--netbsd)
X-Edit-Time: 16 min
X-Total-Time: 16 min
Archived-At: <>
Subject: Re: [Secdispatch] Controller-IKE
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Security Dispatch <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 22 Jul 2019 22:35:36 -0000

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 <<

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.