Subject: [Cfrg] Finishing Ed448 definition

From: Alexey Melnikov <[email-masked]>
Date: Sat, 21 Nov 2015 15:22:08 +0000

Dear CFRG participants,
Chairs would like to get Ed448 finished and send
draft-irtf-cfrg-eddsa to RFC Editor.

In order to do that, we need to pick 1) pre-hashing algorithm and 2)
912-bit internal hash function.

Chairs would like to ask participants to submit their detailed
implementable proposals within 1 week (till November 29th). After that
we will have a Quaker poll to settle on one choice for each of the above
(alternatively chairs can just pick something and ask for objections).

Best Regards,
Kenny and Alexey

---

From: Bryan A Ford <[email-masked]>
Date: Sat, 21 Nov 2015 16:18:44 -0800

Here are two closely-related proposals for the pre-hashing and internal
hashing scheme.  For discussion purposes let's call them "twoshakes-s"
and "twoshakes-d".  Both are defined in clearly-demarked sections below.

---
#1: twoshakes-s ("s" is for "simple"):

This scheme uses the SHAKE256 extensible-output functions (XOFs) to
implement both the internal hash and prehash. The internal hash uses the
first 912 bits (114 octets) of the output produced by SHAKE256, whereas
the prehash uses the first 512 bits (64 octets) of SHAKE256-produced output.

In PureEdDSA, the prehash PH(M) is the identity function, PH(M)=M. In
HashEdDSA, the prehash PH(M) is computed as SHAKE256(M, 512), where M is
the message to be hashed and the second parameter determines the number
of bits of output the SHAKE256 XOR produces.  Note that this notation is
consistent with the two-parameter definition of SHAKE256 in section 6.3
of FIPS 202.

The internal hash H(M) is similarly computed as SHAKE256(M, 912),
yielding a 912-bit output.  (Note that the M here merely names the
internal hash's input parameter, not the message ultimately input to the
EdDSA scheme.  In its usage by EdDSA this M will be substituted with
'Prefix || M' or 'R || A || M' in the signing process.)

Design justification:

The overall justification for using SHAKE256 for both internal hash and
prehash, as discussed already on this list, is: (a) implementations need
only a single symmetric crypto primitive (Keccak) for both; and (b)
SHAKE256 operates the underlying Keccak sponge function with a rate and
capacity designed to be appropriate for a 256-bit security level, and
not at an overly-conservative rate as she SHA3-* hashes do. This latter
performance consideration is important mainly for the prehash, since the
prehash can be used to operate on long messages making its hashing
throughput potentially significant (and not necessarily always dominated
by the cost of the public-key operations).

This scheme has the advantage of simplicity and consistency with how the
Ed25519 signature scheme works, only dropping in SHAKE256 with
appropriate output-size parameters in place of SHA-512.  I do not
perceive any real security problem with using the same SHAKE256 XOF
(with different output-size parameters) for the two hashes, because in
practice part of the input M will always be different for the XOF's
different uses, yielding implicit domain-separation.  In particular:

- The secret per-message 'r' value gets computed using the internal hash
as SHAKE256(prefix || M, 912), which depends on the secret and
cryptographically unique 'prefix'.

- The Schnorr challenge gets computed using the internal hash (again) as
SHAKE256(R || A || M, 912), where R depends on r and in turn on the
secret prefix, and hence should be cryptographically unique and
unpredictable to anyone not holding the private signing key.

Argued another way, if there was a real problem with using SHAKE256 for
both the internal hash and prehash in Ed448, it seems the same problem
would probably exist with using SHA-512 for both the internal hash and
prehash in Ed25519.

Still, in case we would like to make the design a bit more conservative
with explicit domain separation, I suggest the following alternative scheme.

---
#2: twoshakes-d ("d" is for "domain-separated"):

This scheme again uses the SHAKE256 extensible-output functions (XOFs)
to implement both hashes, with the inputs prefixed as specified below
for explicit domain separation purposes.

