14 ms·

It’s 255:19AM. Do you know what your validation criteria are?

199 points by FloDo 6y ago

classified 6y ago
I would recommend using a 24-hours clock, not AM/PM 256-hourglasses. There is also the outrageously absurd idea of putting units next to your entry fields so users know to enter metric values instead of furlongs.
- 3pt14159 6y ago
  Are you being sarcastic? The title is clearly chosen so that it makes the number 25519 in reference to the algorithm.
  - chrisseaton 6y ago
    But what has anything got to do with time here?
    - V99 6y ago
      The title is a reference to public service commercials that ran decades ago: https://en.wikipedia.org/wiki/Do_you_know_where_your_children_are%3F https://en.wikipedia.org/wiki/Do_you_know_where_your_childre...
      - deleted 6y ago
        [deleted]
  - floatingatoll 6y ago
    Wait, seriously? checks Okay, that's funny. I totally did not realize that at all until I found your comment.
- suprfsat 6y ago
  I would simply take 255 modulo 24 and use 15 rather than require the user to enter a so-called "canonical" encoding of an hour.
- nullc 6y ago
  It's also relevant to the topic because some of the issues its discussing relate to how over full inputs are validated. Do you reduce the 255 mod 24 to decide if the time is acceptable, or do you just reject anything over 23 as unreasonable... or maybe you only reject larger than 99 (because two digits is enough) but from 23 and 99 you reduce mod 24. In many kinds of programs it isn't too critical exactly how you handle unreasonable inputs. Garbage in Garbage out. In consensus systems, however, any difference in behaviour can be a fatal vulnerability. Some might find the motivation section of Bitcoin's BIP340 informative: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#Motivation https://github.com/bitcoin/bips/blob/master/bip-0340.mediawi... Or this earlier publication: https://slowli.github.io/ed25519-quirks/ https://slowli.github.io/ed25519-quirks/ (which has more explanation for the S value related issues that the parent article mostly skips over-- but lacks the breadth and the amazing illustration of the incompatibility train-wreak).
  - im3w1l 6y ago
    > In consensus systems, however, any difference in behaviour can be a fatal vulnerability. Another issue can come if you have code like this, and different validations are used. if (signature_valid()) { // Safe because we already verified signature. use_signed_message_or_die(); } In practice the check and usage could be very far apart in the code (maybe using the type system to keep track of verified signatures), or even in different programs.
bjornedstrom 6y ago
Relevant quote from the Ed25519 paper [1] under the heading "Signature System": "This section specifies the signature system used in this paper, and a generalized signature system EdDSA that can be used with other choices of elliptic curves": > Malleability. We also see no relevance of “malleability” to the standard definition of signature security. For example, if we slightly modified the system then replacing S by −S and replacing A by −A (a slight variant of the “attack” of [75]) would convert one valid signature into another valid signature of the same message under a new public key; but it would still not accomplish the attacker’s goal, namely to forge a signature on a new message under a target public key. One such modification would be to omit A from the hashing; another such modification would be to have A encode only |A|, rather than A. They key here is the second half of the paragraph: "it would still not accomplish the attacker’s goal, namely to forge a signature on a new message under a target public key". Similarly how the design doesn't see a problem with malleability in the sense of converting one valid signature into another valid signature, It seems to me it was never a design goal of Ed25519 to begin with to strictly define the set of valid (and invalid) signatures. This is why cryptography is difficult, because it's easy to use a primitive in a complex system and assume things about the primitives that possibly make them unsuited for the system developed. [1] https://ed25519.cr.yp.to/ed25519-20110926.pdf https://ed25519.cr.yp.to/ed25519-20110926.pdf
- Joker_vD 6y ago
  > it was never a design goal of Ed25519 to begin with to strictly define the set of valid (and invalid) signatures For a popular enough protocol, if there is an underspecified thing then there will be two implementations that implement that thing differently, and if possible, incompatibly. And I am talking about correctly programmed and compliant implementations, never mind the buggy and/or deliberately non-compliant implementations (cf. Microsoft's "No standard or clause in a standard has a divine right of existence" stance). That's why the designer should not leave the implementers any rope whatsoever to strangle themselves, especially in cryptography.
  - formerly_proven 6y ago
    > That's why the designer should not leave the implementers any rope whatsoever to strangle themselves, especially in cryptography. 5 bits of choice is a lot of rope to auto-asphyxiate oneself in cryptography.
kelnage 6y ago
This is very nice work. For those who are interested in academic work about detecting/preventing such attacks, there have been some recent papers that looked at the formal verifying protocol models [1, 2] to (dis)prove the absence of such vulnerabilities. 1. https://eprint.iacr.org/2019/779 https://eprint.iacr.org/2019/779 2. https://eprint.iacr.org/2020/823 https://eprint.iacr.org/2020/823
- srfilipek 6y ago
  The article discusses interoperability issues; it isn't an attack or vulnerability. The issue is that implementations will reject valid signatures.
  - kelnage 6y ago
    Yeah, sorry, my wording wasn’t clear. I meant that attacks exist based on not utilising appropriate validation criteria (and, for example, libsodium’s more strict criteria do indeed prevent them).
    - laksdjfkasljdf 6y ago
      Which attack(s) would that be?
- deleted 6y ago
  [deleted]
exabrial 6y ago
I'm curious, does ECDSA provide this? Not a crypto expert.
- nullc 6y ago
  Your question is a bit underspecified... ECDSA by itself isn't an implementable protocol: you also need to specify a curve and an encoding for the values at a minimum and ideally a hash function too. The common DER encoding used for ECDSA signatures introduces several behaviours similar to the ones being discussed here which differ between implementations. (Or, rather, DER itself doesn't but BER does and what things that implement DER usually implement is some subset of BER and some superset of DER). For curves with a cofactor similar issues also probably arise there-- I haven't thought much about that since I just try to avoid cofactor generally, because it's a pretty big footgun. :) ECDSA implemented as Bitcoin does today (post BIP66) with a perfectly strict and completely specified DER encoding-- a near-power-of-2-size cofactorless curve-- and an additional requirement on S being in the lower half of the range doesn't have these issues. ... except to the extent that someone could try to make an implementation copying some off-the-shelf-ecdsa and miss those specific requirements and only be partially compatible.
  - exabrial 6y ago
    Argh. The more I ask the less I know
