3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The x-coordinate is usually bigger than the key needed and is not uniformly distributed. Using a KDF fixes this. $\endgroup$ – mikeazo Nov 6 '15 at 13:24
  • 3
    $\begingroup$ You get a stronger security proof if you hash the output, since that way you turn a computational Diffie-Hellman oracle into a decisional Diffie-Hellman oracle. $\endgroup$ – CodesInChaos Nov 6 '15 at 15:30
  • $\begingroup$ Sometimes the x-coordinate is smaller than the needed key bits. For instance, if you have a 256 bit curve and need two 256 bit keys , an encryption and a mac key, for a secure messaging channel. $\endgroup$ – user27950 Nov 6 '15 at 16:59
  • $\begingroup$ Is your goal to conceal prv, or to do DH or signatures with the result? $\endgroup$ – Squeamish Ossifrage Feb 22 at 22:07
  • $\begingroup$ @SqueamishOssifrage The protocol is ECDH. My goal is to conceal $prv$. But if you can have an adavantage on ECDH, without recovering $prv$, I would consider it. $\endgroup$ – Ruggero Feb 25 at 9:52
3
$\begingroup$

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.

    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$.

$\endgroup$
  • $\begingroup$ What do you think about Cheon's attack, better summarized at the end of section 4 of this survey ? $\endgroup$ – Ruggero Mar 20 at 9:17
  • $\begingroup$ @Ruggero An oracle for $Q \mapsto H([n]Q)$ doesn't help to carry out Cheon's attack, while an oracle for $Q \mapsto [n]Q$ does, by iterating it $d - 1$ times to compute $[n^{d - 1}]P = [n^d]B$ where $P = [n]B$ is the target public key, $B$ is the standard base point, and $d \mid \operatorname{ord} P-1$, as Cheon's attack needs—so that further justifies not working with $Q \mapsto [n]Q$ except via $H$? (It's not clear to me that Cheon's attack is an improvement over Pollard's rho in realistic cost models anyway, but even if it were, it seems like it would be thwarted by hashing the output.) $\endgroup$ – Squeamish Ossifrage Mar 20 at 15:06
  • $\begingroup$ That was my point. Hashing thwarts Cheon's attack. If you could add this point to the answer as an example of why hashing improves security over non hashing, I would accept it. Regarding costs, in the best scenario you do $ord(P)/4$ computation, but those computations are $nP$ not just add, but still worth it. $\endgroup$ – Ruggero Mar 21 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.