The scheme accepts two optional, application-defined parameters for
customization, but applications simply needing a generic signature
scheme (and APIs offering no convenient way to specify optional
parameters) can simply use the defaults as specified below:

- Prehash: 1-bit flag, default True
- Context: octet string of length 0..255, default empty (0-octet)

In PureEdDSA, the prehash PH(M) is the identity function, PH(M)=M.
In HashEdDSA, the prehash PH(M) is computed as SHAKE256(dom||M, 512),
where dom is a domain separation prefix defined below with the Flags
octet set to 0x02.  The 512 parameter means use the first 512 bits of
SHAKE256 output as the hash prehash output.

The internal hash H(M) is computed as SHAKE256(dom||M, 912), where dom
is defined below, with the Flags octet it contains set to 0x00 for
PureEdDSA or to 0x01 for HashEdDSA.  The 912 again means use the first
912 bits of SHAKE256 output as the internal hash output.

The domain separation prefix 'dom' in each case above consists of:
- 8 octets: the ASCII characters "SigEd448"
- 1 octet: Flags, as defined below
- 1 octet: length of optional Context string, 0-255 (0 meaning empty)
- 0-255 octets: Context string

The Flags octet is defined as follows:
- Bit 0: Prehash parameter: 0 for PureEdDSA or 1 for HashEdDSA.
- Bit 1: 0 for the internal hash, 1 for the prehash
- Bits 2-7: reserved, MUST be zero

Justification for this design:

The 8-octet 'SigEd448' prefix provides (weak) explicit domain separation
of EdDSA+Goldilocks's use of SHAKE256 from other independent uses of
SHAKE256.  It is not by any means essential to the scheme's security but
is included merely as a low-cost conservative precaution.

The optional Context parameter enables applications to distinguish
signatures intended for use in one context from signatures intended for
another.  In particular, if a signature S is generated with one context
C1, i.e., S = Sign_C1(M), then any attempt to verify S in a different
context C2 != C1 will fail, i.e., Verify_C2(M) = False.  A Context could
simply be a well-known application- or protocol-defined name, or a hash
or random number to allow more fine-grained context separation.  The
document defining how EdDSA is to be used in a given application or
protocol is expected to specify how the Context parameter is to be
determined.

The Flags octet provides explicit domain separation between the three
uses of SHAKE256 in EdDSA+Goldilocks: namely the prehash (flags=0x02),
the PureEdDSA internal hash (flags=0x00), or the HashEdDSA internal hash
(flags=0x01).

Any or all of these domain separation provisions could of course be
dropped without affecting the resulting signature scheme's security in
any one use-case considered independently, but are included as a
conservative security precaution that costs little in terms of either
performance or implementation complexity.  As such, I feel these
domain-separation provisions are useful but am also fine with dropping
any of them if the balance of the WG feels they are not worth the
trouble.  (Or just go with twoshakes-s above.)

---

Cheers
Bryan

On 11/21/15 7:22 AM, Alexey Melnikov wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Gilles Van Assche <[email-masked]>
Date: Wed, 25 Nov 2015 17:59:31 +0100

Hi Bryan,

I have a preference for your second proposal "twoshakes-d", for its
domain separation between PureEdDSA and HashEdDSA. This would have the
practical advantage of allowing a single key to be used for both options
(if certified as such), without input clashes at the internal hash level.

Kind regards,
Gilles

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 25 Nov 2015 10:14:47 -0800

+1

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 25 Nov 2015 23:22:12 +0100

> (alternatively chairs can just pick something and ask for objections).

I submit two proposals:

#1: Use SHAKE256 as the internal hash and SHA3-512 as the prehash.

#2: Use SHA2-512/912 as described in [1] as the internal hash and
SHA2-512 as the prehash.

I believe there is no amiguity in these descriptions, but if someone
believe it is underspecified what I mean, please point out what is
unclear and I'll attempt to clarify.

/Simon

[1] http://ed25519.cr.yp.to/eddsa-20150704.pdf

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 26 Nov 2015 09:58:48 +0100

