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

Nadim Kobeissi <nadim@nadim.computer> Wed, 22 March 2017 21:40 UTC

Return-Path: <nadim@nadim.computer>
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 93CF7129464 for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 14:40:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.701
X-Spam-Level:
X-Spam-Status: No, score=-2.701 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=nadim.computer
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 uIz0MttH1ObH for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 14:40:46 -0700 (PDT)
Received: from mail-wm0-x22e.google.com (mail-wm0-x22e.google.com [IPv6:2a00:1450:400c:c09::22e]) (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 EB4181293D6 for <cfrg@irtf.org>; Wed, 22 Mar 2017 14:40:45 -0700 (PDT)
Received: by mail-wm0-x22e.google.com with SMTP id t189so48968154wmt.1 for <cfrg@irtf.org>; Wed, 22 Mar 2017 14:40:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nadim.computer; s=mail; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=fvidga30TJuvZ9mhUGV8Rs3LymYXoXKHyyOYlOuts4k=; b=cGxBfVkq1LHYAM4sjCELiuYm9U/1TASZ117GpXjV3SzW4WaiduwxplFdtYU+aethzG qQMDjk6Zzy5XWBG00ENz0cnNI/Ssa7dGYAXR1pEPadXeDXHE/yvbETUO4jpFwFG5A24r WoQKoWirDICMvnZNzQV92Ew+FnOErmRzFvex4=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=fvidga30TJuvZ9mhUGV8Rs3LymYXoXKHyyOYlOuts4k=; b=WrQ4XDZVtueHIj4RkMfW/CCotaIXeTh9PvvfagZYAzmGOGMPTdCqdaF2ZM38lTJKGQ oFvlNVlf3gGbxk/MOMNPujkvnmwUS7j1VidvFDDeilvWyVO9XRsHBvldETefrXTdhGgb mVdPgY0jN6YCIBKN86D2JTyV6d94HNzcZ0BOT3OB69sGOGe+/VOMxoE7Az2zhIkdg8p+ gkygiiei8iAPw4a826jK6sAP7M/UA7PDIXvMdOvwY5W8SFWAcxvqh42YXdWFWLv9GsXc 2gysuXmQs8nsmktNAqViq5k0mVvf5h3zme2mEHfQwKMeOxrGt7thICUnrO0+hNhrQFh8 iziw==
X-Gm-Message-State: AFeK/H2fQPFAgwnmAw/3X/mSQIhLUe+X7cgP1i3Ke6UeKNGRePLoXrd6Q5OIYS9BhIL6Ug==
X-Received: by 10.28.47.15 with SMTP id v15mr9950442wmv.116.1490218844322; Wed, 22 Mar 2017 14:40:44 -0700 (PDT)
Received: from [192.168.0.11] (89-156-80-177.rev.numericable.fr. [89.156.80.177]) by smtp.gmail.com with ESMTPSA id b91sm3307661wrd.29.2017.03.22.14.40.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 22 Mar 2017 14:40:43 -0700 (PDT)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3259\))
From: Nadim Kobeissi <nadim@nadim.computer>
In-Reply-To: <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com>
Date: Wed, 22 Mar 2017 22:40:42 +0100
Cc: Phillip Hallam-Baker <phill@hallambaker.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <BD3A22C9-1E2F-45E4-9180-6DE52E7CF990@nadim.computer>
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>
To: Tony Arcieri <bascule@gmail.com>
X-Mailer: Apple Mail (2.3259)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/00gxBSFljolGeySNaCQMmoL2W-I>
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:40:48 -0000

> On Mar 22, 2017, at 9: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.

From a potentially naïve reading of this thread, it sounds like the HKDF construction (the one proposed by Hugo Krawczyk and used by Signal and TLS 1.3, among others) satisfies all of the properties requested by “hierarchical key derivation” systems. Is this right or am I missing something?

Thanks,
Nadim

> 
> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg