[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

APR-util UUID generator broken

From: Ralf S. Engelschall <rse_at_engelschall.com>
Date: 2006-04-14 10:21:49 CEST

Let's retry to get this mail through...

----- Forwarded message from "Ralf S. Engelschall" <rse@en1.engelschall.com> -----
Date: Tue, 4 Apr 2006 21:02:52 +0200
From: "Ralf S. Engelschall" <rse@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(&timestamp);

- 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
Received on Fri Apr 14 12:15:28 2006

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.