Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New fastest portable hash: wyhash

github.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: New fastest portable hash: wyhash

#41

Post by stcredzero »

haberman wrote: post #38

I would love for this to be solid, but something here seems too good to be true. Modern hashing is well-studied, with lots of smart people attacking the problem. Modern hashes like Google's FarmHash are thousands of lines of code with platform-specific intrinsics for acceleration. This hash claims to beat other modern hashes in speed, without using platform-specific intrinsics, and without quality problems, and in a…

I would love for this to be solid, but something here seems too good to be true.

How so? It's much slower than AES based hashes. It's about the throughput same as xxHash64. It uses fewer cycles/hash than xxHash64.

Re: New fastest portable hash: wyhash

#42

Post by orasis »

bradleyjg wrote: post #34
orasis wrote: post #23

I’d really like to see progress on hashes that fit into a few lines of code. It seems FNV-1a is still the best option in that regard.

If this is all there is to it: https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h That doesn’t seem like much.

It’s bigger than I’d want to include in JavaScript for a web page.

Re: New fastest portable hash: wyhash

#43

Post by haberman »

stcredzero wrote: post #41
haberman wrote: post #38

I would love for this to be solid, but something here seems too good to be true. Modern hashing is well-studied, with lots of smart people attacking the problem. Modern hashes like Google's FarmHash are thousands of lines of code with platform-specific intrinsics for acceleration. This hash claims to beat other modern hashes in speed, without using platform-specific intrinsics, and without quality problems, and in a…

I would love for this to be solid, but something here seems too good to be true. How so? It's much slower than AES based hashes. It's about the throughput same as xxHash64. It uses fewer cycles/hash than xxHash64.

> It's much slower than AES based hashes.

I must have misinterpreted the following:

> So the fastest hash functions on x86_64 without quality problems are: > > - wyhash > - t1ha > - [...]

I interpreted that to be an ordered list, saying that wyhash was the fastest.

But looking at the actual table I am confused. There are MB/s numbers and cycles/hash numbers. In cycles/hash wyhash appears to beat all FarmHash variants, but in MiB/s it is slower than some of them. I don't understand why these two performance measures would not track perfectly, since the CPUs should be running a constant number of cycles/second.

Re: New fastest portable hash: wyhash

#44

Post by stcredzero »

haberman wrote: post #43
stcredzero wrote: post #41

Earlier quoted context omitted.

I would love for this to be solid, but something here seems too good to be true. How so? It's much slower than AES based hashes. It's about the throughput same as xxHash64. It uses fewer cycles/hash than xxHash64.

> It's much slower than AES based hashes. I must have misinterpreted the following: > So the fastest hash functions on x86_64 without quality problems are: > > - wyhash > - t1ha > - [...] I interpreted that to be an ordered list, saying that wyhash was the fastest. But looking at the actual table I am confused. There are MB/s numbers and cycles/hash numbers. In cycles/hash wyhash appears to beat all FarmHash variants…

I don't understand why these two performance measures would not track perfectly, since the CPUs should be running a constant number of cycles/second.

x86 isn't RISC and not all operations take the same number of cycles. Also, the code might have different levels of possible parallelism and might impact the pipeline differently.

Comp Sci education for the low level basics is often completely neglected nowadays. This should be freshman year stuff. I'm certainly not an expert, myself, just familiar with the issues. (Know enough to know what you don't know.)

Re: New fastest portable hash: wyhash

#45

Post by haberman »

stcredzero wrote: post #44
haberman wrote: post #43

Earlier quoted context omitted.

> It's much slower than AES based hashes. I must have misinterpreted the following: > So the fastest hash functions on x86_64 without quality problems are: > > - wyhash > - t1ha > - [...] I interpreted that to be an ordered list, saying that wyhash was the fastest. But looking at the actual table I am confused. There are MB/s numbers and cycles/hash numbers. In cycles/hash wyhash appears to beat all FarmHash variants…

I don't understand why these two performance measures would not track perfectly, since the CPUs should be running a constant number of cycles/second. x86 isn't RISC and not all operations take the same number of cycles. Also, the code might have different levels of possible parallelism and might impact the pipeline differently. Comp Sci education for the low level basics is often completely neglected nowadays. This s…

> x86 isn't RISC and not all operations take the same number of cycles.

