incubator-couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Paul Davis" <paul.joseph.da...@gmail.com>
Subject Re: couch_util:new_uuid problem?
Date Sat, 04 Oct 2008 00:46:37 GMT
The following quote from wikipedia assumes a reliable source of
randomness. I'm gonna guess the OpenSSL team is pretty good at what
they do. And even if not, it becomes painfully obvious when things are
wrong. (For instance the SSH key brouhaha)

Quoting wikipedia:

[In] perspective, one's annual risk of being hit by a meteorite is
estimated to be one chance in 17 billion [15], that means the
probability is about 0.00000000006 (6 x 10-11), equivalent to the odds
of creating a few tens of trillions of UUIDs in a year and having one
duplicate.

Found at: http://en.wikipedia.org/wiki/Universally_Unique_Identifier#Random_UUID_probability_of_duplicates

These numbers are huge. If you have collisions, its because
something's broken. If something like this breaks, the internet breaks
and it gets fixed pronto.

The only alternative that I could say would be better would be to read
/dev/urandom directly but that would break on machines that don't have
a native source of randomness.

HTH,
Paul

On Fri, Oct 3, 2008 at 8:30 PM, Ayende Rahien <ayende@ayende.com> wrote:
> The problem is with the guarantees that the method does.
> This is a valid implementation for random number generator:
> http://xkcd.com/221/
>
> A UUID isn't going to be duplicated, because it is unique to the machine and
> time it was generated, and there is care taken to ensure that even if you
> have two thread creating the a guid on the same micro second, you'll get two
> different guids.
> There is no such guarantees for random numbers.
>
> On Sat, Oct 4, 2008 at 3:06 AM, Paul Davis <paul.joseph.davis@gmail.com>wrote:
>
>> Ayende,
>>
>> Perhaps I'm missing something, but I don't see the problem.
>>
>> I suppose you could technically claim that we're not setting the
>> version bits properly but that seems rather not important given that
>> we have the revision protection. Also unless I'm mistaken this would
>> only be a problem if someone is using an external UUID generation
>> scheme that happens to be extremely not random. Which while possible,
>> would still send up red flags on constant collisions on document
>> creation.
>>
>> Paul
>>
>> On Fri, Oct 3, 2008 at 7:49 PM, Ayende Rahien <ayende@ayende.com> wrote:
>> > Looking at the method implementation, it looks like there might be a
>> problem
>> > here.
>> >
>> > new_uuid() ->
>> >    list_to_binary(to_hex(crypto:rand_bytes(16))).
>> >
>> > In particular, we aren't actually guaranteed to have a unique value.
>> > You can read more about what needs to be done to get unique guids: here:
>> > http://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx
>> >
>>
>

Mime
View raw message