Re: [Cfrg] Finishing Ed448 definition

[Mike Hamburg <[e-mail]>]

+1

On 11/25/2015 08:59 AM, Gilles Van Assche wrote:
> 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
>>> [e-mail]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg