[Cryptography] More efficient and just as secure to sign message hash using Ed25519?

[Ron Garret]

On Aug 2, 2015, at 9:35 PM, Viktor Dukhovni <cryptography at dukhovni.org> wrote:

> On Sun, Aug 02, 2015 at 09:28:06AM -0700, Ron Garret wrote:
> 
>>> What you're losing is collision resilience.
>> 
>> I think it's important to note here that the collision resilience you are
>> losing is resilience against collisions in the underlying hash H.  Ed25519
>> *is* a hash of M and the secret key, and it obviously cannot be resilient
>> against collisions in *that* hash (i.e. collisions in ed25519 itself).
>> So if you hash first, you now have two collision risks whereas before you
>> only had one.  But the output of Ed25519 is 256 bits, so if H is, say,
>> SHA512 the incremental risks of collisions in H over the inherent risk of
>> collisions in Ed25519 are (almost certainly) pretty darn low.  Almost
>> certainly the least of your worries in any real-world application.
>> 
>> If you're really worried about collisions, you can probably produce an
>> overall more collision-resistent signature scheme by concatenating the
>> signatures of two different hashes of M.  (But I am not an expert so don't
>> do this until someone who actually knows what they're doing has analyzed
>> it.)
> 
> This analysis is too naive.  The risk is internal collisions in
> the hash function, which might enable extension attacks.  The
> Ed25519 construct is resistant against internal collisions and
> extension attacks, while SHA-2 is not.

I don’t see how Ed25519 is resistant against length extension attacks.  It is true that collisions in H do not produce collisions in Ed25519 because Ed25519 applies H twice to two different inputs.  But it seems to me that a collision in Ed25519 itself could be length-extended if that collision resulted from two collisions in H, because both applications of H put M at the end.

> Now of course internal collisions on the full SHA-2 are far from
> feasible at present, but not depending on unexpected progress on
> that front is reasonable defense in depth.

If you are really worried about future collisions in SHA-512 you can sign an HMAC instead of a simple hash.  (In fact, if I’m right and Ed25519 really is vulnerable to length-extension attacks on two collisions in H, then signing an HMAC might actually be (very slightly) more secure than signing the message directly.)

rg