Score:3

Is it safe to reveal an arbitrary EC point multiplied by a secret key?

jp flag

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.

Maarten Bodewes avatar
in flag
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.
jp flag
@MaartenBodewes: normally in DH the peer has no incentives to extract your nonce.
fgrieu avatar
ng flag
@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.
jp flag
@fgrieu: Yes and Yes. So the adversary can easily calculate `(d^n)G` for arbitrary power `n`. What difference does it make? Does this enable the adversary to extract any information about the key?
fgrieu avatar
ng flag
@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](https://doi.org/10.1007/11761679_1)), 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.
jp flag
@MaartenBodewes: yes, but depends on what you mean by "broken". AFAIK DH's primary purpose is not about protecting the secret key, it's about deducing a shared secret with a cooperating party over a public communication channel, right?
Maarten Bodewes avatar
in flag
Could we please use "(ephemeral / static) private key instead of "nonce" or "secret key"? Those terms muddle the water. While we are at it, the result is a "shared secret" indeed, or derived "secret key"s after using a KDF. For *static* DH of course all about protecting private keys. If you have the private key you would also leak the shared secret, for one, as the public keys (or public key points) should be considered public. If it is also used for authentication of one party - as common in ephemeral-static DH - then leaking the static private key destroys that authenticity.
jp flag
@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.
fgrieu avatar
ng flag
@valdo: you will be interested in the info [there](https://chat.stackexchange.com/transcript/message/59152377#59152377) (and in it's [linked material](https://mailarchive.ietf.org/arch/msg/cfrg/YDVS5Trpr6suig_VCFEOH6SOn8Q/)). I get it mostly confirms what I was suspecting above, but I'm too far from my comfort zone to write an answer.
Score:2
kr flag

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.

fgrieu avatar
ng flag
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.
jp flag
@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.
jp flag
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 (k*G). Recently we decided to allow it to get (k*P), 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.
fgrieu avatar
ng flag
@valdo: I get that. Although you might have only recently seen [my comment above](https://crypto.stackexchange.com/posts/comments/206590), it's an old one, predating [this one you did](https://crypto.stackexchange.com/posts/comments/206603) clarifying the number of queries an adversary can make.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.