Bug 28990

If we're generating things that appear to be UUIDs, we should make a reasonable effort to make them universally unique, so I don't think the GLib PRNG is a suitable fallback mechanism.

Windows has API to create UUIDs (<http://msdn.microsoft.com/en-us/library/Aa379205>, example usage <http://wiki.tcl.tk/10554>), and I find it hard to believe that there isn't a similarly good solution on Mac OS X, *BSD, etc. I'd accept patches to make Gabble able to use a more portable UUID library on non-Linux Unixes.

I've wondered whether to put this functionality in telepathy-glib (perhaps it should even be in GLib), if we're going to start requiring CMs with Message to stamp unique identifiers on individual IMs.

(In reply to comment #1)
> I've wondered whether to put this functionality in telepathy-glib (perhaps it
> should even be in GLib), if we're going to start requiring CMs with Message to
> stamp unique identifiers on individual IMs.

Irrespective of any message identifier issues, it would make sense to put this in GLib.

OSSP UUID might be a good alternative: http://www.ossp.org/pkg/lib/uuid/

(On Linux we should continue to prefer e2fsprogs' libuuid, though, since basically all Linux systems will have it for e2fsprogs already.)

(In reply to comment #1)
> If we're generating things that appear to be UUIDs, we should make a reasonable
> effort to make them universally unique, so I don't think the GLib PRNG is a
> suitable fallback mechanism.

Well if you look attentively, we use the random version from libuuid, not the time based one, this is the reason I proposed a default fallback that uses random and does not guaranty uniqueness. Maybe that is a mistake and we should use the timed based version in libuuid and implement the same fallback based on time ?

> 
> Windows has API to create UUIDs
> (<http://msdn.microsoft.com/en-us/library/Aa379205>, example usage
> <http://wiki.tcl.tk/10554>), and I find it hard to believe that there isn't a
> similarly good solution on Mac OS X, *BSD, etc. I'd accept patches to make
> Gabble able to use a more portable UUID library on non-Linux Unixes.

Well even OSX have it's own UUID library, but they all use a different format. From what I understand, Google server expect the libuuid format which make this feature quite Gabble/XMPP specific. Also, even implemented base on time, it will still take 3-4 lines of code.  I wonder if it's actually worth having external dependency?

(In reply to comment #4)
> Well if you look attentively, we use the random version from libuuid, not the
> time based one

A random UUID is not guaranteed to be unique, but it's much less likely to collide than one generated from a general-purpose PRNG with a relatively small amount of state. libuuid uses /dev/urandom or /dev/random, or the Windows equivalent, as does ossp-uuid.

Similarly, RFC 4122 recommends using MD5 or SHA-1 as the PRNG; UUID libraries do, but GLib doesn't.

> > Windows has API to create UUIDs
> > (<http://msdn.microsoft.com/en-us/library/Aa379205>, example usage
> > <http://wiki.tcl.tk/10554>), and I find it hard to believe that there isn't a
> > similarly good solution on Mac OS X, *BSD, etc. I'd accept patches to make
> > Gabble able to use a more portable UUID library on non-Linux Unixes.
> 
> Well even OSX have it's own UUID library, but they all use a different format.

Really? As I understand it, the de facto standard is the one used in RFC 4122 for the urn:uuid: URN namespace, i.e. aaaaaaaa-bbbb-cccc-dddd-eeeeeeeeeeee (where all the digits are lower-case hex); I'd expect any UUID library to be able to produce this format, albeit possibly via a call to g_ascii_tolower(). libuuid's uuid_unparse_lower(), OSSP's UUID_FMT_STR, /proc/sys/kernel/random/uuid, etc. produce this.

(For instance, COM's GUIDs are a UUID in the same hex representation, but with upper-case digits, and wrapped in {} - translating one to the other is easy.)

For reference, here's Qt's UUID implementation: http://qt.gitorious.org/qt/qt/blobs/4.7/src/corelib/plugin/quuid.cpp#line562

On Windows, it uses CoCreateGuid(); on Unix it tries to use /dev/urandom (falling back to qrand()) and formats it specially, as described here: http://qt.gitorious.org/qt/qt/blobs/4.7/src/corelib/plugin/quuid.cpp#line546

Created attachment 39105 [details] [review]
Remove dependency to libuuid

Remove dependency on external libuuid by implementing an RFC4122
compliant UUID generator.

Created attachment 39106 [details] [review]
Remove dependency to libuuid (less call to g_random_*)

Remove dependency on external libuuid by implementing an RFC4122
compliant UUID generator.

This version is exactly like attachement 39105, but requires less calls to g_random_*. Note that it depends on g_strdup_fprintf() ability to handle on 64bit integers, which is document in GLib has non-portable across compilers, is it ?

Let me know which one you prefer, the 64bit thingy can probably be removed in this one.

> +  /* Fill with random. The g_random_int() call uses Mersenne Twister PRNG
> +   * seeded with /dev/random or the current time, which comply with
> +   * RFC4122 requirement.

That's the "general-purpose PRNG with a relatively small amount of state" that I mentioned previously. RFC4122 says:

   See Section 4.5 for a discussion on random numbers.

and in that section

   A better solution is to obtain a 47-bit cryptographic quality random
   number
...
   Advice on generating cryptographic-quality random numbers can be
   found in RFC1750 [5].

Reference [5] is in fact to RFC4086, which obsoletes RFC1750, and discusses /dev/random and Windows' CryptGenRandom.

Since Qt is LGPL these days, porting the Qt implementation (which Will linked above) to C might be a good basis for UUID generation.

It'd also be reasonable to have Gabble/telepathy-glib support both e2fsprogs uuid and OSSP uuid: see Bug #22972 for more background on that (and why uuid.h could come from either!).

I think the new patch is fine. These UUIDs don't have to be perfectly cryptographically sound. They're just for IMs.

Having an optional dependency on one of two different UUID libraries, falling back to an internal implementation, feels like overkill to me.

(In reply to comment #9)
> > +  /* Fill with random. The g_random_int() call uses Mersenne Twister PRNG
> > +   * seeded with /dev/random or the current time, which comply with
> > +   * RFC4122 requirement.
> 
> That's the "general-purpose PRNG with a relatively small amount of state" that
> I mentioned previously. RFC4122 says:
> 
>    See Section 4.5 for a discussion on random numbers.
> 
> and in that section
> 
>    A better solution is to obtain a 47-bit cryptographic quality random
>    number
> ...
>    Advice on generating cryptographic-quality random numbers can be
>    found in RFC1750 [5].
> 
> Reference [5] is in fact to RFC4086, which obsoletes RFC1750, and discusses
> /dev/random and Windows' CryptGenRandom.
> 
> Since Qt is LGPL these days, porting the Qt implementation (which Will linked
> above) to C might be a good basis for UUID generation.
> 
> It'd also be reasonable to have Gabble/telepathy-glib support both e2fsprogs
> uuid and OSSP uuid: see Bug #22972 for more background on that (and why uuid.h
> could come from either!).

The PRNG in GLib is seeded with /dev/random, which is a cryptographic source of entropy. Also, we need to evaluate the *risk* according to our use of it, this risk is very low since Gabble does not consume a very large amount of it. Couple of millions of states (that all depend on a cryptographic seed) is way enough for us. I think it's not reasonnable to force having ifdef for every implementatons of libuuid, which all have conflicting uuid.h files.

Please, consider one of these patches so our users can stop suffering the problem with conflicting or unsupported libuuid that we currently depend on. A merge into tp-glib or even GLib can be considered later, currently the goal is to allow Gabble to be cross-platform with a minimum effort, and correctness.

OK, OK, you've convinced me that we don't need cryptographically strong uniqueness. However, please amend the comments to make it clear that this doesn't use a cryptographically strong PRNG, but is "good enough" for uses where global uniqueness and high unpredictability isn't necessary, like those in Gabble.

(Seeding a general-purpose PRNG with entropy from /dev/random still only gives you a relatively small number of possible states - it just makes the initial choice from among those states highly unpredictable.)

Depending on how we use UUIDs in practice, we can reassess this if we need to do better in future; at the moment we only use them as message IDs and Google chatroom names, I think.

The second version of the patch looks better, so I'm not reviewing the first here.

> Note that it depends on g_strdup_fprintf() ability to handle on
> 64bit integers, which is document in GLib has non-portable across compilers

It should be trivial to avoid this: just split uuid.node into guint16 node_hi and guint32 node_low (which matches how you're generating it, in fact), and emit them separately as %04x%08x with no intervening punctuation. The fact that you generate them separately and concatenate is just an implementation detail anyway.

If it's less trivial than I expect, "get a better compiler" also seems like a reasonable answer.

stormer pointed out on IRC that if we call g_rand_new() once per UUID, that reads an implementation-dependent amount of entropy (currently 128 bits) from /dev/urandom for use as a seed. Conveniently, that's enough for a UUID.

I think that's a good approach in the short term, and we can push for a UUID implementation in GLib as a longer term solution.

Created attachment 39153 [details] [review]
Remove dependency to libuuid

Remove dependency on external libuuid by implementing an RFC4122
compliant UUID generator

This is just like attachement 39106, but this time I use a new GRand for better entropy and avoid the 64bit printf with _hi,_low trick.

Review of attachment 39153 [details] [review]:

Ship it

Fixed upstream.