Subject: [Cfrg] Twist security question

From: Dan Brown <[email-masked]>
Date: Mon, 21 Jul 2014 17:07:05 +0000

Since Curve25519 DH protocol lets info about private key out via the twist (then kdf, mac and cipher), it seems to require an extra computational assumption, right? 

Probably this has been considered before. Maybe there's a reduction to a standard problem, or a generic group model proof, at least, which ought to be easy.

Best regards, 

-- Dan

PS N. Smart's comments about twist security got me thinking about this.

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 21 Jul 2014 10:35:47 -0700

Yeah, I’ve wondered about that too.  If you give the attacker the point on the twist, it probably gives away information in E(F^2) as well which she wouldn't obtain otherwise.  But in Curve25519 you hash the point, and in the random oracle the attack is going to be really weak.

The attacker supplies a point P on the twist, and gets (information derived from) the hash of some other point Q on the twist.  She can’t force Q into a subgroup other than {identity} or the whole q-torsion.  She can’t guess Q if it’s in the q-torsion.  So it seems she can’t learn anything from that hash.  Likewise, she can’t predict anything about the hash (except whether it’s H(identity)), so she can’t attack the rest of the protocol with it.

In the ROM there's not even an attack through discrete log or CDH on the twist, because no honest party ever outputs a point on the twist.

This isn’t a rigorous argument, though, because I don’t see an obvious proof that the attacker can’t narrow down Q on the twist.  That is, maybe she can figure out that your public key corresponds to at most a million “twist-public-keys” G_twist^secret, and then figure out which one by sending G_twist.

But it seems that the attacker cannot learn anything at all in the ROM without solving a sort of twisting problem:
Given (G, G^x) on the curve where x is in some big set (the Curve25519 public key set is weird),
And some sort of fixed-DDH oracle on the curve, because she can interact with the real protocol,
Find points (H, H^x) with order q on the twist with non-negligible probability.

Cheers,
— Mike

On Jul 21, 2014, at 10:07 AM, Dan Brown <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Robert Ransom <[email-masked]>
Date: Mon, 21 Jul 2014 10:51:36 -0700

On 7/21/14, Michael Hamburg <[email-masked]> wrote:
> Yeah, I’ve wondered about that too.  If you give the attacker the point on
> the twist, it probably gives away information in E(F^2) as well which she
> wouldn't obtain otherwise.  But in Curve25519 you hash the point, and in the
> random oracle the attack is going to be really weak.
>
> The attacker supplies a point P on the twist, and gets (information derived
> from) the hash of some other point Q on the twist.  She can’t force Q into a
> subgroup other than {identity} or the whole q-torsion.  She can’t guess Q if
> it’s in the q-torsion.  So it seems she can’t learn anything from that hash.
>  Likewise, she can’t predict anything about the hash (except whether it’s
> H(identity)), so she can’t attack the rest of the protocol with it.

This does leak whether the honest party is using a Montgomery-ladder
implementation or an implementation which decompresses to Edwards form
on only one of the curves, which is relevant to anonymity systems.

> In the ROM there's not even an attack through discrete log or CDH on the
> twist, because no honest party ever outputs a point on the twist.

Is there any useful attack against systems which use Möller's
curve-or-twist trick for generating ciphertexts indistinguishable from
uniform?

Is there any useful attack against the obvious variant of Möller's
technique where a single scalar is used on both the curve and the
twist?  (I didn't realize that Möller had specified to use independent
scalars until the Elligator paper pointed it out.)

If those systems are not vulnerable to any useful attack (and they
certainly should be secure), then Curve25519 is clearly safe too.

Robert Ransom