### Re: [Cfrg] uniform random distribution in ECDH public key

Dan Brown <dbrown@certicom.com> Thu, 23 August 2012 12:28 UTC

Return-Path: <prvs=05829ebb01=dbrown@certicom.com>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A3B5C21F8491 for <cfrg@ietfa.amsl.com>; Thu, 23 Aug 2012 05:28:02 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -5.184

X-Spam-Level:

X-Spam-Status: No, score=-5.184 tagged_above=-999 required=5 tests=[AWL=0.019, BAYES_00=-2.599, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4]

Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id NoB+J6CW+IyP for <cfrg@ietfa.amsl.com>; Thu, 23 Aug 2012 05:28:01 -0700 (PDT)

Received: from mhs061cnc.rim.net (mhs061cnc.rim.net [208.65.73.35]) by ietfa.amsl.com (Postfix) with ESMTP id 9F45B21F8470 for <cfrg@irtf.org>; Thu, 23 Aug 2012 05:28:01 -0700 (PDT)

X-AuditID: 0a412830-b7f996d000004398-89-503621d0e0e1

Received: from XCT102CNC.rim.net (xct102cnc.rim.net [10.65.161.202]) (using TLS with cipher AES128-SHA (AES128-SHA/128 bits)) (Client did not present a certificate) by mhs061cnc.rim.net (SBG) with SMTP id 33.D9.17304.0D126305; Thu, 23 Aug 2012 12:28:00 +0000 (GMT)

Received: from XCT114CNC.rim.net (10.65.161.214) by XCT102CNC.rim.net (10.65.161.202) with Microsoft SMTP Server (TLS) id 14.2.298.4; Thu, 23 Aug 2012 08:27:59 -0400

Received: from XMB111CNC.rim.net ([fe80::fcd6:cc6c:9e0b:25bc]) by XCT114CNC.rim.net ([::1]) with mapi id 14.02.0298.004; Thu, 23 Aug 2012 08:27:59 -0400

From: Dan Brown <dbrown@certicom.com>

To: "dmjacobson@sbcglobal.net" <dmjacobson@sbcglobal.net>, "cfrg@irtf.org" <cfrg@irtf.org>

Thread-Topic: [Cfrg] uniform random distribution in ECDH public key

Thread-Index: AQHNekb3xzJbLzv3CU6oe+qYCRXyhpdZ4i+AgA1JiYCAADUvFg==

Date: Thu, 23 Aug 2012 12:27:58 +0000

Message-ID: <810C31990B57ED40B2062BA10D43FBF50B2B38@XMB111CNC.rim.net>

In-Reply-To: <5035BCF1.9030903@sbcglobal.net>

Accept-Language: en-CA, en-US

Content-Language: en-US

X-MS-Has-Attach:

X-MS-TNEF-Correlator:

x-originating-ip: [10.65.160.246]

Content-Type: text/plain; charset="iso-8859-1"

content-transfer-encoding: quoted-printable

MIME-Version: 1.0

X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrMKsWRmVeSWpSXmKPExsXC5bjwlO4FRbMAgz2zpSy6fxxksmg6tpnd gclj8sbDbB7r/y9mDWCKamC0SUosKQvOTM/Tt7NJzMvLL0ksSVVISS1OtlXySU1PzFEIKMos S0yuVHDJLE7OSczMTS1SUshMsVUyUVIoyElMTs1NzSuxVUosKEjNS1Gy41LAADZAZZl5Cql5 yfkpmXnptkqewf66FhamlrqGSna6CZ08GU93rmMt6JCtuDC5k7mBsUu8i5GTQ0LAROLl0XVM ELaYxIV769m6GLk4hAT6mCRmzn/MBOGsZJT4+Hc1VGYOo0TzvAnMIC1sAqoS94+eA7I5OEQE YiR+LUsFCQsLOEn8/jqNBcQWEXCW2Nf/jAnCdpL427OMFaScBaj1+YMEEJNXwE1i3/oskApO AV2J3TfPsoLYjAKyErvPXgfrZBYQl7j1ZD7UnQISS/acZ4awRSVePv7HCmErSjw5eY0Fol5P 4sbUKWwQtrbEsoWvwep5BQQlTs58AlYjJKAgceX6PpYJjGKzkKyYhaR9FpL2WUjaFzCyrGIU zM0oNjAzTM5L1ivKzNXLSy3ZxAhOEhoGOxjfv7c4xCjAwajEw/uY1SxAiDWxrLgy9xCjBAez kgivFydQiDclsbIqtSg/vqg0J7X4EKMFMEwmMktxJ+cDE1heSbyxgQEKR0mcl8nDKEBIIB2Y eLJTUwtSi2BamTg4QUZzSYkUA9NHalFiaUlGPCjJxRcD05xUA2PdZYe115LZ59xkkglUX5p5 8P5s3g1VO7Ue+s/39Nukb27yeNH+qxeld96LMvf+z5/61/FB+0Mhlw/Pr57KLDtoKWQyIX/N i33JodM4F1fNP73PgrFTP3mp/+wzPo99eFj0PQ4w6s/q2Jrx+NakHc/TLtZNauO24MhKdTzh rSDYzj75i+095T1KLMUZiYZazEXFiQA7kRBxRgMAAA==

