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

Question

According to the Ed25519 paper, the (potentially long) input message is hashed twice (see Section 4 page 12 steps 1 and 3). This webpage has a nice diagram toward the bottom that illustrates this, and I confirmed it in the reference code on Supercop (see supercop-20141124/crypto_sign/ed25519/ref/sign.c, function calls crypto_hash_sha512(nonce, sm+32, mlen+32) and crypto_hash_sha512(hram,sm,mlen + 64)).

My question is, for long messages, wouldn't it be more efficient and just as secure to hash the entire message just once, and then use the 64 byte hash as the input to the signing algorithm? In other words, the code would look like:

crypto_hash_sha512(mhash, m, mlen);
crypto_sign(output, mhash, 64, key);

The would seem to me to be faster for mlen > approx 128 bytes without any loss of security.

I'm I missing something here? Is there a potential loss of security to using mhash as the signing input instead of the original message m?

Answer 1

Peter Schwabe, one of the authors of Ed25519, directed me to a recent paper titled "EdDSA for more curves". The section "Security notes on prehashing", page 5, says that the Ed25519 algorithm without prehashing the message is resistant to collisions in the hash function, while using the algorithm with prehashing is not. Of course the hash function is not supposed to have collisions, but if it does, not prehashing gives added protection.

Answer 2

The goal of this method is to achieve collision-resilience (resistance against collision attacks). The second hash can be viewed as $H(R || M)$ for message M and some randomness R that is unknown to an attacker. Now, even if an attacker could efficiently find collisions for $H$, he cannot use this ability to run the standard forgery attack that works as follows:

1. Find collision $M,M'$ for $H$,
2. Ask signer for signature $\sigma$ on message $M$,
3. Output forgery $(\sigma, M')$.

This attack normally works because the signature actually only signs $H(M)$ and $H(M) = H(M')$. Now, if an attacker does not know $R$ he cannot efficiently search for a collision $H(R||M) = H(R||M')$. Especially, a collision $M,M'$ for $H$ does not lead a collision $H(R||M) = H(R||M')$ for random $R$ with overwhelming probability.

Now, why do they hash twice? The reason is to avoid the use of "real" randomness in the signature algorithm. One motivation is that there have been to many issues with bad randomness sources / wrong implementations over the last years that one tries to avoid the use of randomness whenever possible. The first hash generates a pseudorandom value $R$ using the message and a secret value $S$ that is part of the secret key: $R = H(S||M)$.

Now, why is your proposal less secure? Because it is vulnerable to the above collision attack.

Of course, cryptographic hash functions should provide collision resistance. However, collision resistance is quite a strong assumption that is easier to break than other properties like second-preimage resistance, one-wayness, or pseudorandomness. On the one hand, already the complexity of a collision attack against a perfectly secure hash function is only the square-root of that of the attacks against the other properties. On the other hand, there hash been much more progress in breaking the collision resistance (see attacks on MD5 and SHA1 for example) than in breaking one of the other properties. Hence, it seems a good choice to avoid the requirement of collision resistance whenever possible.

P.S.: One might think that using $R = H(M||S), OUT = H(M || R)$ would provide the same benefits while allowing to reuse most of the computation (the state of $H$ after processing $M$). But exactly this makes the thing vulnerable to (inner) collisions again: If I find to messages $M,M'$ that lead to the same internal state of $H$ after being processed, they will also result in the same value $OUT$. Hence, I can use such a inner-collison to forge a signature.