apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ralf S. Engelschall" <...@engelschall.com>
Subject APR-util UUID generator broken
Date Fri, 14 Apr 2006 08:21:49 GMT
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


Mime
View raw message