deleted 6y ago
[deleted]
LeonM 6y ago
Ed25519 curves are currently being adopted for DKIM in RFC8463 [0]. I I wrote an article about this [1], where I concluded that Ed25519 is an improvement for DKIM over RSA (smaller keys, deprecation of SHA1). However, this finding may have big impact on the adoption rate of Ed25519 for DKIM. Specifically for DKIM validators (MTAs). MTAs are already amongst the worst offenders when it comes to not adhering to the standards. The DKIM canonicalisation scheme [2] is already hard enough to implement on it's own, now with this finding we might get even more false positives and negatives in DKIM validation. Let's hope that the finding will encourage library maintainers to come to a consensus on how to validate Ed25519. And also hope that MTA developers will not try to roll their own... [0] https://tools.ietf.org/html/rfc8463 https://tools.ietf.org/html/rfc8463 [1] https://www.mailhardener.com/kb/how-to-use-dkim-with-ed25519 https://www.mailhardener.com/kb/how-to-use-dkim-with-ed25519 [2] https://tools.ietf.org/html/rfc6376#section-3.4 https://tools.ietf.org/html/rfc6376#section-3.4
- GoblinSlayer 6y ago
  The author's concern is an attack on decentralized consensus process, which isn't a problem for DKIM.
- fanf2 6y ago
  If I understand the article correctly this isn't a problem for uses of Ed25519 in systems like DKIM or DNSSEC. These Ed25519 interop problems only arise with maliciously crafted keys and nonces. This is a problem for consensus systems (like Zcash in the article) because the signature is recorded and needs to be verified by many parties, and if a malicious signature it tickles an interop bug it can maybe (handwave) force third parties to treat the blockchain as invalid, or something like that. But in the context of DKIM if a sender generates a signature that a recipient can't validate, by using buggy key generation code that produces small cofactors or noncanonical encodings, only the sender suffers pain.
  - nullc 6y ago
    It's been a LONG time since I had to administer an SMTP server that handled mail for other people ... Is there a potential for, say, getting an intermediate gateway banned for sending invalid signatures by relaying them via it?
