lib/uuid.c

   1 /* Copyright (c) 2008, 2009, 2010, 2011, 2013, 2016, 2017 Nicira, Inc.
   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 "ovs-thread.h"
  30 #include "sha1.h"
  31 #include "timeval.h"
  32 #include "util.h"
  33
  34 static struct aes128 key;
  35 static uint64_t counter[2];
  36 BUILD_ASSERT_DECL(sizeof counter == 16);
  37
  38 static void do_init(void);
  39
  40 /*
  41  * Initialize the UUID module.  Aborts the program with an error message if
  42  * initialization fails (which should never happen on a properly configured
  43  * machine.)
  44  *
  45  * Currently initialization is only needed by uuid_generate().  uuid_generate()
  46  * will automatically call uuid_init() itself, so it's only necessary to call
  47  * this function explicitly if you want to abort the program earlier than the
  48  * first UUID generation in case of failure.
  49  */
  50 void
  51 uuid_init(void)
  52 {
  53     static pthread_once_t once = PTHREAD_ONCE_INIT;
  54     pthread_once(&once, do_init);
  55 }
  56
  57 /* Generates a new random UUID in 'uuid'.
  58  *
  59  * We go to some trouble to ensure as best we can that the generated UUID has
  60  * these properties:
  61  *
  62  *      - Uniqueness.  The random number generator is seeded using both the
  63  *        system clock and the system random number generator, plus a few
  64  *        other identifiers, which is about as good as we can get in any kind
  65  *        of simple way.
  66  *
  67  *      - Unpredictability.  In some situations it could be bad for an
  68  *        adversary to be able to guess the next UUID to be generated with some
  69  *        probability of success.  This property may or may not be important
  70  *        for our purposes, but it is better if we can get it.
  71  *
  72  * To ensure both of these, we start by taking our seed data and passing it
  73  * through SHA-1.  We use the result as an AES-128 key.  We also generate a
  74  * random 16-byte value[*] which we then use as the counter for CTR mode.  To
  75  * generate a UUID in a manner compliant with the above goals, we merely
  76  * increment the counter and encrypt it.
  77  *
  78  * [*] It is not actually important that the initial value of the counter be
  79  *     random.  AES-128 in counter mode is secure either way.
  80  */
  81 void
  82 uuid_generate(struct uuid *uuid)
  83 {
  84     static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
  85     uint64_t copy[2];
  86
  87     uuid_init();
  88
  89     /* Copy out the counter's current value, then increment it. */
  90     ovs_mutex_lock(&mutex);
  91     copy[0] = counter[0];
  92     copy[1] = counter[1];
  93     if (++counter[1] == 0) {
  94         counter[0]++;
  95     }
  96     ovs_mutex_unlock(&mutex);
  97
  98     /* AES output is exactly 16 bytes, so we encrypt directly into 'uuid'. */
  99     aes128_encrypt(&key, copy, uuid);
 100
 101     uuid_set_bits_v4(uuid);
 102 }
 103
 104 struct uuid
 105 uuid_random(void)
 106 {
 107     struct uuid uuid;
 108     uuid_generate(&uuid);
 109     return uuid;
 110 }
 111
 112 void
 113 uuid_set_bits_v4(struct uuid *uuid)
 114 {
 115     /* Set bits to indicate a random UUID.  See RFC 4122 section 4.4. */
 116     uuid->parts[2] &= ~0xc0000000;
 117     uuid->parts[2] |=  0x80000000;
 118     uuid->parts[1] &= ~0x0000f000;
 119     uuid->parts[1] |=  0x00004000;
 120 }
 121
 122 /* Sets 'uuid' to all-zero-bits. */
 123 void
 124 uuid_zero(struct uuid *uuid)
 125 {
 126     *uuid = UUID_ZERO;
 127 }
 128
 129 /* Returns true if 'uuid' is all zero, otherwise false. */
 130 bool
 131 uuid_is_zero(const struct uuid *uuid)
 132 {
 133     return (!uuid->parts[0] && !uuid->parts[1]
 134             && !uuid->parts[2] && !uuid->parts[3]);
 135 }
 136
 137 /* Compares 'a' and 'b'.  Returns a negative value if 'a < b', zero if 'a ==
 138  * b', or positive if 'a > b'.  The ordering is lexicographical order of the
 139  * conventional way of writing out UUIDs as strings. */
 140 int
 141 uuid_compare_3way(const struct uuid *a, const struct uuid *b)
 142 {
 143     if (a->parts[0] != b->parts[0]) {
 144         return a->parts[0] > b->parts[0] ? 1 : -1;
 145     } else if (a->parts[1] != b->parts[1]) {
 146         return a->parts[1] > b->parts[1] ? 1 : -1;
 147     } else if (a->parts[2] != b->parts[2]) {
 148         return a->parts[2] > b->parts[2] ? 1 : -1;
 149     } else if (a->parts[3] != b->parts[3]) {
 150         return a->parts[3] > b->parts[3] ? 1 : -1;
 151     } else {
 152         return 0;
 153     }
 154 }
 155
 156 /* Attempts to convert string 's' into a UUID in 'uuid'.  Returns true if
 157  * successful, which will be the case only if 's' has the exact format
 158  * specified by RFC 4122.  Returns false on failure.  On failure, 'uuid' will
 159  * be set to all-zero-bits. */
 160 bool
 161 uuid_from_string(struct uuid *uuid, const char *s)
 162 {
 163     if (!uuid_from_string_prefix(uuid, s)) {
 164         return false;
 165     } else if (s[UUID_LEN] != '\0') {
 166         uuid_zero(uuid);
 167         return false;
 168     } else {
 169         return true;
 170     }
 171 }
 172
 173 /* Same as uuid_from_string() but s[UUID_LEN] is not required to be a null byte
 174  * to succeed; that is, 's' need only begin with UUID syntax, not consist
 175  * entirely of it. */
 176 bool
 177 uuid_from_string_prefix(struct uuid *uuid, const char *s)
 178 {
 179     /* 0         1         2         3      */
 180     /* 012345678901234567890123456789012345 */
 181     /* ------------------------------------ */
 182     /* 00000000-1111-1111-2222-222233333333 */
 183
 184     bool ok;
 185
 186     uuid->parts[0] = hexits_value(s, 8, &ok);
 187     if (!ok || s[8] != '-') {
 188         goto error;
 189     }
 190
 191     uuid->parts[1] = hexits_value(s + 9, 4, &ok) << 16;
 192     if (!ok || s[13] != '-') {
 193         goto error;
 194     }
 195
 196     uuid->parts[1] += hexits_value(s + 14, 4, &ok);
 197     if (!ok || s[18] != '-') {
 198         goto error;
 199     }
 200
 201     uuid->parts[2] = hexits_value(s + 19, 4, &ok) << 16;
 202     if (!ok || s[23] != '-') {
 203         goto error;
 204     }
 205
 206     uuid->parts[2] += hexits_value(s + 24, 4, &ok);
 207     if (!ok) {
 208         goto error;
 209     }
 210
 211     uuid->parts[3] = hexits_value(s + 28, 8, &ok);
 212     if (!ok) {
 213         goto error;
 214     }
 215     return true;
 216
 217 error:
 218     uuid_zero(uuid);
 219     return false;
 220 }
 221
 222 /* If 's' is a string representation of a UUID, or the beginning of one,
 223  * returns strlen(s), otherwise 0.
 224  *
 225  * For example:
 226  *
 227  *     "123" yields 3
 228  *     "xyzzy" yields 0
 229  *     "123xyzzy" yields 0
 230  *     "e66250bb-9531-491b-b9c3-5385cabb0080" yields 36
 231  *     "e66250bb-9531-491b-b9c3-5385cabb0080xyzzy" yields 0
 232  */
 233 int
 234 uuid_is_partial_string(const char *s)
 235 {
 236     static const char tmpl[UUID_LEN] = "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx";
 237     size_t i;
 238     for (i = 0; i < UUID_LEN; i++) {
 239         if (s[i] == '\0') {
 240             return i;
 241         } else if (tmpl[i] == 'x'
 242                    ? hexit_value(s[i]) < 0
 243                    : s[i] != '-') {
 244             return 0;
 245         }
 246     }
 247     if (s[i] != '\0') {
 248         return 0;
 249     }
 250     return i;
 251 }
 252
 253 /* Compares 'match' to the string representation of 'uuid'.  If 'match' equals
 254  * or is a prefix of this string representation, returns strlen(match);
 255  * otherwise, returns 0. */
 256 int
 257 uuid_is_partial_match(const struct uuid *uuid, const char *match)
 258 {
 259     char uuid_s[UUID_LEN + 1];
 260     snprintf(uuid_s, sizeof uuid_s, UUID_FMT, UUID_ARGS(uuid));
 261     size_t match_len = strlen(match);
 262     return !strncmp(uuid_s, match, match_len) ? match_len : 0;
 263 }
 264 \f
 265 static void
 266 sha1_update_int(struct sha1_ctx *sha1_ctx, uintmax_t x)
 267 {
 268    sha1_update(sha1_ctx, &x, sizeof x);
 269 }
 270
 271 static void
 272 do_init(void)
 273 {
 274     uint8_t sha1[SHA1_DIGEST_SIZE];
 275     struct sha1_ctx sha1_ctx;
 276     uint8_t random_seed[16];
 277     struct timeval now;
 278
 279     /* Get seed data. */
 280     get_entropy_or_die(random_seed, sizeof random_seed);
 281     xgettimeofday(&now);
 282
 283     /* Convert seed into key. */
 284     sha1_init(&sha1_ctx);
 285     sha1_update(&sha1_ctx, random_seed, sizeof random_seed);
 286     sha1_update(&sha1_ctx, &now, sizeof now);
 287     sha1_update_int(&sha1_ctx, getpid());
 288 #ifndef _WIN32
 289     sha1_update_int(&sha1_ctx, getppid());
 290     sha1_update_int(&sha1_ctx, getuid());
 291     sha1_update_int(&sha1_ctx, getgid());
 292 #endif
 293     sha1_final(&sha1_ctx, sha1);
 294
 295     /* Generate key. */
 296     BUILD_ASSERT(sizeof sha1 >= 16);
 297     aes128_schedule(&key, sha1);
 298
 299     /* Generate initial counter. */
 300     get_entropy_or_die(counter, sizeof counter);
 301 }