paralleldrive / cuid2

Next generation guids. Secure, collision-resistant ids optimized for horizontal scaling and performance.
MIT License
2.68k stars 54 forks source link

Issues with comparisons #68

Open rkistner opened 1 year ago

rkistner commented 1 year ago

Cuid2 appears to be a good format and library overall, but the readme has some issues around its comparisons with other formats.

The comparisons to other id formats seem to conflate some things when making comparisons:

Taking UUIDv4 as an example - going by the spec, UUIDv4 should roughly match in every aspect other than "Not URL or name friendly".

If we break it down:

You could use the Cuid2 CSPRNG in an UUIDv4 implementation, and get exactly the same security (ignoring the 124 vs 122 bits). So what you're really comparing is the security of the CSPRNG, rather than the format itself.

There is something to be said for specifying the CSPRNG used in the format, versus UUIDv4 that leaves it up to the implementation. JWTs had similar issues where the spec wasn't specific enough about some details, leading to major security issues in many implementations.

When comparing the PRNGs

As long as the PRNG satisfies the required properties for a CSPRNG, there is little meaningful difference between different implementations.

Id generation should be fast enough that humans won't notice a delay, but too slow to feasibly brute force (even in parallel)

The faster you can generate ids, the faster you can run collision attacks

If you start at the output of the PRNG, you can generate IDs equally fast - the speed of the PRNG doesn't matter. You have 122+ bits of entropy either way, and there's no way you're going to find a collision.

Using the PRNG itself to generate collisions only makes sense if the PRNG isn't secure to begin with.

A slow PRNG isn't a requirement for security.

Cuid2 uses multiple, independent entropy sources and hashes them with a security-audited, NIST-standard cryptographically secure hashing algorithm (Sha3).

That the hashing algorithm is NIST-standard doesn't prove on its own that the Cuid2 PRNG is secure - it's just one component of the PRNG. NIST does actually go further and provides recommendations for creating a CSPRNG using hash functions or other crypto primitives - why are one of those recommendations not used?

Using a completely custom PRNG here instead of using a known secure has the possibility of introducing new security issues.

For example, the Wikipedia page on CSPRNGs mentions this requirement:

Every CSPRNG should withstand "state compromise extension attacks". In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation.

Does the Cuid2 implementation meet that requirement? Has that been audited?

there may be bugs in browser CSPRNGs

The linked Chromium issue was from 2015/2016. Are there any currently known issues / weaknesses? Otherwise there is no more reason to believe there is a bug in the browser CSPRNGs than there being a bug in Cuid2.