Subject: [Cfrg] EdDSA choice of hash function/parameter derivation for curves > 256 bit

From: Björn Edström <[email-masked]>
Date: Mon, 22 Jun 2015 15:20:54 +0200

This is somewhat relevant to the current proposal round.

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?

Regards
Björn

---

From: Hanno Böck <[email-masked]>
Date: Mon, 22 Jun 2015 15:26:29 +0200

On Mon, 22 Jun 2015 15:20:54 +0200

> hash functions with larger than 512 bit output?

SHA-3 will afaik have hashes with configurable output size ("SHAKE").

Earlier protocols had a construction called "MGF1" (see RFC 3447)
that allows having hashes with a defined output size (pretty
simple construction, combining a counter with a hash function).

Both should work.

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 22 Jun 2015 17:13:32 +0300

> 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

---

From: Watson Ladd <[email-masked]>
Date: Mon, 22 Jun 2015 07:42:02 -0700

> pseudorandom parameter (and that actually becomes a problem before

I'm not entirely sure what you are saying here. Yes, we need to
generate larger Schnorr random values. But that's the only place where
there is a problem if we store the key as two parts: the Schnorr
protocol will work with challenges which are not uniform over all the
scalars, unless I'm badly missing something. Yes, the security
reduction will be a bit different, but it's inherently lossy with the
proof methods we know. ECDSA on E-521 uses SHA-512, not some larger
output variant, and still works.

Sincerely,
Watson Ladd

>
>
> -Ilari
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 22 Jun 2015 09:21:38 -0700

Another option for everything but E-521 is

k = HMAC(sk, “derive secret key”)
nonce = HMAC(sk, “derive nonce” || m)

Since HMAC is a PRF, you can extend it by chaining the output into HMAC(sk, “extend secret key / nonce” || k_0) or similar.

— Mike

> On Jun 22, 2015, at 6:20 AM, Björn Edström <[email-masked]> wrote:
>