GoblinSlayer 6y ago
In the context of consensus can't the attacker simply send invalid signatures to some participants and valid signatures to other participants thus preventing consensus?

199 points by FloDo 6y ago

I would recommend using a 24-hours clock, not AM/PM 256-hourglasses. There is also the outrageously absurd idea of putting units next to your entry fields so users know to enter metric values instead of furlongs.

3pt14159 6y ago
Are you being sarcastic? The title is clearly chosen so that it makes the number 25519 in reference to the algorithm.
- chrisseaton 6y ago
  But what has anything got to do with time here?
  - V99 6y ago
    The title is a reference to public service commercials that ran decades ago: https://en.wikipedia.org/wiki/Do_you_know_where_your_children_are%3F https://en.wikipedia.org/wiki/Do_you_know_where_your_childre...
    - deleted 6y ago
      [deleted]
- floatingatoll 6y ago
  Wait, seriously? checks Okay, that's funny. I totally did not realize that at all until I found your comment.
suprfsat 6y ago
I would simply take 255 modulo 24 and use 15 rather than require the user to enter a so-called "canonical" encoding of an hour.
nullc 6y ago
It's also relevant to the topic because some of the issues its discussing relate to how over full inputs are validated. Do you reduce the 255 mod 24 to decide if the time is acceptable, or do you just reject anything over 23 as unreasonable... or maybe you only reject larger than 99 (because two digits is enough) but from 23 and 99 you reduce mod 24. In many kinds of programs it isn't too critical exactly how you handle unreasonable inputs. Garbage in Garbage out. In consensus systems, however, any difference in behaviour can be a fatal vulnerability. Some might find the motivation section of Bitcoin's BIP340 informative: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#Motivation https://github.com/bitcoin/bips/blob/master/bip-0340.mediawi... Or this earlier publication: https://slowli.github.io/ed25519-quirks/ https://slowli.github.io/ed25519-quirks/ (which has more explanation for the S value related issues that the parent article mostly skips over-- but lacks the breadth and the amazing illustration of the incompatibility train-wreak).
- im3w1l 6y ago
  > In consensus systems, however, any difference in behaviour can be a fatal vulnerability. Another issue can come if you have code like this, and different validations are used. if (signature_valid()) { // Safe because we already verified signature. use_signed_message_or_die(); } In practice the check and usage could be very far apart in the code (maybe using the type system to keep track of verified signatures), or even in different programs.

bjornedstrom 6y ago

Relevant quote from the Ed25519 paper [1] under the heading "Signature System": "This section specifies the signature system used in this paper, and a generalized signature system EdDSA that can be used with other choices of elliptic curves": > Malleability. We also see no relevance of “malleability” to the standard definition of signature security. For example, if we slightly modified the system then replacing S by −S and replacing A by −A (a slight variant of the “attack” of [75]) would convert one valid signature into another valid signature of the same message under a new public key; but it would still not accomplish the attacker’s goal, namely to forge a signature on a new message under a target public key. One such modification would be to omit A from the hashing; another such modification would be to have A encode only |A|, rather than A. They key here is the second half of the paragraph: "it would still not accomplish the attacker’s goal, namely to forge a signature on a new message under a target public key". Similarly how the design doesn't see a problem with malleability in the sense of converting one valid signature into another valid signature, It seems to me it was never a design goal of Ed25519 to begin with to strictly define the set of valid (and invalid) signatures. This is why cryptography is difficult, because it's easy to use a primitive in a complex system and assume things about the primitives that possibly make them unsuited for the system developed. [1] https://ed25519.cr.yp.to/ed25519-20110926.pdf https://ed25519.cr.yp.to/ed25519-20110926.pdf

Joker_vD 6y ago
> it was never a design goal of Ed25519 to begin with to strictly define the set of valid (and invalid) signatures For a popular enough protocol, if there is an underspecified thing then there will be two implementations that implement that thing differently, and if possible, incompatibly. And I am talking about correctly programmed and compliant implementations, never mind the buggy and/or deliberately non-compliant implementations (cf. Microsoft's "No standard or clause in a standard has a divine right of existence" stance). That's why the designer should not leave the implementers any rope whatsoever to strangle themselves, especially in cryptography.
- formerly_proven 6y ago
  > That's why the designer should not leave the implementers any rope whatsoever to strangle themselves, especially in cryptography. 5 bits of choice is a lot of rope to auto-asphyxiate oneself in cryptography.

kelnage 6y ago

This is very nice work. For those who are interested in academic work about detecting/preventing such attacks, there have been some recent papers that looked at the formal verifying protocol models [1, 2] to (dis)prove the absence of such vulnerabilities. 1. https://eprint.iacr.org/2019/779 https://eprint.iacr.org/2019/779 2. https://eprint.iacr.org/2020/823 https://eprint.iacr.org/2020/823

srfilipek 6y ago
The article discusses interoperability issues; it isn't an attack or vulnerability. The issue is that implementations will reject valid signatures.
- kelnage 6y ago
  Yeah, sorry, my wording wasn’t clear. I meant that attacks exist based on not utilising appropriate validation criteria (and, for example, libsodium’s more strict criteria do indeed prevent them).
  - laksdjfkasljdf 6y ago
    Which attack(s) would that be?
deleted 6y ago
[deleted]

exabrial 6y ago

I'm curious, does ECDSA provide this? Not a crypto expert.

nullc 6y ago
Your question is a bit underspecified... ECDSA by itself isn't an implementable protocol: you also need to specify a curve and an encoding for the values at a minimum and ideally a hash function too. The common DER encoding used for ECDSA signatures introduces several behaviours similar to the ones being discussed here which differ between implementations. (Or, rather, DER itself doesn't but BER does and what things that implement DER usually implement is some subset of BER and some superset of DER). For curves with a cofactor similar issues also probably arise there-- I haven't thought much about that since I just try to avoid cofactor generally, because it's a pretty big footgun. :) ECDSA implemented as Bitcoin does today (post BIP66) with a perfectly strict and completely specified DER encoding-- a near-power-of-2-size cofactorless curve-- and an additional requirement on S being in the lower half of the range doesn't have these issues. ... except to the extent that someone could try to make an implementation copying some off-the-shelf-ecdsa and miss those specific requirements and only be partially compatible.
- exabrial 6y ago
  Argh. The more I ask the less I know

