Subject: [Cfrg] Prime order + twisty DH benefit (theoretical)

From: Dan Brown <[email-masked]>
Date: Mon, 21 Jul 2014 21:09:50 +0000

‎Sorry, if the following has been discussed previously. Curve25519 has cofactor 8 because it uses a different shape curve.

If cofactor multiplication DH is used, this gives the shared secrets about 3 bits of information theoretical bias. Of course, the kdf etc should hide that bias just fine, but it would be theoretically simpler to have a shared secret with potentially no bias, eg prime order for both curve and twist.

Best regards, 

-- Dan

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 21 Jul 2014 16:05:13 -0700

Dan, this doesn’t seem right.  The shared secret on an ordinary curve has at least one bit of information, because not every value in the field is the x-coordinate of a point.  Even if the input can be either on the twist or the curve, so that every x-coordinate can come out (not the case in current NIST curves), the adversary can see whether the shared secret is on the curve or the twist.

Amplifying this to 4 bits of information isn’t going to change much.

So you can’t get to no bias, unless you do a completely unwarranted hack involving Elligator.

So you should use a KDF no matter what, and the KDF must be able to hide the small amount of bias.

Is your argument that people who use Curve25519 with no KDF are slightly more edgy than people who use NISTp256 ECDH with no KDF?  In this case, you should add another bit, because the high bit out of Curve25519 is always clear.  This is more serious than the cofactor.  But I still don’t think this is a good argument.

Cheers,
— Mike

On Jul 21, 2014, at 2:09 PM, Dan Brown <[email-masked]> wrote:

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