3
$\begingroup$

We have a primary-order EC group. Need to perform a (sort-of) DH protocol, whereas the key is permanent, not a nonce (single-usage ephemeral key).

So we receive an arbitrary group element (EC point) from an untrusted party, and reveal it multiplied by the secret key.

Is it always safe to do that? I mean, can the attacker craft the EC point in some manner to extract some info about the key? We ensure that the EC point is indeed on the curve, and, as I mentioned, it's a primary-order group.

$\endgroup$
9
  • 1
    $\begingroup$ I think you can deduce this from the fact that ephemeral-static DH would be extremely broken if this wasn't the case. If I remember correctly there is no other check on the ephemeral public key other than that it is on the curve. $\endgroup$
    – Maarten Bodewes
    Sep 14 at 9:59
  • $\begingroup$ @MaartenBodewes: normally in DH the peer has no incentives to extract your nonce. $\endgroup$
    – valdo
    Sep 14 at 10:39
  • $\begingroup$ @valdo: Your description lacks two important details: would adversaries be able to perform many (say $2^{24}$) queries? And would these be iterated queries, or not? That makes a difference, because $k$ iterated queries let one compute $(d^{k+1})\,G$ where $d$ is a private key and $d\,G$ is a known public key, whereas $k\ge1$ pre-established queries would allow to compute $(d^2)\,G$ but not $(d^j)\,G$ for $j\ge3$ regardless of $k$. Independently: if the result of DH (before key derivation function) became public, then adversaries in ephemeral DH would be about in the position you describe. $\endgroup$
    – fgrieu
    Sep 14 at 11:55
  • 2
    $\begingroup$ @valdo: if $k$ divides $p-1$ and the adversary has $G, d\,G, (d^k)\,G$, then according to my reading of the summary of Jung Hee Cheon's Security Analysis of the Strong Diffie-Hellman Problem (in proceedings of Eurocrypt 2006), there's an attack $\sqrt k$ times faster than Baby Step/Giant Step to recover $d$. As in the summary the attack requires impractically much memory, but so does BSGS, yet collision search solves that, and allows distribution; so it could get practical. Note: I should not get the credit for coming with this idea for this question. $\endgroup$
    – fgrieu
    Sep 14 at 15:39
  • 1
    $\begingroup$ @fgrieu: thanks a lot! This is an excellent point. Good to know. I believe in my particular case this is still fine. Practically the adversary can invoke this protocol several millions of times, perhaps even billions, but not trillions. We're talking about p order of 2^256. So the complexity of the attack is reduced by like 30/2 = 15 bits. from 128 bits to something like 113 bits. Still good enough for our particular case. $\endgroup$
    – valdo
    Sep 14 at 16:12
2
$\begingroup$

Assuming that by “primary order” you mean “prime order”, this is called the static Diffie-Hellman problem, and there are some known attacks against it. The main ones to consider off the top of my head would be:

  • the Cheon DLP with auxiliary inputs attack: there are several variants, but for example if the prime order $p$ of your elliptic curves satisfies that $d$ is a divisor of $p-1$, then an attacker making many queries can solve the discrete log problem in time $\widetilde{O}(\sqrt{p/d} + \sqrt{d})$, which in the worst case $d = \Theta(p^{1/2})$ is $\widetilde{O}(p^{1/4})$. This could be pretty bad in principle, but there are various reasons why the attack is not extremely threatening in this setting. Firstly, due to the attack's memory requirements and the fact most values of $p$ would be fairly far from the worst case, it's likely to be hard to mount in practice in most scenarios. Secondly, if $\alpha$ is the secret key, the attacker needs to somehow obtain both $\alpha G$ and $\alpha^d G$ for $G$ the group generator, and the only way to do so seems to be $d$ sequential adaptive queries $G \to \alpha G \to \alpha^2 G \to \cdots \to \alpha^d G$. This is a lot to expect from the oracle, and since it takes time $O(d)$, this reduces the optimal $d$ to $\Theta(p^{1/3})$ and increases the resulting complexity to $\widetilde{O}(p^{1/3})$ (assuming again that $p-1$ has the required form). There aren't many settings in which the oracle would answer $2^{85}$ queries from the adversary. This is why the Cheon attack is usually more relevant in settings where group elements of the form $\alpha^j G$ are readily available as public key material, rather than obtained using sequential queries;

  • the Granger extension field attack if you happen to be using curves over extension fields of degree $\geq 3$ (which is most likely not the case).


Thanks to @fgrieu for correctly pointing out that several comments I made about this were incorrect, and also pointing to relevant discussions on an IETF mailing list.

$\endgroup$
4
  • 1
    $\begingroup$ I don't see why the Cheon attack that you mention would not work to a degree, when the question uses iterated queries, and $p-1$ has a moderate prime factor. $\endgroup$
    – fgrieu
    Sep 14 at 11:58
  • $\begingroup$ @fgrieu: in my particular case excessive number of queries is not very practical. As I said, the upper bound of number of queries is order of a million. $\endgroup$
    – valdo
    Sep 19 at 10:09
  • $\begingroup$ P.S. to be concrete: we have an application that calls a "plugin". This plugin can't have direct access to a key, but we allow it to get its image (kG). Recently we decided to allow it to get (kP), whereas P is an arbitrary group element. The plugin runtime is limited (i.e. it can't run days). The user can extract any info anyway if he/she wants. So it's about protecting a user against a malicious plugin. $\endgroup$
    – valdo
    Sep 19 at 10:13
  • 1
    $\begingroup$ @valdo: I get that. Although you might have only recently seen my comment above, it's an old one, predating this one you did clarifying the number of queries an adversary can make. $\endgroup$
    – fgrieu
    Sep 19 at 10:30

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.