Re:NUID – An entropy friendly and highly performant unique i...
by tptacek on Wednesday February 24, 2016 @05:00PM
(#11170581)
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".
Re:NUID – An entropy friendly and highly performant unique i...
by derekcollison on Wednesday February 24, 2016 @06:12PM
(#11171011)
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.
Re:NUID – An entropy friendly and highly performant unique i...
by tptacek on Wednesday February 24, 2016 @06:32PM
(#11171118)
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.
Re:NUID – An entropy friendly and highly performant unique i...
by derekcollison on Wednesday February 24, 2016 @09:43PM
(#11172017)
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.
Re:NUID – An entropy friendly and highly performant unique i...
by heavenlyhash on Wednesday February 24, 2016 @09:06PM
(#11171887)
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.)
Re:NUID – An entropy friendly and highly performant unique i...
by fweespeech on Wednesday February 24, 2016 @05:03PM
(#11170596)
> 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.
Re:NUID – An entropy friendly and highly performant unique i...
by derekcollison on Wednesday February 24, 2016 @06:01PM
(#11170952)
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.
Re:NUID – An entropy friendly and highly performant unique i...
by fweespeech on Wednesday February 24, 2016 @05:27PM
(#11170746)
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. ;)
Re:NUID – An entropy friendly and highly performant unique i...
by wongarsu on Wednesday February 24, 2016 @07:24PM
(#11171442)
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.
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".
https://www.google.com/webhp?q=draining+entropy+pool
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.
Fortunately, salvation is readily at hand: http://www.2uo.de/myths-about-urandom/
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...
> 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.
You can use the most basic PRNG to generate your 128 bits. There's your UUID.
Call me when you find a collision.