Re: [Cfrg] Finishing Ed448 definition

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

On 11/22/2015 01:18 AM, Bryan A Ford wrote:
> 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
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>