News for hackers. Stuff that matters.
Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by lucb1e on Friday December 04, 2020 @10:00AM (#25302920)
> UUIDs are 128 bits; that’s large enough that you can reasonably assume in most fields that no collisions will occur.

I'd go a step further than that honestly. Even at 80 bits I'd say you can really be sure that it will never happen. Mind that 2^64 is quite large, and with every single +1 of that power you halve the chance. Anything above 80 bits is quite safe even when someone purposefully tries to find your input, let alone by random chance. The 128 bits includes a decent security margin.

Plain MD5 is pretty much the fastest thing you can find. A decent GPU can do 25GH/s on that. If you can have a $1 000 000 hardware budget, it takes you 150 years to have a 50/50 chance of cracking a 2^80 secret with Hashcat. (Ballpark numbers: can be off by an order of magnitude, but not <10 years for that budget if you use today's hardware and today's hashcat.)

We haven't even cracked the 3DES key used for Adobe's user database backup, which I'm sure a lot of people would be interested in. Not $1M interested maybe, but still.

2^128 is really gigantic and no collision will ever occur there unless you have a quantum computer. It's more than a "reasonable assumption in most fields".

Of course, I agree that 2^64 is too small to just generate a token and assume it's unique without checking if it exists. I'm just trying to prevent someone from assuming that we need 512-bit hashing or something and creating crypto soup (as a security dude, this happens all too often).

Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by chrismorgan on Saturday December 05, 2020 @04:20AM (#25313045)
We’re still talking about two rather different things: you’re talking about the ability to find a particular collision; I’m talking about the probability of any collision occurring, which is the birthday problem. An 80-bit hash has collision resistance of only 2⁴⁰, a mere trillion. This is ample for many applications, but nowhere near enough for many other applications if you consider collisions a bad thing.

2¹²⁸ is indeed overkill for most situations, but it’s about trying to make sure choosing IDs randomly is safe. (I was probably playing it a little too safe in saying “most fields”.)

Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by nextaccountic on Friday December 04, 2020 @04:18PM (#25308148)
> Plain MD5 is pretty much the fastest thing you can find.

Faster than BLAKE3?

Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by oconnor663 on Friday December 04, 2020 @04:56PM (#25308681)
As always, it depends on the platform and the size of the input :) There's some good data here: https://bench.cr.yp.to/results-hash.html
Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by lucb1e on Friday December 04, 2020 @05:40PM (#25309258)
Again, ballpark numbers, but yes you might be right. From the sibling comment's benchmarks, it seems though that MD5 is indeed even faster than BLAKE3 (5.4 cycles/byte for blake3 vs 4.95 for md5).
Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by jcynix on Friday December 04, 2020 @05:58PM (#25309459)
I've been comparing other hashes to MD5 during the last few months to compare and identify large photos and movie files. My experience is that xxhash is much faster than good old MD5.

You can find some numbers at it's site here: https://github.com/Cyan4973/xxHash

Re:Pg-shortkey: YouTube-Like Short IDs as Postgres Primary Keys by lucb1e on Saturday December 05, 2020 @11:44AM (#25315850)
Those are different kinds of algorithms. Something like CRC32, siphash, etc. are much faster than a hashing function meant to be cryptographically secure. They just don't have the same constraints. This xxHash claims it "successfully completes the SMHasher test suite" which is good in the same way that a PRNG passing randomness tests is good but not necessarily cryptographically secure.

The table on the page you linked also says in the notes whether an algorithm was meant for cryptographic purposes, and indeed all of those are at the bottom by quite a margin.