Is randomblob(16) a good guid generation across multiple computers?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Is randomblob(16) a good guid generation across multiple computers?

Andy KU7T
Hi,
I added a randomblob(16) to each record of a Sqlite table via a trigger with the goal of global uniqueness. Is that the correct approach or would it be better to pass Guid from .Net? I am using System.Data.Sqlite. The following article got me questioning the usage of randomblob: https://devblogs.microsoft.com/oldnewthing/20120523-00/?p=7553

Thanks
Andy

Sent from my T-Mobile 4G LTE Device
Get Outlook for Android<https://aka.ms/ghei36>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Keith Medcalf

randomblob(16) generates 16 random bytes.

randomblob(16) does not generate a valid UUID (it does not set the version and variant flags in the resulting 16-bytes of random data).  If you set the version to 4 and the variant to 1 then randomblob(16) does produce valid version 4 uuids with 122-bits of randomness.  The ext/misc/uuid.c extension does this, for example, generating valid version 4 variant 1 UUIDs.

The only other useful type of UUID to generate would be version 1.  Version 1 is a pseudo-sequential clock based value in which the last 48-bits are the MAC address of the computer (or some fixed identifier of 48-bits for the computer) with the variant set appropriately (thus chopping a couple of bits) and the MAC type (thus chopping another bit, to identify whether the origin is a "real MAC unicast address" or a "fake ID -- multicast MAC address").  The clock and sequence is merely the current clock count plus a sequence number of the generated UUID.  Less the 4 bit version which is set to 1.

Microsoft does not generate valid UUIDs (either version 1 or version 4).  They do not have the version and variant set properly and are stored "little endian" rather than in network byte order.  If you pass a "standards based" UUID to a "Microsoft" renderer you will get a different result than if you pass the same UUID bytes to a standards compliant renderer.

Both version 1 and version 4 UUIDs are probabilisticly Universally Unique.  Version 1 because the single-source generator uses a theoretically unique machine ID, and version 4 because hopefully the random 122-bits are in fact 122-bits of entropy.

So really it boils down to a question of how you want these UUIDs to be represented.  There is the "Microsoft way" and the "Microsoft way" is incompatible with the "standard".  So if you choose the "standard" way, then you will have to forgo the "Microsoft way" and use only standard compliant handlers (and therefore will have standard compliant UUIDs on all platforms).  Conversely, if you choose the "Microsoft way" then you will be limited to only ever being compliant with the "Microsoft way" and limited to Microsoft platforms.

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.

>-----Original Message-----
>From: sqlite-users <[hidden email]> On
>Behalf Of Andy KU7T
>Sent: Thursday, 20 February, 2020 11:12
>To: SQLite mailing list <[hidden email]>
>Subject: [sqlite] Is randomblob(16) a good guid generation across
>multiple computers?
>
>Hi,
>I added a randomblob(16) to each record of a Sqlite table via a trigger
>with the goal of global uniqueness. Is that the correct approach or would
>it be better to pass Guid from .Net? I am using System.Data.Sqlite. The
>following article got me questioning the usage of randomblob:
>https://devblogs.microsoft.com/oldnewthing/20120523-00/?p=7553
>
>Thanks
>Andy
>
>Sent from my T-Mobile 4G LTE Device
>Get Outlook for Android<https://aka.ms/ghei36>
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users



_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Richard Hipp-3
In reply to this post by Andy KU7T
On 2/20/20, Andy KU7T <[hidden email]> wrote:
> Hi,
> I added a randomblob(16) to each record of a Sqlite table via a trigger with
> the goal of global uniqueness. Is that the correct approach or would it be
> better to pass Guid from .Net? I am using System.Data.Sqlite. The following
> article got me questioning the usage of randomblob:
> https://devblogs.microsoft.com/oldnewthing/20120523-00/?p=7553

The author of that article, "Raymond", assumes that the random number
generator in the SQL database engine is not cryptographically strong.
That assumption is not correct for SQLite, which does you a
cryptographically strong PRNG.  And the SQLite PRNG is seeded from
/dev/random on unix.  Now, on Windows systems, the seeding is not
quite as strong as it is on unix (unless you compile with
-DSQLITE_WIN32_USE_UUID) but it is still sufficient to reduce the
changes of a collision between two randomblob(16) calls to practically
zero.

