Vulnerability to collision attacks

[sjakobi]

@NorfairKing's blog post describes a HashDoS attack on aeson which is enabled by u-c's O(n) handling of hash collisions and use of the same default salt for all hashing operations.

While possible mitigation measures for aeson are discussed in haskell/aeson#864, u-c should also prepare a proper response and possibly implement security features for users who are affected via aeson or in other ways.

In particular, I hope to find answers for the following questions in this thread (and possibly in separate sub-threads):

1. What mitigation measures can affected u-c users enable in the short term?
2. Is security against collision attacks a design goal for u-c?
   2a. If yes, to what extent should we trade performance and API bloat for security features?
3. What mitigation measures should be implemented in u-c?

I'd also like to point out that I have very limited knowledge and experience with security issues, so I'd be very grateful if more experienced people could chime in and share their advice. :)

[sjakobi]

1. What mitigation measures can affected u-c users enable in the short term?

A few ideas – maybe some more experienced people can comment whether these are any good:

• Switch to a collision-resistant hash function. I'm aware of SipHash, but there may be more suitable hash functions. This should make it harder for an attacker to produce colliding keys.
• Build hashable with -frandom-init-seed, to make it slightly harder to produce colliding keys. The hashable maintainer doesn't recommend this, but it should be somewhat useful anyway. See this discussion on r/haskell.
• Limit the size of any HashMaps and HashSets. When n is small, O(n) operations are less problematic.
• Use Data.Map and Data.Set from containers instead of this package. These use the Ord methods for performing lookups and insertions, and therefore aren't vulnerable to collision attacks.
• Experimental: Use the hashmap package which relies on Data.Map for storing any collisions. Note that this package doesn't offer a Strict API that ensures that map values are evaluated to WHNF. Maybe @RyanGlScott, @augustss or other users can comment in which cases this package is a suitable replacement for u-c.

EDIT 2020-10-03:

• Build hashable with -frandom-init-seed, to make it slightly harder to produce colliding keys. The hashable maintainer doesn't recommend this, but it should be somewhat useful anyway. See [this discussion on r/haskell]

Note that a random hash salt has very limited security benefits as long as a weak hash function like FNV is used. For FNV, it is possible to construct multi-collisions that collide no matter what salt they are hashed with: https://medium.com/@robertgrosse/generating-64-bit-hash-collisions-to-dos-python-5b21404a5306

[dhess]

Thanks for looking into this!

My only bit of feedback is this: because there are existing, deployed services that are vulnerable to this attack, and because shutting those services down or replacing them with something that doesn't use aeson is not feasible, a timely short-term fix is just as important as whatever long-term, proper fix the various parties come up with.

In other words, please let's not let perfect be the enemy of good-enough-for-now here. Even something that makes producing collisions slightly more difficult is helpful at this stage, IMO.

I'm encouraged that you've jumped right into mitigations in your first 2 posts, so it looks like this discussion is off to a great start!

[NorfairKing]

In other words, please let's not let perfect be the enemy of good-enough-for-now here.

• -frandom-init-seed is good enough for the very short term (AFAICT)

• The collisionless containers approach solves the specific exploit that I've built, but doesn't guarantee that there's no other cheap way to produce an exploit.

[treeowl]

Is there a way to mitigate the performance degradation of a random seed? How bad does it measure out?

[brandon-leapyear]

✨ This is an old work account. Please reference @brandonchinn178 for all future communication ✨

---

I also opened this issue for another possible mitigation: haskell-unordered-containers/hashable#218

Is there a way to mitigate the performance degradation of a random seed? How bad does it measure out?

IIUC it's not that a random seed will reduce performance, it's that one would get different hash values every time one restarts the application

[NorfairKing]

More ideas:

• IMHO we should also seriously consider the collisionless containers idea (in the long term)
• A createHashmap :: IO (HashMap k v) api where the hashmap stores its own (randomly generated) salt

[brandon-leapyear]

✨ This is an old work account. Please reference @brandonchinn178 for all future communication ✨

---

+1 to the createHashMap idea, in addition to createHashMapWith :: Int -> HashMap k v to get deterministic seeds (e.g. for getting deterministic results for tests)

[ysangkok]

Why should the function be in IO? We already have a class that captures needing random state, it is RandomGen. A PRNG would be good enough to solve this problem, real randomness is not needed.

[treeowl]

I also opened this issue for another possible mitigation: haskell-unordered-containers/hashable#218

Is there a way to mitigate the performance degradation of a random seed? How bad does it measure out?

IIUC it's not that a random seed will reduce performance, it's that one would get different hash values every time one restarts the application

A random seed will most likely be implemented something like this:

the_random_seed :: Seed
the_random_seed = unsafePerformIO ...
{-# NOINLINE the_random_seed #-}

This means that every (initial) seed access has to check a tag and follow a pointer. The seed will almost always be in L1 cache when heavy HashMap use is happening, but we should check that it's not too bad to access it.

[sjakobi]

Here's some earlier discussion with @tibbe and @infinity0 on mitigating collision attacks: #265 (comment)

The gist is that in order to make it sufficiently hard for an attacker to produce hash collisions, you need both a strong hash function like SipHash and a random seed.

The problem with SipHash is that apparently it's so slow that you might as well switch to Data.Map – at least that's what was mentioned in our internal discussions. Nevertheless, a hashable patch that uses SipHash for the Text instance seems like a reasonable short-term mitigation measure when combined with -frandom-init-seed.

---

Regarding the proposed fix in #217, @tibbe's assessment was that it would still require a strong hash function and a random seed to be reasonably secure. With many weaker hash functions, it is possible to generate seed-independent collisions, see e.g. this blog post. By this assessment, #217 "adds" little security of its own.

[sjakobi]

• A createHashmap :: IO (HashMap k v) api where the hashmap stores its own (randomly generated) salt

Storing the salt within the HashMap was proposed in #45. Maybe we can use that issue to discuss the details of this idea.