2 ms·

Hash Denial-of-Service Attack in Multiple QUIC Implementations

4 points by weinzierl 2y ago

rurban 2y ago
No! > Out of these functions, only SipHash provides significant security guarantees in this context; crafting collisions for the first two can be done fairly efficiently. You can craft collisions against SipHash also trivially. "significant" is not significant, and using SipHash would also make it much slower, comparable to a linked list search. The only fix for DOS attacks against hashtables is to fix the collision resolution method. Eg from linear to logarithmic. Or detecting such attacks (ie collision counting). Using a slower, better hash function is fud, because every hash function will produce collisions in hash tables. Even SHA-256 https://github.com/rurban/smhasher/?tab=readme-ov-file#security https://github.com/rurban/smhasher/?tab=readme-ov-file#secur...
- westurner 2y ago
  I know I've looked it up before, but for whatever reason I can't explain how open address hashmaps work; how does it know to check the next bucket on read after a collision on insert? I know it's a dumb question, and that I've researched it before. Strange. (I recall Python first reporting the open address hashing hash randomization disclosure vuln that resulted in the PYTHONHASHSEED env var, and then dict becoming an odict OrderedHashMap by default.) /? The only fix for DOS attacks against hashtables is to fix the collision resolution method. https://www.google.com/search?q=The+only+fix+for+DOS+attacks+against+hashtables+is+to+fix+the+collision+resolution+method https://www.google.com/search?q=The+only+fix+for+DOS+attacks... "Defending Hash Tables from Subterfuge with Depth Charge" (2024) https://dl.acm.org/doi/fullHtml/10.1145/3631461.3631550 https://dl.acm.org/doi/fullHtml/10.1145/3631461.3631550 "Defending hash tables from algorithmic complexity attacks with resource burning" (2024) https://www.sciencedirect.com/science/article/abs/pii/S0304397524003797 https://www.sciencedirect.com/science/article/abs/pii/S03043... Hash collision: https://en.wikipedia.org/wiki/Hash_collision https://en.wikipedia.org/wiki/Hash_collision

4 points by weinzierl 2y ago

No! > Out of these functions, only SipHash provides significant security guarantees in this context; crafting collisions for the first two can be done fairly efficiently. You can craft collisions against SipHash also trivially. "significant" is not significant, and using SipHash would also make it much slower, comparable to a linked list search. The only fix for DOS attacks against hashtables is to fix the collision resolution method. Eg from linear to logarithmic. Or detecting such attacks (ie collision counting). Using a slower, better hash function is fud, because every hash function will produce collisions in hash tables. Even SHA-256 https://github.com/rurban/smhasher/?tab=readme-ov-file#security https://github.com/rurban/smhasher/?tab=readme-ov-file#secur...

westurner 2y ago
I know I've looked it up before, but for whatever reason I can't explain how open address hashmaps work; how does it know to check the next bucket on read after a collision on insert? I know it's a dumb question, and that I've researched it before. Strange. (I recall Python first reporting the open address hashing hash randomization disclosure vuln that resulted in the PYTHONHASHSEED env var, and then dict becoming an odict OrderedHashMap by default.) /? The only fix for DOS attacks against hashtables is to fix the collision resolution method. https://www.google.com/search?q=The+only+fix+for+DOS+attacks+against+hashtables+is+to+fix+the+collision+resolution+method https://www.google.com/search?q=The+only+fix+for+DOS+attacks... "Defending Hash Tables from Subterfuge with Depth Charge" (2024) https://dl.acm.org/doi/fullHtml/10.1145/3631461.3631550 https://dl.acm.org/doi/fullHtml/10.1145/3631461.3631550 "Defending hash tables from algorithmic complexity attacks with resource burning" (2024) https://www.sciencedirect.com/science/article/abs/pii/S0304397524003797 https://www.sciencedirect.com/science/article/abs/pii/S03043... Hash collision: https://en.wikipedia.org/wiki/Hash_collision https://en.wikipedia.org/wiki/Hash_collision