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

Phillip Hallam-Baker <phill@hallambaker.com> Thu, 23 March 2017 01:30 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 46006128AB0 for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 18:30:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.4
X-Spam-Level:
X-Spam-Status: No, score=-2.4 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, URIBL_BLOCKED=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 qIaL38v7xfRH for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 18:30:53 -0700 (PDT)
Received: from mail-oi0-x230.google.com (mail-oi0-x230.google.com [IPv6:2607:f8b0:4003:c06::230]) (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 868B312422F for <cfrg@irtf.org>; Wed, 22 Mar 2017 18:30:53 -0700 (PDT)
Received: by mail-oi0-x230.google.com with SMTP id r203so53173318oib.3 for <cfrg@irtf.org>; Wed, 22 Mar 2017 18:30:53 -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=Mf2R/N8DfR9YZpqtzRBBjJ54B8Dz3uydlMX6dyLmvxA=; b=PWMaQKzTPj2hmY/ZSxv7a2gPLlFJTNw4EIVfLkjw1ZqOp/9Ysm0QFzTM00fQtVCGuW FvK3OVCCwA1Em7IXbV89mRmcU6z1V4wl6KSxM8x7TfHlMaaLv5TWt9C7rrc+hYWfi3vT a6xAfmBOAJk+U6CmptZl8YQuFChWfbLVljFdkStvb0SvHvsj155lalLraxHeWzqyXOaW 0xif6VeAMgjAUlc0du1gFOg7qGXpJSpTMLksXaYJW6wSN0EFY7BQxJPut8G+CoDvxqA4 8W45KRcujRclE2t25opTe7wNZmwCRqsbQD0F71I/XIZe2rVd8O1cVpXtGdjA50e35Ygg jGMw==
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=Mf2R/N8DfR9YZpqtzRBBjJ54B8Dz3uydlMX6dyLmvxA=; b=Y00TFaBObaYCKVf2kLFVaWb165SyCcieBWvBkRogRnKDNZnokyxIkHHnIoEXIyMjmD 0L/5amshqWLxiyFCV273qQs6VveVZ9P3JFeUqr4RblV1Z18OgvXYyIqxRS6rxQFzaKiu jWGn9eMDhFae9U61IoxkvddZfmiPSlGCusJjm4yUDPnSNwzpWEN0TQ5SVzVeiRnBUD4f Hx27bQT6KJDlN7biWertq/FQx2gUcye6S1yPsn84MeUgevKP8wH/mIdj8y+rnzKFX8vn Mrno/4y+oV0WiowG9r3Ayd6NiGB2In1ZTb58CVOk/eXGYiu5FZhWBHElN5QKcoPiKxO8 mtrA==
X-Gm-Message-State: AFeK/H3lhS1R/INb4GLmjNkxxHY7aP0SBakXjPjoUkU2wLouEHLqTDjZ5cSrwKJRd7DvQaqWlqQA5ROUnJcUXg==
X-Received: by 10.202.80.21 with SMTP id e21mr6237522oib.8.1490232652977; Wed, 22 Mar 2017 18:30:52 -0700 (PDT)
MIME-Version: 1.0
Sender: hallam@gmail.com
Received: by 10.157.46.138 with HTTP; Wed, 22 Mar 2017 18:30:52 -0700 (PDT)
In-Reply-To: <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@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> <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com> <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Wed, 22 Mar 2017 21:30:52 -0400
X-Google-Sender-Auth: 00DHckqWTa-eNnrlb177kW4v0QQ
Message-ID: <CAMm+LwjeZdR=ZGX0topN2w6P12jEmR-TQ8M9+anyETj43nbiqg@mail.gmail.com>
To: Tony Arcieri <bascule@gmail.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=001a113d8408e9db6f054b5bd327
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/IdNhnFwVt4FEt4rqTk2UcrB4qIw>
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: Thu, 23 Mar 2017 01:30:55 -0000

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

> On Wed, Mar 22, 2017 at 2:53 PM, Phillip Hallam-Baker <
> phill@hallambaker.com> wrote:
>
>> 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?
>>
>
> xG can be recovered if you know (x+z)G and the "example.com" string,
> which is the problem.
>
> xG cannot be recovered if you know (x*z)G and the "example.com" string,
> which is the desirable unlinkability property.
>
> You could also do:
>>
>> ​xs = ( H(x + 'example.com')) mod q
>>
>
> This requires knowledge of the parent scalar to derive child keys. One of
> the goals of a scheme like this is to allow a holder of a master public key
> to derive child public keys without any knowledge of secret scalars.
>
>
​Ah, yes, you would want MAC ('example.com', k)

However, g​oing back to

xs = x + ( MAC('example.com', k)) mod q

You could play some interesting games with this. You could have quasi
linkability so that the identifiers are unlikable unless you choose to
claim them be revealing the difference between two of the keys.

I have no idea what you would want to use it for but you could do it.