Re: [Cfrg] Interest in an "Ed25519-HD" standard?

Tony Arcieri <bascule@gmail.com> Wed, 22 March 2017 20:47 UTC

Return-Path: <bascule@gmail.com>
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 CC20812778D for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 13:47:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 CAuOy3ibhjGx for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 13:47:54 -0700 (PDT)
Received: from mail-pg0-x233.google.com (mail-pg0-x233.google.com [IPv6:2607:f8b0:400e:c05::233]) (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 31AB6128BBB for <cfrg@irtf.org>; Wed, 22 Mar 2017 13:47:54 -0700 (PDT)
Received: by mail-pg0-x233.google.com with SMTP id g2so112151134pge.3 for <cfrg@irtf.org>; Wed, 22 Mar 2017 13:47:54 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=OnDY52H5VCWQL1vF0HLjux/fC3bwnGSyyh0Fse5T1wI=; b=mnLU7/fj5bF4vHjkMaO808OKmnABsdVgrc1nXFGvRfjuXMDNuvqv36VHTUUELn96NE W3TF4nRJjGhosfI9tn7dfiOIfZz8OYwGybNb+1E2xnEnyxPPFvHbnAskoGAAmN75aQZj RFyny+eOYdfh2UPnHmTkwUfZ+ajmJEuCEml+hbg8kl1+eERVtEFUiiMUsmLmwz2X6lqS AmzJ7k1OTpm/VA7ZiQG0RCxAs4zjBaKX7BsbmAO8diq4+FWHKO/ihSuuoqv7MqF0JF1r hbtgKAnGQr02xpzBkmHYDXkyNi0v9VdC8HKI6EeOyeH6nfhwxYejqry0GaaBcO4Jbgd1 TOlA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=OnDY52H5VCWQL1vF0HLjux/fC3bwnGSyyh0Fse5T1wI=; b=JeGcSbsNkrsuh6M+4HyUm2sJsuHh1VbmhiXKOABWeO0ChDfuHl+0gjOGN03GHv5t9Z Ige/QKx9l4DMHlncSmevo44JiIMIkGPItfngwJp3TpCvLthdSKiOWXVwMnND8SgHhohF JYAui5pKQYl8xaAIFwWxlKKyDCMx5gSI02CZ5cASEipPIGAPHcW7gxcH73hWwo+Juija yOUYCIzkd2XA3pPcl/qc/WXFbYABf9NjxFucU/C9EaENKxVcO/jJ43XU9sawptbx6RpF EEWM3xQlJfJ70fFD/mBMADcNGjjmPpIoG9aY/ncYBvLqpFb1bi/Rm/uC51BzXs9cXToW 9xpQ==
X-Gm-Message-State: AFeK/H1s6wTQY6cNEf0uEw9ihl5geaPIa804AvyCaMxIkpzPlz4odLeS94S1M0apljIK+cs/1rAPUoX+PV2NDg==
X-Received: by 10.99.247.83 with SMTP id f19mr12789152pgk.158.1490215673808; Wed, 22 Mar 2017 13:47:53 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.100.178.234 with HTTP; Wed, 22 Mar 2017 13:47:33 -0700 (PDT)
In-Reply-To: <CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com>
References: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com> <CAMm+Lwgm8XzTBarZ1eFePTZGORorBJAeF7brDkhWGQKQVT0LPQ@mail.gmail.com> <CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com>
From: Tony Arcieri <bascule@gmail.com>
Date: Wed, 22 Mar 2017 13:47:33 -0700
Message-ID: <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=001a114c325ce04dec054b57df9a
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/vUVh-QXVozNrEgWzd6XeZTqrTBY>
Subject: Re: [Cfrg] Interest in an "Ed25519-HD" standard?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Wed, 22 Mar 2017 20:47:56 -0000

On Tue, Mar 21, 2017 at 9:00 PM, Phillip Hallam-Baker <phill@hallambaker.com
> wrote:

> You can do hierarchical key derivation in Montgomery without the need for
> an add.
>
> Say your master key is x. To generate a key for site 'example.com' we
> take
>
> xs = (x + H('example.com')) mod q
>
> Where q is the sub group order.
>
> In fact that isn't really using any EC relevant operation at all. Perhaps
> I am not understanding the full requirements for the scheme.
>

One of the goals of the scheme is unlinkability: given a set of candidate
keys, some of which are children of the same parent key, and others
randomly generated, an attacker should not be able to do better than chance
in determining which keys in the candidate set have the same parents.

For example, Tor hidden services will be identified by constantly rotating
"epoch keys". To find the "epoch key" for a given hidden service, a user in
possession of the parent public key derives a child key offline from the
parent key. However, it'd be undesirable for someone not in possession of
the parent key to be able to link the child epoch keys together and
enumerate hidden services without knowledge of their parent public keys.

In your scheme, given z=H("example.com"), and a parent key xG, the derived
child key would be (x+z)G. To recover the original parent public key, you
can simply subtract out zG and recover xG. To prevent this from happening
we need to use an operation which is not easily reversible, hence
multiplication

-- 
Tony Arcieri