Why is EdDSA collision-resilient with SHA-512?

Question

In the Bernstein et al. paper about EdDSA, the authors claim EdDSA is resilient against collisions (i.e. it can still be secure even if the hash function used isn't collision-resistant), drawing on a result from Neven et al. that says that Schnorr signatures are secure when used with a hash function that is random-prefix preimage resistant and random-prefix second-preimage resistant. Bernstein says that

Neven, Smart, and Warinschi in [60] proposed taking advantage of collision resilience by choosing $H$ to output only $b/2$ bits, reducing the size of compressed signatures by 25%

and then makes the following claim:

Our verification equation is the same as Schnorr's verification equation with double-size hashing instead of half-size hashing, with $\underline{A}$ inserted as an extra hash input, and without Schnorr's compression of $\underline{R}$. These modifications obviously do not compromise security.

However: In Neven, one mention of halving the hash length occurs at page 8, where they note that the herding attack from Kelsey and Kohno allows one to use a lack of collision-resistance for a Merkle–Damgård hash functions to break the random-prefix preimage and second-preimage resistance requirements, and so recommend not using a Merkle–Damgård hash function as-is, and instead truncating it. They present this not as a convenience thing, but a security thing (so that even if collision-resistance is compromised, the two properties needed for Schnorr signatures to be secure aren't necessarily compromised by the herding attack). SHA-512, of course, is a Merkle–Damgård hash function.

Here's my question: I'm pretty sure I didn't catch something the authors of the EdDSA paper somehow missed. There's probably something I'm missing here. What is it?

Answer 1

The relevant part of Neven et al is this:

What this means for practice is that one should not instantiate the hash function with a Merkle-Damgård iteration of an $n$-bit compression function. Instead, one should probably simply truncate the output of a $2n$-bit hash function to $n$ bits. (Such a method would in our situation be reminiscent of Lucks’ wide-pipe hash [Luc05].) Therefore, using for example the first 128 bits of the SHA-256 hash should in practice provide a security level of 128 bits.

Ed25519 uses SHA-512, a 512-bit hash function. If the herding attack applies but the hash function itself is secure, its security level should be at least about 256 bits (the collision resistance of the hash function). That is way more than the security of the overall algorithm and so not relevant here.

Even if some collision attack on the ~256-bit number that results from the multiplication (after reduction modulo $l$) would allow breaking the signature scheme, that would still not break the claimed ~128-bit security level.

I.e. rather than running into problems due to using a half length Merkle–Damgård hash, Ed25519 uses a conservative double length hash and should not be affected.