EdDSA calculates $s=(r+H(R\mathbin{\Vert}A\mathbin{\Vert}M)\cdot a)\bmod\ell$ and $r=H(h\mathbin{\Vert}M)$, with

  • $H$ being the hash function (SHA2/512);
  • $B$ being the generator;
  • $A$ being the public key;
  • $a$ being the secret exponent;
  • $r$ being the per-signature random;
  • $h$ being the secret seed ($h[b~.\!.~2b-1]$ in the paper).

What is the effect on the security of the signature if $M$ is replaced by $H(M)$ or $H(A\mathbin{\Vert}M)$, thus producing $s=(r+H(R\mathbin{\Vert}A\mathbin{\Vert}H(A\mathbin{\Vert}M))\cdot a)\bmod\ell$ and $r=H(h\mathbin{\Vert}H(A\mathbin{\Vert}M))$?

This would mean the message needs to be hashed only once during signing, which is more efficient for long messages, but would the signature lose any security quality? Specifically the paper says that the signature provides collision resistance, would this disappear with $M$ being replaced by $H(M)$? What about $H(A\mathbin{\Vert}M)$?


Assuming this is the paper you're talking about, your modification completely eliminates resilience to collisions in the underlying hash function $H$. The EdDSA scheme (and in the Schnorr scheme on which it is based) is highly resilient against collisions in $H$. Specifically, in the generic group model, the Schnorr scheme has been proven to be secure even if $H$ isn't collision-resistant; all it requires for security is that $H$ be resistant to random-prefix preimage attacks and random-prefix second preimage attacks (essentially, given random $R$: given $h$ it's hard to find $M$ s.t. $H(R||M)=h$, and given $N$ it's hard to find $N^\prime$ s.t. $H(R||N)=H(R||N^\prime)$ and $N\ne N^\prime$).

So EdDSA can be perfectly OK with a not collision-resistant hash; as far as we know, it doesn't need collision resistance, just random-prefix preimage and random-prefix second-preimage resistance.

However, your modification is trivially vulnerable to a collision in $H$: If $H(M)=H(M^\prime)$, then if you hash $M$ before signing, you end up with an EdDSA signature of $H(M)=H(M^\prime)$ which (under your modification) is a signature for $M^\prime$. If you instead do $H(A||M)$, an attacker who finds any chosen-prefix collision can create two messages such that a signature for one is a signature for the other. If you use $H(A||M)$ as the thing to be signed, someone who can find any two messages s.t. $H(A||M)=H(A||N)$ again can take a signature for one and use it as a valid signature for the other. With a good hash function, they can't find said collision, but Schnorr (and so EdDSA) is designed such that it doesn't break if they can do that.

If someone gets a message $M$ signed with $(R,S)$, and finds a second preimage for $H(R||A||M)$ (i.e. $M^\prime$ s.t. $H(R||A||M^\prime)=H(R||A||M)$, then the signature for $M$ is valid for $M^\prime$. However, an attacker with just the ability to find collisions cannot exploit this: they do not control $R$, and $R$ is different for each $M$. So finding a collision in $f(M)=H(R||A||M)$ is useless for the attacker; to exploit the collision, one of the colliding messages must have $H(h||M)B=R$, which is not going to be the case for a generic one of a colliding pair. Collision attacks do not apply, because a colliding pair only helps if they collide when prefixed by a secret function of one of them, which will not generally be the case.

| improve this answer | |
  • $\begingroup$ Thank you, yes, that's the paper. But if they can find a collision in H(A|M) can't they find a collision in H(R|A|M) ? All I've done is increase the chance by the number of signatures, realistically any given key won't ever sign more than 2^64 messages (or an attacker can store). If that few signatures are enough to produce a collision, wouldn't it be realistic to expect a collision in H(R|A|M). Then again, isn't the problem exactly the same? Both R and A are known to the attacker, only that R is per message while A is constant. What am I missing? $\endgroup$ – Martin Jan 12 '15 at 9:24
  • $\begingroup$ In fact, as I'm thinking about it, isn't H(R|A|M) worse than H(A|M), since A is the public key, thus the attacker isn't in control of it, and H(R|A|M) produces more prefixes to find collisions against? $\endgroup$ – Martin Jan 12 '15 at 9:49
  • $\begingroup$ A collision in $H(R||A||M)$ isn't helpful -- $R=rB$, so it depends on $M$ (and so even if $H(R||A||M)=H(R||A||M^\prime)$, an actual signature doesn't involve $H(R||A||M^\prime)$, but rather $H(R^\prime||A||M^\prime)$. And $r=H(h||M)$ includes secret data, and is itself secret, so the attacker cannot attack that hash value. $\endgroup$ – cpast Jan 12 '15 at 12:24
  • $\begingroup$ A signature, or rather a signed message has A (signer's public key), B (generator), R and s (the actual signature) and M (the message), the verifier compares s * B to R + A * H(R|A|M), what prevents me from finding a M' with H(R|A|M')=H(R|A|M) and passing it off as a valid message, and if I can do that what good is it, and if I can't why isn't H(A|M) enough? $\endgroup$ – Martin Jan 12 '15 at 12:47
  • $\begingroup$ Hm. It looks like you're right; I retract my comments about $H(A||M)$ for now, and need to think about this some more. $\endgroup$ – cpast Jan 12 '15 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.