Re: [Cfrg] Finishing Ed448 definition

[Bryan A Ford <[e-mail]>]

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:
> 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
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>