> (if certified as such), without input clashes at the internal hash level.

That would be nice -- but having Ed25519 and Ed448 differ this
significantly would appear like a strange design choice to me.

So for me, at this point, I would prefer twoshake-s, or both my other
proposals (SHAKE256+SHA3-512 and SHA2-512/912+SHA2-512), over
twoshakes-d.

/Simon

---

From: Bryan Ford <[email-masked]>
Date: Thu, 26 Nov 2015 10:32:38 +0100

> On Nov 26, 2015, at 9:58 AM, Simon Josefsson <[email-masked]> wrote:
> 

This occurred to me to and I agree that it would be nice for the two to be (more) consistent.  I think a domain separation scheme like the one I proposed would be trivial to "back-port" to Ed25519 to make them consistent if we feel that's valuable; I didn't want to suggest this in my proposal for Ed448 though since the call was formally only for Ed448 hash proposals and I didn't want to violate the scope of the call. :)

I suggest we treat the possibility of "back-porting" domain separation to Ed25519 as a separate discussion issue that's (mostly) orthogonal to what to do for Ed448 - but with that in mind, here are three possible back-porting approaches I considered:

1. Direct back-port: just change the Ed25519-based spec to add the same 'dom' prefixes to the hash inputs in exactly the same way as for Ed448, with the 'SigEd448' changed appropriately to (eg) 'SigEd255' or 'SigEd25519'.  Advantage: domain separation features completely consistent across the two curves. Disadvantage: breaks binary signature compatibility with existing "classic" Ed25519 signatures. 

2. Back-port with silent compatibility exception: define the Ed25519 sig scheme to do domain separation in the same way as Ed448, *except* in the one special case of PureEd25529 with an empty context string, in which case the dom prefix becomes empty (no domain separation) for backward compatibility with classic Ed25519. Advantage: mostly consistent across curves, and backward compatible. Disadvantage: hokey special case, and the slight security risk that a use of PureEd25519 with empty context string being confused with a domain-separated use of Ed25519. 

3. Back-port directly as in #1, so both PureEd* and HashEd* are always domain separsted and incompatible with classic Ed25519, but define an additional eg 'BareEd25519' scheme variant just for backward compatibility with non-domain-separsted classic Ed25519. Encourage all new applications/protocols to use PureEd* or BareEd* while defining BareEd25519 as being available for legacy compatibility. 

I guess my (slight) preference would be for #3 followed by #1. I'm sure other variants are possible. 

Cheers
B

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 28 Nov 2015 15:35:47 +0200

> proposals (SHAKE256+SHA3-512 and SHA2-512/912+SHA2-512), over

Agreed (Through I think SHA3-512 isn't good).

Two other proposals:

1)

Hash: SHAKE256@912bits(x)
Prehash: SHA2-512(x)
Brief rationale: The Same prehash for both Ed25519ph and Ed448ph
	might be useful if some application wants to prehash the
	data[1]. Also, SHA-512 is one of the fastest unbroken hash
	functions around (pretty much only Blake2 is faster)[2].

2) From Alex Elsayed (with constraints given[2] fully propagated)

Hash: HKDF-EXPAND(hash=SHA2-512, prk=HKDF-EXTRACT(hash=SHA2-512,
	salt=<blank>, ikm=x), info=<blank>, 114)
Prehash: SHA2-512(x)
Brief rationale: The purpose calls for a KDF, and HKDF is the
	standard KDF. It is broadly implenmented, including in
	hardware, single-wide so doesn't require twice the work,
	not new unlike SHAKE and designed for arbitrary-length
	outputs.

[1] Not that I think this kind of operation is desriable, but...

[2] SHAKE256 is a bit slower than SHA-512. I think SHA3-512 is
hilariously slow (SHA-512 is like 2-3x the speed).

[3]
1) Salt does not contain key material
2) Info does not contain message.
3) (I added this): Collisions can't be trivially exploited.

Propagating the constraints yields that everything must
go into IKM, as anything else would break at least one
of the constraints.

-Ilari