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

Dan Brown <> Mon, 21 July 2014 23:19 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B8DD51A00E5 for <>; Mon, 21 Jul 2014 16:19:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Yc2N2yaPpIxp for <>; Mon, 21 Jul 2014 16:19:44 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id D76471A0085 for <>; Mon, 21 Jul 2014 16:19:43 -0700 (PDT)
Received: from ([]) by with ESMTP/TLS/AES128-SHA; 21 Jul 2014 19:19:28 -0400
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::d824:6c98:60dc:3918%16]) with mapi id 14.03.0174.001; Mon, 21 Jul 2014 19:19:27 -0400
From: Dan Brown <>
To: Michael Hamburg <>
Thread-Topic: [Cfrg] Prime order + twisty DH benefit (theoretical)
Thread-Index: Ac+lOjcrKLQiRF9VS3ietodFNgImmA==
Date: Mon, 21 Jul 2014 23:19:27 +0000
Message-ID: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="===============0478696127=="
MIME-Version: 1.0
Cc: "" <>
Subject: Re: [Cfrg] Prime order + twisty DH benefit (theoretical)
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 21 Jul 2014 23:19:45 -0000

My mistake, sorry again. Thanks Mike for explaining that.

Wasn't really trying to compare p256 and 25519: was just trying to get best of both.

Best regards, 

-- Dan
From: Michael Hamburg
Sent: Monday, July 21, 2014 7:05 PM
To: Dan Brown
Subject: Re: [Cfrg] Prime order + twisty DH benefit (theoretical)

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.

— Mike

On Jul 21, 2014, at 2:09 PM, Dan Brown <> wrote:

‎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
Cfrg mailing list