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

From: Robert Moskowitz <[email-masked]>
Date: Tue, 14 Aug 2012 14:01:46 -0400

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?

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)?

Thank you for helping me get all this straight.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 14 Aug 2012 18:14:41 +0000

No, the value g^j (or jG, if we prefer the more traditional additive notation for elliptic curves) is not uniform; it is a 512 bit value (for P256), and corresponds to a point on the curve (that is, it is a pair of 256 bit values that together are a solution to a specific cubic equation).  There are approximately 2^256 possible values for this 512 bit value, and so there are a large number of 512 bit public values which are not possible.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Robert Moskowitz
Sent: Tuesday, August 14, 2012 2:02 PM
To: [email-masked]
Subject: [Cfrg] uniform random distribution in ECDH public key

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 14 Aug 2012 14:25:29 -0400

thank you. I was using the compact notation (x-coordinate only) for the 
256bit size with p-256. I should have said that.

On 08/14/2012 02:14 PM, Scott Fluhrer (sfluhrer) wrote:
> No, the value g^j (or jG,

And I am going by 6090. Sometimes I suspect the notation used there is 
to distance it from more 'modern' usages as appear in certain documents 
filed with a department of the US gov. But that is pure speculation.

>   if we prefer the more traditional additive notation for elliptic curves) is not uniform; it is a 512 bit value (for P256), and corresponds to a point on the curve (that is, it is a pair of 256 bit values that together are a solution to a specific cubic equation).  There are approximately 2^256 possible values for this 512 bit value, and so there are a large number of 512 bit public values which are not possible.

Is there any information of the distribution of jG?

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 14 Aug 2012 18:26:34 +0000

Hi Bob,

>randomly distributed like j is suppose to be?

Something quick to add to what Scott said.   Note that j is uniformly
random when considered as an integer between 1 and the group order; it is
not uniformly random when considered as a bit string.

David

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 14 Aug 2012 14:28:53 -0400

One more point.

> No, the value g^j (or jG, if we prefer the more traditional additive notation for elliptic curves) is not uniform; it is a 512 bit value (for P256), and corresponds to a point on the curve (that is…

So j is ALSO not uniformly randomly distributed, despite sec 4 in 6090 
stating:

"Party A chooses an exponent j between 1 and t-1, inclusive, uniformly 
at random"

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 14 Aug 2012 14:50:54 -0400

> not uniformly random when considered as a bit string.

AH! Important clearification.

But this means that on the curve, the possible points are uniform. I 
thought that they need to be prime values? I am getting more confused, I 
think, as I think about this!

---

From: Vadym Fedyukovych <[email-masked]>
Date: Tue, 14 Aug 2012 21:51:35 +0300

On Tue, Aug 14, 2012 at 02:01:46PM -0400, 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.

I'd say, shared secret produced by ECDH is "fixed" for two parties,
represented by their public keys.
HKDF (5869) would produce "per-application" keys then

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

g^j (or, in additive notation, jG) is distributed uniformly over non-trivial elements of the group,
on condition at least one of j or k (at section 4 of 6090) was chosen uniformly at random from integers 1 up to (group order -1).

"j" is not a point on the curve, but an index (logarithm) in the finite group

> 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)?

Depends on representation of the point on the curve.
Basically, two numbers (x- and y- coordinates) of 256 bits long.

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 14 Aug 2012 11:23:03 -0700 (PDT)

Hi Bob,

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

> (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.

---

From: David Jacobson <[email-masked]>
Date: Wed, 22 Aug 2012 22:17:37 -0700

> result. The y coordinate is discarded.
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

---

From: Dan Brown <[email-masked]>
Date: Thu, 23 Aug 2012 12:27:58 +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:[email-masked]]
Sent: Thursday, August 23, 2012 01:17 AM
To: [email-masked] <[email-masked]>
Subject: Re: [Cfrg] uniform random distribution in ECDH public key

Thank you,

     --David Jacobson

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

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Fri, 24 Aug 2012 13:12:16 -0400

On 8/23/12 8:27 , "Dan Brown" <[email-masked]> wrote:

>One general advantage: after hashing the shared secret is pseudorandom.

No it is not. Pseudorandomness of the output has not been a design
criteria of hash functions until the SHA3 competition.

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

That holds and helps, though (again, until SHA3 is selected and deployed)
it is hard to tell how well (or otherwise) these extra bits get
"intermixed" or spread over in the output value.

>A third advantage, if the shared key is later revealed, then the hash
>prevents the calculation of the raw ECDH value

That holds, and is a nice property to have.

>>>secret
>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.

---

From: Dan Brown <[email-masked]>
Date: Fri, 24 Aug 2012 18:34:28 +0000

Hi Uri,

Thanks for the response.  

