ECDH security when no KDF is used

Question

Let's suppose our device performs ECDH with a fixed, unknown, private key $\text{prv}$.

It accepts as input any point $Q$ lying in the proper subgroup of the proper elliptic curve, then computes: $P = \mathit{prv}*Q$ and outputs $P$.

An attacker who:

• has access to $P$
• can choose any valid $Q$ as input
• can call ECDH many times

can gain any information about the private key $\mathit{prv}$ ?

If not, then why a KDF is usually used on the x-coordinate of $P$ ?

Is it just to better distribute the possible outputs (since about half of possible x-coordinate won't be valid points on the curve) ?

NOTE: no smallgroups/invalid curve attacks or bad elliptic curves are considered here.

Answer 1

Maybe it doesn't help to recover the private key, but the private key is seldom the object of interest in a real application—instead, your private conversations, your money, etc., are the objects of interest. Hashing the points is important for security of the composition of ECDH with another cryptosystem. This is both for the benefit of the downstream cryptosystem, and for confidence in the DH security.

1. Standard encoding of uniform random curve points into bit strings is a bad way to get a uniform distribution on bit strings—so bad it was one of the first problems publicly reported about Dual_EC_DRBG in a comment by Gjøsteen[1] before everyone realized there was a back door.

   Maybe the related-key attacks of Biryukov and Khovratovich on AES-256[2] don't specifically apply to the encodings of points satisfying $y^2 = x^3 + a x + b$ on your curve, but it's more confidence-inspiring to choose a distribution on keys much closer to uniform with a better hash function like HKDF-SHA512—you don't have to think about possible interactions. For instance, what if you're using a curve over a binary field, and you use the key for a polynomial evaluation MAC over the same binary field?

2. Use of a standard hash function like SHAKE128 justifies using the standard argument of Bellare and Rogaway converting a decisional oracle into a computational oracle[3]. The cost of breaking the system can be studied by studying the costs of implementing the computational Diffie–Hellman problem of inverting $g^{x y}$ rather than the potentially easier decisional Diffie–Hellman problem of distinguishing $(g^x, g^y, g^{x y})$ from $(g^x, g^y, g^z)$ for uniform random $x, y, z$.

   Maybe you don't believe in the random oracle model, but it is hard to imagine that the hashing step—whose cost is negligible compared to the elliptic curve scalar multiplication you just performed—could make the attacker's job easier; this argument suggests that it generally makes the attacker's job much harder.

   E.g., Cheon's attack[4][5] (paywall-free) computes the secret exponent $x$ given $g, g^x, g^{x^2}, \dots, g^{x^d}$ in $O(\sqrt{p/d} + \sqrt d)$ group operations where $p$ is the order of $g$ and $d \mid p - 1$, or $O(\sqrt{p/d} + d)$ group operations if $d \mid p + 1$. An oracle for $h \mapsto h^x$ can be used to find these powers of $g$ by iterating it, while an oracle for $h \mapsto H(h^x)$ cannot. Thus, hashing is sufficient to mitigate Cheon's attack.

   Consequently, the security conjecture of X25519 by Bernstein[6], for example, is that an adversary who knows everyone's public key $\operatorname{X25519}(n_1, 9), \operatorname{X25519}(n_2, 9), \dots$, and has oracles for $q \mapsto H(\operatorname{X25519}(n_i, q))$, can't do much better to generically break cryptosystems downstream of $H(\operatorname{X25519}(n_i, \operatorname{X25519}(n_j, 9)))$ than paying for the energy to compute $2^{125}$ curve additions needed by Pollard's $\rho$.