Yes but it doesn't say instructions per hash, it says cycles per hash. Unless some kind of frequency scaling is going on, the number of cycles per second should be very consistent. If bytes/hash is held constant and cycles/second is constant, then MiB/second and cycles/hash should be exact inverses. I don't understand why this is not the case in these tables.

> Also, the code might have different levels of possible parallelism and might impact the pipeline differently.

Again this can affect the number of instructions being retired, but not the number of cycles. A cycle is a cycle, regardless of how much work is actually being accomplished.

> Comp Sci education for the low level basics is often completely neglected nowadays. This should be freshman year stuff.

I'm a low-level junkie who lives in godbolt.org and Agner Fog's tables, writes JIT compilers, and does FPGA design for fun on the side. It's possible that I'm mistaken here, but I do have a fair amount of background in this.

Re: New fastest portable hash: wyhash

#46

Post by rurban »

WallWextra wrote: post #5
panic wrote: post #4

Here's a link to wyhash itself: https://github.com/wangyi-fudan/wyhash

Maybe the link could be updated to point to this instead?

No, because you need to see it in context. Wang Yi only compared to t1ha, only in one criteria.

This is the code: https://github.com/rurban/smhasher/blob/master/wyhash.h

Re: New fastest portable hash: wyhash

#47

Post by GoblinSlayer »

CodesInChaos wrote: post #39
jchw wrote: post #14

Earlier quoted context omitted.

I didn't know much about this argument so I looked it up and funny enough it's you arguing here too: https://github.com/google/highwayhash/issues/28 Still trying to wrap my head around exactly what is being argued... but it's starting to feel like there's something personal going on here, not gonna lie. It's a bit quaint. (Also a bit curious why Rust is looped into this. It seems like Rust was insecure because the sa…

I think the claim isn't "SipHash is not a secure keyed hash function (PRF)" but rather "secure keyed hash functions are insufficient mitigation for hash DoS". For long lived hash-tables even per-table keys don't prevent finding bucket-collisions via side-channels. So you either have to either rekey when a large number of bucket-collisions are detected. Or you fall back to a balanced tree based data structure for thos…

He means the worst case scenario when the attacker knows the key. In which case it's trivial indeed.

Re: New fastest portable hash: wyhash

#48

Post by switch33 »

https://github.com/switch33/sha2592 something I just coded wondering how it measures up.

and i made another one too: https://github.com/switch33/sha29893

and a third one: https://github.com/switch33/sha5987

and an even better one: https://github.com/switch33/sha2999999

and maybe the best for quite some time: https://github.com/switch33/sha130000000-

Re: New fastest portable hash: wyhash

#49

Post by rurban »

GoblinSlayer wrote: post #47
CodesInChaos wrote: post #39

Earlier quoted context omitted.

I think the claim isn't "SipHash is not a secure keyed hash function (PRF)" but rather "secure keyed hash functions are insufficient mitigation for hash DoS". For long lived hash-tables even per-table keys don't prevent finding bucket-collisions via side-channels. So you either have to either rekey when a large number of bucket-collisions are detected. Or you fall back to a balanced tree based data structure for thos…

He means the worst case scenario when the attacker knows the key. In which case it's trivial indeed.

As I explained there, getting the hash seed of a running process in a dynamic language is trivial. Every language has enough ropes to hang yourself and print the value from some known offset. And if not, there's still enough information from a typical bad hash table (95% of hash tables are bad) to get at the seed via ordering and timing. From there you just brute force an attack even with an extremely slow hash like siphash. A seed is no secure protection against an determined attacker, only for newbies. A newbie would just DOS the system with simplier means.

The point is, don't believe the theatre, use proper protection against the attack (no linear list on collisions), and keep the hash table fast. Collision counting or fallback to tree really is trivial.

Re: New fastest portable hash: wyhash

#50

Post by rurban »

gliptic wrote: post #15
rurban wrote: post #8

Earlier quoted context omitted.

> misinformed rant Only siphash fans would say that, and they are very misinformed about the false recommendations from their paper. Prove me wrong.

Have you published your SipHash seed finder yet?

A seed finder is independent on the hash function. It is dependent on the framework you are using. If you are using perl, ruby, python or php e.g. I won't publish the perl solution as nobody is protected and I had my own services on Redhat Openshift, which is unsafe forever. I only published the proof of the various attacks on most hash functions in my testsuite, to verify the proper protection against it.
Post reply on HN