3 ms·

I've done some security testing against this hash function. Does anyone want to follow up and see if they can extend the attacks I describe[1]? [1]https://gith

by Genbox 2y ago

I've done some security testing against this hash function. Does anyone want to follow up and see if they can extend the attacks I describe[1]? [1]https://github.com/ogxd/gxhash/issues/25 https://github.com/ogxd/gxhash/issues/25

Quarrel 2y ago
I may well be missing something, but isn't the point of the title: "GxHash is a fast and robust non-cryptographic hashing algorithm" Exactly that I should use it when I want a fast hash, but not when I want a robust cryptographic hash? In which case I can ignore your attack? (Not to discount your work, I'm just trying to understand the scope here) So I can use it in my hash-map, or whatever O(1) lookup, but I shouldn't use it in my rewrite of SSL?
- TacticalCoder 2y ago
  > So I can use it in my hash-map, or whatever O(1) lookup... BTW in the past (20 years ago?) there have been attacks on non-cryptographic hashes used for hash maps: denial of service by creating crafted requests to HTTP servers... The parameteres would be picked maliciously and would be all ending in the same "buckets". That attack worked on both Java and PHP servers. IIRC it's been solved by adding random seeding (and I noticed that GxHash mentions it's seedable: not saying it'd counter every attack but it's already something).
  - Quarrel 2y ago
    Very good point, and one I had heard of, but wasn't considering here.
  - chii 2y ago
    > there have been attacks on non-cryptographic hashes used for hash maps There have been places where a dev chose to use a non-cryptographic hash when they should not have, because they hadn't thought of the threat model (out of ignorance, or just didnt occur to them). But in most cases, nothing happens. They gained performance, or ease of development, etc. So it's a worthy trade off most of the time (whether they did it knowingly or not).
- Genbox 2y ago
  Even non-cryptographic hashes must provide some sort of security against attacks. Let's say we use a weak hash function in an open addressing hash-map - if I can calculate a set of inputs that will all collide in the hash-map, then it will turn the O(1) lookup into a O(n) lookup. If a small change to the seed mixing (literally moving a line from the end to the beginning of the function) increases the security with no penalty to performance, then we might as well make the change.
AlotOfReading 2y ago
I'm a bit confused why the author thinks the key recovery complexity would be on the order of full AES. It's a reduced 4-round AES, and even 5 round key recoveries are quite practical with modern hardware.

by Genbox 2y ago

Quarrel 2y ago

I may well be missing something, but isn't the point of the title: "GxHash is a fast and robust non-cryptographic hashing algorithm" Exactly that I should use it when I want a fast hash, but not when I want a robust cryptographic hash? In which case I can ignore your attack? (Not to discount your work, I'm just trying to understand the scope here) So I can use it in my hash-map, or whatever O(1) lookup, but I shouldn't use it in my rewrite of SSL?

TacticalCoder 2y ago
> So I can use it in my hash-map, or whatever O(1) lookup... BTW in the past (20 years ago?) there have been attacks on non-cryptographic hashes used for hash maps: denial of service by creating crafted requests to HTTP servers... The parameteres would be picked maliciously and would be all ending in the same "buckets". That attack worked on both Java and PHP servers. IIRC it's been solved by adding random seeding (and I noticed that GxHash mentions it's seedable: not saying it'd counter every attack but it's already something).
- Quarrel 2y ago
  Very good point, and one I had heard of, but wasn't considering here.
- chii 2y ago
  > there have been attacks on non-cryptographic hashes used for hash maps There have been places where a dev chose to use a non-cryptographic hash when they should not have, because they hadn't thought of the threat model (out of ignorance, or just didnt occur to them). But in most cases, nothing happens. They gained performance, or ease of development, etc. So it's a worthy trade off most of the time (whether they did it knowingly or not).
Genbox 2y ago
Even non-cryptographic hashes must provide some sort of security against attacks. Let's say we use a weak hash function in an open addressing hash-map - if I can calculate a set of inputs that will all collide in the hash-map, then it will turn the O(1) lookup into a O(n) lookup. If a small change to the seed mixing (literally moving a line from the end to the beginning of the function) increases the security with no penalty to performance, then we might as well make the change.

AlotOfReading 2y ago

I'm a bit confused why the author thinks the key recovery complexity would be on the order of full AES. It's a reduced 4-round AES, and even 5 round key recoveries are quite practical with modern hardware.