Re: [Cfrg] Twist security question

[Robert Ransom <[e-mail]>]

On 7/21/14, Michael Hamburg <[e-mail]> 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