Security model scalar multiplication in NaCl

Question

I'm having trouble understanding what the “security model” for “scalar multiplication” in NaCl is.

Security model

crypto_scalarmult is designed to be strong as a component of various well-known "hashed Diffie–Hellman" applications. In particular, it is designed to make the "computational Diffie–Hellman" problem (CDH) difficult with respect to the standard base.

crypto_scalarmult is also designed to make CDH difficult with respect to other nontrivial bases. In particular, if a represented group element has small order, then it is annihilated by all represented scalars. This feature allows protocols to avoid validating membership in the subgroup generated by the standard base.

NaCl does not make any promises regarding the "decisional Diffie–Hellman" problem (DDH), the "static Diffie–Hellman" problem (SDH), etc. Users are responsible for hashing group elements.

Since “crypto_scalarmult is the function crypto_scalarmult_curve25519”, does this mean that Curve25519 does not provide any guarantees for the DDH problem to be hard?

If so, how can one—as suggested—hash group elements to achieve this? E.g., how does one implement elliptic curve El-Gamal in a semantically secure way using this implementation, if possible at all?

Answer 1

Since "crypto_scalarmult is the function crypto_scalarmult_curve25519", does this mean that Curve25519 does not provide any guarantees for the DDH problem to be hard?

No, it just means, that the NaCl specification or API, which is different from the NaCl implementation / library, makes no guarantees about the DDH problem being hard in the group being used. The implementation however may of course go beyond what is guaranteed by the API and use a group where DDH is hard, such as Curve25519.

If so, how can one hash group elements to achieve this?

The output of the crypto_scalarmult function essentially is a chunk of bytes. You can then use your favorite hash function (e.g. SHA-3-256 or SHA-256) or preferably your favorite key-based key derivation function (KBKDF) (e.g. HKDF) to derive symmetric key material for bulk encryption.

How does one implement elliptic curve El-Gamal using this implementation, if possible at all?

ElGamal requires the message to be represented as a group element which is not trivially possible to do in an (easily) invertible way and thus I strongly discourage anyone from using EC-Elgamal and instead use ECIES.

However you asked and I shall answer (using the notation from the HAC (PDF)):
Let $\alpha$ be your generator of the (sub)group. Let $\beta$ be your recipient's public key and $a$ be his private key. $\beta$ can be generated from $\alpha$ as $\alpha^a=\beta$, which maps 1-to-1 to a call to crypto_scalarmult.

For encryption you then pick a random $k$ which is smaller than the group's order and compute $\beta^k$ and $\gamma=\alpha^k$ which both can be done by single calls to crypto_scalarmult and then you compute $\delta=m\cdot(\beta^k)$, e.g. you apply the group operation to $m$ and the buffered $\beta^k$. Your ciphertext of the plaintext $m$ is now $(\gamma,\delta)$.

Decryption is even easier, you compute $\gamma^{q-a}$ where $q$ is the (sub)group's order and then perform a group operation using $\gamma^{q-a}$ and $\delta$, the result will be $m$.