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

[Mike Hamburg <[e-mail]>]

On Jan 12, 2014, at 7:53 AM, Adam Back <[e-mail]> wrote:

> 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

My personal preference here is for either SHA512 or SHA3, in that order.  But is SHA3 defined yet?

I don't care that SHA2 was designed by NSA.  The SHA2 functions are widely deployed and have survived more than a dozen years of public analysis.  Their performance is good enough that they won't be the bottleneck in an EC signature implementation.  SHA512 has a wide enough output and a high enough security level to be suitable for many of these curves, though for some curves it will need to be evaluated twice in order to be wide enough.

BLAKE2 is probably fine.  But it hasn't had as much time in the spotlight as SHA2 or Keccak.

The SHA3 finalists are also fine.  But we should test timings to see whether their extreme performance is a gain in an EC hash setting.

Using a widely-deployed and widely-respected hash function will ease implementation and improve acceptance and deployment of any new standard we might make.

I also wonder if a new signature scheme should support hash-and-sign, or just signing where you have the full message.  Hash-and-sign is less secure because of collision attacks, but the API is much nicer especially for deterministic hashes, and that matters.

Cheers,
-- Mike