lib/uuid.c

   1 /* Copyright (c) 2008, 2009, 2010 Nicira Networks
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "uuid.h"
  19
  20 #include <ctype.h>
  21 #include <errno.h>
  22 #include <fcntl.h>
  23 #include <sys/time.h>
  24 #include <sys/types.h>
  25 #include <unistd.h>
  26
  27 #include "aes128.h"
  28 #include "entropy.h"
  29 #include "sha1.h"
  30 #include "util.h"
  31
  32 static struct aes128 key;
  33 static uint64_t counter[2];
  34 BUILD_ASSERT_DECL(sizeof counter == 16);
  35
  36 static void do_init(void);
  37
  38 /*
  39  * Initialize the UUID module.  Aborts the program with an error message if
  40  * initialization fails (which should never happen on a properly configured
  41  * machine.)
  42  *
  43  * Currently initialization is only needed by uuid_generate().  uuid_generate()
  44  * will automatically call uuid_init() itself, so it's only necessary to call
  45  * this function explicitly if you want to abort the program earlier than the
  46  * first UUID generation in case of failure.
  47  */
  48 void
  49 uuid_init(void)
  50 {
  51     static bool inited;
  52     if (!inited) {
  53         do_init();
  54         inited = true;
  55     }
  56 }
  57
  58 /* Generates a new random UUID in 'uuid'.
  59  *
  60  * We go to some trouble to ensure as best we can that the generated UUID has
  61  * these properties:
  62  *
  63  *      - Uniqueness.  The random number generator is seeded using both the
  64  *        system clock and the system random number generator, plus a few
  65  *        other identifiers, which is about as good as we can get in any kind
  66  *        of simple way.
  67  *
  68  *      - Unpredictability.  In some situations it could be bad for an
  69  *        adversary to be able to guess the next UUID to be generated with some
  70  *        probability of success.  This property may or may not be important
  71  *        for our purposes, but it is better if we can get it.
  72  *
  73  * To ensure both of these, we start by taking our seed data and passing it
  74  * through SHA-1.  We use the result as an AES-128 key.  We also generate a
  75  * random 16-byte value[*] which we then use as the counter for CTR mode.  To
  76  * generate a UUID in a manner compliant with the above goals, we merely
  77  * increment the counter and encrypt it.
  78  *
  79  * [*] It is not actually important that the initial value of the counter be
  80  *     random.  AES-128 in counter mode is secure either way.
  81  */
  82 void
  83 uuid_generate(struct uuid *uuid)
  84 {
  85     uuid_init();
  86
  87     /* Increment the counter. */
  88     if (++counter[1] == 0) {
  89         counter[0]++;
  90     }
  91
  92     /* AES output is exactly 16 bytes, so we encrypt directly into 'uuid'. */
  93     aes128_encrypt(&key, counter, uuid);
  94
  95     /* Set bits to indicate a random UUID.  See RFC 4122 section 4.4. */
  96     uuid->parts[2] &= ~0xc0000000;
  97     uuid->parts[2] |=  0x80000000;
  98     uuid->parts[1] &= ~0x0000f000;
  99     uuid->parts[1] |=  0x00004000;
 100 }
 101
 102 /* Sets 'uuid' to all-zero-bits. */
 103 void
 104 uuid_zero(struct uuid *uuid)
 105 {
 106     uuid->parts[0] = uuid->parts[1] = uuid->parts[2] = uuid->parts[3] = 0;
 107 }
 108
 109 /* Returns true if 'uuid' is all zero, otherwise false. */
 110 bool
 111 uuid_is_zero(const struct uuid *uuid)
 112 {
 113     return (!uuid->parts[0] && !uuid->parts[1]
 114             && !uuid->parts[2] && !uuid->parts[3]);
 115 }
 116
 117 /* Compares 'a' and 'b'.  Returns a negative value if 'a < b', zero if 'a ==
 118  * b', or positive if 'a > b'.  The ordering is lexicographical order of the
 119  * conventional way of writing out UUIDs as strings. */
 120 int
 121 uuid_compare_3way(const struct uuid *a, const struct uuid *b)
 122 {
 123     if (a->parts[0] != b->parts[0]) {
 124         return a->parts[0] > b->parts[0] ? 1 : -1;
 125     } else if (a->parts[1] != b->parts[1]) {
 126         return a->parts[1] > b->parts[1] ? 1 : -1;
 127     } else if (a->parts[2] != b->parts[2]) {
 128         return a->parts[2] > b->parts[2] ? 1 : -1;
 129     } else if (a->parts[3] != b->parts[3]) {
 130         return a->parts[3] > b->parts[3] ? 1 : -1;
 131     } else {
 132         return 0;
 133     }
 134 }
 135
 136 /* Attempts to convert string 's' into a UUID in 'uuid'.  Returns true if
 137  * successful, which will be the case only if 's' has the exact format
 138  * specified by RFC 4122.  Returns false on failure.  On failure, 'uuid' will
 139  * be set to all-zero-bits. */
 140 bool
 141 uuid_from_string(struct uuid *uuid, const char *s)
 142 {
 143     if (!uuid_from_string_prefix(uuid, s)) {
 144         return false;
 145     } else if (s[UUID_LEN] != '\0') {
 146         uuid_zero(uuid);
 147         return false;
 148     } else {
 149         return true;
 150     }
 151 }
 152
 153 /* Same as uuid_from_string() but s[UUID_LEN] is not required to be a null byte
 154  * to succeed; that is, 's' need only begin with UUID syntax, not consist
 155  * entirely of it. */
 156 bool
 157 uuid_from_string_prefix(struct uuid *uuid, const char *s)
 158 {
 159     /* 0         1         2         3      */
 160     /* 012345678901234567890123456789012345 */
 161     /* ------------------------------------ */
 162     /* 00000000-1111-1111-2222-222233333333 */
 163
 164     bool ok;
 165
 166     uuid->parts[0] = hexits_value(s, 8, &ok);
 167     if (!ok || s[8] != '-') {
 168         goto error;
 169     }
 170
 171     uuid->parts[1] = hexits_value(s + 9, 4, &ok) << 16;
 172     if (!ok || s[13] != '-') {
 173         goto error;
 174     }
 175
 176     uuid->parts[1] += hexits_value(s + 14, 4, &ok);
 177     if (!ok || s[18] != '-') {
 178         goto error;
 179     }
 180
 181     uuid->parts[2] = hexits_value(s + 19, 4, &ok) << 16;
 182     if (!ok || s[23] != '-') {
 183         goto error;
 184     }
 185
 186     uuid->parts[2] += hexits_value(s + 24, 4, &ok);
 187     if (!ok) {
 188         goto error;
 189     }
 190
 191     uuid->parts[3] = hexits_value(s + 28, 8, &ok);
 192     if (!ok) {
 193         goto error;
 194     }
 195     return true;
 196
 197 error:
 198     uuid_zero(uuid);
 199     return false;
 200 }
 201 \f
 202 static void
 203 do_init(void)
 204 {
 205     uint8_t sha1[SHA1_DIGEST_SIZE];
 206     struct sha1_ctx sha1_ctx;
 207     uint8_t random_seed[16];
 208     struct timeval now;
 209     pid_t pid, ppid;
 210     uid_t uid;
 211     gid_t gid;
 212
 213     /* Get seed data. */
 214     get_entropy_or_die(random_seed, sizeof random_seed);
 215     if (gettimeofday(&now, NULL)) {
 216         ovs_fatal(errno, "gettimeofday failed");
 217     }
 218     pid = getpid();
 219     ppid = getppid();
 220     uid = getuid();
 221     gid = getgid();
 222
 223     /* Convert seed into key. */
 224     sha1_init(&sha1_ctx);
 225     sha1_update(&sha1_ctx, random_seed, sizeof random_seed);
 226     sha1_update(&sha1_ctx, &pid, sizeof pid);
 227     sha1_update(&sha1_ctx, &ppid, sizeof ppid);
 228     sha1_update(&sha1_ctx, &uid, sizeof uid);
 229     sha1_update(&sha1_ctx, &gid, sizeof gid);
 230     sha1_final(&sha1_ctx, sha1);
 231
 232     /* Generate key. */
 233     BUILD_ASSERT(sizeof sha1 >= 16);
 234     aes128_schedule(&key, sha1);
 235
 236     /* Generate initial counter. */
 237     get_entropy_or_die(counter, sizeof counter);
 238 }