NUID – An entropy friendly and highly performant unique identifier generator | Hacker News Reader

NUID – An entropy friendly and highly performant unique identifier generator

github.com

40 pointstylertreat18 comments

There is no such thing as "entropy draining".

If it's higher-performance than other UUID generators, fine, that's a win. But it's not doing anything useful for the system as a whole by sparing the "entropy pool".

I disagree, either the entropy is drained and the randomness of what the pool returns (based on OS) is compromised or you get stalled waiting for more of it and decrease performance of the generator.

https://www.google.com/webhp?q=draining+entropy+pool

In the immortal words of Timecube: "You have been educated stupid".

Fortunately, salvation is readily at hand: http://www.2uo.de/myths-about-urandom/

I think entropy, in however you measure it, does influence something like a UUID generator differently than the cryptographic algorithms. What you are trying to achieve, or more importantly the condition you are trying to avoid, is different.

A simple thought exercise to show you how false this is:

Instantiate AES-128-CTR with a random key. Encrypt 100 megabytes with it. Have you "drained" "key" from AES? No, not in any meaningful sense. If you could, the AES-CTR recommendations would say "don't encrypt more than 100 megabytes with AES-CTR". In practice, people routinely encrypt many gigabytes with it.

Every modern OS uses a DRBG for its kernel CSPRNG. You can think of a DRBG as a stream cipher, just like AES-128-CTR, where random events are hashed to form the key, and the output is the raw keystream. Asking for 100 megabytes of additional keystream doesn't "drain" the "key" from the keystream.

Linux has a terrible misfeature, born of a failure to understand the crypto primitives they're using in their CSPRNG. /dev/random keeps an "estimator" that tries to determine how much "entropy" has been fed to the CSPRNG, and it decrements that estimator when requests come in for random bytes. Linux claims you can drain its CSPRNG. Linux is wrong; that is not how crypto works.

Linux should lose that feature, but they will not. But there's no reason you should have to go along with it; just use urandom, which will not block for the estimator.

I wrote Yet Another UUID [1] for my own purposes recently as well. Mine's based on Firebase's style UIDs [2] -- they sort roughly chronologically, because operationally, I find that irritates me less. Arbitrary choice? Entirely. Regrets? None. Do I recommend it for use? Also not at all. Unless you feel like it. It's fine. I guess.

I've kind of given up on there being any purpose to a One True Spec for UUIDs. Count how many bits of entropy you want. Shove some CSPRNG into it. Call it a day.

¯\_(ツ)_/¯

(This a fine implementation, fwiw. I only mean to share my honest question as to whether there's any real utility to UUIDs-as-a-library.)

[1] https://github.com/polydawn/repeatr/blob/dd41ca72421a173b5aa... [2] https://www.firebase.com/blog/2015-02-11-firebase-unique-ide...

I agree, was simply sharing because it was a need we had, which might be a need someone else had as well. Anyone can feel free to use it or not.

> NUID needs to be very fast to generate and be truly unique, all while being entropy pool friendly. NUID uses 12 bytes of crypto generated data (entropy draining), and 10 bytes of pseudo-random sequential data that increments with a pseudo-random increment.

> Total length of a NUID string is 22 bytes of base 36 ascii text, so 36^22 or 17324272922341479351919144385642496 possibilities.

Isn't 22 bytes = 176 bits?

UUID = 128 bit

Storage performance is more than per-ns on a CPU core, imo.

UUIDs are 120 Bit or less. Depending on the Version you use. But you lose 8 bit on any version because 1 byte is used to decode the UUID version.

Yes. 128bit is the worst case for UUIDs, I was trying to avoid the claim I was being overly generous by using the smallest size I could get away with. ;)

Hm. The RFC says 4 bits + 2 bits (variant and variant version) are taken. That leaves 122 bits?

Yes, but most UUID when moved across networks are translated to hex, so 32 bytes/characters whereas NUID's are 22 bytes, so generally a savings of 10 bytes per when stored as a string.

Why on earth would you care about entropy for a UUID?

You can use the most basic PRNG to generate your 128 bits. There's your UUID.

Call me when you find a collision.

A basic PRNG might not be enough if you care about malicious collisions. There's plenty of cases of UUIDs being used in a context where a CSPRNG is preferable.

What's the use case here over a UUID?

Performance mainly, I think. Benchmarking against UUID v4 shows a ~175% speedup.

UUID V4 is ~900ns/op, NUID is ~60ns/op, so 15X speedup, or 1500%.

"Entropy draining" :(

Reply on news.ycombinator.com