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

"Dan Harkins" <dharkins@lounge.org> Tue, 14 August 2012 18:58 UTC

Return-Path: <dharkins@lounge.org>
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 <cfrg@ietfa.amsl.com>; 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 <cfrg@ietfa.amsl.com>; 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 <cfrg@irtf.org>; 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: <def0111a5e81f715d26eb4a6c426295e.squirrel@www.trepanning.net>
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" <dharkins@lounge.org>
To: "Robert Moskowitz" <rgm-sec@htt-consult.com>
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 <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: 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.