Regarding your point about pseudorandomness: would you confirm that you merely mean that the SHA-1 and SHA-2 standards do not claim the functions to have "pseudorandom" (ignoring definability and provability see below *), and that you do not mean there is some kind of distinguisher of SHA-1 and SHA-2 (i.e. for non-contrived inputs, see **)?

If not, then please elaborate.  

If so, then I would add, that although the original standards for SHA-1 and SHA-2 did not make pseudorandomness claims, many others have gone ahead to make such claims (at least implicitly).  Such claims include: most random oracle proofs (if they use the term "hash function", which implicitly includes SHA-1 or SHA-2, unless the papers explicitly exclude them); standards RSA-OAEP and RSA-PSS; SHA-based KDF (the topic of this thread); HMAC-KDF (SP 800-56C); Hash-based DRBG and HMAC-DRBG in SP 800-90A.   These claims have created a large incentive to find distinguishability properties of SHA-1 and SHA-2.  

So now I clarify my original point in 2 ways: (1) the abundantly apparent pseudorandomness of SHA-1 (at least relevant pseudorandomness, see **), and of SHA-2, means that their use in the KDF is a definite general-purpose improvement over the easy distinguishability of the raw ECDH (or DH) shared secret, and (2) if one takes a much looser meaning of "hash" that includes easily-distinguishable hash functions, then hashing of the raw ECDH shared secret does add value.

(*) Definability and provability: it's hard (if not impossible) to even define general pseudorandomness of a general keyless function (and therefore to hard prove anything). In the context of KDFs, with fixed input lengths, or even when fixed input domains (e.g. an EC point), one may be able to at least define something: e.g. KDF(uniformly distributed EC point) -> (bit string computationally indistinguishable from uniformly distributed bit string).

(**) A contrived distinguisher would be to select inputs such that hash output has some bias, this is the main obstacle to defining pseudorandomness (see * above).  A distinguisher would need to be faster than a distinguisher for a random oracle.  I suppose that the SHA-1 collision algorithms can be viewed as a distinguisher, though not with any impact on most typical pseudorandom hash applications such as KDF.  Is there a more direct distinguisher for SHA-1 or SHA-2?

Daniel Brown
Research In Motion Limited

> From: Blumenthal, Uri - 0668 - MITLL [mailto:[email-masked]]
> Sent: Friday, August 24, 2012 1:12 PM
> To: Dan Brown; [email-masked]; [email-masked]

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Fri, 24 Aug 2012 14:46:28 -0400

>Regarding your point about pseudorandomness: would you confirm that you
>merely mean that the SHA-1 and SHA-2 standards do not claim the functions
>to have "pseudorandom" (ignoring definability and provability see below
>*),

"Merely"... The whole concept of "keyless" functions is interesting - by
the same token you can make "keyless DES" by fixing its key to X...

> and that you do not mean there is some kind of distinguisher of SHA-1
>and SHA-2 (i.e. for non-contrived inputs, see **)?

No, I am not aware of a distinguisher (and possibly if I knew about one I
might not be at liberty to disclose that :).

>If so, then I would add, that although the original standards for SHA-1
>and SHA-2 did not make pseudorandomness claims, many others have gone
>ahead to make such claims (at least implicitly).

And these claims are quite unsubstantiated, IMHO. Are we talking about
proofs, or conjectures that were spawned by engineers looking for
convenience?

>Such claims include: most random oracle proofs (if they use the term
>"hash function", which implicitly includes SHA-1 or SHA-2, unless the
>papers explicitly exclude them); standards RSA-OAEP and RSA-PSS;
>SHA-based KDF (the topic of this thread); HMAC-KDF (SP 800-56C);
>Hash-based DRBG and HMAC-DRBG in SP 800-90A.   These claims have created
>a large incentive to find distinguishability properties of SHA-1 and
>SHA-2.

I wonder then, with such great field use - why bother with SHA3 and why
bother including pseudorandomness into design requirements if the existing
hash functions are so good at it?

>So now I clarify my original point in 2 ways: (1) the abundantly apparent
>pseudorandomness of SHA-1 (at least relevant pseudorandomness, see **),
>and of SHA-2, means that their use in the KDF is a definite
>general-purpose improvement over the easy distinguishability of the raw
>ECDH (or DH) shared secret, and (2) if one takes a much looser meaning of
>"hash" that includes easily-distinguishable hash functions, then hashing
>of the raw ECDH shared secret does add value.

"Abundantly apparent"? You must have better eyes than I do, because to me
it's not apparent at all.
The fact that quite a few people chose to use MD4/5 and then SHA0/1/2 as
if they were randomizers doesn't prove anything.

>(*) Definability and provability: it's hard (if not impossible) to even
>define general pseudorandomness of a general keyless function (and
>therefore to hard prove anything).

