You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by "Ralf S. Engelschall" <rs...@engelschall.com> on 2006/04/14 08:21:49 UTC
APR-util UUID generator broken
Let's retry to get this mail through...
----- Forwarded message from "Ralf S. Engelschall" <rs...@en1.engelschall.com> -----
Date: Tue, 4 Apr 2006 21:02:52 +0200
From: "Ralf S. Engelschall" <rs...@en1.engelschall.com>
To: dev@apr.apache.org, dev@subversion.tigris.org
Subject: APR-util UUID generator broken
Reply-To: rse@engelschall.com
Organization: Engelschall, Germany.
User-Agent: Mutt/1.5.11 OpenPKG/CURRENT
As UUIDs found in Subversion repositories looked strange to me...
| $ svnadmin create /tmp/repository
| $ uuid -d `cat /tmp/repository/db/uuid`
| UUID: 4ac08136-9f10-0410-b9d4-41ac6b128626
| variant: DCE 1.1, ISO/IEC 11578:1996
| version: 0 (unknown)
| content: 4A:C0:81:36:9F:10:04:10:39:D4:41:AC:6B:12:86:26
| (not decipherable: unknown UUID version)
...I've reviewed the UUID generator in APR-util. It unfortunately is
totally broken and generates neither valid (format) nor useful (content)
RFC4122 UUIDs. It has the following particular problems:
1. ERROR: for generating the version 1 UUIDs the function apr_time_now()
(using Unix Epoch time basis) is used although a local function
get_system_time() was defined (which time adjusts to the UUID time
basis). This way the time in the generated UUIDs is time shifted and
this way incorrect.
2. ERROR: UUIDs have a 128 bit binary representation where each field is
encoded in _network byte order_. As a result the UUIDs generated
by APR-util were totally bogus as even the "version" field was
encoded into the wrong part of the 128 bit. Additionally, as another
side-effect, the encoded time was also totally bogus, of course.
3. OPTIMIZATION: for generating random content the local
get_system_time() function (which is based on apr_time_now()) is used
which time-adjusts for the UUID vs Unix Epoch time. For generating
random bytes it is fully sufficient to just use plain apr_time_now().
A patch for APR-util 1.2.6, which fixes all of the above, is appended
below and in the latest version also can be found in our OpenPKG CVS
under http://cvs.openpkg.org/getfile/openpkg-src/apr/apr.patch. After
this Subversion (using APR-util) finally generates correct version 1
UUIDs in its repositories:
| $ svnadmin create /tmp/repository
| $ uuid -d `cat /tmp/repository/db/uuid`
| UUID: 3688951a-c40a-11da-b96e-e7d09f6386f4
| variant: DCE 1.1, ISO/IEC 11578:1996
| version: 1 (time and node based)
| content: time: 2006-04-04 18:38:30.448873.0 UTC
| clock: 14702 (usually random)
| node: e7:d0:9f:63:86:f4 (local multicast)
Yours,
Ralf S. Engelschall
rse@engelschall.com
www.engelschall.com
Index: apr-util-1.2.6/crypto/getuuid.c
--- apr-util-1.2.6/crypto/getuuid.c.orig 2005-02-04 21:45:35 +0100
+++ apr-util-1.2.6/crypto/getuuid.c 2006-04-04 19:49:37 +0200
@@ -131,7 +131,7 @@
/* crap. this isn't crypto quality, but it will be Good Enough */
- get_system_time(&time_now);
+ time_now = apr_time_now();
srand((unsigned int)(((time_now >> 32) ^ time_now) & 0xffffffff));
return rand() & 0x0FFFF;
@@ -151,7 +151,7 @@
static apr_interval_time_t time_last = 0;
static apr_interval_time_t fudge = 0;
- time_now = apr_time_now();
+ get_system_time(&time_now);
/* if clock reading changed since last UUID generated... */
if (time_last != time_now) {
@@ -188,17 +188,26 @@
get_current_time(×tamp);
- d[0] = (unsigned char)timestamp;
- d[1] = (unsigned char)(timestamp >> 8);
- d[2] = (unsigned char)(timestamp >> 16);
- d[3] = (unsigned char)(timestamp >> 24);
- d[4] = (unsigned char)(timestamp >> 32);
- d[5] = (unsigned char)(timestamp >> 40);
- d[6] = (unsigned char)(timestamp >> 48);
- d[7] = (unsigned char)(((timestamp >> 56) & 0x0F) | 0x10);
+ /* UUID field: time_low */
+ d[0] = (unsigned char)(timestamp >> (8*3));
+ d[1] = (unsigned char)(timestamp >> (8*2));
+ d[2] = (unsigned char)(timestamp >> (8*1));
+ d[3] = (unsigned char)(timestamp);
+
+ /* UUID field: time_mid */
+ d[4] = (unsigned char)(timestamp >> (8*5));
+ d[5] = (unsigned char)(timestamp >> (8*4));
+
+ /* UUID field: time_hi_and_version */
+ d[6] = (unsigned char)(((timestamp >> (8*7)) & 0x0F) | 0x10);
+ d[7] = (unsigned char)(timestamp >> (8*6));
+ /* UUID field: clk_seq_hi_res */
d[8] = (unsigned char)(((uuid_state_seqnum >> 8) & 0x3F) | 0x80);
+
+ /* UUID field: clk_seq_low */
d[9] = (unsigned char)uuid_state_seqnum;
+ /* UUID field: node */
memcpy(&d[10], uuid_state_node, NODE_LENGTH);
}
----- End forwarded message -----
Ralf S. Engelschall
rse@engelschall.com
www.engelschall.com
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: APR-util UUID generator broken
Posted by Max Bowsher <ma...@ukf.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Ralf S. Engelschall wrote:
> As UUIDs found in Subversion repositories looked strange to me...
> ...I've reviewed the UUID generator in APR-util. It unfortunately is
> totally broken and generates neither valid (format) nor useful (content)
> RFC4122 UUIDs.
Since the generation is entirely in the hands of APR-util, not
Subversion, I've replied substansively on dev@apr only.
Max.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (Cygwin)
iD8DBQFEP7y0fFNSmcDyxYARAt48AJ9rgOe8E93Q6475+pzwCIwPDQZFDgCeKr68
fIhgt345Q2Pg145TiD94RIE=
=Q4ty
-----END PGP SIGNATURE-----
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: APR-util UUID generator broken
Posted by "Ralf S. Engelschall" <rs...@engelschall.com>.
On Fri, Apr 14, 2006, Max Bowsher wrote:
> [...]
> OK, backports committed to 1.2.x and 0.9.x branches.
Thanks for your efforts.
Ralf S. Engelschall
rse@engelschall.com
www.engelschall.com
Re: APR-util UUID generator broken
Posted by Max Bowsher <ma...@ukf.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Ralf S. Engelschall wrote:
> On Fri, Apr 14, 2006, Max Bowsher wrote:
>
>> [...]
>> OK, I'll backport it. Just out of curiosity, is there any problem caused
>> by the weird UUIDs?
>
> I'm not aware of any functional problems.
>
> I'm just still trying hard to fix the existing UUID implementations
> to make sure that everything which looks like a UUID actually is also
> a standard-conforming UUID. You would be surprised how many software
> exists on the net which claim to produce "UUIDs" but actually generates
> nothing more than 128 bit of pseudo-randomness, printed as hex values
> with a few dashes between them ;-)
>
>> Should I be considering backporting it to 0.9.x as well? (Anyone using
>> Apache 2.0.x must continue to use APR 0.9.x, and 0.9.x will remain the
>> default bundled with Subversion for the forseeable future.)
>> [...]
>
> If APR 0.9.x will be still productive even in the forseeable future I
> suggest to backport the fix to APR 0.9.x, too. Because even if there is
> most of the time no functional problem with the bogus UUIDs (as long as
> nobody tries to _decode_ them as I do with OSSP uuid ;-) it looks rather
> unprofessional when modern applications like Subversion generate such
> bogus UUIDs into every repository.
>
> Thanks for your investigation.
OK, backports committed to 1.2.x and 0.9.x branches.
Max.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (Cygwin)
iD8DBQFEQBRofFNSmcDyxYARAhPHAKDWpDjYW6WyyN9TB23mec8pdiYAZACeJrJ/
KisLMv6dk/bzSFvKnER0jB4=
=Emsa
-----END PGP SIGNATURE-----
Re: APR-util UUID generator broken
Posted by "Ralf S. Engelschall" <rs...@engelschall.com>.
On Fri, Apr 14, 2006, Max Bowsher wrote:
> [...]
> OK, I'll backport it. Just out of curiosity, is there any problem caused
> by the weird UUIDs?
I'm not aware of any functional problems.
I'm just still trying hard to fix the existing UUID implementations
to make sure that everything which looks like a UUID actually is also
a standard-conforming UUID. You would be surprised how many software
exists on the net which claim to produce "UUIDs" but actually generates
nothing more than 128 bit of pseudo-randomness, printed as hex values
with a few dashes between them ;-)
> Should I be considering backporting it to 0.9.x as well? (Anyone using
> Apache 2.0.x must continue to use APR 0.9.x, and 0.9.x will remain the
> default bundled with Subversion for the forseeable future.)
> [...]
If APR 0.9.x will be still productive even in the forseeable future I
suggest to backport the fix to APR 0.9.x, too. Because even if there is
most of the time no functional problem with the bogus UUIDs (as long as
nobody tries to _decode_ them as I do with OSSP uuid ;-) it looks rather
unprofessional when modern applications like Subversion generate such
bogus UUIDs into every repository.
Thanks for your investigation.
Yours,
Ralf S. Engelschall
rse@engelschall.com
www.engelschall.com
Re: APR-util UUID generator broken
Posted by Max Bowsher <ma...@ukf.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Ralf S. Engelschall wrote:
> On Fri, Apr 14, 2006, Max Bowsher wrote:
>
>> [...]
>>> ...I've reviewed the UUID generator in APR-util. It unfortunately is
>>> totally broken and generates neither valid (format) nor useful (content)
>>> RFC4122 UUIDs.
>> REMOVING CC to dev@subversion, as this is entirely an APR issue.
>
> Please keep in mind that Subversion ships with a _copy_ of APR (and seem
> to not very often upgrade their copy) and hence they have to fix it in
> their copy (or upgrade once your released a fixed APR version ;-), too.
I'm a Subversion committer, so I can say with complete certainty that
your understanding of the Subversion release process with respect to APR
is wildly inaccurate.
Subversion bundles the latest released version of APR 0.9.x. We do not
do anything as nastily inelegant as keeping a local copy that is allowed
to get stale.
>> Thankyou for taking the time to hunt down bugs, but you could have saved
>> yourself a lot of time by just checking trunk. Both of the above are
>> already fixed.
>>
>> I did not propose a backport at the time I fixed the bugs, but I take it
>> from your considerable action on this topic that you would like one. I
>> guess that's fine - the change does not have compatibility issues that I
>> am aware of.
>
> Yes, please backport those fixes to your APR 1.2 branch as you yesterday
> even released APR 1.2.7 (from that branch, yes, I know) which still
> contains the same buggy UUID generator. As long as those fixes are not
> part of an official APR release the generated bogus UUIDs are still
> spreading around...
OK, I'll backport it. Just out of curiosity, is there any problem caused
by the weird UUIDs?
Should I be considering backporting it to 0.9.x as well? (Anyone using
Apache 2.0.x must continue to use APR 0.9.x, and 0.9.x will remain the
default bundled with Subversion for the forseeable future.)
>>> 3. OPTIMIZATION: for generating random content the local
>>> get_system_time() function (which is based on apr_time_now()) is used
>>> which time-adjusts for the UUID vs Unix Epoch time. For generating
>>> random bytes it is fully sufficient to just use plain apr_time_now().
>>> Index: apr-util-1.2.6/crypto/getuuid.c
>>> --- apr-util-1.2.6/crypto/getuuid.c.orig 2005-02-04 21:45:35 +0100
>>> +++ apr-util-1.2.6/crypto/getuuid.c 2006-04-04 19:49:37 +0200
>>> @@ -131,7 +131,7 @@
>>>
>>> /* crap. this isn't crypto quality, but it will be Good Enough */
>>>
>>> - get_system_time(&time_now);
>>> + time_now = apr_time_now();
>>> srand((unsigned int)(((time_now >> 32) ^ time_now) & 0xffffffff));
>>>
>>> return rand() & 0x0FFFF;
>> This seems sensible to me.
>>
>> Could someone give a second opinion that this is fine, and isn't going
>> to impact the randomness quality?
>
> The difference between your get_system_time() and apr_time_now() is
> nothing more than the time offset between Unix epoch and the one used
> by UUIDs. Adding a value doesn't change the randomness _quality_ of an
> integer at all (it still is as bad or good as it was before)...
Naturally. I was mainly wondering about the multiplication combined with
the 64bit->32bit folding.
Max.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (Cygwin)
iD8DBQFEP9kkfFNSmcDyxYARAqh+AJ93cOJVfkQMswxSnlPmeJJWHqiEqgCgyuBn
foXI18vEFbX4TeF2mU9jAOU=
=uF3X
-----END PGP SIGNATURE-----
Re: APR-util UUID generator broken
Posted by "Ralf S. Engelschall" <rs...@engelschall.com>.
On Fri, Apr 14, 2006, Max Bowsher wrote:
> [...]
> > ...I've reviewed the UUID generator in APR-util. It unfortunately is
> > totally broken and generates neither valid (format) nor useful (content)
> > RFC4122 UUIDs.
>
> REMOVING CC to dev@subversion, as this is entirely an APR issue.
Please keep in mind that Subversion ships with a _copy_ of APR (and seem
to not very often upgrade their copy) and hence they have to fix it in
their copy (or upgrade once your released a fixed APR version ;-), too.
> [...]
> Thankyou for taking the time to hunt down bugs, but you could have saved
> yourself a lot of time by just checking trunk. Both of the above are
> already fixed.
>
> I did not propose a backport at the time I fixed the bugs, but I take it
> from your considerable action on this topic that you would like one. I
> guess that's fine - the change does not have compatibility issues that I
> am aware of.
Yes, please backport those fixes to your APR 1.2 branch as you yesterday
even released APR 1.2.7 (from that branch, yes, I know) which still
contains the same buggy UUID generator. As long as those fixes are not
part of an official APR release the generated bogus UUIDs are still
spreading around...
> > 3. OPTIMIZATION: for generating random content the local
> > get_system_time() function (which is based on apr_time_now()) is used
> > which time-adjusts for the UUID vs Unix Epoch time. For generating
> > random bytes it is fully sufficient to just use plain apr_time_now().
>
> > Index: apr-util-1.2.6/crypto/getuuid.c
> > --- apr-util-1.2.6/crypto/getuuid.c.orig 2005-02-04 21:45:35 +0100
> > +++ apr-util-1.2.6/crypto/getuuid.c 2006-04-04 19:49:37 +0200
> > @@ -131,7 +131,7 @@
> >
> > /* crap. this isn't crypto quality, but it will be Good Enough */
> >
> > - get_system_time(&time_now);
> > + time_now = apr_time_now();
> > srand((unsigned int)(((time_now >> 32) ^ time_now) & 0xffffffff));
> >
> > return rand() & 0x0FFFF;
>
> This seems sensible to me.
>
> Could someone give a second opinion that this is fine, and isn't going
> to impact the randomness quality?
The difference between your get_system_time() and apr_time_now() is
nothing more than the time offset between Unix epoch and the one used
by UUIDs. Adding a value doesn't change the randomness _quality_ of an
integer at all (it still is as bad or good as it was before)...
Ralf S. Engelschall
rse@engelschall.com
www.engelschall.com
Re: APR-util UUID generator broken
Posted by Max Bowsher <ma...@ukf.net>.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Ralf S. Engelschall wrote:
> As UUIDs found in Subversion repositories looked strange to me...
>
> | $ svnadmin create /tmp/repository
> | $ uuid -d `cat /tmp/repository/db/uuid`
> | UUID: 4ac08136-9f10-0410-b9d4-41ac6b128626
> | variant: DCE 1.1, ISO/IEC 11578:1996
> | version: 0 (unknown)
> | content: 4A:C0:81:36:9F:10:04:10:39:D4:41:AC:6B:12:86:26
> | (not decipherable: unknown UUID version)
>
> ...I've reviewed the UUID generator in APR-util. It unfortunately is
> totally broken and generates neither valid (format) nor useful (content)
> RFC4122 UUIDs.
REMOVING CC to dev@subversion, as this is entirely an APR issue.
> It has the following particular problems:
>
> 1. ERROR: for generating the version 1 UUIDs the function apr_time_now()
> (using Unix Epoch time basis) is used although a local function
> get_system_time() was defined (which time adjusts to the UUID time
> basis). This way the time in the generated UUIDs is time shifted and
> this way incorrect.
>
> 2. ERROR: UUIDs have a 128 bit binary representation where each field is
> encoded in _network byte order_. As a result the UUIDs generated
> by APR-util were totally bogus as even the "version" field was
> encoded into the wrong part of the 128 bit. Additionally, as another
> side-effect, the encoded time was also totally bogus, of course.
Thankyou for taking the time to hunt down bugs, but you could have saved
yourself a lot of time by just checking trunk. Both of the above are
already fixed.
I did not propose a backport at the time I fixed the bugs, but I take it
from your considerable action on this topic that you would like one. I
guess that's fine - the change does not have compatibility issues that I
am aware of.
> 3. OPTIMIZATION: for generating random content the local
> get_system_time() function (which is based on apr_time_now()) is used
> which time-adjusts for the UUID vs Unix Epoch time. For generating
> random bytes it is fully sufficient to just use plain apr_time_now().
> Index: apr-util-1.2.6/crypto/getuuid.c
> --- apr-util-1.2.6/crypto/getuuid.c.orig 2005-02-04 21:45:35 +0100
> +++ apr-util-1.2.6/crypto/getuuid.c 2006-04-04 19:49:37 +0200
> @@ -131,7 +131,7 @@
>
> /* crap. this isn't crypto quality, but it will be Good Enough */
>
> - get_system_time(&time_now);
> + time_now = apr_time_now();
> srand((unsigned int)(((time_now >> 32) ^ time_now) & 0xffffffff));
>
> return rand() & 0x0FFFF;
This seems sensible to me.
Could someone give a second opinion that this is fine, and isn't going
to impact the randomness quality?
Max.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (Cygwin)
iD8DBQFEP3XyfFNSmcDyxYARAgr8AJ4/jNRQV7pWBrZoD925I/GxywVt4gCeNU6V
BmJISEdEp2OVVLQoIGPOOxM=
=QRBf
-----END PGP SIGNATURE-----