deleted 6y ago

[deleted]

LeonM 6y ago

Ed25519 curves are currently being adopted for DKIM in RFC8463 [0]. I I wrote an article about this [1], where I concluded that Ed25519 is an improvement for DKIM over RSA (smaller keys, deprecation of SHA1). However, this finding may have big impact on the adoption rate of Ed25519 for DKIM. Specifically for DKIM validators (MTAs). MTAs are already amongst the worst offenders when it comes to not adhering to the standards. The DKIM canonicalisation scheme [2] is already hard enough to implement on it's own, now with this finding we might get even more false positives and negatives in DKIM validation. Let's hope that the finding will encourage library maintainers to come to a consensus on how to validate Ed25519. And also hope that MTA developers will not try to roll their own... [0] https://tools.ietf.org/html/rfc8463 https://tools.ietf.org/html/rfc8463 [1] https://www.mailhardener.com/kb/how-to-use-dkim-with-ed25519 https://www.mailhardener.com/kb/how-to-use-dkim-with-ed25519 [2] https://tools.ietf.org/html/rfc6376#section-3.4 https://tools.ietf.org/html/rfc6376#section-3.4

GoblinSlayer 6y ago
The author's concern is an attack on decentralized consensus process, which isn't a problem for DKIM.
fanf2 6y ago
If I understand the article correctly this isn't a problem for uses of Ed25519 in systems like DKIM or DNSSEC. These Ed25519 interop problems only arise with maliciously crafted keys and nonces. This is a problem for consensus systems (like Zcash in the article) because the signature is recorded and needs to be verified by many parties, and if a malicious signature it tickles an interop bug it can maybe (handwave) force third parties to treat the blockchain as invalid, or something like that. But in the context of DKIM if a sender generates a signature that a recipient can't validate, by using buggy key generation code that produces small cofactors or noncanonical encodings, only the sender suffers pain.
- nullc 6y ago
  It's been a LONG time since I had to administer an SMTP server that handled mail for other people ... Is there a potential for, say, getting an intermediate gateway banned for sending invalid signatures by relaying them via it?

GoblinSlayer 6y ago

In the context of consensus can't the attacker simply send invalid signatures to some participants and valid signatures to other participants thus preventing consensus?