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

Phillip Hallam-Baker <phill@hallambaker.com> Wed, 22 March 2017 21:53 UTC

Return-Path: <hallam@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 BF0171289B0 for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 14:53:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.401
X-Spam-Level:
X-Spam-Status: No, score=-2.401 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.197, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, 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 pBND-oflIwVk for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 14:53:50 -0700 (PDT)
Received: from mail-oi0-x22a.google.com (mail-oi0-x22a.google.com [IPv6:2607:f8b0:4003:c06::22a]) (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 6FC0E1294B5 for <cfrg@irtf.org>; Wed, 22 Mar 2017 14:53:35 -0700 (PDT)
Received: by mail-oi0-x22a.google.com with SMTP id w81so55902070oig.1 for <cfrg@irtf.org>; Wed, 22 Mar 2017 14:53:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=MfXBcXyYng3HGGIMAFEGY0xjCfEanLWz5XaiwlcrPxE=; b=nhLWfWoZwukt/CNPpz+7HHm5UeZhqEja7OkACfLaYqj8oph1LKFJasWv+1B3UxM+JK hzkNsplRgMnBL6+KQMcFcro9NydBD8y/uGK46IHNpC9rd1TZGj02jTkwhsw0kcpJmkuN ecQ61PzixYZlZphgXhI5hPK4McGLx09/85wCEKEKcojfg4TKST0NXOLDYtZA6kYqA+Yc Ds7IWDwpUEK0Rvem4na1DmND6YEAevmax4P2xYWxQZ166+w4loKwToO7XYx1HJ4GNuNe gHEidJRSUyyf/hVX3DWdcCZNAOiLrG1XIJV8uT4D47dTZAIUn2/r0sIXltAK2Jf46IuZ 7HUw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=MfXBcXyYng3HGGIMAFEGY0xjCfEanLWz5XaiwlcrPxE=; b=HQuJB60jOEfreaLzkBR5eV5M/jk5ghXJtxy1rqJ9Ty3alaayo1zmFbQMUTB3MsnBTN C9G3y7f209y1PvBxaHnUN9hWnJkQ4keYyY8PDeGxh4fOO0iBnjvzAjOw0KekoCSqDze5 I5bW1fEjxy2O+H/mDsNllY2SKfccJ9SLFLlEibn8zKho29Gjod/N32JVQkhUFdGwwBBZ /KWg3It4FNBJaDAtd6hW+JqKtuTMWC+J+i8NgvzYqsfBBesdCctAZC/ZlXYFWvRn2DxS lA0HxY8xIEsKAG/5agi9gUaG8KWq/TwS+C5I+oRznzbGpJnvwV/KtpzMf4D7qa9UePAr 9UhA==
X-Gm-Message-State: AFeK/H15CdwgEChEpCaFKWrNna7LBKByXdDjuEPftlr16BYKAzKL8MOLV3H6A1EEF/T/rxeUYEaKBRz3ARkDKA==
X-Received: by 10.202.63.85 with SMTP id m82mr23419150oia.151.1490219614882; Wed, 22 Mar 2017 14:53:34 -0700 (PDT)
MIME-Version: 1.0
Sender: hallam@gmail.com
Received: by 10.157.46.138 with HTTP; Wed, 22 Mar 2017 14:53:34 -0700 (PDT)
In-Reply-To: <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@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> <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Wed, 22 Mar 2017 17:53:34 -0400
X-Google-Sender-Auth: 8GpQJh7J1fF0K6sBUv5ittKdvFE
Message-ID: <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com>
To: Tony Arcieri <bascule@gmail.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=001a113dd492c85493054b58caf9
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/3dGkCnlTyFhG5UYdvMjV6dfVZAg>
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 21:53:54 -0000

On Wed, Mar 22, 2017 at 4:47 PM, Tony Arcieri <bascule@gmail.com> wrote:

> 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
>
>
That is the case if you disclose x.G. But why would you do that?

You could also do:

​xs = ( H(x + 'example.com')) mod q

Which is more robust.