Re: [Cfrg] Twist security question

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 <dbrown@certicom.com> wrote:

> 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.
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg