Using Diffie–Hellman without a key derivation function

Question

In an answer to another question, it was suggested that the shared secret derived from Diffie–Hellman key exchange could then be used directly as a one-time pad to encrypt a message (by XORing the message with the shared secret after writing everything in binary). This forms a simple hybrid cryptosystem.

User fgrieu writes in the comments that this has a flaw, saying:

"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 sizeably better than random. There is a similar issue with ElGamal encryption. Problem is: in $\mathbb 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.

Recall that the Legendre symbol determines whether an element of a group is a quadratic residue.

Could we fix this by choosing an element $g$ that generates a large subgroup, all of whose elements are quadratic residues? Concretely, we could take $p= 2q + 1$ for a large prime $p$ and then find an element which generates the order $q$ subgroup.

Now, if Diffie–Hellman is done with this group element, any eavesdropper knows the lowest order bit of the shared secret. So I could just remove this bit and use all the higher order bits as the one-time pad, and no information about the shared secret leaks.

Is this scheme secure, assuming an eavesdropper can't break Diffie–Hellman? Even if the particular flaw fgrieu points out is fixed by this scheme, are there other compelling reasons to combine Diffie–Hellman with a key derivation function?

The Wikipedia page for Diffie–Hellman notes that IKEv2 chooses the public group element this way. However, they do not say whether a further key derivation function is applied.

Answer 1

Could we fix this by choosing an element $g$ that generates a large subgroup (of $\Bbb Z_p^*\ $), all of whose elements are quadratic residues? Concretely, we could take $p=2q+1$ for a large prime $p$ and then find an element which generates the order $q$ subgroup.

Now, if Diffie–Hellman is done with this group element, any eavesdropper knows the lowest order bit of the shared secret. So I could just remove this bit and use all the higher order bits as the one-time pad, and no information about the shared secret leaks.

That's not safe. Problems:

• What the adversary learns is not the low-order bit of the Diffie-Hellman shared secret $a$ as stated. Rather, what leaks is the Legendre symbol $\bigl(\frac ap\bigr)=a^q\bmod p$, which is always $+1$. Therefore, even if we remove the low-order bit, the adversary still learns something about the shared secret, and that's an advantage.
  E.g. with $p=23$, $q=11$, $g=3=7^2\bmod p$, the adversary knows that $a$ is among the powers of $g$ modulo $p$, that is $a\in\{3,9,4,12,13,16,2,6,18,8,1\}$ (which low-order bits are rather haphazard). Thus for example if the ciphertext is $101_2$, the adversary can tell that the plaintext can not be $000_2$, because that would imply that $\lfloor a/2\rfloor=000_2\oplus101_2=101_2=5$ thus that $a\in\{10,11\}$, which can't be since $\bigl(\frac{10}p\bigr)=10^q\bmod p\ne+1$ and $\bigl(\frac{11}p\bigr)=11^q\bmod p\ne+1$.
  That attack also works for large $p$ and in practical scenarios. E.g. if a name on the class roll was enciphered, then at the cost of two Legendre symbol computations per name on the class roll (one for each of the two possible DH shared secrets), an adversary likely could rule out with certainty about a quarter of the names (those with two negative results), and find another quarter (those with two positive results) among which the actual name is more likely to be than for the remaining of the class roll.
• The high-order bit of $a$ expressed as a fixed-length bitstring of $\lceil\log_2(p)\rceil$ bits is not well distributed.
• If $q$ has moderate prime factors, then I can't rule out that much more than one bit of information about the shared secret could leak due to the Pohlig-Hellman algorithm.

---

I conjecture that this variant is safe (ind-CPA):

• Pick $p$ a safe prime (that is $p=2q+1$ with $q$ prime), $p$ large (e.g. $4096$-bit), and not of the special form $r^e\pm s$ for small $r$ and $s$.
• Chose $g\in[2,p-2]$ such that $g^q\bmod p=1$, implying that $g$ is a generator of the subgroup of the quadratic residues of $\Bbb Z_p^*$, which has prime order $q$.
• Perform DH as usual, yielding shared secret $a$.
• Truncate $a$ to its e.g. $\lceil\log_2(p)\rceil-k$ low-order bits yielding $a'$, where $k$ is a security parameter (e.g. $k=128$, giving a $496$-byte $a'$).
• Use $a'$ for XOR-encryption of a plaintext at most as large as $a'$ (or best, devote some of $a'$ to provide integrity of the message using universal hashing à la Carter-Wegman).

Argument: DH's security hypothesis tells that $a$ is computationally indistinguishable from a uniformly random quadratic residue in $\Bbb Z_p^*$, since that has prime order. I conjecture that these quadratic residues are well-enough distributed on $\Bbb Z_p^*$ that $a'$ is computationally indistinguishable from uniformly random, with the advantage vanishing as $\mathcal O(2^{-k})$.

This is possibly the simplest academically correct way to perform ind-CPA public-key cryptography on a link spied by a passive adversary. But caution: this not commonly used. The accepted practice is to feed the DH shared secret $a$ thru a Key Derivation Function, or Pseudo Random Function / hash such as SHA-256, and use the outcome as a key for an authenticated symmetric cipher such as AEAD_AES_256_GCM_SIV of RFC 8452.