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

[David Jacobson <[e-mail]>]

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
> [e-mail]
> 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