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

"Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu> Fri, 24 August 2012 18:46 UTC

Return-Path: <prvs=9583242b3b=uri@ll.mit.edu>

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 D5A0121F8712 for <cfrg@ietfa.amsl.com>; Fri, 24 Aug 2012 11:46:36 -0700 (PDT)

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

X-Spam-Flag: NO

X-Spam-Score: -5.757

X-Spam-Level:

X-Spam-Status: No, score=-5.757 tagged_above=-999 required=5 tests=[AWL=0.090, BAYES_00=-2.599, RCVD_IN_DNSWL_MED=-4, SARE_OBFU_ALL=0.751, UNPARSEABLE_RELAY=0.001]

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 d-SPDFsU5ADQ for <cfrg@ietfa.amsl.com>; Fri, 24 Aug 2012 11:46:35 -0700 (PDT)

Received: from mx2.ll.mit.edu (MX2.LL.MIT.EDU [129.55.12.46]) by ietfa.amsl.com (Postfix) with ESMTP id 858CA21F8717 for <cfrg@irtf.org>; Fri, 24 Aug 2012 11:46:35 -0700 (PDT)

Received: from LLE2K7-HUB01.mitll.ad.local (LLE2K7-HUB01.mitll.ad.local) by mx2.ll.mit.edu (unknown) with ESMTP id q7OIkX18001247; Fri, 24 Aug 2012 14:46:33 -0400

From: "Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu>

To: Dan Brown <dbrown@certicom.com>, "dmjacobson@sbcglobal.net" <dmjacobson@sbcglobal.net>, "cfrg@irtf.org" <cfrg@irtf.org>

Date: Fri, 24 Aug 2012 14:46:28 -0400

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

Thread-Index: Ac2CKMdaPhelexLXQnS/2KFUI0PL3Q==

Message-ID: <CC5D419E.F533%uri@ll.mit.edu>

In-Reply-To: <810C31990B57ED40B2062BA10D43FBF50B32C7@XMB111CNC.rim.net>

Accept-Language: en-US

Content-Language: en-US

X-MS-Has-Attach: yes

X-MS-TNEF-Correlator:

user-agent: Microsoft-MacOutlook/14.12.0.110505

acceptlanguage: en-US

Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg="sha1"; boundary="B_3428664388_161164784"

MIME-Version: 1.0

X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.7.7855, 1.0.260, 0.0.0000 definitions=2012-08-24_06:2012-08-24, 2012-08-24, 1970-01-01 signatures=0

X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 ipscore=0 suspectscore=2 phishscore=0 bulkscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=6.0.2-1203120001 definitions=main-1208240174

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: Fri, 24 Aug 2012 18:46:37 -0000

>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 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). 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 :)? >>-----Original Message----- >> From: Blumenthal, Uri - 0668 - MITLL [mailto:uri@ll.mit.edu] >> Sent: Friday, August 24, 2012 1:12 PM >> To: Dan Brown; dmjacobson@sbcglobal.net; cfrg@irtf.org >> Subject: Re: [Cfrg] uniform random distribution in ECDH public key >> >> On 8/23/12 8:27 , "Dan Brown" <dbrown@certicom.com> 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. >> >> >> >----- 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 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