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

David Jacobson <dmjacobson@sbcglobal.net> Thu, 23 August 2012 05:17 UTC

Return-Path: <dmjacobson@sbcglobal.net>

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 469B021F8470 for <cfrg@ietfa.amsl.com>;
Wed, 22 Aug 2012 22:17:44 -0700 (PDT)

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

X-Spam-Flag: NO

X-Spam-Score: -0.74

X-Spam-Level:

X-Spam-Status: No,
score=-0.74 tagged_above=-999 required=5 tests=[BAYES_20=-0.74]

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 6PFD605VO08V for
<cfrg@ietfa.amsl.com>; Wed, 22 Aug 2012 22:17:43 -0700 (PDT)

Received: from nm22-vm4.bullet.mail.ne1.yahoo.com
(nm22-vm4.bullet.mail.ne1.yahoo.com [98.138.91.182]) by ietfa.amsl.com
(Postfix) with SMTP id 719BC21F8471 for <cfrg@irtf.org>;
Wed, 22 Aug 2012 22:17:42 -0700 (PDT)

Received: from [98.138.90.54] by nm22.bullet.mail.ne1.yahoo.com with NNFMP;
23 Aug 2012 05:17:39 -0000

Received: from [209.191.108.96] by tm7.bullet.mail.ne1.yahoo.com with NNFMP;
23 Aug 2012 05:17:39 -0000

Received: from [66.94.237.116] by t3.bullet.mud.yahoo.com with NNFMP;
23 Aug 2012 05:17:39 -0000

Received: from [127.0.0.1] by omp1021.access.mail.mud.yahoo.com with NNFMP;
23 Aug 2012 05:17:39 -0000

X-Yahoo-Newman-Id: 595923.10127.bm@omp1021.access.mail.mud.yahoo.com

Received: (qmail 60069 invoked from network); 23 Aug 2012 05:17:39 -0000

DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=sbcglobal.net;
h=DKIM-Signature:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
b=icGVbA9mCf7OfJfl5l5hLw+cLpR9hyWPtf1SSqzCtup+0E1j7ccPVc2m2i1iAOKwsisFZ8xvQjBJg5oCkdsOf6rmmZNXAiSnq8aXeZz9c+C9NESHFcCy/M7TRTbDtJ/RjZHpHDC1mL6KI4e6T/deJZ3Al1VH3WbP67+UXNNI1nM=
;

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024;
t=1345699059; bh=57BnRH57dpPT3Oc1DxayLYUiANp7JWcn7WLZivYNaWU=;
h=X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding;
b=6ngj7xcijRLaNr4m6xikBQpJcH1dwfP60RMju9kL+IcCKNG0tX+KjBX0d72/KG1HdCWSu4zEhitnpOmROMNk6lm+1y5ZpuWV+AJY5YzjV4aoni56P/YOtWdjz3romZO74OniQ4Lspye/lGjY1ts7zCFDszyld8w03E+q5jeJ5vI=

X-Yahoo-Newman-Property: ymail-3

X-YMail-OSG: evCRO00VM1nfQBf1kDA4L9OkwRV_v1eoW9m2PctAv0.LZV1
ZWxr9fiWIxOj1yDPIrEJBoy95fWYwdVEMak5zGgiCfPyUa8sXeGJisTozKIF
ii57mtA0hb58pWzcCTkk4VTH3aLmpzJ2N.n40KNgqbEdzmpCqU2nY5ey52mC
FjDkyQBCOAaLiPhU1EVHBlAAMJmjDrXvSICYicYLtamq.2g4Kc74QU9zcwb4
cooMjZIHSnEjKz2ov3n29Obp.8dr_yHaGjdGsfUw_ayL4lE4MZEjMmGTxJxj
JNbSUt7TcF8kOPeKmpiQofxbqEirFdBU4vzlWsKAff0LY_Pbw3DDJEhsPKFi
KD12N1.g1C9X2T1SwAJtlMsNK_uOUvhUJyujwUyWKnmenH7W8X_NsjeZlm07
bzDawDhS6zVCUGGdJBHh9sS0s2Z9DgCreC8Q3czYs2rzMFqiNHdUCCLPp68K yiTeUUbBqHQ--

X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--

Received: from [192.168.1.73] (dmjacobson@99.120.98.171 with plain) by
smtp108.sbc.mail.mud.yahoo.com with SMTP; 22 Aug 2012 22:17:39 -0700 PDT

Message-ID: <5035BCF1.9030903@sbcglobal.net>

Date: Wed, 22 Aug 2012 22:17:37 -0700

From: David Jacobson <dmjacobson@sbcglobal.net>

User-Agent: Mozilla/5.0 (X11; Linux i686;
rv:14.0) Gecko/20120714 Thunderbird/14.0

MIME-Version: 1.0

To: cfrg@irtf.org

References: <502A928A.7090003@htt-consult.com>
<def0111a5e81f715d26eb4a6c426295e.squirrel@www.trepanning.net>

In-Reply-To: <def0111a5e81f715d26eb4a6c426295e.squirrel@www.trepanning.net>

Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Content-Transfer-Encoding: 7bit

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 05:17:44 -0000

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] 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