The way EdDSA works, one needs to hash the message twice, in a way that makes incremental hashing impossible (you need to complete the first pass before you begin the second):
r = Hash(secret_key | message)
R = Base_point × r
H = Hash(R | public_key | message)
// use H to compute the signature
Because of this, we cannot have a streaming interface. Thus, signing and verifying huge messages is a hassle. I think there are ways to avoid this, if we're willing to mess with EdDSA (I'm not).We could for instance change the second hash to this:
H = Hash(public_key | message | R)
By appending R to the rest, instead of pre-pending it, we can perform the two hashes in parallel, and use the result of the first hash only for the last bit of the second hash.A more involved tweak would hash the message first:
r = Hash(message | secret_key)
R = Base_point × r
H = Hash(message | R | public_key)
That way you can hash the message once, then duplicate the hash context to complete the two hashes.---
Now the question: would those modifications work? Are they still immune to collision attacks? How about length extension attacks?
Subsidiary question: if my modifications are secure, how DJB and al didn't think of it? DJB in particular is reputed to be quite performance sensitive.
Look for posts around June 2015, e.g., with Subject:s like "Summary of the poll: Elliptic Curves - signature scheme: friendliness to low memory implementations" or subjects containing "IUF" (Init, Update, Final) here:
https://www.ietf.org/mail-archive/web/cfrg/current/mail5.htm...
(The archives' main page is https://www.ietf.org/mail-archive/web/cfrg/current/maillist....)
I think the idea with the ordering of the inputs to the hash functions was to always put the most secret data first, to make things harder for the attacker. It was probably expected that the "message" would always be small, like it must be with for instance RSA.
It could be, and that's what I currently recommend. But then isn't there a problem with collision attacks? Or does one still has to perform a pre-image attack on the hashes of previous messages?
Edit: Removed silly question on why the order has to be 'r' before the second hash. Spolier: Signature is two parts - and at least one needs to be fixed to prevent an forger just modifying both. That needs to be the 'r' part, so it has to be before the S.