[Cfrg] Should Ed25519 use a pseudo-random generator point?

Bill Cox <waywardgeek@gmail.com> Sun, 25 October 2015 13:52 UTC

Return-Path: <waywardgeek@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DA9631B2F0C for <cfrg@ietfa.amsl.com>; Sun, 25 Oct 2015 06:52:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.1
X-Spam-Level:
X-Spam-Status: No, score=-0.1 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id I6PHpTW6-GMX for <cfrg@ietfa.amsl.com>; Sun, 25 Oct 2015 06:52:19 -0700 (PDT)
Received: from mail-ob0-x232.google.com (mail-ob0-x232.google.com [IPv6:2607:f8b0:4003:c01::232]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5CDFF1B2EF8 for <cfrg@irtf.org>; Sun, 25 Oct 2015 06:52:19 -0700 (PDT)
Received: by obctp1 with SMTP id tp1so97564305obc.2 for <cfrg@irtf.org>; Sun, 25 Oct 2015 06:52:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=CxWZtUcrY4wLL9qJdsXh1pu8yzPNFwsHYXoZeW9hyGM=; b=rBtQhhqJzl2OavLKOQFrUBFqPQFwMacUiAQCW7bXK7IJLr/orxFt4cI4i1k5v81Pby 31kYVmJwdMJk6J9unKi0YxyfxrbAHnAJHOjX6KA8egCqZxjcradPRYHYQo0kKneXgZV0 pJQG6ZzJ9tqyOZxO2SYk4ZCO3pGffjMJrGZ2bRW2CaQcWt44/6c1jQ/rDcN3DwR5Dy1V PAfr/W7cYMbJp+l1IW9TBeyhbMVP2OdTlQVBQoiksIkkDiIGrkIVfYux3hb3xDjLZGRD IiHTm+1OoFh1e5JYg073M0B0gwQm4uZtTCT/5z3Gpl0TbhR5iAhfzPfg/foYbNCevhsR 7Mbw==
MIME-Version: 1.0
X-Received: by 10.60.164.73 with SMTP id yo9mr20861313oeb.33.1445781138687; Sun, 25 Oct 2015 06:52:18 -0700 (PDT)
Received: by 10.60.5.47 with HTTP; Sun, 25 Oct 2015 06:52:18 -0700 (PDT)
Date: Sun, 25 Oct 2015 06:52:18 -0700
Message-ID: <CAOLP8p7Q_+CgWzqSN=gN_wjSkUFVOR8t7xq0WiGuBKmyrRzarA@mail.gmail.com>
From: Bill Cox <waywardgeek@gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="047d7b450b7e31cfe20522ee2730"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/u1EGqaRbiCeYUo0Qclr71VbZu8s>
Subject: [Cfrg] Should Ed25519 use a pseudo-random generator point?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 25 Oct 2015 13:52:21 -0000

Sorry again for my arm-chair level of crypto knowledge.  I think the answer
is "no", especially given how far Ed25519 is along the standardization
path, but here's my arm-chair concern anyway.  Does using 4/5 as the X
coordinate of the generator have speed benefits or any other benefit?

I am concerned that using 4/5 as the X-coordinate might lead to an attack
someday.  I think this is _very_ unlikely, but is it worth worrying about?
Instead of using 4/5 for g's X coordinate, we could use SHA256(n), where n
is the smallest non-negative integer that puts g in the right group.

When we know the rational X coordinate of the generator point g, then we
can easily map any point m*g to m*h, where h is very to the origin.  On the
actual curve, not mod p, the point m*h would wrap around the curve
typically at most once, given any m < p.  While this seems to mean nothing
mod p, given floating-point representations of m*g on the curve, it is
easier to compute m without wrapping around the curve many times.  I am not
saying this implies anything about ECC security in any way, but it makes me
go "hmm..."

Given this lame geometric insight, and also how the NIST curves did not
offer any justification for how their generator points were derived, I am
concerned that there might be some weakness in ECC that can only be
exploited when we know the rational X-coordinate of the generator.  Is
there any harm in using a generator with a pseudo-random X coordinate?

Bill