net - Custom, probably inspired by SipHash but seems much weaker Some big projects upgrading their hashtables: These attacks hit dynamically typed languages very hard, since they typically use hashtables almost everywhere (member names to values etc.) Many programming languages are currently upgrading their standard libraries to avoid Hash DoS. Slides of the presentation "Hash-flooding DoS reloaded: attacks and defenses" at Application Security Forum Western Switzerland 2012 (Aumasson, Boßlet) See this oCERT advisory, and the following resources: Some of the technologies affected have switched to SipHash. Jointly with Martin Boßlet, we demonstrated weaknesses in MurmurHash (used in Ruby, Java, etc.), CityHash (used in Google), and in Python's hash. My recommendation is using SipHash and to avoid key reuse across requests where possible.īreaking Murmur: Hash-flooding DoS Reloaded (On Martin Boßlet's blog) Currently SipHash is gaining popularity, since it's fast, but still cryptographically secure. Earlier keyed hashes often suffered from key independent collisions, and thus didn't prevent the attack once these were found. If the keyed hash is good, this prevents the attacker from producing collisions quickly. Then it uses a keyed hash to determine the bucket, instead of an unkeyed hashfunction. Longer lifetimes can allow adaptive attacks over multiple requests, but I'm not sure how big a problem that is in practice. Depending on the situation this key can be per-process, per-table, per-request. There are two common strategies to avoid Hash DoS: You can switch to trees, or you can use keyed hashes.įor keyed hashes the server chooses a random secret key. If the hashes are well distributed, the relevant operations are O(1) and really fast, but if they're badly distributed they become O(n). These are naturally immune to this attack, but they're slower. The relevant operations have logarithmic performance, regardless of the data. There are several ways to implement lookup tables: This attack is known as Hash DoS, or more generally as Algorithmic Complexity Attack.
0 kommentar(er)