So, I think randomblob(16) is a fine way to generate a UUID.

Though, I tend to use randomblob(20), and I often run it through hex()
too, so that it is human-readable.


--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Richard Hipp-3
In reply to this post by Keith Medcalf
On 2/20/20, Keith Medcalf <[hidden email]> wrote:
>
> randomblob(16) does not generate a valid UUID (it does not set the version
> and variant flags in the resulting 16-bytes of random data).

If you need a UUID in the "standard format", rather than just an ID
that its universally unique, you can use the uuid.c extension:
https://www.sqlite.org/src/artifact/5bb2264c1b64d163


--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Keith Medcalf
In reply to this post by Richard Hipp-3

On Thursday, 20 February, 2020 11:48, Richard Hipp <[hidden email]> wrote:

>The author of that article, "Raymond", assumes that the random number
>generator in the SQL database engine is not cryptographically strong.

Actaully, what "Raymond" is on about is the fact that the original definition of a GUID, according to Microsoft, was what is now called, in standard parlance, a Version 1 Variant 2 UUID, only without the Version and Variant identifiers.  It used the "clock and sequence" based on the current clock in huns and a sequence number to "break ties" in case you tried to have Windows generate more than 1 GUID per hun.  The last 48-bits were the "Unique ID" of the computer as generated and stored in the registry by Microsoft when Windows was installed (with no generated-id flag as provided in the current standard).

It was always stored in little-endian order exclusively, even on big-endian processors.  There was no randomness at all.  Not even the slightest.  Ever.  It was exclusively a (more or less) sequential number.

Several years ago Microsoft decided to replace the version 1 GUID, which contained an identifier traceable back to the computer on which it was created, with a truly random Version 4 type UUID (though still without a version number and still without variant encoding, and still always in little endian format) -- apparently Microsoft software loves storing "GUIDs" thither and yon like in Word and Excel documents, and Microsoft's Legal Department determined that this was a "liability" because the Justice Department would be able to prove which computer was used to compose a document, spreadsheet, or email message with trivial effort, thus exposing the company and its executives to liability which could be avoided by simply using "random" GUIDs rather than "machine specific" GUIDs.

A new API was introduced to permit the "old fashioned sequential GUIDs linked inexoribly to the computer" to be generated by those that wanted to still use them, but the default API changed internally to now providing version 4 UUIDs (though still without the standard UUID version and variant flags, and still in exclusively little endian byte order).

So it has nothing to do with randomness.  It has to do with the fact that a "GUID" contains two parts:  a time stamp in UTC and a sequence number, plus the (hopefully) unique ID of the computer generating the GUID.  It is not random.  It is sequential.  And the "Global Uniqueness" part is determined solely by the hopefully "Global Uniqueness" of the machine identifier which created the GUID.

Only later did the "GUID" contain randomness by default though Windows was still capable of generating the old sequential GUIDs.

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Jens Alfke-2
In reply to this post by Richard Hipp-3


> On Feb 20, 2020, at 10:48 AM, Richard Hipp <[hidden email]> wrote:
>
> That assumption is not correct for SQLite, which does you a
> cryptographically strong PRNG.  And the SQLite PRNG is seeded from
> /dev/random on unix.

