4 ms·

It has always seemed like a footgun for the algorithm to totally cave if the 'r' value is reused for the same key and different message. This attack uses the de

It has always seemed like a footgun for the algorithm to totally cave if the 'r' value is reused for the same key and different message. This attack uses the deterministic 'r' generation using the key and the message (to ensure that the 'r' is only reused if the message is the same), but then glitches the hash function that is used on the message during signing (so the same'r' is used on a different message). 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.

loup-vaillant 9y ago
I have another, perhaps less silly question. 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.
- cesarb 9y ago
  Shouldn't the "message" being signed by EdDSA (or others like RSA) be a hash of the real data? That way you can do a streaming interface just fine, and the "message" being hashed within EdDSA is small and constant-sized. 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.
  - loup-vaillant 9y ago
    > Shouldn't the "message" being signed by EdDSA (or others like RSA) be a hash of the real data? 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?
    - deleted 9y ago
      [deleted]
- bascule 9y ago
  RFC 8032 already specifies an "Ed25519ph" variant which prehashes the message and therefore facilitates Initialize-Update-Finalize (IUF) APIs: https://tools.ietf.org/html/rfc8032#section-4 https://tools.ietf.org/html/rfc8032#section-4
- cryptonector 9y ago
  EdDSA is NOT online, but it's trivial to use it in an online way: sign a hash of the data rather than the data. But now you're back to having collisions (EdDSA is collision resistant). So it's a trade-off you have to make. As for DJB's take on this, there were lengthy debates about this on the CFRG list, and you find out for yourself (spoilers: he's very big on collision resistance). Of course, the need for online algorithms is real, but there's more than one way to skin that cat.
  - loup-vaillant 9y ago
    Do you have a link to those debates? I'm searching through the mailing list, no luck so far.
    - cryptonector 9y ago
      The list archives are difficult to link to. 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.html 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.html https://www.ietf.org/mail-archive/web/cfrg/current/maillist....)

loup-vaillant 9y ago

I have another, perhaps less silly question. 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.

cesarb 9y ago
Shouldn't the "message" being signed by EdDSA (or others like RSA) be a hash of the real data? That way you can do a streaming interface just fine, and the "message" being hashed within EdDSA is small and constant-sized. 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.
- loup-vaillant 9y ago
  > Shouldn't the "message" being signed by EdDSA (or others like RSA) be a hash of the real data? 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?
  - deleted 9y ago
    [deleted]
bascule 9y ago
RFC 8032 already specifies an "Ed25519ph" variant which prehashes the message and therefore facilitates Initialize-Update-Finalize (IUF) APIs: https://tools.ietf.org/html/rfc8032#section-4 https://tools.ietf.org/html/rfc8032#section-4
cryptonector 9y ago
EdDSA is NOT online, but it's trivial to use it in an online way: sign a hash of the data rather than the data. But now you're back to having collisions (EdDSA is collision resistant). So it's a trade-off you have to make. As for DJB's take on this, there were lengthy debates about this on the CFRG list, and you find out for yourself (spoilers: he's very big on collision resistance). Of course, the need for online algorithms is real, but there's more than one way to skin that cat.
- loup-vaillant 9y ago
  Do you have a link to those debates? I'm searching through the mailing list, no luck so far.
  - cryptonector 9y ago
    The list archives are difficult to link to. 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.html 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.html https://www.ietf.org/mail-archive/web/cfrg/current/maillist....)