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

Peter Schwabe peter at cryptojedi.org
Wed Aug 5 22:30:04 EDT 2015


Allen <allenpmd at gmail.com> wrote:

Dear Allen, dear all,

> > Exploiting hash collisions in digital signature algorithms have led
> > to real-world attacks. See e.g. Flame MD5 collision. 
> 
> Would hashing twice with MD5 be the best way to prevent that attack,
> or might it be better to use a stronger hash function?  

Please note that Ed25519 is not just simply "hashing with MD5 twice".

> See also my
> earlier comment: "I could probably find a way to use those CPU cycles
> that would yield a better payoff (using a stronger curve or a more
> complicated hash function perhaps?)."

I have the impression that there are two aspects of EdDSA that get
confused in this discussion: the issue of pre-hashing (and losing
collision resilience) and the issue of deterministic signing (which
requires the two hash computations). 

The two hashes computed for Ed25519 signing are
1.) r = H(h_b,...,h_{2b-1},M) and
2.) H(R,A,M)

Instead of computing the first hash, one *could* pick r as a uniformly
random scalar modulo the group order l. This is in fact what Schnorr
signatures (and similarly ECDSA signatures) do. However, then the
security of the scheme then largely depends on the RNG, which is outside
the scope of testing of the signature scheme. Also, cryptographically
secure random numbers are not always easy to obtain and RNG failures
have been the reason for multiple real-world attacks in the past, so
EdDSA is designed to not rely on a secure RNG for signing.

The second hash includes R at the beginning, which is not
attacker-controlled and makes the scheme collision-resilient. The point
is that an attacker who can compute an internal or external collision
of H cannot forge a signature. Obviously, this feature is lost when
replacing M with H(M) (i.e., when pre-hashing the message). The cost of
not pre-hashing depends on the length of the message. For signatures on
short messages (like, e.g., public keys) the overhead is neglible, for
very long messages it approaches a factor of 2.
I certainly agree that it's a good idea to use a stronger hash function
than MD5. When suggesting a better payoff for CPU cycles, then the
questions are what message lengths you're dealing with and what attacks
you're worried about. Personally, until quantum computers are built, I
am less concerned about a DLP attack against Curve25519 than about a
collision in SHA-2.

Best regards,

Peter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 173 bytes
Desc: Digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150806/cc9a54f0/attachment.sig>


More information about the cryptography mailing list