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.

Answer 3

It wouldn't be as secure as Ed25519, but it could well be as secure in practice.

Let's put things in perspective. By doing pre-hashing, you are exposed to collision attacks in the hash function [1]. But SHA-512 provides a 256-bit security level against collisions. Even if we reduce that level by 2, which would be a total break much worse than the break of say SHA-1, you would still have a very comfortable security level of 128 bits. Divide it by 3, and you still have 80 bit of security, which may become reachable in the future, but would still give you enough of time to adapt, and in fact still better than the broken SHA-1 (still used, I recall). In practice, the only reason to go for such a high security level is exactly to provide you with a strong margin in case of cryptographic breaks.

So your proposal is certainly fine. There are however two other options you can consider.

The better option is to use Ed25519ph (see RFC 8032 [1]). If available in your application, Ed25519ph provides by default a pre-hashing step and offers better protection against fault attacks, which is more interesting in practice.

But if you have to stick to Ed25519, and still would like to mitigate the collision issue, you could do pre-hashing with salting. At the time of signing, you generate a random salt that you prepend to your message. So, instead of doing hash(M) you would do hash(Salt || M). The signing output would be the standard signature and that salt. Note that salting wouldn't remove the collision attacks, but would prevent its offline exploitation, which in most cases is largely sufficient. There are various ways to produce the salt, but you have to make sure that it cannot be controlled or predicted by the adversary. This solution is a bit messy, and I wouldn't recommend it over your simpler proposal.

[1] https://tools.ietf.org/html/rfc8032