7 ms·

Even JSON isn't great. It's still a hash-collision DoS attack vector. https://paragonie.com/blog/2016/04/securely-implementing-de-serialization-in-php https://

Even JSON isn't great. It's still a hash-collision DoS attack vector. https://paragonie.com/blog/2016/04/securely-implementing-de-serialization-in-php https://paragonie.com/blog/2016/04/securely-implementing-de-...

nickpsecurity 10y ago
Dude, that's horrific. I figured some secure coders wouldve at least implemented a better JSON one by now since it's relatively simple. Or are they already available but dev's often rely on these broken ones?
- justinlardinois 10y ago
  Hash functions designed for hash tables are generally not hard to find collisions for, so there's not much that can be done. You could shoehorn in a secure hash function, but that would hurt performance.
  - perlgeek 10y ago
    You can randomize some parameters of the hashing function when you detect too many collisions. Which makes a DOS much harder. The Perl interpreter has been doing that for ages.
  - nickpsecurity 10y ago
    I was thinking more on lines of (a) does JSON handling need hash tables and (b) if do, do they have to be open addressing or something vulnerable to DOS? A No on either can lead to an implementation with better DOS resistance.
    - qwertyuiop924 10y ago
      For B) All hash table implementations are vulnerable to this kind of attack. However, some kinds of chaining are less vulnerable. In particular, balanced binary tree chaining would make the worst-case lookup (and insertion?) time complexity O(log n), which is a significant improvement over probing or linked list chaining. The tricks mentioned in the other comments above also improve things, by making such an event less likely. As for A), no. No, JSON handling doesn't need hashtables. Since your app will only look at certain values in the JSON, you can simply ignore all the other values, and dump the values in an object/struct of your choosing. It wouldn't even be all that hard to write, provided you know how to write a parser...
      - nickpsecurity 10y ago
        Since your app will only look at certain values in the JSON, you can simply ignore all the other values, and dump the values in an object/struct of your choosing. It wouldn't even be all that hard to write, provided you know how to write a parser..." That's what I was thinking. Never seen verified parsers or generators requiring these things. So I figured it was an unnecessary requirement bringing in its own security issue.
        vidarh 10y ago
        A large part of the problem is that people want to be able to "just" de-serialize a chunk of JSON into a suitable generic structure they can then "just" de-reference as a suitable tree of dictionaries and arrays. It'd be fantastic to see easier-to-use patterns to discourage resorting to this, but it's very hard to beat for simplicity.
  - Scaevolus 10y ago
    Having per-table random seeds and properly designed hash function prevents remotely forced collisions. This is the typical defense against hashtable DOS. It has to be done properly, of course -- for example, a poorly designed hash function could have characteristic collisions for many different seeds.
    - haberman 10y ago
      Please be aware that many common hash functions are easy to generate collisions for independent of the seed. This includes both MurmurHash and CityHash. These aren't poorly-designed hash functions: they have excellent distribution characteristics. But the way they use their seed wasn't designed to resist this kind of attack.
      - Scaevolus 10y ago
        Rather than "poorly-designed", I should have said "cryptographically insecure". Most hash functions are engineered for speed and collision resistance, in that order. Trading collision resistance for speed is worthwhile for many workloads, since it barely affects the average case.
        haberman 10y ago
        > Most hash functions are engineered for speed and collision resistance, in that order. I disagree with that assessment. I think most hash functions are designed for speed and good distribution of outputs given normal inputs. But designing to resist collisions against someone trying to deliberately create them is a different thing entirely. > Trading collision resistance for speed is worthwhile for many workloads, since it barely affects the average case. I think that is far from established. SipHash is marketed under this premise, but from what I have heard it is significantly slower, particularly for short inputs.
        Scaevolus 10y ago
        Yes, speed for normal inputs is what's generally desired. A faster hash function can yield better overall performance than having fewer collisions. Here's some empirical evidence for this: https://www.strchr.com/hash_functions https://www.strchr.com/hash_functions The speed is correlated only weakly with the number of collisions-- and using the modern x86 CRC32 instruction yields the best results.
  - JeremyBanks 10y ago
    I think that most major languages have fixed this for years. Python in 2012: http://bugs.python.org/issue13703 http://bugs.python.org/issue13703
    - peteretep 10y ago
      Almost 13 years in Perl's case: http://perl5.git.perl.org/perl.git/commit/4b5190b5321b9b9e2ec46674b256120d4fdab72a http://perl5.git.perl.org/perl.git/commit/4b5190b5321b9b9e2e...
  - adrianratnapala 10y ago
    Or you could use tries.

