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

Tony Arcieri <bascule@gmail.com> Wed, 22 March 2017 22:06 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 5A7201298A3 for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 15:06:48 -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 x4aa5m-POeD1 for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 15:06:46 -0700 (PDT)
Received: from mail-pf0-x235.google.com (mail-pf0-x235.google.com [IPv6:2607:f8b0:400e:c00::235]) (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 BD14E129430 for <cfrg@irtf.org>; Wed, 22 Mar 2017 15:06:45 -0700 (PDT)
Received: by mail-pf0-x235.google.com with SMTP id 20so49067160pfk.2 for <cfrg@irtf.org>; Wed, 22 Mar 2017 15:06:45 -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=eb0Ry3iHog3kzkdKH9iMkkplwQxPl3e/KwhAmtcHT58=; b=Up3uw0GqQwAQYQLybOeXlaBC+5/VQT0dHRrJwL3yxRD+hrZnFrwBV0urCVu9GWSLbn jsGqAQPOHHh0CWG96xap3JMLlwg05SEH6eTeOCRjc6UT68g2kj3egRwHjalgHxOu5YqZ 4UP3lzkrWW2WTCMUOgc188mh4aNSgFoRae8nipu4oz4iTanXqjCrZfybsVzWqVi9CjTQ RULsl1ElgZtqYtUlOP7sSWug7qwURj54ML4EX3yCCY7PbfcxwlNt0s6ytZfHir9YuYBQ CR95Aho1kqp1U6JiG+XaUaBe3T0Hmdkmf9vfs4ZuYnGazufaYL7QBr65Ep1X5WuDZYwu /Riw==
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=eb0Ry3iHog3kzkdKH9iMkkplwQxPl3e/KwhAmtcHT58=; b=euNwR0IB9KrcQzVUA7Ga2exSbBqi50blYxgaIqWpNDEsRgfLZ4Sly2AxDymABv4Zy0 2FisnAcVOMLx6nD14WMfBCFKZcVIodZuEoFDOH19LnT8mGPnlC/ffCVISvQ36shBZ9EY qnC7v5PJuh5ris2qAGULE9BKM3ZRxGdv6myhgOikdn72rHGHsFGCDIiFUf7B8ki/8ppU QyRpbmniGGx1rpMPTh/hS3GHFansdmJPdI4Ca0kJY020WGwpPYK1LlKZgqNToR0G7ESh ekqDAWMSfQNMusmBRouy/v/biuJREaESY3mfdEdfk/aUq9MQ/EIzv79wKLP0/5gP5khG v8dw==
X-Gm-Message-State: AFeK/H0Dk+CK5krhp/yllPvc3v+Sjhre4HpkKDkIYERjBqCg4EJOOLXmGfeb+Bcbd5OKSqWHTocx6dKVjUnKQA==
X-Received: by 10.98.23.202 with SMTP id 193mr48248684pfx.141.1490220405391; Wed, 22 Mar 2017 15:06:45 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.100.178.234 with HTTP; Wed, 22 Mar 2017 15:06:24 -0700 (PDT)
In-Reply-To: <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@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>
From: Tony Arcieri <bascule@gmail.com>
Date: Wed, 22 Mar 2017 15:06:24 -0700
Message-ID: <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=94eb2c03d062e68929054b58f92a
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/h6RGwSl7Z07bkWP4jR2W18Y0BcQ>
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 22:06:48 -0000

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.

-- 
Tony Arcieri