Re: How can I build OSSP UUID support on Windows to avoid duplicate UUIDs?

On Thu, Oct 31, 2013 at 2:44 PM, Garick Hamlin <ghamlin(at)isc(dot)upenn(dot)edu> wrote:
> On Thu, Oct 31, 2013 at 01:59:04PM -0400, Robert Haas wrote:
>> On Thu, Oct 31, 2013 at 1:02 PM, Garick Hamlin <ghamlin(at)isc(dot)upenn(dot)edu> wrote:
>> > On Thu, Oct 31, 2013 at 09:54:14PM +0900, MauMau wrote:
>> >> From: "Robert Haas" <robertmhaas(at)gmail(dot)com>
>> >>> ISTM that the biggest problem is that we don't have a random number
>> >>> generator which generates enough bits of randomness to implement
>> >>> uuid_generate_v3. I think relatively few people would cry if we
>> >>> didn't support uuid_generate_v1(), and the others all look simple
>> >>> enough, provided there's somewhere to get lots of random bits.
>> >>>
>> >>> On Linux, it seems like we could get those bits from /dev/urandom,
>> >>> though I'm not sure how efficient that would be for the case where
>> >>> many UUIDs are being generated at once. But that wouldn't be very
>> >>> portable. It's tempting to think that we'd need a PRNG that generates
>> >>> wider values, for which we might find other application also. But I'm
>> >>> not volunteering to be the one to create such a thing.
>> >>
>> >> OpenSSL provides rand_bytes() which generates random bytes of any length.
>> >> It uses /dev/urandom or /dev/random on UNIX/Linux and Crypto API of
>> >> Microsoft on Windows.
>> >
>> > What about using a cipher here as the PRNG? It seems like using openssl
>> > rand_bytes() to seed aes in ctr would work ok without starving the system of
>> > entropy when making a lot of uuids.
>>
>> There are two good reasons for us NOT to rely on OpenSSL:
>
> Right, that makes sense. openssl is a non-starter here. In which case that
> approach is no easier than any other prng.
>
> I think using /dev/urandom directly would be surprising. At least it would
> have probably have taken me a while to figure out what was depleting the
> entropy pool here.

There's something arguably duplicative about this, but I'd be kind of
inclined to
implement an entropy pool, and enable introducing entropy using whatever
means are wished.

That way, we can "scale" reasonably well for all the cases.

By default, we seed using a timestamp (or similar) and use some stream cipher
that is of suitable portability to "stir the pot." That's obviously
not perfect, but it
will *work*, and offer reasonable results on systems that don't offer better
facilities.

Having a pool lends itself to "stirring" extra ingredients in with
reasonable ease.

- If you have a better PRNG, you can stir that in. Perhaps it replaces the
default; I'm not sure it's important.

- If you have /dev/random or /dev/urandom, you can stir some of that into
the mix.

- Someone that is feeling paranoid about their PRNG could stir in
data from an entropy key (like <http://www.entropykey.co.uk/>)

The latter options aren't much use to someone without suitable hardware or
OS support, but they're not imperative.

Doing funky things to the pool seems like an example of something useful to
do using the background worker facility of 9.3+. And if you have an application
where you're using really a lot of UUIDs, the burden of configuring that may be
reasonable to pay.
--
When confronted by a difficult problem, solve it by reducing it to the
question, "How would the Lone Ranger handle this?"