From rgm-sec@htt-consult.com Tue Aug 14 11:02:26 2012 Return-Path: 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 1909021F876D for ; Tue, 14 Aug 2012 11:02:26 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LLgezxOrNuOk for ; Tue, 14 Aug 2012 11:02:25 -0700 (PDT) Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by ietfa.amsl.com (Postfix) with ESMTP id 5272F21F8773 for ; Tue, 14 Aug 2012 11:02:25 -0700 (PDT) Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id E570962A79 for ; Tue, 14 Aug 2012 18:01:59 +0000 (UTC) X-Virus-Scanned: amavisd-new at localhost Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id iezs00MAOIyd for ; Tue, 14 Aug 2012 14:01:49 -0400 (EDT) Received: from lx120e.htt-consult.com (nc4010.htt-consult.com [208.83.67.156]) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id 8214E62A71 for ; Tue, 14 Aug 2012 14:01:49 -0400 (EDT) Message-ID: <502A928A.7090003@htt-consult.com> Date: Tue, 14 Aug 2012 14:01:46 -0400 From: Robert Moskowitz User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0 MIME-Version: 1.0 To: cfrg@irtf.org Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Subject: [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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:02:26 -0000 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 sfluhrer@cisco.com Tue Aug 14 11:14:44 2012 Return-Path: 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 1E7EC21F8793 for ; Tue, 14 Aug 2012 11:14:44 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.599 X-Spam-Level: X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xNa+a4eWYlW2 for ; Tue, 14 Aug 2012 11:14:43 -0700 (PDT) Received: from rcdn-iport-6.cisco.com (rcdn-iport-6.cisco.com [173.37.86.77]) by ietfa.amsl.com (Postfix) with ESMTP id 5995F21F878B for ; Tue, 14 Aug 2012 11:14:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=sfluhrer@cisco.com; l=1476; q=dns/txt; s=iport; t=1344968083; x=1346177683; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=Kl0yFL8WSOFZUIPAgQNUEhGgbIdvCqhR4sm2vZm4E7U=; b=lwgFiqfwflMf0bn12cCL7oCHNy5ZOPTvgGA2T/AUuSRiRgk0gi8Zg4ya gcI+BOS3VlQEHk0+zFyz+6uO2e0PfQEezaI3iZ/RjUm0QTAEEU3KBmPi0 Mhwy/lNWFNXYEFAsCg6iqjKO83QiCyyqC5vF0B9/2qVX+zxmZlIJMXnZO 0=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av8EAKaUKlCtJXG+/2dsb2JhbABFuhyBB4IgAQEBBAEBAQ8BJzQXBAIBCA4DBAEBCxQJBycLFAkIAgQBEggBEgeHawuYH6B8iwWFUWADo3WBZoJf X-IronPort-AV: E=Sophos;i="4.77,768,1336348800"; d="scan'208";a="111524951" Received: from rcdn-core2-3.cisco.com ([173.37.113.190]) by rcdn-iport-6.cisco.com with ESMTP; 14 Aug 2012 18:14:42 +0000 Received: from xhc-aln-x11.cisco.com (xhc-aln-x11.cisco.com [173.36.12.85]) by rcdn-core2-3.cisco.com (8.14.5/8.14.5) with ESMTP id q7EIEgvE022728 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Tue, 14 Aug 2012 18:14:42 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.159]) by xhc-aln-x11.cisco.com ([173.36.12.85]) with mapi id 14.02.0298.004; Tue, 14 Aug 2012 13:14:42 -0500 From: "Scott Fluhrer (sfluhrer)" To: Robert Moskowitz , "cfrg@irtf.org" Thread-Topic: [Cfrg] uniform random distribution in ECDH public key Thread-Index: AQHNekb9jeMcpOeb9EuiRpkm0AlB15dZm7Kw Date: Tue, 14 Aug 2012 18:14:41 +0000 Message-ID: References: <502A928A.7090003@htt-consult.com> In-Reply-To: <502A928A.7090003@htt-consult.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.32.244.83] x-tm-as-product-ver: SMEX-10.2.0.1135-7.000.1014-19112.005 x-tm-as-result: No--32.925400-8.000000-31 x-tm-as-user-approved-sender: No x-tm-as-user-blocked-sender: No Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:14:44 -0000 No, the value g^j (or jG, if we prefer the more traditional additive notati= on for elliptic curves) is not uniform; it is a 512 bit value (for P256), a= nd corresponds to a point on the curve (that is, it is a pair of 256 bit va= lues 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 a= re a large number of 512 bit public values which are not possible. -----Original Message----- From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Rob= ert Moskowitz Sent: Tuesday, August 14, 2012 2:02 PM To: cfrg@irtf.org Subject: [Cfrg] uniform random distribution in ECDH public key I understand from RFC 6090 and 5869 that the secret key produced from an=20 ECDH exchange is not uniformly randomly distributed and that is why we=20 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=20 curve is p-256, both j and g^j are 256 bits long. But is g^j uniformly=20 randomly distributed like j is suppose to be? Side question: I am still unclear on the length of the exchanged secret=20 (g^j)^k, is it 256 bits (for p-256) or larger (perhaps 512 bits)? Thank you for helping me get all this straight. _______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg From rgm-sec@htt-consult.com Tue Aug 14 11:26:05 2012 Return-Path: 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 1A91821F863B for ; Tue, 14 Aug 2012 11:26:05 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZoiTaXmAbu1v for ; Tue, 14 Aug 2012 11:26:04 -0700 (PDT) Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by ietfa.amsl.com (Postfix) with ESMTP id 4F9CC21F8611 for ; Tue, 14 Aug 2012 11:26:04 -0700 (PDT) Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id 5393D62A5D; Tue, 14 Aug 2012 18:25:40 +0000 (UTC) X-Virus-Scanned: amavisd-new at localhost Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id U1aKYPZ2Vnjr; Tue, 14 Aug 2012 14:25:30 -0400 (EDT) Received: from lx120e.htt-consult.com (nc4010.htt-consult.com [208.83.67.156]) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id EBF7062820; Tue, 14 Aug 2012 14:25:29 -0400 (EDT) Message-ID: <502A9819.7080708@htt-consult.com> Date: Tue, 14 Aug 2012 14:25:29 -0400 From: Robert Moskowitz User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0 MIME-Version: 1.0 To: "Scott Fluhrer (sfluhrer)" References: <502A928A.7090003@htt-consult.com> In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Cc: "cfrg@irtf.org" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:26:05 -0000 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? > > -----Original Message----- > From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Robert Moskowitz > Sent: Tuesday, August 14, 2012 2:02 PM > To: cfrg@irtf.org > Subject: [Cfrg] uniform random distribution in ECDH public key > > 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. > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > From mcgrew@cisco.com Tue Aug 14 11:26:37 2012 Return-Path: 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 A0E7221F876A for ; Tue, 14 Aug 2012 11:26:37 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -110.513 X-Spam-Level: X-Spam-Status: No, score=-110.513 tagged_above=-999 required=5 tests=[AWL=0.086, BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8, USER_IN_WHITELIST=-100] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LpdD8Y5JO9So for ; Tue, 14 Aug 2012 11:26:37 -0700 (PDT) Received: from rcdn-iport-4.cisco.com (rcdn-iport-4.cisco.com [173.37.86.75]) by ietfa.amsl.com (Postfix) with ESMTP id AE35D21F86B5 for ; Tue, 14 Aug 2012 11:26:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=mcgrew@cisco.com; l=1074; q=dns/txt; s=iport; t=1344968795; x=1346178395; h=from:to:subject:date:message-id:in-reply-to:content-id: content-transfer-encoding:mime-version; bh=Y5t0pRIsCN+9mdRL0rQvX2v4L/f7zV/sTqaG4TIKXqQ=; b=FU3LstYD+3KkhHS3wmoI6wU1TxaNUUtvVtiq1w0XoOk7TGmVhDnDZyJd Ufas8jYQbFfhY45uGUxeui5h8e653JXLHUdRr7CtNd6Oan8huDtr3yjRn nVnGbgptZI1NNythW8kppom4C9lR8GwezH+x3TyXqJIqwLHzMariwwWI5 4=; X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av4EACWXKlCtJXHB/2dsb2JhbABFuhyBB4IiAQQBAQEPASc0HQEIDig3CyUCBAESCRmHawuYHaB7kTYDlUuOKoFmgl8 X-IronPort-AV: E=Sophos;i="4.77,768,1336348800"; d="scan'208";a="111558940" Received: from rcdn-core2-6.cisco.com ([173.37.113.193]) by rcdn-iport-4.cisco.com with ESMTP; 14 Aug 2012 18:26:35 +0000 Received: from xhc-rcd-x03.cisco.com (xhc-rcd-x03.cisco.com [173.37.183.77]) by rcdn-core2-6.cisco.com (8.14.5/8.14.5) with ESMTP id q7EIQZ3W021921 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Tue, 14 Aug 2012 18:26:35 GMT Received: from xmb-rcd-x04.cisco.com ([169.254.8.159]) by xhc-rcd-x03.cisco.com ([173.37.183.77]) with mapi id 14.02.0298.004; Tue, 14 Aug 2012 13:26:34 -0500 From: "David McGrew (mcgrew)" To: Robert Moskowitz , "cfrg@irtf.org" Thread-Topic: [Cfrg] uniform random distribution in ECDH public key Thread-Index: AQHNekb92R2TNl0fjUq9ua4MtNyB0ZdZsN6A Date: Tue, 14 Aug 2012 18:26:34 +0000 Message-ID: In-Reply-To: <502A928A.7090003@htt-consult.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: user-agent: Microsoft-MacOutlook/14.2.1.120420 x-originating-ip: [10.117.10.228] x-tm-as-product-ver: SMEX-10.2.0.1135-7.000.1014-19112.005 x-tm-as-result: No--31.490000-8.000000-31 x-tm-as-user-approved-sender: No x-tm-as-user-blocked-sender: No Content-Type: text/plain; charset="us-ascii" Content-ID: <1A581EA350DA6949B36CC6971349981F@cisco.com> Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:26:37 -0000 Hi Bob, On 8/14/12 2:01 PM, "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? 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 > >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. > >_______________________________________________ >Cfrg mailing list >Cfrg@irtf.org >http://www.irtf.org/mailman/listinfo/cfrg From rgm-sec@htt-consult.com Tue Aug 14 11:29:26 2012 Return-Path: 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 D2A1121E8039 for ; Tue, 14 Aug 2012 11:29:26 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xNF18qRXT27X for ; Tue, 14 Aug 2012 11:29:26 -0700 (PDT) Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by ietfa.amsl.com (Postfix) with ESMTP id 1D5DA21F876A for ; Tue, 14 Aug 2012 11:29:26 -0700 (PDT) Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id ACE3062A5D; Tue, 14 Aug 2012 18:29:04 +0000 (UTC) X-Virus-Scanned: amavisd-new at localhost Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id AOYBDBknzicK; Tue, 14 Aug 2012 14:28:54 -0400 (EDT) Received: from lx120e.htt-consult.com (nc4010.htt-consult.com [208.83.67.156]) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id 2561562820; Tue, 14 Aug 2012 14:28:54 -0400 (EDT) Message-ID: <502A98E5.2030304@htt-consult.com> Date: Tue, 14 Aug 2012 14:28:53 -0400 From: Robert Moskowitz User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0 MIME-Version: 1.0 To: "Scott Fluhrer (sfluhrer)" References: <502A928A.7090003@htt-consult.com> In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Cc: "cfrg@irtf.org" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:29:27 -0000 One more point. On 08/14/2012 02:14 PM, Scott Fluhrer (sfluhrer) wrote: > 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. 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" > > -----Original Message----- > From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of Robert Moskowitz > Sent: Tuesday, August 14, 2012 2:02 PM > To: cfrg@irtf.org > Subject: [Cfrg] uniform random distribution in ECDH public key > > 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. > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > From rgm-sec@htt-consult.com Tue Aug 14 11:51:37 2012 Return-Path: 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 0467321E8041 for ; Tue, 14 Aug 2012 11:51:37 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[AWL=0.000, BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id t0VBdNdwSpec for ; Tue, 14 Aug 2012 11:51:36 -0700 (PDT) Received: from klovia.htt-consult.com (klovia.htt-consult.com [208.83.67.149]) by ietfa.amsl.com (Postfix) with ESMTP id 6F1A021E803C for ; Tue, 14 Aug 2012 11:51:36 -0700 (PDT) Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id BD48062A80; Tue, 14 Aug 2012 18:51:12 +0000 (UTC) X-Virus-Scanned: amavisd-new at localhost Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Ft6q7evt9F0X; Tue, 14 Aug 2012 14:50:55 -0400 (EDT) Received: from lx120e.htt-consult.com (nc4010.htt-consult.com [208.83.67.156]) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id 83CE762A5D; Tue, 14 Aug 2012 14:50:55 -0400 (EDT) Message-ID: <502A9E0E.6060209@htt-consult.com> Date: Tue, 14 Aug 2012 14:50:54 -0400 From: Robert Moskowitz User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0 MIME-Version: 1.0 To: "David McGrew (mcgrew)" References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Cc: "cfrg@irtf.org" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:51:37 -0000 On 08/14/2012 02:26 PM, David McGrew (mcgrew) wrote: > Hi Bob, > > On 8/14/12 2:01 PM, "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? > 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. 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! > > David > >> 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. >> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> http://www.irtf.org/mailman/listinfo/cfrg > From vf@unity.net Tue Aug 14 11:51:38 2012 Return-Path: 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 9966821E8048 for ; Tue, 14 Aug 2012 11:51:38 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZXeZ3LlGOFpN for ; Tue, 14 Aug 2012 11:51:38 -0700 (PDT) Received: from vc.unity.net (140-242.trifle.net [195.24.140.242]) by ietfa.amsl.com (Postfix) with ESMTP id CAB9521E8042 for ; Tue, 14 Aug 2012 11:51:37 -0700 (PDT) Received: from vf by vc.unity.net with local (Exim 4.72) (envelope-from ) id 1T1MDH-00024W-Cm for cfrg@irtf.org; Tue, 14 Aug 2012 21:51:35 +0300 Date: Tue, 14 Aug 2012 21:51:35 +0300 From: Vadym Fedyukovych To: cfrg@irtf.org Message-ID: <20120814185135.GJ20940@unity.net> References: <502A928A.7090003@htt-consult.com> MIME-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline In-Reply-To: <502A928A.7090003@htt-consult.com> User-Agent: Mutt/1.5.20 (2009-06-14) 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:51:38 -0000 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 > 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? 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. > Thank you for helping me get all this straight. From dharkins@lounge.org Tue Aug 14 11:58:26 2012 Return-Path: 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 BC38821F867D for ; Tue, 14 Aug 2012 11:58:26 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -6.216 X-Spam-Level: X-Spam-Status: No, score=-6.216 tagged_above=-999 required=5 tests=[AWL=0.049, BAYES_00=-2.599, IP_NOT_FRIENDLY=0.334, RCVD_IN_DNSWL_MED=-4] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lu4XTZljRwvz for ; Tue, 14 Aug 2012 11:58:26 -0700 (PDT) Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id 59E0221F8569 for ; Tue, 14 Aug 2012 11:58:26 -0700 (PDT) Received: from www.trepanning.net (localhost [127.0.0.1]) by colo.trepanning.net (Postfix) with ESMTP id DC4541022404C; Tue, 14 Aug 2012 11:23:02 -0700 (PDT) Received: from 69.12.173.8 (SquirrelMail authenticated user dharkins@lounge.org) by www.trepanning.net with HTTP; Tue, 14 Aug 2012 11:23:03 -0700 (PDT) Message-ID: In-Reply-To: <502A928A.7090003@htt-consult.com> References: <502A928A.7090003@htt-consult.com> Date: Tue, 14 Aug 2012 11:23:03 -0700 (PDT) From: "Dan Harkins" To: "Robert Moskowitz" User-Agent: SquirrelMail/1.4.14 [SVN] MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal Cc: cfrg@irtf.org 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Aug 2012 18:58:26 -0000 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. From housley@vigilsec.com Tue Aug 21 06:50:24 2012 Return-Path: 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 C9E9221F8682 for ; Tue, 21 Aug 2012 06:50:24 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -102.444 X-Spam-Level: X-Spam-Status: No, score=-102.444 tagged_above=-999 required=5 tests=[AWL=0.154, BAYES_00=-2.599, HTML_MESSAGE=0.001, USER_IN_WHITELIST=-100] 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 UY-02YitBkJj for ; Tue, 21 Aug 2012 06:50:23 -0700 (PDT) Received: from odin.smetech.net (mail.smetech.net [208.254.26.82]) by ietfa.amsl.com (Postfix) with ESMTP id B798721F864A for ; Tue, 21 Aug 2012 06:50:23 -0700 (PDT) Received: from localhost (unknown [208.254.26.81]) by odin.smetech.net (Postfix) with ESMTP id AD9E6111C009; Tue, 21 Aug 2012 09:51:05 -0400 (EDT) X-Virus-Scanned: amavisd-new at smetech.net Received: from odin.smetech.net ([208.254.26.82]) by localhost (ronin.smetech.net [208.254.26.81]) (amavisd-new, port 10024) with ESMTP id MqDuIt+uTRIW; Tue, 21 Aug 2012 09:50:17 -0400 (EDT) Received: from [192.168.1.3] (96-37-2-47.dhcp.sffl.va.charter.com [96.37.2.47]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by odin.smetech.net (Postfix) with ESMTP id BCF63111C001; Tue, 21 Aug 2012 09:50:59 -0400 (EDT) From: Russ Housley Content-Type: multipart/alternative; boundary=Apple-Mail-86-30111657 Date: Tue, 21 Aug 2012 09:50:15 -0400 References: To: IRTF CFRG , IETF SAAG Message-Id: Mime-Version: 1.0 (Apple Message framework v1084) X-Mailer: Apple Mail (2.1084) Subject: [Cfrg] Fwd: NIST Requests Comments on Draft Revision NIST SP 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography X-BeenThere: cfrg@irtf.org 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: Tue, 21 Aug 2012 13:50:24 -0000 --Apple-Mail-86-30111657 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii This is probably of interest to CFRG and SAAG. > From: "Caswell, Sara J." > Date: August 21, 2012 8:08:59 AM EDT > To: "'housley@vigilsec.com'" > Subject: NIST Requests Comments on Draft Revision NIST SP 800-56A, = Recommendation for Pair-Wise Key Establishment Schemes Using Discrete = Logarithm Cryptography >=20 > NIST announces the release of a draft revision of Special Publication = 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using = Discrete Logarithm Cryptography. SP 800-56A specifies key-establishment = schemes based on the discrete logarithm problem over finite fields and = elliptic curves, including several variations of Diffie-Hellman and MQV = key establishment schemes. The revision is made on the March 2007 = version. The main changes are listed in Appendix D. The document is = available at = http://csrc.nist.gov/publications/PubsDrafts.html#SP-800-56-A%20Rev. > =20 > Please submit comments to 56A2012rev-comments@nist.gov with "Comments = on SP 800-56A (Revision)" in the subject line. The comment period closes = on October 31, 2012. > =20 --Apple-Mail-86-30111657 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii This = is probably of interest to CFRG and = SAAG.



From: "Caswell, Sara J." = <sara.caswell@nist.gov>
Date: August 21, 2012 8:08:59 AM EDT
Subject: NIST Requests = Comments on Draft Revision NIST SP 800-56A, Recommendation for Pair-Wise = Key Establishment Schemes Using Discrete Logarithm = Cryptography

NIST announces = the release of a draft revision of Special Publication = 800-56A, Recommendation for = Pair-Wise Key Establishment Schemes Using Discrete Logarithm = Cryptography. SP 800-56A specifies key-establishment schemes = based on the discrete logarithm problem over finite fields and elliptic = curves, including several variations of Diffie-Hellman and MQV key = establishment schemes. The revision is made on the March 2007 version. = The main changes are listed in Appendix D. The document is = available at 56A2012rev-comments@nist.gov with "Comments on SP = 800-56A (Revision)" in the subject line. The comment period closes = on , "cfrg@irtf.org" Thread-Topic: [Cfrg] uniform random distribution in ECDH public key Thread-Index: AQHNekb3xzJbLzv3CU6oe+qYCRXyhpdZ4i+AgA1JiYCAADUvFg== Date: Thu, 23 Aug 2012 12:27:58 +0000 Message-ID: <810C31990B57ED40B2062BA10D43FBF50B2B38@XMB111CNC.rim.net> In-Reply-To: <5035BCF1.9030903@sbcglobal.net> Accept-Language: en-CA, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.65.160.246] Content-Type: text/plain; charset="iso-8859-1" content-transfer-encoding: quoted-printable MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrMKsWRmVeSWpSXmKPExsXC5bjwlO4FRbMAgz2zpSy6fxxksmg6tpnd gclj8sbDbB7r/y9mDWCKamC0SUosKQvOTM/Tt7NJzMvLL0ksSVVISS1OtlXySU1PzFEIKMos S0yuVHDJLE7OSczMTS1SUshMsVUyUVIoyElMTs1NzSuxVUosKEjNS1Gy41LAADZAZZl5Cql5 yfkpmXnptkqewf66FhamlrqGSna6CZ08GU93rmMt6JCtuDC5k7mBsUu8i5GTQ0LAROLl0XVM ELaYxIV769m6GLk4hAT6mCRmzn/MBOGsZJT4+Hc1VGYOo0TzvAnMIC1sAqoS94+eA7I5OEQE YiR+LUsFCQsLOEn8/jqNBcQWEXCW2Nf/jAnCdpL427OMFaScBaj1+YMEEJNXwE1i3/oskApO AV2J3TfPsoLYjAKyErvPXgfrZBYQl7j1ZD7UnQISS/acZ4awRSVePv7HCmErSjw5eY0Fol5P 4sbUKWwQtrbEsoWvwep5BQQlTs58AlYjJKAgceX6PpYJjGKzkKyYhaR9FpL2WUjaFzCyrGIU zM0oNjAzTM5L1ivKzNXLSy3ZxAhOEhoGOxjfv7c4xCjAwajEw/uY1SxAiDWxrLgy9xCjBAez kgivFydQiDclsbIqtSg/vqg0J7X4EKMFMEwmMktxJ+cDE1heSbyxgQEKR0mcl8nDKEBIIB2Y eLJTUwtSi2BamTg4QUZzSYkUA9NHalFiaUlGPCjJxRcD05xUA2PdZYe115LZ59xkkglUX5p5 8P5s3g1VO7Ue+s/39Nukb27yeNH+qxeld96LMvf+z5/61/FB+0Mhlw/Pr57KLDtoKWQyIX/N i33JodM4F1fNP73PgrFTP3mp/+wzPo99eFj0PQ4w6s/q2Jrx+NakHc/TLtZNauO24MhKdTzh rSDYzj75i+095T1KLMUZiYZazEXFiQA7kRBxRgMAAA== 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 23 Aug 2012 12:28:02 -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 bi= t string. This may matter if one just wanted to use the key to pad a messa= ge. This does not really matter for AES, but the ECDH standards don't speci= fy 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 HM= AC. A third advantage, if the shared key is later revealed, then the hash preven= ts the calculation of the raw ECDH value, which is harmful mostly in the cas= e where one public key is static: it allows the adversary to do replay, inva= lid curve attacks, and Cheon-type attacks. ----- Original Message ----- From: David Jacobson [mailto:dmjacobson@sbcglobal.net] Sent: Thursday, August 23, 2012 01:17 AM=0A= To: 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 =3D 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 infor= mation, privileged material (including material protected by the solicitor-c= lient 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 immedia= tely reply to the sender and delete this information from your system. Use,= dissemination, distribution, or reproduction of this transmission by uninte= nded recipients is not authorized and may be unlawful. From prvs=9583242b3b=uri@ll.mit.edu Fri Aug 24 10:28:47 2012 Return-Path: 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 E3D9A21F86E0 for ; Fri, 24 Aug 2012 10:28:46 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -5.9 X-Spam-Level: X-Spam-Status: No, score=-5.9 tagged_above=-999 required=5 tests=[AWL=0.699, BAYES_00=-2.599, RCVD_IN_DNSWL_MED=-4, 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 fHRxp486rtWM for ; Fri, 24 Aug 2012 10:28:46 -0700 (PDT) Received: from mx2.ll.mit.edu (MX2.LL.MIT.EDU [129.55.12.46]) by ietfa.amsl.com (Postfix) with ESMTP id B7F4A21F8646 for ; Fri, 24 Aug 2012 10:28:45 -0700 (PDT) Received: from LLE2K7-HUB01.mitll.ad.local (LLE2K7-HUB01.mitll.ad.local) by mx2.ll.mit.edu (unknown) with ESMTP id q7OHSdhx017132; Fri, 24 Aug 2012 13:28:40 -0400 From: "Blumenthal, Uri - 0668 - MITLL" To: Dan Brown , "dmjacobson@sbcglobal.net" , "cfrg@irtf.org" Date: Fri, 24 Aug 2012 13:12:16 -0400 Thread-Topic: [Cfrg] uniform random distribution in ECDH public key Thread-Index: Ac2CG52z9szvPmQ+T3i/YBALZDcSWw== Message-ID: In-Reply-To: <810C31990B57ED40B2062BA10D43FBF50B2B38@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_3428658737_160858436" 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-1208240159 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 24 Aug 2012 17:28:47 -0000 --B_3428658737_160858436 Content-type: text/plain; charset="US-ASCII" Content-transfer-encoding: 7bit On 8/23/12 8:27 , "Dan Brown" 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 >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 --B_3428658737_160858436 Content-Type: application/pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" MIIUAAYJKoZIhvcNAQcCoIIT8TCCE+0CAQExCzAJBgUrDgMCGgUAMAsGCSqGSIb3DQEHAaCC EeMwggTLMIIDs6ADAgECAgoTvp8EAAAAAEiAMA0GCSqGSIb3DQEBCwUAMFExCzAJBgNVBAYT AlVTMR8wHQYDVQQKExZNSVQgTGluY29sbiBMYWJvcmF0b3J5MQwwCgYDVQQLEwNQS0kxEzAR BgNVBAMTCk1JVExMIENBLTIwHhcNMTIwNzE2MTgwNzA2WhcNMTMwNzE2MTgwNzA2WjBhMQsw CQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEPMA0GA1UECxMG UGVvcGxlMSAwHgYDVQQDExdCbHVtZW50aGFsLlVyaS41MDAxMDU4NDCCASIwDQYJKoZIhvcN AQEBBQADggEPADCCAQoCggEBALQbhERcgi7bVsw6WLXunsi9ymPD09JMrF1iGlCDF4ZO1+W5 Lp6znDFyubLdbP3qikgcXWfByMzsHUzoSQD1Bp9O7mKa656rMu3mez/ItydJBw/LMZYSYc+6 4DB4KuzvA2DnTaQ41I0SqFE0DrksfBi8ePO/Xv7PQRNUl45Y7VSB6xoA7DfTZO5IZ4e6Om90 /AnVBE+aee40kxvmDWGr1jvFxv/gSvQA3PxcwnCxzn699bpAtz8VUdfTsewhy+g5OonBLSzg I/yIyCd6g2eQQcw6g10eQJopUnoKv1o0TIss1pwK5SZG3mM2FCFECL1vV8NMTQ4AuS3OSO7i 3AX2g1cCAwEAAaOCAZMwggGPMB0GA1UdDgQWBBSw8IXAP4OJKTOqBKNPgRR1LceLVzAOBgNV HQ8BAf8EBAMCBsAwHwYDVR0jBBgwFoAUjkp9iaFjFxyBiDRXNyZFXhmKfiQwMwYDVR0fBCww KjAooCagJIYiaHR0cDovL2NybC5sbC5taXQuZWR1L2dldGNybC9MTENBMjBiBggrBgEFBQcB AQRWMFQwLQYIKwYBBQUHMAKGIWh0dHA6Ly9jcmwubGwubWl0LmVkdS9nZXR0by9MTENBMjAj BggrBgEFBQcwAYYXaHR0cDovL29jc3AubGwubWl0LmVkdS8wDAYDVR0TAQH/BAIwADA9Bgkr BgEEAYI3FQcEMDAuBiYrBgEEAYI3FQiDg+Udh+ynZoathxWD6vBFhbahHx2Fy94yh/+KcwIB ZAIBBTAiBgNVHSUBAf8EGDAWBggrBgEFBQcDBAYKKwYBBAGCNwoDDDAYBgNVHSAEETAPMA0G CyqGSIb3EgIBAwEIMBkGA1UdEQQSMBCBDnVyaUBsbC5taXQuZWR1MA0GCSqGSIb3DQEBCwUA A4IBAQCheTHY3ppuUbzU5Quma4TR1Rhr0r+BfIMJyrfrmA9gNIoFzK0MbK1xxRv/9Nz/9sRQ ukIWIIfjyQlNDIiCl+8yut3V31v5NW+T0NB4GGIYicWI+ID8tBfvaHaniZ+bP/wEsZMOPq1J kh4E28mRAsHMuYhu6kraGj0yRi4Y3zuxJIeRN7NGYFCglFaPSeOQ33m0o5oyyMNfdDcDX7T/ 3pSSNFk/gAcPoI+XvC0sXS2cVYqvDGwzsT58M+6jvg0FDb8z/BIO2OL2KpO+ojeNSNud4Cf4 7gEpChuvx36vgLLq+J1s9BIXKk7FVAIdbD5KKnO/HiDpqamScI6p3Lc3PQZuMIIEtzCCA5+g AwIBAgIBFDANBgkqhkiG9w0BAQsFADBUMQswCQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExp bmNvbG4gTGFib3JhdG9yeTEMMAoGA1UECxMDUEtJMRYwFAYDVQQDEw1NSVRMTCBSb290IENB MB4XDTA5MTIxNDEyMDAwMFoXDTE1MTIzMTIzNTk1OVowUTELMAkGA1UEBhMCVVMxHzAdBgNV BAoTFk1JVCBMaW5jb2xuIExhYm9yYXRvcnkxDDAKBgNVBAsTA1BLSTETMBEGA1UEAxMKTUlU TEwgQ0EtMjCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBAKcEyyNhSIfsN6AzBwVh Zkzo6SdjNGAQ7mA2A8T0kmdCB8MH6jWjVVMwFZwlg9cgjgLKEuEO9KN8K9M8jgeZEMoinlRf k3YELPC7sEkkzBQkcVpLhEwALue9iHowgSLGmXZpYKmRhfvhvYJ4MNCuIaWpcK/GaDZCE+U2 aTg42kv/zQrH3AoqFX81OF7niwXNnanP1hQRfkMTRrnaEW8DX0TMaG/t9Ry5xSMrLTNc9DvQ tjA5ZcuWnECiUpyDBFWxLr9yx7xgf1/LwgCxcoBeKSBBoWzkQmKAsgMo9Mq1Fp/nnIqw5FKm gOs7Vy+6e0Dk+cgf+oAV8AK8ZFMQrVE0uH0CAwEAAaOCAZUwggGRMBIGA1UdEwEB/wQIMAYB Af8CAQAwHQYDVR0OBBYEFI5KfYmhYxccgYg0VzcmRV4Zin4kMB8GA1UdIwQYMBaAFGeqes/0 Cqa5crWKoNKd8hDDQ+0pMA4GA1UdDwEB/wQEAwIBhjBhBggrBgEFBQcBAQRVMFMwLQYIKwYB BQUHMAKGIWh0dHA6Ly9jcmwubGwubWl0LmVkdS9nZXR0bz9MTFJDQTAiBggrBgEFBQcwAYYW aHR0cDovL29jc3AubGwubWl0LmVkdTAzBgNVHR8ELDAqMCigJqAkhiJodHRwOi8vY3JsLmxs Lm1pdC5lZHUvZ2V0Y3JsP0xMUkNBMIGSBgNVHSAEgYowgYcwDQYLKoZIhvcSAgEDAQYwDQYL KoZIhvcSAgEDAQgwDQYLKoZIhvcSAgEDAQcwDQYLKoZIhvcSAgEDAQkwDQYLKoZIhvcSAgED AQowDQYLKoZIhvcSAgEDAQswDQYLKoZIhvcSAgEDAQ4wDQYLKoZIhvcSAgEDAQ8wDQYLKoZI hvcSAgEDARAwDQYJKoZIhvcNAQELBQADggEBAIh3BqHQ/XH8C6DCL+eEGroOzxBcCqTNItms v4MANaOTodgU2jrjHcGjXlzqhpb8ZxOlkAK3dK09rc6+yACcoK2TzVtDRZXYxov/SqZRjI3d ufU2JatAPxosCyy/1otjl1TKUY47Wvft31vdf5i0XK2DQVEJ+XlqtgBiFTVIMIfBJwPajrsi z+pgFEYwhhwJxvs8flSi0FLCE77VYLEioP5hxG6zIPeQRxzh1bogbfphWHHtoiTDkBSZ4Ufv GXQTVf7QjhD5yYw10yICtjHmtgbfgBkH5/vvR92NY9RSlNPzZqmGKIia61bJCmagRYGyexfe dVNF0cJWL4J/cLHhgNYwggODMIICa6ADAgECAgEBMA0GCSqGSIb3DQEBBQUAMFQxCzAJBgNV BAYTAlVTMR8wHQYDVQQKExZNSVQgTGluY29sbiBMYWJvcmF0b3J5MQwwCgYDVQQLEwNQS0kx FjAUBgNVBAMTDU1JVExMIFJvb3QgQ0EwHhcNMDgwOTIzMTIwMDAwWhcNMjkxMjMxMjM1OTU5 WjBUMQswCQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEMMAoG A1UECxMDUEtJMRYwFAYDVQQDEw1NSVRMTCBSb290IENBMIIBIjANBgkqhkiG9w0BAQEFAAOC AQ8AMIIBCgKCAQEAxU4pF1iyJrL5rYq/XBAKg93kCTATG7Bw0NGFpEJ1A3Xsr6UIIq9/1VJB OgCwDqrVsAK1lRwy/lkrHzPkobiMr1wzjQ28SR/9sg5kAcmrMqBYbc302qtwCGKZxdNdhAh2 nUOCO10AMpUsCNdpikPY9ukT8lsA+eorM4Q1rc/L0J6AHRptOU7IuDBdZj+tdNb7gv+GKknr 6wj9m2sVGawoaG7AAqhsWvQUM/q4h/H5FpYlwnVAEh2AzhqiG9bwl6uJJIzJ/8uUWldNkVwz 1I5fR/vCaxiLXIW4oUydBuRKTG+ekEoxHGuD73yx5JtsSciS8HQL2oEM8tv+VAC+albqgwID AQABo2AwXjAPBgNVHRMBAf8EBTADAQH/MB0GA1UdDgQWBBRnqnrP9AqmuXK1iqDSnfIQw0Pt KTAfBgNVHSMEGDAWgBRnqnrP9AqmuXK1iqDSnfIQw0PtKTALBgNVHQ8EBAMCAYYwDQYJKoZI hvcNAQEFBQADggEBAD4bbQVg0Hh42EpYX4/JPkNS3OUAEWR/YgzZUY1QGi9rQZ4pfcjU1/Ta oNT8Y7Yf0RO+e9NiG9+BDhQH/kQiZOQo9rv9NUb8xDtKCYCad7zEQtVsYsWuvK2XLw/Ji1m2 eBvoOB4RS/5LAWfNws7W+DWt2ayzeTCyrLSrx7ZVgBjzNOm0TPIkbfppdwgxuo7FZL8ts+M2 492Al87d3VasevUS1pprRBEupChmPTt1hjtajkQOpT4BQAzP1lVEYrWzlv+O/lbP9iujKpYW cfYqQ3FGf37YCvuDeues4xm+nqmyraNsNeI8Gh3XDIwqfzHnLhy4Y80VyqN/Jj8df3SK9AAw ggTOMIIDtqADAgECAgpDgT5qAAAAADKHMA0GCSqGSIb3DQEBCwUAMFExCzAJBgNVBAYTAlVT MR8wHQYDVQQKExZNSVQgTGluY29sbiBMYWJvcmF0b3J5MQwwCgYDVQQLEwNQS0kxEzARBgNV BAMTCk1JVExMIENBLTIwHhcNMTIwMzA1MTUxODA3WhcNMTMwMzA1MTUxODA3WjBhMQswCQYD VQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEPMA0GA1UECxMGUGVv cGxlMSAwHgYDVQQDExdCbHVtZW50aGFsLlVyaS41MDAxMDU4NDCCASIwDQYJKoZIhvcNAQEB BQADggEPADCCAQoCggEBAM1hd7gYE3EAuUHpQXBAAsld4ttPFF2dJILTwLxpMAwAOeuCE2FN Qm7r5aIXSmwfYReSBSvZ01k6YOx3hqxMUJYgDTWvQ9A5OEufC3aD71g18VhHvqMs8uBEj7aX Na6dNd8V10yl4GZ4pXffNSN1Qb1S6pQ0r9NNILb+ZSevs3DGNE5rZwHxM0Ed62MjDyR4r7tL pFbkvlEFDdj8epEz7C6zEUPLyr8JjCDbLqhV4uoNdQQxweEPhSVadd5bDoT5w9OM4h4g/1hU PI/zuzp1pZLWiRigsmsCiT2YQUs3phYnRGkRzyenY3Usu+HtXtG1fSleaoeZtOqlcT01RBtP K1MCAwEAAaOCAZYwggGSMB0GA1UdDgQWBBShib6es0uFKEYxkMQRe+e7efVhBzAOBgNVHQ8B Af8EBAMCBSAwHwYDVR0jBBgwFoAUjkp9iaFjFxyBiDRXNyZFXhmKfiQwMwYDVR0fBCwwKjAo oCagJIYiaHR0cDovL2NybC5sbC5taXQuZWR1L2dldGNybC9MTENBMjBiBggrBgEFBQcBAQRW MFQwLQYIKwYBBQUHMAKGIWh0dHA6Ly9jcmwubGwubWl0LmVkdS9nZXR0by9MTENBMjAjBggr BgEFBQcwAYYXaHR0cDovL29jc3AubGwubWl0LmVkdS8wDAYDVR0TAQH/BAIwADA9BgkrBgEE AYI3FQcEMDAuBiYrBgEEAYI3FQiDg+Udh+ynZoathxWD6vBFhbahHx2F69Bwg+vtIAIBZAIB BDAlBgNVHSUEHjAcBgRVHSUABggrBgEFBQcDBAYKKwYBBAGCNwoDBDAYBgNVHSAEETAPMA0G CyqGSIb3EgIBAwEIMBkGA1UdEQQSMBCBDnVyaUBsbC5taXQuZWR1MA0GCSqGSIb3DQEBCwUA A4IBAQBqmZjWIBD5zFsLODc5rYV8zKQKukfF+u4DpNFzEHbCjNn1TBLBa0HVy1kLBA1ZwQPi cOw/XFgW8GHJo6Zpnd0NWwr02KbzJEn3wm5NmYWRTvuW9ld9O8/vkoPl0EmOfCbLoeQHNiEM lkBgoiC3nx54JaUTubWVcY7/caYldaT+VllH+y3PDB5yfO0YnAXkDbDqr+OBAM7dRe0QhcgS ZxTcRnrWGTUHwVV1yl4+Mxc++V1iLX1HdC1IdfKYHhswJbKOteuuCRLuhbKLpX/+y5cl6I/w 9u44Y86l34NExCasoNebcTzSVR5bKEWGhbntpDULl8cLMzXGlPQ5Oh614HeSMYIB5TCCAeEC AQEwXzBRMQswCQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEM MAoGA1UECxMDUEtJMRMwEQYDVQQDEwpNSVRMTCBDQS0yAgoTvp8EAAAAAEiAMAkGBSsOAwIa BQCgXTAjBgkqhkiG9w0BCQQxFgQUqhwwBi1Y7pea3ov1/FfaHr9ztYIwGAYJKoZIhvcNAQkD MQsGCSqGSIb3DQEHATAcBgkqhkiG9w0BCQUxDxcNMTIwODI0MTcxMjE3WjANBgkqhkiG9w0B AQEFAASCAQBX2ptutiAAksDYPX8oEcF1X7N/s1rYkXVjyCKzFaRKuK2OAA+voOArPC7DDWOQ omAXF0HEwF5eJftUqnhgKkgsMQ0MZ5ndZbOMGW44TFxKWto2lUXHcH9TtGn5g39L0IPTr8B3 F+ch/f/tjHQlBsU1+LFbA4bVzGA5y/PObOlNTXzBiavT+6irpRW4alfjh7SEYmcehFJW6nS1 fjobFbEYv7U56u1tRxN/uoJJgo340UgRS8nNBih2BmUkpTFwNO3VS3L2Z29ojd5OBY6/3VHC XxVLYRCxAImlbSB0tWoxzphhukw0TBz8d8n8xWeaT3n7ujd3OfuLgB9a0iQ4ktuU --B_3428658737_160858436-- From prvs=15835d3ee0=dbrown@certicom.com Fri Aug 24 11:34:32 2012 Return-Path: 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 670BE21F8613 for ; Fri, 24 Aug 2012 11:34:32 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -4.511 X-Spam-Level: X-Spam-Status: No, score=-4.511 tagged_above=-999 required=5 tests=[AWL=-0.659, BAYES_00=-2.599, J_CHICKENPOX_39=0.6, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4, SARE_OBFU_ALL=0.751] 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 MfYLRMS6tpxd for ; Fri, 24 Aug 2012 11:34:31 -0700 (PDT) Received: from mhs060cnc.rim.net (mhs060cnc.rim.net [208.65.73.34]) by ietfa.amsl.com (Postfix) with ESMTP id D982021F85A8 for ; Fri, 24 Aug 2012 11:34:30 -0700 (PDT) X-AuditID: 0a41282f-b7fbe6d000004851-08-5037c93520b6 Received: from XCT107CNC.rim.net (xct107cnc.rim.net [10.65.161.207]) by mhs060cnc.rim.net (SBG) with SMTP id 73.FC.18513.539C7305; Fri, 24 Aug 2012 13:34:29 -0500 (CDT) Received: from XCT114CNC.rim.net (10.65.161.214) by XCT107CNC.rim.net (10.65.161.207) with Microsoft SMTP Server (TLS) id 14.2.298.4; Fri, 24 Aug 2012 14:34:29 -0400 Received: from XMB111CNC.rim.net ([fe80::fcd6:cc6c:9e0b:25bc]) by XCT114CNC.rim.net ([::1]) with mapi id 14.02.0298.004; Fri, 24 Aug 2012 14:34:28 -0400 From: Dan Brown To: "'Blumenthal, Uri - 0668 - MITLL'" , "dmjacobson@sbcglobal.net" , "cfrg@irtf.org" Thread-Topic: [Cfrg] uniform random distribution in ECDH public key Thread-Index: AQHNekb3xzJbLzv3CU6oe+qYCRXyhpdZ4i+AgA1JiYCAADUvFoACJNEA///IDAA= Date: Fri, 24 Aug 2012 18:34:28 +0000 Message-ID: <810C31990B57ED40B2062BA10D43FBF50B32C7@XMB111CNC.rim.net> References: <810C31990B57ED40B2062BA10D43FBF50B2B38@XMB111CNC.rim.net> In-Reply-To: Accept-Language: en-CA, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.65.160.246] Content-Type: text/plain; charset="us-ascii" content-transfer-encoding: quoted-printable MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrNKsWRmVeSWpSXmKPExsXC5bjwvK7pSfMAg8mLFS26fxxksmg6tpnd 4va3cgdmj8kbD7N5bHr5hM1j/f/FrAHMUQ2MNkmJJWXBmel5+nY2iXl5+SWJJakKKanFybZK PqnpiTkKAUWZZYnJlQoumcXJOYmZualFSgqZKbZKJkoKBTmJyam5qXkltkqJBQWpeSlKdlwK GMAGqCwzTyE1Lzk/JTMv3VbJM9hf18LC1FLXUMlON6GTJ2PRguOMBa+tK1beOcfSwNhn0MXI ySEhYCLx58BHNghbTOLCvfVANheHkMAqRon5b3azQzgrGSX6jr1jgXDmMEr8n7uQCaSFTUBV 4v7Rc8wgCRGByYwSOxt2sIAkhAWcJP5MXcYOYosIOEvs63/GBGH7SZzb2MsIYrMANV/90M0K YvMKuElcOvcczBYSSJd4frADqJeDg1NAW6L9YDVImFFAVmL32etgY5gFxCVuPZnPBHG2gMSS PeeZIWxRiZeP/7FC2IoST05eY4Go15FYsPsTG4StLbFs4WtmiLWCEidnPmGBWKsgceX6PpYJ jOKzkKyYhaR9FpL2WUjaFzCyrGIUzM0oNjAzSM5L1ivKzNXLSy3ZxAhOKhr6Oxjfvrc4xCjA wajEw/t3nXmAEGtiWXFl7iFGCQ5mJRFeAT+gEG9KYmVValF+fFFpTmrxIUYLYABNZJbiTs4H Jry8knhjAwMUjpI4L6OHUQAwtIBpKTs1tSC1CKaViYMTZDSXlEgxMLmkFiWWlmTEg1JgfDEw CUo1MJZ++5/CVTNH53H5Yv2XYnnil3n2tm5QuPV6W9C581bLotj+bzdINPu50j1k3UqH7euq PaY61ScYTti0MqtTVu7ZZRmf6KviZ2p63296K5xx+IKMT9z/Oi3Lfka3xncnn2dmxLp+fet/ w+SS3V5+axvhbrXpW3T+b2o8dUGz4cmUyjKu2cEv9iuxFGckGmoxFxUnAgAeqY2RXgMAAA== 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 24 Aug 2012 18:34:32 -0000 Hi Uri, Thanks for the response. Regarding your point about pseudorandomness: would you confirm that you mere= ly mean that the SHA-1 and SHA-2 standards do not claim the functions to hav= e "pseudorandom" (ignoring definability and provability see below *), and th= at 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 o= racle proofs (if they use the term "hash function", which implicitly include= s 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 crea= ted 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 ps= eudorandomness of SHA-1 (at least relevant pseudorandomness, see **), and of= SHA-2, means that their use in the KDF is a definite general-purpose improv= ement 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 d= oes add value. (*) Definability and provability: it's hard (if not impossible) to even defi= ne 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 lea= st 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 outp= ut has some bias, this is the main obstacle to defining pseudorandomness (se= e * above). A distinguisher would need to be faster than a distinguisher fo= r a random oracle. I suppose that the SHA-1 collision algorithms can be vie= wed as a distinguisher, though not with any impact on most typical pseudoran= dom hash applications such as KDF. Is there a more direct distinguisher for= SHA-1 or SHA-2? Daniel Brown Research In Motion Limited > -----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" 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 > >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 uniforml= y > >>> 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 =3D 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 tha= t > >> 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 infor= mation, privileged material (including material protected by the solicitor-c= lient 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 immedia= tely reply to the sender and delete this information from your system. Use,= dissemination, distribution, or reproduction of this transmission by uninte= nded recipients is not authorized and may be unlawful. From prvs=9583242b3b=uri@ll.mit.edu Fri Aug 24 11:46:36 2012 Return-Path: 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 ; 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 ; 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 ; 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" To: Dan Brown , "dmjacobson@sbcglobal.net" , "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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 24 Aug 2012 18:46:37 -0000 --B_3428664388_161164784 Content-type: text/plain; charset="US-ASCII" Content-transfer-encoding: 7bit >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" 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 >> >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. --B_3428664388_161164784 Content-Type: application/pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" MIIUAAYJKoZIhvcNAQcCoIIT8TCCE+0CAQExCzAJBgUrDgMCGgUAMAsGCSqGSIb3DQEHAaCC EeMwggTLMIIDs6ADAgECAgoTvp8EAAAAAEiAMA0GCSqGSIb3DQEBCwUAMFExCzAJBgNVBAYT AlVTMR8wHQYDVQQKExZNSVQgTGluY29sbiBMYWJvcmF0b3J5MQwwCgYDVQQLEwNQS0kxEzAR BgNVBAMTCk1JVExMIENBLTIwHhcNMTIwNzE2MTgwNzA2WhcNMTMwNzE2MTgwNzA2WjBhMQsw CQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEPMA0GA1UECxMG UGVvcGxlMSAwHgYDVQQDExdCbHVtZW50aGFsLlVyaS41MDAxMDU4NDCCASIwDQYJKoZIhvcN AQEBBQADggEPADCCAQoCggEBALQbhERcgi7bVsw6WLXunsi9ymPD09JMrF1iGlCDF4ZO1+W5 Lp6znDFyubLdbP3qikgcXWfByMzsHUzoSQD1Bp9O7mKa656rMu3mez/ItydJBw/LMZYSYc+6 4DB4KuzvA2DnTaQ41I0SqFE0DrksfBi8ePO/Xv7PQRNUl45Y7VSB6xoA7DfTZO5IZ4e6Om90 /AnVBE+aee40kxvmDWGr1jvFxv/gSvQA3PxcwnCxzn699bpAtz8VUdfTsewhy+g5OonBLSzg I/yIyCd6g2eQQcw6g10eQJopUnoKv1o0TIss1pwK5SZG3mM2FCFECL1vV8NMTQ4AuS3OSO7i 3AX2g1cCAwEAAaOCAZMwggGPMB0GA1UdDgQWBBSw8IXAP4OJKTOqBKNPgRR1LceLVzAOBgNV HQ8BAf8EBAMCBsAwHwYDVR0jBBgwFoAUjkp9iaFjFxyBiDRXNyZFXhmKfiQwMwYDVR0fBCww KjAooCagJIYiaHR0cDovL2NybC5sbC5taXQuZWR1L2dldGNybC9MTENBMjBiBggrBgEFBQcB AQRWMFQwLQYIKwYBBQUHMAKGIWh0dHA6Ly9jcmwubGwubWl0LmVkdS9nZXR0by9MTENBMjAj BggrBgEFBQcwAYYXaHR0cDovL29jc3AubGwubWl0LmVkdS8wDAYDVR0TAQH/BAIwADA9Bgkr BgEEAYI3FQcEMDAuBiYrBgEEAYI3FQiDg+Udh+ynZoathxWD6vBFhbahHx2Fy94yh/+KcwIB ZAIBBTAiBgNVHSUBAf8EGDAWBggrBgEFBQcDBAYKKwYBBAGCNwoDDDAYBgNVHSAEETAPMA0G CyqGSIb3EgIBAwEIMBkGA1UdEQQSMBCBDnVyaUBsbC5taXQuZWR1MA0GCSqGSIb3DQEBCwUA A4IBAQCheTHY3ppuUbzU5Quma4TR1Rhr0r+BfIMJyrfrmA9gNIoFzK0MbK1xxRv/9Nz/9sRQ ukIWIIfjyQlNDIiCl+8yut3V31v5NW+T0NB4GGIYicWI+ID8tBfvaHaniZ+bP/wEsZMOPq1J kh4E28mRAsHMuYhu6kraGj0yRi4Y3zuxJIeRN7NGYFCglFaPSeOQ33m0o5oyyMNfdDcDX7T/ 3pSSNFk/gAcPoI+XvC0sXS2cVYqvDGwzsT58M+6jvg0FDb8z/BIO2OL2KpO+ojeNSNud4Cf4 7gEpChuvx36vgLLq+J1s9BIXKk7FVAIdbD5KKnO/HiDpqamScI6p3Lc3PQZuMIIEtzCCA5+g AwIBAgIBFDANBgkqhkiG9w0BAQsFADBUMQswCQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExp bmNvbG4gTGFib3JhdG9yeTEMMAoGA1UECxMDUEtJMRYwFAYDVQQDEw1NSVRMTCBSb290IENB MB4XDTA5MTIxNDEyMDAwMFoXDTE1MTIzMTIzNTk1OVowUTELMAkGA1UEBhMCVVMxHzAdBgNV BAoTFk1JVCBMaW5jb2xuIExhYm9yYXRvcnkxDDAKBgNVBAsTA1BLSTETMBEGA1UEAxMKTUlU TEwgQ0EtMjCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBAKcEyyNhSIfsN6AzBwVh Zkzo6SdjNGAQ7mA2A8T0kmdCB8MH6jWjVVMwFZwlg9cgjgLKEuEO9KN8K9M8jgeZEMoinlRf k3YELPC7sEkkzBQkcVpLhEwALue9iHowgSLGmXZpYKmRhfvhvYJ4MNCuIaWpcK/GaDZCE+U2 aTg42kv/zQrH3AoqFX81OF7niwXNnanP1hQRfkMTRrnaEW8DX0TMaG/t9Ry5xSMrLTNc9DvQ tjA5ZcuWnECiUpyDBFWxLr9yx7xgf1/LwgCxcoBeKSBBoWzkQmKAsgMo9Mq1Fp/nnIqw5FKm gOs7Vy+6e0Dk+cgf+oAV8AK8ZFMQrVE0uH0CAwEAAaOCAZUwggGRMBIGA1UdEwEB/wQIMAYB Af8CAQAwHQYDVR0OBBYEFI5KfYmhYxccgYg0VzcmRV4Zin4kMB8GA1UdIwQYMBaAFGeqes/0 Cqa5crWKoNKd8hDDQ+0pMA4GA1UdDwEB/wQEAwIBhjBhBggrBgEFBQcBAQRVMFMwLQYIKwYB BQUHMAKGIWh0dHA6Ly9jcmwubGwubWl0LmVkdS9nZXR0bz9MTFJDQTAiBggrBgEFBQcwAYYW aHR0cDovL29jc3AubGwubWl0LmVkdTAzBgNVHR8ELDAqMCigJqAkhiJodHRwOi8vY3JsLmxs Lm1pdC5lZHUvZ2V0Y3JsP0xMUkNBMIGSBgNVHSAEgYowgYcwDQYLKoZIhvcSAgEDAQYwDQYL KoZIhvcSAgEDAQgwDQYLKoZIhvcSAgEDAQcwDQYLKoZIhvcSAgEDAQkwDQYLKoZIhvcSAgED AQowDQYLKoZIhvcSAgEDAQswDQYLKoZIhvcSAgEDAQ4wDQYLKoZIhvcSAgEDAQ8wDQYLKoZI hvcSAgEDARAwDQYJKoZIhvcNAQELBQADggEBAIh3BqHQ/XH8C6DCL+eEGroOzxBcCqTNItms v4MANaOTodgU2jrjHcGjXlzqhpb8ZxOlkAK3dK09rc6+yACcoK2TzVtDRZXYxov/SqZRjI3d ufU2JatAPxosCyy/1otjl1TKUY47Wvft31vdf5i0XK2DQVEJ+XlqtgBiFTVIMIfBJwPajrsi z+pgFEYwhhwJxvs8flSi0FLCE77VYLEioP5hxG6zIPeQRxzh1bogbfphWHHtoiTDkBSZ4Ufv GXQTVf7QjhD5yYw10yICtjHmtgbfgBkH5/vvR92NY9RSlNPzZqmGKIia61bJCmagRYGyexfe dVNF0cJWL4J/cLHhgNYwggODMIICa6ADAgECAgEBMA0GCSqGSIb3DQEBBQUAMFQxCzAJBgNV BAYTAlVTMR8wHQYDVQQKExZNSVQgTGluY29sbiBMYWJvcmF0b3J5MQwwCgYDVQQLEwNQS0kx FjAUBgNVBAMTDU1JVExMIFJvb3QgQ0EwHhcNMDgwOTIzMTIwMDAwWhcNMjkxMjMxMjM1OTU5 WjBUMQswCQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEMMAoG A1UECxMDUEtJMRYwFAYDVQQDEw1NSVRMTCBSb290IENBMIIBIjANBgkqhkiG9w0BAQEFAAOC AQ8AMIIBCgKCAQEAxU4pF1iyJrL5rYq/XBAKg93kCTATG7Bw0NGFpEJ1A3Xsr6UIIq9/1VJB OgCwDqrVsAK1lRwy/lkrHzPkobiMr1wzjQ28SR/9sg5kAcmrMqBYbc302qtwCGKZxdNdhAh2 nUOCO10AMpUsCNdpikPY9ukT8lsA+eorM4Q1rc/L0J6AHRptOU7IuDBdZj+tdNb7gv+GKknr 6wj9m2sVGawoaG7AAqhsWvQUM/q4h/H5FpYlwnVAEh2AzhqiG9bwl6uJJIzJ/8uUWldNkVwz 1I5fR/vCaxiLXIW4oUydBuRKTG+ekEoxHGuD73yx5JtsSciS8HQL2oEM8tv+VAC+albqgwID AQABo2AwXjAPBgNVHRMBAf8EBTADAQH/MB0GA1UdDgQWBBRnqnrP9AqmuXK1iqDSnfIQw0Pt KTAfBgNVHSMEGDAWgBRnqnrP9AqmuXK1iqDSnfIQw0PtKTALBgNVHQ8EBAMCAYYwDQYJKoZI hvcNAQEFBQADggEBAD4bbQVg0Hh42EpYX4/JPkNS3OUAEWR/YgzZUY1QGi9rQZ4pfcjU1/Ta oNT8Y7Yf0RO+e9NiG9+BDhQH/kQiZOQo9rv9NUb8xDtKCYCad7zEQtVsYsWuvK2XLw/Ji1m2 eBvoOB4RS/5LAWfNws7W+DWt2ayzeTCyrLSrx7ZVgBjzNOm0TPIkbfppdwgxuo7FZL8ts+M2 492Al87d3VasevUS1pprRBEupChmPTt1hjtajkQOpT4BQAzP1lVEYrWzlv+O/lbP9iujKpYW cfYqQ3FGf37YCvuDeues4xm+nqmyraNsNeI8Gh3XDIwqfzHnLhy4Y80VyqN/Jj8df3SK9AAw ggTOMIIDtqADAgECAgpDgT5qAAAAADKHMA0GCSqGSIb3DQEBCwUAMFExCzAJBgNVBAYTAlVT MR8wHQYDVQQKExZNSVQgTGluY29sbiBMYWJvcmF0b3J5MQwwCgYDVQQLEwNQS0kxEzARBgNV BAMTCk1JVExMIENBLTIwHhcNMTIwMzA1MTUxODA3WhcNMTMwMzA1MTUxODA3WjBhMQswCQYD VQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEPMA0GA1UECxMGUGVv cGxlMSAwHgYDVQQDExdCbHVtZW50aGFsLlVyaS41MDAxMDU4NDCCASIwDQYJKoZIhvcNAQEB BQADggEPADCCAQoCggEBAM1hd7gYE3EAuUHpQXBAAsld4ttPFF2dJILTwLxpMAwAOeuCE2FN Qm7r5aIXSmwfYReSBSvZ01k6YOx3hqxMUJYgDTWvQ9A5OEufC3aD71g18VhHvqMs8uBEj7aX Na6dNd8V10yl4GZ4pXffNSN1Qb1S6pQ0r9NNILb+ZSevs3DGNE5rZwHxM0Ed62MjDyR4r7tL pFbkvlEFDdj8epEz7C6zEUPLyr8JjCDbLqhV4uoNdQQxweEPhSVadd5bDoT5w9OM4h4g/1hU PI/zuzp1pZLWiRigsmsCiT2YQUs3phYnRGkRzyenY3Usu+HtXtG1fSleaoeZtOqlcT01RBtP K1MCAwEAAaOCAZYwggGSMB0GA1UdDgQWBBShib6es0uFKEYxkMQRe+e7efVhBzAOBgNVHQ8B Af8EBAMCBSAwHwYDVR0jBBgwFoAUjkp9iaFjFxyBiDRXNyZFXhmKfiQwMwYDVR0fBCwwKjAo oCagJIYiaHR0cDovL2NybC5sbC5taXQuZWR1L2dldGNybC9MTENBMjBiBggrBgEFBQcBAQRW MFQwLQYIKwYBBQUHMAKGIWh0dHA6Ly9jcmwubGwubWl0LmVkdS9nZXR0by9MTENBMjAjBggr BgEFBQcwAYYXaHR0cDovL29jc3AubGwubWl0LmVkdS8wDAYDVR0TAQH/BAIwADA9BgkrBgEE AYI3FQcEMDAuBiYrBgEEAYI3FQiDg+Udh+ynZoathxWD6vBFhbahHx2F69Bwg+vtIAIBZAIB BDAlBgNVHSUEHjAcBgRVHSUABggrBgEFBQcDBAYKKwYBBAGCNwoDBDAYBgNVHSAEETAPMA0G CyqGSIb3EgIBAwEIMBkGA1UdEQQSMBCBDnVyaUBsbC5taXQuZWR1MA0GCSqGSIb3DQEBCwUA A4IBAQBqmZjWIBD5zFsLODc5rYV8zKQKukfF+u4DpNFzEHbCjNn1TBLBa0HVy1kLBA1ZwQPi cOw/XFgW8GHJo6Zpnd0NWwr02KbzJEn3wm5NmYWRTvuW9ld9O8/vkoPl0EmOfCbLoeQHNiEM lkBgoiC3nx54JaUTubWVcY7/caYldaT+VllH+y3PDB5yfO0YnAXkDbDqr+OBAM7dRe0QhcgS ZxTcRnrWGTUHwVV1yl4+Mxc++V1iLX1HdC1IdfKYHhswJbKOteuuCRLuhbKLpX/+y5cl6I/w 9u44Y86l34NExCasoNebcTzSVR5bKEWGhbntpDULl8cLMzXGlPQ5Oh614HeSMYIB5TCCAeEC AQEwXzBRMQswCQYDVQQGEwJVUzEfMB0GA1UEChMWTUlUIExpbmNvbG4gTGFib3JhdG9yeTEM MAoGA1UECxMDUEtJMRMwEQYDVQQDEwpNSVRMTCBDQS0yAgoTvp8EAAAAAEiAMAkGBSsOAwIa BQCgXTAjBgkqhkiG9w0BCQQxFgQUbQMdOIsap0M0e1l9IIN+1W59IwEwGAYJKoZIhvcNAQkD MQsGCSqGSIb3DQEHATAcBgkqhkiG9w0BCQUxDxcNMTIwODI0MTg0NjI4WjANBgkqhkiG9w0B AQEFAASCAQByTa/KWdG8mf3MPMDFLGv+hw/ijCxoUZBSTu6yShvV2OhyUbNHeou3njd1DDBC JVeuNf5tWx9fM7qb/Wsmwp4CbCmfQMlup5s0jhK1GdEPP55/ONS22xGieHlP1gUKIgwIXV4H 6tynEiv8syJVNiueBLNtZdwYwRZpTCcCvTBcjD/tDO4MDaDaRdxbRKTvXzNQ3mkEsingA6w3 /QOyW/OeRFvUZJB+/k/Yc+CpJDx4LgqdHPh0Fy2wdvxfGurnn1zf2MUCM125mgyXisdOvDB9 eSm2k6QwhC/OjMpDfBvbnimRnwtrbmIAD4+oA5cT7R+FqGWLcKwG3DG/IsCsVhs6 --B_3428664388_161164784-- From prvs=9583e548da=dbrown@certicom.com Fri Aug 24 13:08:02 2012 Return-Path: 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 F351C21F8469 for ; Fri, 24 Aug 2012 13:08:01 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -4.729 X-Spam-Level: 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 mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id x1jT97KK5pwz for ; Fri, 24 Aug 2012 13:08:01 -0700 (PDT) Received: from mhs061cnc.rim.net (mhs061cnc.rim.net [208.65.73.35]) by ietfa.amsl.com (Postfix) with ESMTP id D0F5121F8463 for ; Fri, 24 Aug 2012 13:08:00 -0700 (PDT) X-AuditID: 0a412830-b7f996d000004398-1f-5037df1d5cb8 Received: from XCT101CNC.rim.net (xct101cnc.rim.net [10.65.161.201]) (using TLS with cipher AES128-SHA (AES128-SHA/128 bits)) (Client did not present a certificate) by mhs061cnc.rim.net (SBG) with SMTP id C8.11.17304.D1FD7305; Fri, 24 Aug 2012 20:07:57 +0000 (GMT) Received: from XMB111CNC.rim.net ([fe80::fcd6:cc6c:9e0b:25bc]) by XCT101CNC.rim.net ([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'" , "dmjacobson@sbcglobal.net" , "cfrg@irtf.org" 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: <810C31990B57ED40B2062BA10D43FBF50B3389@XMB111CNC.rim.net> References: <810C31990B57ED40B2062BA10D43FBF50B32C7@XMB111CNC.rim.net> In-Reply-To: Accept-Language: en-CA, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.65.160.246] 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-BeenThere: cfrg@irtf.org 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 [mailto:uri@ll.mit.edu] > Sent: Friday, August 24, 2012 2:46 PM > To: Dan Brown; dmjacobson@sbcglobal.net; cfrg@irtf.org > 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, mor= e 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, su= ch as ANSI X9F1, also had some level of comfort with the security of these e= xtensions, and included member with fairly close connections to their design= ers 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. Ps= eudorandomness was required to cover the widespread use of hashes for random= izing. So, any SHA-3 submissions that sacrificed pseudorandomness, for what= ever 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 pseudorandomn= ess (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 (=3D "abunda= nt") 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 distin= guisher (being widely and publicly known) does prove something. This is wh= at I meant by "incentive". So, the fact cryptanalysts could have found and= published distinguisher on these hash functions and thereby broken the prot= ocols that use them, and this has not been, proves either no cryptanalysts t= ried 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 be= cause I haven't heard about such an attack, and that because I usually someh= ow hear about a major attacks (e.g. I'm on the SHA-3 mailing list, I check e= print.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. --------------------------------------------------------------------- This transmission (including any attachments) may contain confidential infor= mation, privileged material (including material protected by the solicitor-c= lient 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 immedia= tely reply to the sender and delete this information from your system. Use,= dissemination, distribution, or reproduction of this transmission by uninte= nded recipients is not authorized and may be unlawful. From dmjacobson@sbcglobal.net Fri Aug 24 21:13:04 2012 Return-Path: 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 1531421F84C2 for ; Fri, 24 Aug 2012 21:13:04 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] 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 Cm5xEgN28mCF for ; Fri, 24 Aug 2012 21:13:03 -0700 (PDT) Received: from nm30-vm0.access.bullet.mail.sp2.yahoo.com (nm30-vm0.access.bullet.mail.sp2.yahoo.com [98.139.44.194]) by ietfa.amsl.com (Postfix) with SMTP id 7A80721F84A7 for ; Fri, 24 Aug 2012 21:13:03 -0700 (PDT) Received: from [98.139.44.97] by nm30.access.bullet.mail.sp2.yahoo.com with NNFMP; 25 Aug 2012 04:12:59 -0000 Received: from [98.139.44.68] by tm2.access.bullet.mail.sp2.yahoo.com with NNFMP; 25 Aug 2012 04:12:59 -0000 Received: from [127.0.0.1] by omp1005.access.mail.sp2.yahoo.com with NNFMP; 25 Aug 2012 04:12:59 -0000 X-Yahoo-Newman-Id: 957864.12409.bm@omp1005.access.mail.sp2.yahoo.com Received: (qmail 36896 invoked from network); 25 Aug 2012 04:12:59 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=sbcglobal.net; h=DKIM-Signature:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=AG1Pq+75EnpM1NaKdN/zvjUOf1n4cMDeltGZEIDuzt7By5i1dGdmL3msbA8lS5mzZI9LG8CUj5oL9+OBQHQz4GD5bXJuue5jUfUUkzVnfssX27GdXPwUkMEcsB9AVh62YerRs24TB4rB9cpMAT8oVxHgzu23xZOKSjoGbgnBUxM= ; DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1345867979; bh=3tjD+sj+zF7x8cdHtDkyk2GAwhGqclkUjkdo4OhUK3E=; h=X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=CuQpOOHi6U/pLLBc6zygpvrgh0jzWh56v3IIZ8XITbRN8YRT1VjmB6PjoAHuNK3iY3MVZZhtFYObkacYTUHtpuzSqn/Pujx9R07aP5ZWn5w50nW1OQWYJ2b4oN0XyZHDew2ixyHpL0R418yUN8F8HtR6Qr0VbLSQJqC4xwkGV8c= X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: YWlfDMwVM1mM83lg_WSODumwS2LhVWQjzqY.SYU5UOW8kfz MAdFS2WUezlCTSVk4D9kl6ABNBiPs3e1CrayCwceKHr22k0IEGJhVCNMd9gO LLkmq5EVSM2iAEdbKow.BY52K7P75ooKjmI_3y9euDQ9n.K76XGBevvLc7kf h_E3A0YSOzB8hudz9edu12CillmYLPTXcG8z7PMxUEI6iuZX2nYnQupHK10j 1NUdSE23fjzV.aiNR7pUZsYgsrCNIyfJyqEfAZP9nKXrvipp_9caI4.vp2lf 7E67ibxb2cCCKSOBS8K2ymKvgi_tPBKxWTfVswQPF8fQVmTAjPX73FCmL8Zf 8rSLpE7QadLANiFSGxT79YyFI239uON0VCMDGJtqBsT0LMTzaJkMaOKwLaj9 94WB_VfPtZU3.5uHnN1NoUGH8vGj34JxTyVM3zVeD0ke_lUOFd.XmX3Kyq.G 7vhkLsBOhER3.12gzvvRvpreml10- X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g-- Received: from [192.168.1.73] (dmjacobson@99.120.98.171 with plain) by smtp107.sbc.mail.gq1.yahoo.com with SMTP; 24 Aug 2012 21:12:59 -0700 PDT Message-ID: <503850C9.8000608@sbcglobal.net> Date: Fri, 24 Aug 2012 21:12:57 -0700 From: David Jacobson User-Agent: Mozilla/5.0 (X11; Linux i686; rv:14.0) Gecko/20120714 Thunderbird/14.0 MIME-Version: 1.0 To: Dan Brown References: <810C31990B57ED40B2062BA10D43FBF50B32C7@XMB111CNC.rim.net> <810C31990B57ED40B2062BA10D43FBF50B3389@XMB111CNC.rim.net> In-Reply-To: <810C31990B57ED40B2062BA10D43FBF50B3389@XMB111CNC.rim.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: "cfrg@irtf.org" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 25 Aug 2012 04:13:04 -0000 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