Re: [Cfrg] EdDSA choice of hash function/parameter derivation for curves > 256 bit
Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Mon, 22 June 2015 14:13 UTC
Return-Path: <ilari.liusvaara@elisanet.fi>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1AEC21AC410 for <cfrg@ietfa.amsl.com>; Mon, 22 Jun 2015 07:13:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.099
X-Spam-Level: *
X-Spam-Status: No, score=1.099 tagged_above=-999 required=5 tests=[BAYES_50=0.8, MIME_8BIT_HEADER=0.3, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=no
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 UVfJa5zAURWH for <cfrg@ietfa.amsl.com>; Mon, 22 Jun 2015 07:13:35 -0700 (PDT)
Received: from emh06.mail.saunalahti.fi (emh06.mail.saunalahti.fi [62.142.5.116]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 662801AC429 for <cfrg@irtf.org>; Mon, 22 Jun 2015 07:13:35 -0700 (PDT)
Received: from LK-Perkele-VII (a91-155-194-207.elisa-laajakaista.fi [91.155.194.207]) by emh06.mail.saunalahti.fi (Postfix) with ESMTP id DE788699D2; Mon, 22 Jun 2015 17:13:32 +0300 (EEST)
Date: Mon, 22 Jun 2015 17:13:32 +0300
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: Björn Edström <be@bjrn.se>
Message-ID: <20150622141332.GA19669@LK-Perkele-VII>
References: <CAA4PzX2k6ZZOkFMcR-AkN-1-D3-=sdmQi_MCo-aO+Ev3KN3N8Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAA4PzX2k6ZZOkFMcR-AkN-1-D3-=sdmQi_MCo-aO+Ev3KN3N8Q@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/WqLoydrOmYcEwNfCbE1RMXG-4BI>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] EdDSA choice of hash function/parameter derivation for curves > 256 bit
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://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: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 22 Jun 2015 14:13:37 -0000
On Mon, Jun 22, 2015 at 03:20:54PM +0200, Björn Edström wrote: > > I've been looking at the EdDSA paper and a reference implementation of > Ed25519. Recall that it uses a deterministic variant of Schnorr where > the random "k" parameter is derived from a hash function. Specifically > Ed25519 takes the SHA2-512 of a seed "sk" and splits in into two > halves: > > - The first half is used for the secret key, "a". > > - The second half is the Schnorr random value "k". > > This happens to work very well for the Ed25519 curve because the > single hash call will result in two 256 bit values, as desired. > > The (open, rhetorical) question would then be: How would you derive > "a" and "k" for a curve bigger than 256 bit, in the absence of common > hash functions with larger than 512 bit output? Or just add some labels and call hash function twice with different labels (this works with curves up to 512 bits[1]). [1] To reach E-521 you would need some tricks (most likely some KDF). But once curves get big enough, one also gets the trouble of (uniformly!) generating the hash term in scalar part and the pseudorandom parameter (and that actually becomes a problem before a and k). -Ilari
- [Cfrg] EdDSA choice of hash function/parameter de… Björn Edström
- Re: [Cfrg] EdDSA choice of hash function/paramete… Hanno Böck
- Re: [Cfrg] EdDSA choice of hash function/paramete… Ilari Liusvaara
- Re: [Cfrg] EdDSA choice of hash function/paramete… Watson Ladd
- Re: [Cfrg] EdDSA choice of hash function/paramete… Michael Hamburg