Authenticated Key Exchange of Kyber.AKE

P_Gate

5/4/24, 4:24 PM

I have some questions about the setting of the one-way authenticated key exchange of Kyber.AKE as defined in section 5 of the paper.

How does $P_2$ authenticate itself to $P_1$? It is not obvious to me in the paper how it is ensured that $P_1$ really communicates with $P_2$. So how does $P_1$ know that it can actually trust $P_2$? I would have expected something like a certificate authority here.
From $P_2$'s point of view, in a one-sided authenticated key exchange, $P_2$ does not know with whom he communicates or from whom he receives messages (the other side is not authenticated). Are there concrete attack possibilities here, something like MITM or replay attacks?
Goes in the direction of question 2. Does the one-sided authenticated key exchange prevent MITM attacks at all?
Suppose an attacker eavesdrops on the communication between $P_1$ and $P_2$, then he knows $pk$ and $c_2$. Assuming by a mistake, the long term key $sk_2$ is revealed, then an attacker could still recover the key and could thus crack old messages he has previously collected now? Is this a conceivable attack, or is there a mechanism that prevents this?

1 + 0

key-exchange

kyber

Score:1

Crypto

Daniel S

5/4/24, 4:54 PM

In section 5, the paper states "party $P_1$ knows the static (long-term) key of party $P_2$". You should interpret this as meaning that by unspecified means, $P_1$ is assured that $P_2$ knows the private key associated with the (long-term) public key in question. This could be achieved by any number of means (pre-positioning, certification, web of trust), but the paper does not mandate or specify how this should be achieved.
There is the possibility of impersonation of $P_1$, but not of MitM on a session initiated by the legitimate $P_1$. If Kyber is secure and the private key is handled properly, any interceptor would not have the means to recover the $K_2$ value selected by $P_1$ and hence would not be able to reconstruct the final key (assuming that the hash function $H$ is secure). A replay of the exchange would not see $P_2$ selecting the same value $K$ and so a different final key would be established.
Yes, the one-way AKE prevents man in the middle, but not impersonation. Once the shared key is established, $P_2$ should require additional authentication information form $P_1$ (e.g. password, multi-factor data) before communicating any information that should be limited to a group of which $P_1$ is part.
No, this would only allow the eavesdropper to recover $K_2$. To crack old messages they would also need to recover $K$. Assuming that Kyber is secure, recovering $K$ from transmitted data would requires knowledge of $sk$. Both $K$ and $K_2$ are needed to reconstruct the final key (assuming that the hash function $H$ is secure).

+ 4

P_Gate

5/4/24, 6:56 PM

Thanks for your answer! A few questions: How to recover $K_2$, what would be the procedure? Don't you just need $K$ and $K_2'$ to recover the final key? In the end the keys are the same, so either $K'$ and $K_2$ or $K$ and $K_2'$ should be enough to recover? (When we sepeak about the one-sided AKE)

Daniel S

5/4/24, 8:05 PM

Yes, $K'$ and $K$ and also $K_2$ and $K_2'$ should be the same value for protocol correctness (may be some low probability failure rate due to using lattices). $K_2$ could be recovered if $sk_2$ is compromised (so the adversary can execute $\mathrm{Decaps}(sk_2,c_2)$, or if its generated using weak randomness, or if the computational environments of either participant are compromised, or if sidechannel data compromises information about $K_2$... In short there are many things to defend against, but hopefully most will have been thought of by the implementor.

P_Gate

5/6/24, 5:29 PM

Regarding your first point, this does not guarantee the authenticity of $P_2$? The "authenticated" must come from somewhere to speak of an AKE. Then I am still interested in how the label "public/private auth. key" is to be understood? Is that supposed to mean that it guarantees that the key (private/public) actually comes from $P_2$ (I'm confused by the "auth." in the label.

Daniel S

5/8/24, 12:48 PM

All secure cryptography requires (at least) one root of trust from which all subsequent trust and authentication is derived. What the root is may vary from scenario to scenario (and might even be $P_2$ itself). To cope with all scenarios, rather than stipulate how $P_2$ has bee authenticated, it is simply assumed that it has been.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Authenticated Key Exchange of Kyber.AKE

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.