Re: [Cfrg] EdDSA and > 512 curve & hash (Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement)

Adam Back <adam@cypherspace.org> Sun, 12 January 2014 15:54 UTC

Return-Path: <adam@cypherspace.org>
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 0BA511ADFCE for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 07:54:12 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001] autolearn=ham
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 0G_n0zOF97qk for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 07:54:11 -0800 (PST)
Received: from mout.perfora.net (mout.perfora.net [74.208.4.195]) by ietfa.amsl.com (Postfix) with ESMTP id DCC971ADFC9 for <cfrg@irtf.org>; Sun, 12 Jan 2014 07:54:10 -0800 (PST)
Received: from netbook (c107-70.i07-27.onvol.net [92.251.107.70]) by mrelay.perfora.net (node=mrus3) with ESMTP (Nemesis) id 0M6zfx-1V8TPo2gwn-00wfnp; Sun, 12 Jan 2014 10:53:58 -0500
Received: by netbook (Postfix, from userid 1000) id 2D3AC2E283A; Sun, 12 Jan 2014 16:53:52 +0100 (CET)
Received: by flare (hashcash-sendmail, from uid 1000); Sun, 12 Jan 2014 16:53:50 +0100
Date: Sun, 12 Jan 2014 16:53:50 +0100
From: Adam Back <adam@cypherspace.org>
To: Robert Ransom <rransom.8774@gmail.com>
Message-ID: <20140112155350.GC19922@netbook.cypherspace.org>
References: <87eh4e7a2y.fsf@latte.josefsson.org> <52D18475.10709@akr.io> <20140112062942.GA32437@LK-Perkele-VII> <52D29153.7000301@akr.io> <20140112142923.GA19922@netbook.cypherspace.org> <CABqy+srUUiFcniM404uPcqDChW3xkcTcAjqTejG=Q_pEQMaTsg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <CABqy+srUUiFcniM404uPcqDChW3xkcTcAjqTejG=Q_pEQMaTsg@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:140112:rransom.8774@gmail.com::8vLV/8perAXPXOiR:000000000000000 00000000000000000000000006y/
X-Hashcash: 1:20:140112:akr@akr.io::pmft+8oa632oP62T:000000016e9
X-Hashcash: 1:20:140112:cfrg@irtf.org::dzZoWIXWqa+vIjGi:000046uN
X-Hashcash: 1:20:140112:adam@cypherspace.org::PJgPWJ5SmIZHVz/k:00000000000000000 00000000000000000000000040dS
X-Provags-ID: V02:K0:CJ/6AUD3O2EjqhH+3NUtAlYKzfNQg6BcMdDKv9VG+M/ CBerYOhXsy8i95Hs/n3Cfn5DwrZB3aIHDq9P8E/uSF9d/1LAnq O1Bj+W7lROTjTEGsCR2ogQSAxl3PC/2QAmKje9ciYXBOIjiqh8 LwhDKxmsti+WMRWGzkPZfGDbLnK4y4oRLTxKWgVlVGyTIgSuGG TgJUZFzzEgWbMqnwz8bvrpstMyMT5bcUePYqvXwJYiaSQlKv3y L/iebXfnmE/pdPbV7QDxGXr7oouFu9sRAHLV2GSBRKqZMIamXC uWmrulPvVBniE8oQZYtNzxv+OlaQRh0H27ZOOQFUwF2SKvupbQ 0VlYZ3JhZ7rj3deDdaH9bIyaTT37cyyZek6CzlDhz
Cc: Adam Back <adam@cypherspace.org>, cfrg@irtf.org
Subject: Re: [Cfrg] EdDSA and > 512 curve & hash (Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement)
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: <http://www.irtf.org/mail-archive/web/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: Sun, 12 Jan 2014 15:54:12 -0000

On Sun, Jan 12, 2014 at 07:13:16AM -0800, Robert Ransom wrote:
>Deterministic generation of message keys is the primary reason that
>EdDSA requires a double-length hash function.
>
>EdDSA relies on the hash function having double-length output in two ways:
>
>* Message key generation relies on the output being noticeably longer
>than the group order in order to generate *uniform* exponents.
>
>* EdDSA also uses the hash function to expand the secret-key bitstring
>into (a) the secret exponent of the public key and (b) a secret
>bitstring used to key the message key generation hash function.

My point is compared to the deterministic CRNG that eg DSA specifies for k
generation, follow that pattern, but using SHA3-512 as the building
block, seeded with d, the private key, is certainly doable to scale EdDSA to
512-bit curve without needing a 1024-bit hash function.

Some KDF functions are designed to provide the needed one-way security
beyond the hash input size of the underlying hash or MAC function.  So I was
suggesting this as an alternative method than using a not-widely-used hash
or hash-parameterization (Keccak).

Adam