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

Dan Brown <dbrown@certicom.com> Mon, 21 July 2014 23:19 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B8DD51A00E5 for <cfrg@ietfa.amsl.com>; Mon, 21 Jul 2014 16:19:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Yc2N2yaPpIxp for <cfrg@ietfa.amsl.com>; Mon, 21 Jul 2014 16:19:44 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id D76471A0085 for <cfrg@irtf.org>; Mon, 21 Jul 2014 16:19:43 -0700 (PDT)
Received: from xct106cnc.rim.net ([10.65.161.206]) by mhs211cnc.rim.net with ESMTP/TLS/AES128-SHA; 21 Jul 2014 19:19:28 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT106CNC.rim.net ([fe80::d824:6c98:60dc:3918%16]) with mapi id 14.03.0174.001; Mon, 21 Jul 2014 19:19:27 -0400
From: Dan Brown <dbrown@certicom.com>
To: Michael Hamburg <mike@shiftleft.org>
Thread-Topic: [Cfrg] Prime order + twisty DH benefit (theoretical)
Thread-Index: Ac+lOjcrKLQiRF9VS3ietodFNgImmA==
Date: Mon, 21 Jul 2014 23:19:27 +0000
Message-ID: <20140721231901.6656149.47385.16948@certicom.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="===============0478696127=="
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/pBCRoignGEc58AdCPr6wzcrsVyg
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Prime order + twisty DH benefit (theoretical)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=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
Cc: cfrg@irtf.org
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.

Cheers,
— Mike

On Jul 21, 2014, at 2:09 PM, Dan Brown <dbrown@certicom.com> 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
Cfrg@irtf.org
http://www.irtf.org/mailman/listinfo/cfrg