5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I am totally not impressed that another person is able to edit the words I wrote If they are inappropriate, deleting them is fine, but editing them? WTF? With that brilliant move, Stack Exchange and it's editors have significantly reduced the chance I will participate in this site... $\endgroup$ – Allen Aug 5 '15 at 9:43
  • $\begingroup$ Hi Allen. Other persons can edit your answers and questions yes, but you will be notified and it is possible to roll them back, as can we. If there is too much abuse then the mods & trusted users (10K and up, if I'm not mistaken) can protect an entire Q/A against modifications. You can always see the revision history by clicking on the edited (time of edit) link between the answer and the person that last edited it. But yes, SE is a collaberative effort; if you really require exclusive rights a blog is more appropriate. $\endgroup$ – Maarten Bodewes Aug 5 '15 at 13:06
  • $\begingroup$ I cannot remember anything being protected on the crypto site though; there isn't much flaming going on. Generally the edits are rather mundane and keep to formatting an answer :) . Note that substantive edits that change the answer are not allowed and will be acted upon. More information here $\endgroup$ – Maarten Bodewes Aug 5 '15 at 13:13
2
$\begingroup$

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.

$\endgroup$

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.