# Is there a key exchange protocol that requires only one message?

Say I want to exchange a secret with someone, but I only get to send one message to the other person, and then we encrypt with that secret. Diffie-Hellman and ECDH require multiple messages to be sent back and forth to get a shared secret.
Is there a key exchange that requires just one message to be sent from one party securely? (I know that sending the key over plaintext works, but that isn't secure.)
(Define message as a packet over the internet or one SMS for example)

• Do you have the ability to view data the other party generated, even if not securely? Do you have any prior communication with the other party? Can you get a reply? It's definitely possible to do key exchange in a single round trip. If you don't worry about authenticating the other party - which I assume you don't, or at least have another way to handle, since [EC]DH doesn't do that - you won't even need any external data. – CBHacking Oct 12 '19 at 3:21
• 1. No. 2. In this case you would have prior communication with the party, BUT I am looking for forward secrecy (so if a prior secret is made, that doesn't create forward secrecy since something shared would be long term) 3. You cannot get a reply. 4. Authentication does not matter. (Also: this is a purely academic question, I'm not actually implementing forward secrecy) – mngxyuiso Oct 12 '19 at 3:23
• Given that this is a pure academic question I see this more on-topic at Cryptography. – Steffen Ullrich Oct 12 '19 at 6:45
• Did you ever hear the Crypto-Box and the sealed-box? – kelalaka Oct 12 '19 at 11:33

For forward secrecy without a synchronous handshake, you want something like the "ratcheting" protocol that Signal uses. It's a quite clever system, really:

1. Each party generates an asymmetric key pair, and gives the public key to anybody who wants it.
2. Each party generates and stores some number of [EC]DH parameters - one set for everybody you expect to need to talk to soon - then signs the public part of the parameters with the private key and makes the signed part publicly available too.

In Signal's case, the keys and signed public parameters are sent to the central server. Assuming you want to start a secure communication and either trust the server, have some way to verify the public key, or don't care about authentication, you can then do the following steps:

1. Download the recipients's key and their next, not-yet-used public key exchange parameters (the server and the recipient both track which parameters have been used).
2. Optionally, authenticate the key and verify the signature on the parameters.
3. Generate your own ephemeral set of key exchange parameters, and sign the public portion with your private key.
4. Use the private portion from your parameters and the public portion from the recipient's parameters to derive a symmetric key.
5. Optionally, encrypt a message with that key.
6. Send your public key, both sides' signed public key parameters, and the message all to the recipient.
7. Delete the ephemeral key parameters.

The recipient:

1. Looks up the pre-signed key exchange parameters, and verifies that the one of theirs just received had never been used before.
2. Optionally, verifies the sender's public key and the signature on their public key exchange parameter.
3. Retrieves their corresponding private portion of the key exchange parameters, and uses it plus the sender's public portion to re-derive the symmetric key.
4. Deletes the now-used private portion of the key exchange parameters, to ensure forward secrecy.
5. Decrypts the message, and/or encrypts one to send back, using the exchanged key.

For your scenario, if you can't have the central server, you'd need to retrieve the public key exchange parameter (and optionally public key to verify it) beforehand. However, you'd then be able to complete the key exchange and initiate secure communication, asynchronously, with one message... and (at least as soon as the recipient gets the message and completes the key exchange) it would be forward-secret.

The sender must know and trust something about the intended receiver. Otherwise, the sender can't know who s/he shares a secret with.

Also, the intended receiver must know and trust something about the intended sender; otherwise, the receiver will share a secret but can't know with who.

The standard solution is that the above known and trusted "somethings" are public keys. These are not secret, and can be reused.

There must be some way to prevent replay to the intended receiver. I'll consider a shared time reference, such as UTC time in second accurate well within $$\pm\delta$$ second, and a computation+transmission delay in $$[0,t]$$ second (e.g. $$t=1$$ second on an Ethernet network, $$t=1400$$ second for sender on Earth and receiver on Mars with a line-of-sight radio beam).

The sender

• generates a random key $$K$$ and sender time $$T_S$$ (of fixed width), and takes whatever precaution is necessary to not perform that step again in the next $$t+2\delta$$ seconds
• signs the concatenation of $$K$$ and $$T_S$$ with the sender's private key $$S_\text{SEC}$$, yielding signature $$\operatorname{Sign}_{S_\text{SEC}}(K\mathbin\|T_S)$$
• enciphers the concatenation of $$K$$, $$T_S$$ and signature with the intended receiver's public key $$R_\text{PUB}$$
• sends that single packet: $${\,\\S}\quad\underrightarrow{\operatorname{Enc}_{R_\text{PUB}}\bigl(K\mathbin\|T_S\mathbin\|\operatorname{Sign}_{S_\text{SEC}}(K\mathbin\|T_S)\bigr)}\quad{\,\\R}$$

• deciphers it with the receiver's private key $$R_\text{SEC}$$, yielding alleged $$K\mathbin\|T_S\mathbin\|\operatorname{Sign}_{S_\text{SEC}}(K\mathbin\|T_S)$$
• extracts alleged $$K$$, $$T_S$$ and signature
• verifies signature against $$K\mathbin\|T_S$$ and the sender's public key $$S_\text{PUB}$$
• verifies that $$T_R-T_S$$ is within $$[-2\delta,t+2\delta]$$ were $$T_R$$ is the receiver's time
• confidently uses the shared key $$K$$.