Re: CORE Key Exchange

[Christian Grothoff]

Hi Martin,

A few comments:

1) I don't know why you want to go for a KEM. Using a KEM seems 
well-motivated if the goal is to go post-quantum, but AFAIK that is not 
the objective here. I generally consider DH to be cleaner, simpler and 
just overall better than a KEM. That said, your write-up doesn't exactly 
elaborate on what you intend to use for the Encaps/Decaps operations.

2) The fact that the KX transcript is not signed is something I consider 
a feature. Look at 3DH (developed in the OTR-context) and similar 
designs that go through quite some lengths to avoid signing messages and 
thereby providing proof that a communication did take place. So the fact 
that the KX transcript is not signed was a design goal. That said, I 
don't see where your 'recipient' checks anything, at least your 
algorithm doesn't state a failure case, only I has an "assert" at the 
end. But what does R get?

3) Static DH key: this was again a design decision as otherwise an 
attacker may be able to DDoS you. Let's for a second assume we're not 
above transport, but just run CONG directly over UDP. If that were the 
case, I think your design will suffer from having to do quite a bit of 
work for the equivalent of a TCP SYN flooding attack.  Can you estimate 
how much work an initiator would have to do in relation to the 
recipient's processing in your design?

I'm not arguing to keep the original protocol, and I like explicitly 
including the supported algs/services/version in the handshake. But I 
don't exactly see the advantage of using KEM over say a 2DH (with 
static+ephemeral keys), and while a 1 round-trip design is obviously 
neat, I also think this is a bit too vulnerable to resource exhaustion 
attacks.

A 2DH-based approach taking 2 round-trips might allow the recipient to 
avoid significant computation and storage until it has at least some 
evidence of effort from the initiator. Now, MAYBE we can argue that with 
transport below this is not as much of an issue, but I'm not sure 
transport/communicators are intended (or sufficiently hardened) to 
categorically prevent CONG from being exposed to flooding attacks. And, 
while I could be convinced otherwise, I wonder if defense-in-depth isn't 
the simpler and thus better answer on this count.


So my first cut might look like this:


Initiator has: ip, Ip (long-term keys)
Recipient has: rp, Rp (long-term keys)

SK/RK are symmetric keys for AEAD with IV as needed.

Initiator knows Rp.

Initiator:

(ie,Ie) <- Keygen() # initiator ephemeral
ETS <- DH(ie,Rp)    # not initiator replay-safe for recpient
Meta0 := Ie,Ip,ISupportedAlgs,IServices,IVersions
Meta1 := Rp,Meta0
ISig := HKDF(ETS,Meta1)
transmit Meta0+Isig

Receiver:

receives Meta0+Isig
ETS <- DH(iE,rp)               # same ETS as above
assert ISig == HKDF(ETS,Meta1)
  # Note: replay by Initiator possible ...
(re,Re) <- Keygen() # receiver ephemeral
[SK|RK] <- HKDF(ETS, DH(re,Ip))
Meta2 := RSupportedAlgs, RServices, RVersions
Payload <- AEAD-encrypt(SK, Meta2)
transmit Re,Payload

Initiator:

[SK|RK] <- HKDF(ETS, DH(Re,ip)) # same SK&RK as above
Meta2 <- AEAD-decrypt(SK, Meta2)
assert AEAD-tag valid
Payload2 <- AEAD-encrypt(RK, ApplicationData)
transmit Payload2

Receiver:

ApplicationData <- AEAD-decrypt (RK, Payload2)
assert AEAD-tag valid
mark-connection-up
handle ApplicationData
(continue sending using SK and receiving via RK).


The above obviously has the disadvantage of 2RTT and two DH for each 
peer. Compared to what we did before, we now include the Meta-data and 
use fresh ephemerals, which I guess is slightly better replay-prevention 
compared to the monotonic time used in the existing design. Any other 
issues with it? Is what I write clear? (Again, just a quick first draft, 
nothing I thought about too hard.)


My 2 cents

Christian


On 11/6/24 11:39, Martin Schanzenbach wrote:
> Hi,
>
> I would like to restart the discussion on the ML here again as I keep
> forgetting what we established and what the way forward is and I think
> it is better to discuss this "out in the open".
>
> Our current "PingPong" KX in CORE seems quite odd and complex to me and
> the requirements fuzzy.
> In a nutshell, the protocol tries to establish a DH secret and it goes
> something like:
>
>
> 0. MyPeerID: Generate an "ephemeral" DH key pair and sign it with
> PeerID private key. Lets call this "cert"
> 1. MyPeerID: If MyPeerID > OtherPeerID goto 2; otherwise wait T time
> and then goto 2
> 2. PyPeerID: Send "cert" to OtherPeerID (Ping)
> 3. OtherPeerID: Calculates the DH secret from ephemeral public key in
> "cert" and its own ephemeral DH key (from 0)
> 4. OtherPeerID: Confirms handshake by sending message back; sending its
> own "cert" (Pong).
> 5. MyPeerID calculates the DH secret from ephemeral public key of
> OtherPeerID in "cert".
>
> Now, I have various issues with the protocol:
>
> a. Freshness: We should use nonces, which we don't and can't for
> reasons including the following
> b. Static DH key: The "ephemeral" DH key is actually static across
> handshakes with other peers and across the rekey interval (or key
> validity period, whatever you want to call it).
> c. The KX transcript is not signed/verified
> d. The roles are not clear.
>
> Now, the issues seem to stem from the idea that we do not know which
> peer initiates the handshake, so we cannot know which role a peer is
> in.
> In fact, the KX could be initiatet theoretically from both peers at the
> same time, and we need to take this into account.
> Peers determine a KX initiation based on various factors, for example a
> peer may just have learned of the existance of the other peer, just
> started, etc.
> This is why the protocol (Steps 0-5) may (within the key validity
> period overlap of both PeerIDs) converge to the same DH secret
> regardless of role and KX flow (and yes, this is bad from
> security/crypto view).
> The state machine to make this happen is implemented, as far as I can
> see, but I am not sure how well this actually works in practice given
> that we see some erratic behaviour from CORE and regular bug reports
> regarding connectivity (even to the bootstrap peer).
>
>
> Now, I would really like to converge to a semi-standard, known secure
> KX protocol for CORE that has clear requirements and is much more
> streamlined.
> As already discussed, I have drafted a KEMTLS-inspired handshake here
> with 1.5 RTT:
> https://docs.gnunet.org/master/developers/apis/cong.html#handshake-protocol-draft
>
>
> I also started to document the current protocol, but it is very complex
> due to its state machine and 3RTT+.
>
> My Idea: IF we can agree that transport only notifies CORE of a
> connection if it can send AND receive messages from that peer (bi-
> directional connectivity, which afair is the case in transport right
> now), I strongly believe that we can simply rely on protocol Step 1
> that a KX is initiated _at all_.
> It can still happen that two KX are initiated one from each peer at the
> same time.
> But in this case, since we assume that we have bi-directional comms, we
> can simply drop the "late" initiator message on one side based on the
> same condition in Step 1.
>
> Wdyt? Any comments?
>
> BR
> Martin