Not quite; I'm looking at the function unixRandomness() in SQLite 3.28. It's seeded from /dev/urandom, which on Linux "will produce lower quality output if the entropy pool drains, while /dev/random will prefer to block and wait for additional entropy to be collected." (I'm quoting the macOS man page, which goes on to say that on macOS it always returns high-quality randomness.)

I'm a bit doubtful about how the function handles errors, too.

* If /dev/urandom can't be opened, it instead cobbles together some decidedly low-entropy bytes from the results of the time() and getpid() system calls. IIRC this is very much like the way Netscape seeded its RNG in their first implementation of SSL, which turned out to be easily crackable by guessing the seed.

* If there's a read error on /dev/urandom, it just returns a buffer full of zeros, which is about as non-random as you can get.

Admittedly these are unlikely scenarios, but failure to properly seed an RNG can be catastrophic for security. And a lot of security exploits come from 'unlikely' scenarios that an attacker finds a way to force.

There's a disclaimer about this, actually, inside the source code of sqlite3_randomness():

>   /* Initialize the state of the random number generator once,
>   ** the first time this routine is called.  The seed value does
>   ** not need to contain a lot of randomness since we are not
>   ** trying to do secure encryption or anything like that…

That's kind of at odds with your calling it a cryptographically strong PRNG. :(

—Jens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Rowan Worth-2
On Fri, 21 Feb 2020 at 03:59, Jens Alfke <[hidden email]> wrote:

> > On Feb 20, 2020, at 10:48 AM, Richard Hipp <[hidden email]> wrote:
> >
> > That assumption is not correct for SQLite, which does you a
> > cryptographically strong PRNG.  And the SQLite PRNG is seeded from
> > /dev/random on unix.
>
> Not quite; I'm looking at the function unixRandomness() in SQLite 3.28.
> It's seeded from /dev/urandom, which on Linux "will produce lower quality
> output if the entropy pool drains, while /dev/random will prefer to block
> and wait for additional entropy to be collected." (I'm quoting the macOS
> man page, which goes on to say that on macOS it always returns high-quality
> randomness.)
>

There are a lot of myths in this area, but from what I gather /dev/urandom
is totally fine for cryptographic purposes in modern linux, and any
advantages of /dev/random are highly overstated.

https://www.2uo.de/myths-about-urandom/
 -Rowan
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Andy KU7T
I admit I do not fully understand all the arguments. I am running on Windows. Are you saying the PRNG on Windows is not good enough to use randomblob(16) in Sqlite? All I need is a reasonable assurance that is are unique...

Andy

Sent from my T-Mobile 4G LTE Device
Get Outlook for Android<https://aka.ms/ghei36>

________________________________
From: sqlite-users <[hidden email]> on behalf of Rowan Worth <[hidden email]>
Sent: Thursday, February 20, 2020 7:00:20 PM
To: SQLite mailing list <[hidden email]>
Subject: Re: [sqlite] Is randomblob(16) a good guid generation across multiple computers?

On Fri, 21 Feb 2020 at 03:59, Jens Alfke <[hidden email]> wrote:

> > On Feb 20, 2020, at 10:48 AM, Richard Hipp <[hidden email]> wrote:
> >
> > That assumption is not correct for SQLite, which does you a
> > cryptographically strong PRNG.  And the SQLite PRNG is seeded from
> > /dev/random on unix.
>
> Not quite; I'm looking at the function unixRandomness() in SQLite 3.28.
> It's seeded from /dev/urandom, which on Linux "will produce lower quality
> output if the entropy pool drains, while /dev/random will prefer to block
> and wait for additional entropy to be collected." (I'm quoting the macOS
> man page, which goes on to say that on macOS it always returns high-quality
> randomness.)
>

There are a lot of myths in this area, but from what I gather /dev/urandom
is totally fine for cryptographic purposes in modern linux, and any
advantages of /dev/random are highly overstated.

https://www.2uo.de/myths-about-urandom/
 -Rowan
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Keith Medcalf

On Thursday, 20 February, 2020 22:06, Andy KU7T <[hidden email]> wrote:

>I admit I do not fully understand all the arguments. I am running on
>Windows. Are you saying the PRNG on Windows is not good enough to use
>randomblob(16) in Sqlite? All I need is a reasonable assurance that is
>are unique...

Yes, it is reasonably random.  To improve the entropy of the seed you should compile the amalgamation with -DSQLITE_WIN32_USE_UUID=1 and include RPCRT4.LIB in the link.

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Is randomblob(16) a good guid generation across multiple computers?

Richard Hipp-3
In reply to this post by Andy KU7T
On 2/21/20, Andy KU7T <[hidden email]> wrote:
> Are you saying the PRNG on Windows is not good enough to use
> randomblob(16) in Sqlite? All I need is a reasonable assurance that is are
> unique...

The default PRNG on Windows is fine for generating globally unique identifiers.

The complaint is that the seeding of the PRNG on Windows is such that
an attacker could by brute force discover the seed of the PRNG by
examining a sequence of generated UUIDs.  In that scenario, the
attacker might be able to guess the next UUID that your system will be
generating.  If that is a problem for your application, then fix it by
compiling with -DSQLITE_WIN32_USE_UUID=1 and linking against
RPCRT4.LIB.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users