Possible DOS due to hash collision

[TomMD]

As detailed in a blog, Aeson is susceptible to DOS if given maliciously-crafted JSON. This is likely a tired conversation for many developers, but with the public posting today it seems good to have a public issue tracking the discussion and resolution.

[NorfairKing]

Author here: Happy to help with this.

[phadej]

Indeed, it's old and known problem. See e.g. https://oleg.fi/gists/posts/2021-05-19-dont-default-to-hashmap.html

Yet, I'm not keen at changing Value, but rather would skip Value in decoding pipeline entirely. That would allow people e.g. process key-value pairs on order (if it matters for them), deal with duplicate keys (again, if it matters), possibly work with as-written values of number literals etc.

[NorfairKing]

Indeed, it's old and known problem. See e.g. https://oleg.fi/gists/posts/2021-05-19-dont-default-to-hashmap.html

With all due respect, that makes this worse, not better.

Yet, I'm not keen at changing Value, but rather would skip Value in decoding pipeline entirely.

That's a much bigger breaking change and would make it entirely new library.
We have played around with this idea by making the equivalent of optparse-applicative, but for json parsing without an intermediate type.
That approach has different tradeoffs and can be cool, but it doesn't solve the problem at hand in aeson right now.

[TomMD]

@NorfairKing In the post you indicated a rejected PR, could you link that here now that the issue is publicly discussed?

@phadej Among the proposed paths forward, is there a short-term solution you'd be in favor of? This issue deserves a short term fix, even if it isn't the desired end state.

[NorfairKing]

@NorfairKing In the post you indicated a rejected PR, could you link that here now that the issue is publicly discussed?

It's linked in the post but here's the link again: haskell-unordered-containers/unordered-containers#217

[phadej]

@TomMD:

• Introduce Data.Aeson.Object module with anObject opaque newtype(fromList, toList, member), maybe TextMap v would be simpler to avoid circular dependencies.
• Add a manual flag to switch between Map to HashMap- the internals shouldn't matter if they are hidden behind opaque TextMap.

EDIT: bonus points for providing HashMap SHA256HashedText variant too, maybe 64 lower bits would be enough to get collision resistance. That would be interesting benchmark wise.

[lehins]

Just a suggestion, but maybe Blake2b_64/Blake2s_32 here is a good solution. Blake2b_256 is much faster than SHA-256, but maybe doing Blake2b_64 is even faster than just cropping 256bit hash to 64 bits.

I have suspicion that cooking up collisions for Blake2 (even with a small digest size) would be prohibitively expensive for the purpose of DoS attack

[konsumlamm]

Another solution could be using some map data structure specialized to Text keys (something like a trie, for example text-trie (although I have no idea how performant that implementation is) or a ternary search tree). This would of course be a breaking change, but so would using Data.Map (and it could be hidden behind a newtype, as suggested by @phadej).

This would have the advantage (apart from not being susceptible to hash DoS attacks obviously) that it doesn't (potentially) cause lots of string comparisons (this could be a problem with Data.Map if lots of the keys share the same prefix). Disclaimer: I didn't run any benchmarks, so I'm not sure if this would actually be faster in practice than using Data.Map (which has been extensively optimized after all), especially since text-2.0 will apparently use a more efficient compare implementation (see here).

[phadej]

@konsumlamm my solution is to make Object opaque.Then people are free to experiment with different representations, secure, fast, both, neither.

[phadej]

More concretely, something like: https://github.com/haskell/aeson/compare/textmap

The rest is just H.foo -> TM.foo all over the place. (And something to make FromJSONKeyCoerce work in happy situations)

I hope someone will complete that and make a PR.

[Boarders]

I'm going to try and push that through @phadej.

[joelmccracken]

@Boarders @phadej I was just considering that too. Please flag me if you could use any help.

[Boarders]

@phadej What did you have in mind with the Lift instance, is there an easy way to write it?

[TravisCardwell]

That would allow people e.g. process key-value pairs on order (if it matters for them), ...

I often work with YAML files where the order of object properties is important. Humans edit YAML files, and a logical order of object properties maximizes the usability. I do not know of a way to do this in Haskell using existing libraries, and this issue unfortunately sometimes results in having to use a different language.

This comment is in agreement with the current direction, but I am adding it as a concrete example of a real-world issue that Oleg's suggestion would resolve, in addition to the hash collision issue.

[phadej]

@Boarders, thanks for working on this!

@phadej What did you have in mind with the Lift instance, is there an easy way to write it?

look at the diff, probably something like

lift (TextMap m) = [| TextMap (H.fromList . map (first pack) $ m') |]
      where m' = map (first unpack) . H.toList $ m

It would be good to first introduce TextMap, and only then fiddle with its implementation.