I have a doubt about the Diffie-Hellman problem:
Is it possible to send a message to someone using only the Diffie–Hellman key exchange?
Since it's called a key exchange can you only make a key?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Explain what you mean. $\endgroup$ – mentallurg Mar 7 '20 at 23:29
-
$\begingroup$ @Raynold Gordon: if you are the OP, log under your original ID to edit. To the OP: please clarify. Does "send a message" come with a requirement beyond the implicit one that the receiver gets the message in the absence of adversary? In particular, is there a security requirement (confidentiality, integrity..)? What does "only" preclude, like sending extra message, extra operations like a XOR? $\endgroup$ – fgrieu♦ Mar 8 '20 at 7:18
-
$\begingroup$ @Zexion12 As mentallurg and fgrieu have said, please expand upon your question. You are very likely to get a well-considered and detailed response! $\endgroup$ – Patriot Mar 8 '20 at 8:26
Add a comment
|
$\begingroup$
$\endgroup$
5
What exactly do you doubt about the CDH or DDH problems?
Is it possible to send a message to someone using only the Diffie–Hellman key exchange?
You cannot "send" a message using DHKE but you may use its resulting shared secret as a one-time-pad (by multiplication; not XOR) to "encrypt" a message encoded as a group element. When the sender uses a unique key per message, this is called ElGamal.
To encrypt a larger message we'll step back to Diffie-Hellman and use the hash of its shared secret as our key for a symmetric stream cipher. This is called hybrid encryption.
However neither scheme above authenticates our messages, thus an active adversary may tamper with our messages and depending on our application may recover our messages. Along the symmetric route we just need to replace encryption with authenticated encryption.
Instead of reinventing the wheel, this function is known to libsodium as crypto_seal_box. If you want to send many messages, you may prefer one handshake per session and use streams.
You probably don't want to use a single DHKE, but perhaps two or three. Two if you need forward secrecy and three if you want forward secrecy and mutual authentication. The Noise protocol elaborates on many variations and Signal uses an extension of triple-DH. All of these options require the receiver to send the sender at least one message per handshake.
-
$\begingroup$ TL;DR: Yes you can but you probably don't want to for various reasons. $\endgroup$ – cypherfox Mar 8 '20 at 8:24
-
3$\begingroup$ "you may use its resulting shared secret as a one-time-pad": but this less than satisfactorily secure! If one simply XORs the message with the shared key and sends the whole result, then it is possible to recognize which of two messages was sent with probability sizeable better than random. There is a similar issue with ElGamal encryption. Problem is: in $\Bbb Z^*_p$, Diffie–Hellman leaks the Legendre symbol of the shared key. That's one reason we stick a key derivation function on top of DH. $\endgroup$ – fgrieu♦ Mar 8 '20 at 9:02
-
$\begingroup$ One-time-pad doesn't imply xor, for ElGamal the operation is multiplication. I don't use $\mathbb{Z}^*_p$ for DH (I use Ristretto255). Is this leak similar to point validation in ECC (where I know the KDF is necessary)? $\endgroup$ – cypherfox Mar 8 '20 at 9:31
-
2$\begingroup$ The issues have similarities. DH and ElGamal are secure when operating in an appropriate group of large prime order. Mapping things to that group requires care. When in $\Bbb Z^*_p$ (which has order $p-1$ thus is not prime), the DH shared secret is distinguishable from random in $[1,p)$, and accordingly ElGamal with messages in $[1,p)$, and XOR of message in $[0,2^{\lfloor\log_2(p)\rfloor})$ with shared key, both leak information about the plaintext. DH can be made secure with an extra key derivation. ElGamal can be made secure with restriction of the message to the group. $\endgroup$ – fgrieu♦ Mar 8 '20 at 10:51
-
1$\begingroup$ @fgrieu By restriction you mean the mapping of the message into the group? If so, that is part of the definition of ElGamal (or the definitions I use) and mentioned in my answer. $\endgroup$ – cypherfox Mar 8 '20 at 11:10
$\begingroup$
$\endgroup$
Diffie–Hellman is a method for key exchange, not encryption. Typically, you use it to determine a shared secret with your partner, then use that shared secret as a key (or to derive a key) for a symmetric encryption scheme, such as AES. The symmetric cryptosystem is what you use to transmit the actual message.
This two-step process of first exchanging keys, then sending the actual encrypted message, is known as a hybrid cryptosystem.
