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

Dan Brown <> Fri, 24 August 2012 20:08 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id F351C21F8469 for <>; Fri, 24 Aug 2012 13:08:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.729
X-Spam-Status: No, score=-4.729 tagged_above=-999 required=5 tests=[AWL=-0.277, BAYES_00=-2.599, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4, SARE_OBFU_ALL=0.751]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id x1jT97KK5pwz for <>; Fri, 24 Aug 2012 13:08:01 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id D0F5121F8463 for <>; Fri, 24 Aug 2012 13:08:00 -0700 (PDT)
X-AuditID: 0a412830-b7f996d000004398-1f-5037df1d5cb8
Received: from ( []) (using TLS with cipher AES128-SHA (AES128-SHA/128 bits)) (Client did not present a certificate) by (SBG) with SMTP id C8.11.17304.D1FD7305; Fri, 24 Aug 2012 20:07:57 +0000 (GMT)
Received: from ([fe80::fcd6:cc6c:9e0b:25bc]) by ([fe80::9c22:d9c:c906:c488%16]) with mapi id 14.02.0298.004; Fri, 24 Aug 2012 16:07:57 -0400
From: Dan Brown <>
To: "'Blumenthal, Uri - 0668 - MITLL'" <>, "" <>, "" <>
Thread-Topic: [Cfrg] uniform random distribution in ECDH public key
Thread-Index: AQHNekb3xzJbLzv3CU6oe+qYCRXyhpdZ4i+AgA1JiYCAADUvFoACJNEA///IDACAAFJGAP//x9ow
Date: Fri, 24 Aug 2012 20:07:56 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: text/plain; charset="us-ascii"
content-transfer-encoding: quoted-printable
MIME-Version: 1.0
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrEKsWRmVeSWpSXmKPExsXC5bjwpK7sffMAg4UN5hbdPw4yWTQd28xu cftbuQOzx+SNh9k8Nr18wuax/v9i1gDmqAZGm6TEkrLgzPQ8fTubxLy8/JLEklSFlNTiZFsl n9T0xByFgKLMssTkSgWXzOLknMTM3NQiJYXMFFslEyWFgpzE5NTc1LwSW6XEgoLUvBQlOy4F DGADVJaZp5Cal5yfkpmXbqvkGeyva2FhaqlrqGSnm9DJk7F4xSHGgtWKFRPfvGVpYPwg1cXI ySEhYCJxatZWFghbTOLCvfVsXYxcHEICfUwS115+Y4dwtjBKdK4+zQpSxSagKnH/6DlmkISI wGRGiZ0NO8DahQWcJP5MXcYOYosIOEvs63/GBGFHSVzt+ABWwwLUPOPMGUYQm1fATeJz6y+g OAfQhnSJeTPTQMKcAtoSO25dACtnFJCV2H32OtgYZgFxiVtP5jNBXCogsWTPeWYIW1Ti5eN/ rBC2osSTk9dYIOp1JBbs/sQGYWtLLFv4mhliraDEyZlPWCYwis5CMnYWkpZZSFpmIWlZwMiy ilEwN6PYwMwwOS9ZrygzVy8vtWQTIzhFaBjsYHz/3uIQowAHoxIPr+ZG8wAh1sSy4srcQ4wS HMxKIrwCfkAh3pTEyqrUovz4otKc1OJDjBbAQJnILMWdnA9MX3kl8cYGBigcJXFeJg+jAGAI AZNMdmpqQWoRTCsTByfIaC4pkWJgqkgtSiwtyYgHJbT4YmBKk2pg3N3QdFd23/xntZ8cbZ80 zlHckCKhryh3r/QSm77NhUMPu74JsJ38lXbklVXW92v3X5wvkb3h18/XeW+qu8/f89d+NwlU alxVsXpbI1UWUy55ninZddUB11P6iy+eC34gmxooqxITb3fpQvIEK5+n33wO9Ur9V/rndGLW xFVz7s3kD8nWPTP7shJLcUaioRZzUXEiADDapFxFAwAA
Subject: Re: [Cfrg] uniform random distribution in ECDH public key
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 24 Aug 2012 20:08:02 -0000

> -----Original Message-----
> From: Blumenthal, Uri - 0668 - MITLL []
> Sent: Friday, August 24, 2012 2:46 PM
> To: Dan Brown;;
> Subject: Re: [Cfrg] uniform random distribution in ECDH public key

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

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

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

> "Abundantly apparent"? You must have better eyes than I do, because to me
> 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.  

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

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.  

> >Is there a more direct distinguisher for SHA-1 or SHA-2?
> 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
> (besides the fact that neither one of us is a cryptanalyst good enough to
> break SHA :)?

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

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.