nickpsecurity 10y ago

Dude, that's horrific. I figured some secure coders wouldve at least implemented a better JSON one by now since it's relatively simple. Or are they already available but dev's often rely on these broken ones?

justinlardinois 10y ago
Hash functions designed for hash tables are generally not hard to find collisions for, so there's not much that can be done. You could shoehorn in a secure hash function, but that would hurt performance.
- perlgeek 10y ago
  You can randomize some parameters of the hashing function when you detect too many collisions. Which makes a DOS much harder. The Perl interpreter has been doing that for ages.
- nickpsecurity 10y ago
  I was thinking more on lines of (a) does JSON handling need hash tables and (b) if do, do they have to be open addressing or something vulnerable to DOS? A No on either can lead to an implementation with better DOS resistance.
  - qwertyuiop924 10y ago
    For B) All hash table implementations are vulnerable to this kind of attack. However, some kinds of chaining are less vulnerable. In particular, balanced binary tree chaining would make the worst-case lookup (and insertion?) time complexity O(log n), which is a significant improvement over probing or linked list chaining. The tricks mentioned in the other comments above also improve things, by making such an event less likely. As for A), no. No, JSON handling doesn't need hashtables. Since your app will only look at certain values in the JSON, you can simply ignore all the other values, and dump the values in an object/struct of your choosing. It wouldn't even be all that hard to write, provided you know how to write a parser...
    - nickpsecurity 10y ago
      Since your app will only look at certain values in the JSON, you can simply ignore all the other values, and dump the values in an object/struct of your choosing. It wouldn't even be all that hard to write, provided you know how to write a parser..." That's what I was thinking. Never seen verified parsers or generators requiring these things. So I figured it was an unnecessary requirement bringing in its own security issue.
      - vidarh 10y ago
        A large part of the problem is that people want to be able to "just" de-serialize a chunk of JSON into a suitable generic structure they can then "just" de-reference as a suitable tree of dictionaries and arrays. It'd be fantastic to see easier-to-use patterns to discourage resorting to this, but it's very hard to beat for simplicity.
- Scaevolus 10y ago
  Having per-table random seeds and properly designed hash function prevents remotely forced collisions. This is the typical defense against hashtable DOS. It has to be done properly, of course -- for example, a poorly designed hash function could have characteristic collisions for many different seeds.
  - haberman 10y ago
    Please be aware that many common hash functions are easy to generate collisions for independent of the seed. This includes both MurmurHash and CityHash. These aren't poorly-designed hash functions: they have excellent distribution characteristics. But the way they use their seed wasn't designed to resist this kind of attack.
    - Scaevolus 10y ago
      Rather than "poorly-designed", I should have said "cryptographically insecure". Most hash functions are engineered for speed and collision resistance, in that order. Trading collision resistance for speed is worthwhile for many workloads, since it barely affects the average case.
      - haberman 10y ago
        > Most hash functions are engineered for speed and collision resistance, in that order. I disagree with that assessment. I think most hash functions are designed for speed and good distribution of outputs given normal inputs. But designing to resist collisions against someone trying to deliberately create them is a different thing entirely. > Trading collision resistance for speed is worthwhile for many workloads, since it barely affects the average case. I think that is far from established. SipHash is marketed under this premise, but from what I have heard it is significantly slower, particularly for short inputs.
        Scaevolus 10y ago
        Yes, speed for normal inputs is what's generally desired. A faster hash function can yield better overall performance than having fewer collisions. Here's some empirical evidence for this: https://www.strchr.com/hash_functions https://www.strchr.com/hash_functions The speed is correlated only weakly with the number of collisions-- and using the modern x86 CRC32 instruction yields the best results.
- JeremyBanks 10y ago
  I think that most major languages have fixed this for years. Python in 2012: http://bugs.python.org/issue13703 http://bugs.python.org/issue13703
  - peteretep 10y ago
    Almost 13 years in Perl's case: http://perl5.git.perl.org/perl.git/commit/4b5190b5321b9b9e2ec46674b256120d4fdab72a http://perl5.git.perl.org/perl.git/commit/4b5190b5321b9b9e2e...
- adrianratnapala 10y ago
  Or you could use tries.