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