Subject: Re: [Cfrg] uniform random distribution in ECDH public key

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.12

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: Thu, 23 Aug 2012 12:28:02 -0000

One general advantage: after hashing the shared secret is pseudorandom. It has less entropy but it is harder to distinguish from a uniformly random bit string. This may matter if one just wanted to use the key to pad a message. This does not really matter for AES, but the ECDH standards don't specify how the key is, so have to be general. A second advantage, nonces and identifiers can be thrown into the hash input, for various gains, such as generating several keys, one for AES and for HMAC. A third advantage, if the shared key is later revealed, then the hash prevents the calculation of the raw ECDH value, which is harmful mostly in the case where one public key is static: it allows the adversary to do replay, invalid curve attacks, and Cheon-type attacks. ----- Original Message ----- From: David Jacobson [mailto:dmjacobson@sbcglobal.net] Sent: Thursday, August 23, 2012 01:17 AM To: cfrg@irtf.org <cfrg@irtf.org> Subject: Re: [Cfrg] uniform random distribution in ECDH public key On 08/14/2012 11:23 AM, Dan Harkins wrote: > Hi Bob, > > On Tue, August 14, 2012 11:01 am, Robert Moskowitz wrote: >> I understand from RFC 6090 and 5869 that the secret key produced from an >> ECDH exchange is not uniformly randomly distributed and that is why we >> have the 'Extract' phase in HKDF. Got that. >> >> This question is about the public key, g^j: >> >> I understand that like j, it must be a point on the curve, thus if the >> curve is p-256, both j and g^j are 256 bits long. But is g^j uniformly >> randomly distributed like j is suppose to be? > No, it's not. It's it's a special pair (x,y) that satisfy the equation > of the > curve: y^2 = x^3 + ax + b. Not all pairs will satisfy that equation. I > believe about half of them will and about half won't. > > For x to be random, each number between 0 and p would have equal > probability. But that's not the case since about half won't. > >> Side question: I am still unclear on the length of the exchanged secret >> (g^j)^k, is it 256 bits (for p-256) or larger (perhaps 512 bits)? > The result of an ECDH is an element in the group so it's also an (x,y) > pair but the secret that you use in your KDF is the x coordinate of that > result. The y coordinate is discarded. > > regards, > > Dan. > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > So now that we are into tutorial mode on this, I'd like to ask a question. Standard procedure for Diffie-Hellman key exchange is to construct the session key from the X-coordinate by hashing. Now suppose that I'm using the NIST P-256 curve and the symmetric encryption functions is AES-256. The number of possible shared key values is the order of the curve - 1 (point at infinity isn't used), which is extremely close to 2^256. These points come in pairs, if there is a point at an X value, there are 2, one at Y and the other -Y. So essentially all X values occur with probability very close to 2/2^256, which means that the X-coordinate after the DH procedure can be thought of as a source with 255 bits of min-entropy. If we hash the X coordinate with SHA-256, we actually lose a little bit of entropy, since some X values will collide and produce some session key with probability higher than 2/2^256, lowering the min-entropy. So what is the advantage of the hash operation? Thank you, --David Jacobson _______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg --------------------------------------------------------------------- This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

- [Cfrg] uniform random distribution in ECDH public… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… Scott Fluhrer (sfluhrer)
- Re: [Cfrg] uniform random distribution in ECDH pu… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… David McGrew (mcgrew)
- Re: [Cfrg] uniform random distribution in ECDH pu… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… Robert Moskowitz
- Re: [Cfrg] uniform random distribution in ECDH pu… Vadym Fedyukovych
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Harkins
- Re: [Cfrg] uniform random distribution in ECDH pu… David Jacobson
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Brown
- Re: [Cfrg] uniform random distribution in ECDH pu… Blumenthal, Uri - 0668 - MITLL
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Brown
- Re: [Cfrg] uniform random distribution in ECDH pu… Blumenthal, Uri - 0668 - MITLL
- Re: [Cfrg] uniform random distribution in ECDH pu… Dan Brown
- Re: [Cfrg] uniform random distribution in ECDH pu… David Jacobson