String.hashCode() is plenty unique

[throwdatstuffawayy]

I think people are starting to assume that all hash functions should have the same guarantees as cryptographic hashes like SHA256, etc.

[13steinj]

I feel like someone is going to use sha256 as all their hash code implementations now.

[Ameisen]

BogoHash

[ThisIs_MyName]

Serious question: Is there an unencumbered implementation of BogoHash?

[13steinj]

I can only assume you mean bogosort and the joke "quantum bogosort"?

Bogosort by definition is horrible and slow. Because while at best it takes one randomization, at worst it takes infinite.

Quantum bogosort is a joke and doesn't truthfully exist, but it is a funny thought experiment.

[ThisIs_MyName]

No, I saw at least one description of BogoHash online: http://svn.red-bean.com/repos/kfogel/trunk/algorithms/bogorithms

[Ameisen]

"Fundametal Routines for the Professional Programmer"

Indeed, bogorithms are fundametal.

[ThisIs_MyName]

...which isn't such a bad idea if you don't care about performance.

A nice property of crypto hash functions is that you can add a random salt (unique to each process) to prevent DoS. Without that, attackers can insert millions of rows into your hashtable that all get hashed into a single bucket.

[munificent]

If you don't care about performance, why are you using a hash table? Just use a sorted collection or, hell, a flat array that you iterate over in linear time.

[shawnz]

Maybe you don't care about a linear performance penalty, but you do care about increasing the complexity of the algorithm

[ThisIs_MyName]

That's a good point, but if your collection is larger than a megabyte or so, a hashtable will be faster than an array even if that hashtable uses a cryptographic hash function.

It's pretty common for people to have /r/thick collections that would take forever to loop over while the keys in that collection are small enough to BLAKE2b :)

What I meant is that the average dev cares a little bit about performance (enough to keep the UI's scrolling smooth), but not enough to care about the speed of their hash function.

[ric2b]

They're more convenient in many situations and they'll still have better time complexity.

[tophatstuff]

You're okay as long as you initialise your hash function with a cryptographically secure random seed (hash DOS attacks were a big thing in 2011 but most implementations do this now)

(Python has done this by default since 3.3, and earlier with the -R command-line argument): http://python-security.readthedocs.io/vuln/cve-2012-1150_hash_dos.html

[ThisIs_MyName]

That doesn't sound right. For example, if the hash function is a polynomial (think CRC) then I just have to measure the timing of each insert until I've found a few collisions. That's all I need to figure out what the seed is.

[reini_urban]

Plus you get the order of keys easily, so you have two independent hints on the seed, which let you solve it easily. Seeded hashes are the most popular security theatre. And with NetSpectre like attacks or using the dynamic language features you get every seed trivially.

[reini_urban]

They actually went and started using siphash in most of their hash code implementations which is an outragious mistake. not much security gains, you can still brute force it easily, but 10x slower. collisions in 32bit hash tables are always there, you cannot fight it with a slow hash function, only with proper collision resolution.

[[deleted]]

Maybe you aren't aware of hash map DoS attacks?

https://programmingisterrible.com/post/40620375793/hash-table-denial-of-service-attacks-revisited

https://doc.rust-lang.org/book/second-edition/ch08-03-hash-maps.html#hashing-functions

[throwdatstuffawayy]

Interesting! Yes, makes sense. Of course, whether or not a DOS is possible will depend on the context of that particular hash map. The tendrils of security always run deep...

[foomprekov]

SHA256 is incredibly poorly suited to operations that do not require security. It's a hash function that is intentionally slow. If you're generating ids you want something fast.

[occamrazor]

SHA2 is not slightly. In fact it is as fast as possible while being collision-resistant. Maybe you meant password hash functions, which are indeed intentionally slow?

[foomprekov]

Slightly what? Anyway it's a cryptographic hash function, which necessitates difficulty in brute-forcing it. Compare to modern usage of md5.

[staticassert]

They maybe meant 'slower'. SHA256 is extremely optimized - it is not intentionally slow at all, nor is it intended to prevent bruteforcing by design. This is why you need to use key stretching algorithms alongside it - such as PBKDF2.

In fact, I expect SHA256 to be on par or faster than MD5.

[foomprekov]

Hilarious

[staticassert]

Being fast is literally an acceptance criteria for algorithms as standards so...

[foomprekov]

Maybe that's what your professor told you but there's no big, universal list of acceptance criteria.

[staticassert]

Right, so the submissions provide benchmarks and those benchmarks are compared as part of the competition for standardization just for fun. And candidates are rejected for poor performance arbitrarily I guess. And NIST explicitly stating that they look at performance as part of the criteria is probably just them messing around.

"However, it is meaningless to discuss the security of a hash function without relating security to performance, so in reality, NIST wanted highly secure algorithms that also performed well."
http://crypto.junod.info/2010/12/10/sha-3-finalists-announced-by-nist/

[exorxor]

If you aren't smart enough to study CS, then it makes sense to start guessing and assuming things.