If you look at the design of, e.g., SHA - you'd find that there isn't much
of a difference between "keyed" and "keyless", or in other words -
consider initial pre-set state as a key for the "keyless" or fix key value
for "keyed"...

>(**) A contrived distinguisher would be to select inputs such that hash
>output has some bias, this is the main obstacle to defining
>pseudorandomness (see * above).  A distinguisher would need to be faster
>than a distinguisher for a random oracle.  I suppose that the SHA-1
>collision algorithms can be viewed as a distinguisher, though not with
>any impact on most typical pseudorandom hash applications such as KDF.
>Is there a more direct distinguisher for SHA-1 or SHA-2?

I don't know - do you? And if you don't either - does it prove anything
(besides the fact that neither one of us is a cryptanalyst good enough to
break SHA :)?

>>from
>> >>>an
>>the

---

From: Dan Brown <[email-masked]>
Date: Fri, 24 Aug 2012 20:07:56 +0000

> Sent: Friday, August 24, 2012 2:46 PM

> proofs, or conjectures that were spawned by engineers looking for

So, are other claims of security, such as collision resistance of SHA-2, more substantiated, in your opinion?  For what little it's worth, my intuition says that collision resistance is less plausible than preserving entropy.  My understanding that there was indeed as you say an element of convenience in expanding SHA-1 and SHA-2 usage to beyond message digesting in signature computations, but that the standards committees that approved such uses, such as ANSI X9F1, also had some level of comfort with the security of these extensions, and included member with fairly close connections to their designers of SHA1 and SHA2.
 
> hash functions are so good at it?

Not too sure: but I thought it was to avoid the SHA-1 collision attacks.  Pseudorandomness was required to cover the widespread use of hashes for randomizing.  So, any SHA-3 submissions that sacrificed pseudorandomness, for whatever reason, could be easily excluded.

Indeed, I submitted the SHA-3 candidate, based on elliptic curves of course, and had to deal with this very issue, since an elliptic curve point, even a uniformly distributed one, does not meet the SHA-3 conditions pseudorandomness (as a bit string).

> it's not apparent at all.

Oops: I meant "apparent" more in the sense of "alleged" than in the sense of "obvious".  So, what I meant was that there are many reputable (= "abundant") sources claiming the suitability of SHA-1/2 for randomization.  

> if they were randomizers doesn't prove anything.

Their choice doesn't prove anything, but the use without a successful distinguisher (being widely and publicly known) does prove something.   This is what I meant by "incentive".  So, the fact cryptanalysts could have found and published distinguisher on these hash functions and thereby broken the protocols that use them, and this has not been, proves either no cryptanalysts tried to find a distinguisher, or they tried and failed.  

> I don't know - do you? 
 
I don't know. (I don't think this list is the right place for me to ask the questions I don't know the answer to.) 

> And if you don't either - does it prove anything

Not sure if you're looking for an answer, but here's one.  It may not "prove" anything, but it does "say" something.  For example, I could infer that because I haven't heard about such an attack, and that because I usually somehow hear about a major attacks (e.g. I'm on the SHA-3 mailing list, I check eprint.iacr.org), that maybe there's no such publicly-known attack.  I could also infer from your past emails that you seem to follow cryptography, and therefore would also have heard about a major attack.  Therefore, it would be not unreasonable of me to infer it unlikely that somebody has published a major distinguishing attack.

---

From: David Jacobson <[email-masked]>
Date: Fri, 24 Aug 2012 21:12:57 -0700

On 08/24/2012 01:07 PM, Dan Brown wrote:

[ giant SNIP of everything]

Thank you for answering my question about the need for hashing.

I'll summarize the takeaway for me with the following points, with some 
extra stuff by me, that I hope is correct.

1.  It is easy to test whether there exists a Y such that (key,Y) is on 
the curve.  If keys were random that would happen only half the time.  
But without hashing it always happens. I think this has no effect on the 
security of the session communication using AES-256. But it satisfies 
the conditions of various proofs that assume that the key is chosen at 
random.

2.   The hashing provides an opportunity to introduce additional values 
that the Alice and Bob may agree on.  These could be shared secrets, or 
Alice and Bob's identities, or whatever.  Shared secrets make it hard 
for Charlie to mount a man-in-the-middle attack.

3.  Since hashes provide pre-image resistance, the attacker can't learn 
anything about the result of the ECDH protocol, even if he gets the 
session key. This is a nice theoretical touch.  But I can't think of how 
this is an actual advantage.

4. My question specified AES-256.  But if fewer key bits are needed, the 
truncated output after hashing has full entropy, but a truncated X 
coordinate does not.

Thank you,

     --David Jacobson