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.