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

David Jacobson <dmjacobson@sbcglobal.net> Sat, 25 August 2012 04:13 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 <cfrg@ietfa.amsl.com>; 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 <cfrg@ietfa.amsl.com>; 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 <cfrg@irtf.org>; 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 <dmjacobson@sbcglobal.net>
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:14.0) Gecko/20120714 Thunderbird/14.0
MIME-Version: 1.0
To: Dan Brown <dbrown@certicom.com>
References: <810C31990B57ED40B2062BA10D43FBF50B32C7@XMB111CNC.rim.net> <CC5D419E.F533%uri@ll.mit.edu> <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" <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 <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: 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