lib/uuid.c

   1 /* Copyright (c) 2008, 2009 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 "sha1.h"
  29 #include "socket-util.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 static void read_urandom(void *buffer, size_t n);
  38
  39 /*
  40  * Initialize the UUID module.  Aborts the program with an error message if
  41  * initialization fails (which should never happen on a properly configured
  42  * machine.)
  43  *
  44  * Currently initialization is only needed by uuid_generate().  uuid_generate()
  45  * will automatically call uuid_init() itself, so it's only necessary to call
  46  * this function explicitly if you want to abort the program earlier than the
  47  * first UUID generation in case of failure.
  48  */
  49 void
  50 uuid_init(void)
  51 {
  52     static bool inited;
  53     if (!inited) {
  54         do_init();
  55         inited = true;
  56     }
  57 }
  58
  59 /* Generates a new random UUID in 'uuid'.
  60  *
  61  * We go to some trouble to ensure as best we can that the generated UUID has
  62  * these properties:
  63  *
  64  *      - Uniqueness.  The random number generator is seeded using both the
  65  *        system clock and the system random number generator, plus a few
  66  *        other identifiers, which is about as good as we can get in any kind
  67  *        of simple way.
  68  *
  69  *      - Unpredictability.  In some situations it could be bad for an
  70  *        adversary to be able to guess the next UUID to be generated with some
  71  *        probability of success.  This property may or may not be important
  72  *        for our purposes, but it is better if we can get it.
  73  *
  74  * To ensure both of these, we start by taking our seed data and passing it
  75  * through SHA-1.  We use the result as an AES-128 key.  We also generate a
  76  * random 16-byte value[*] which we then use as the counter for CTR mode.  To
  77  * generate a UUID in a manner compliant with the above goals, we merely
  78  * increment the counter and encrypt it.
  79  *
  80  * [*] It is not actually important that the initial value of the counter be
  81  *     random.  AES-128 in counter mode is secure either way.
  82  */
  83 void
  84 uuid_generate(struct uuid *uuid)
  85 {
  86     uuid_init();
  87
  88     /* Increment the counter. */
  89     if (++counter[1] == 0) {
  90         counter[0]++;
  91     }
  92
  93     /* AES output is exactly 16 bytes, so we encrypt directly into 'uuid'. */
  94     aes128_encrypt(&key, counter, uuid);
  95
  96     /* Set bits to indicate a random UUID.  See RFC 4122 section 4.4. */
  97     uuid->parts[2] &= ~0xc0000000;
  98     uuid->parts[2] |=  0x80000000;
  99     uuid->parts[1] &= ~0x0000f000;
 100     uuid->parts[1] |=  0x00004000;
 101 }
 102
 103 /* Sets 'uuid' to all-zero-bits. */
 104 void
 105 uuid_zero(struct uuid *uuid)
 106 {
 107     uuid->parts[0] = uuid->parts[1] = uuid->parts[2] = uuid->parts[3] = 0;
 108 }
 109
 110 /* Compares 'a' and 'b'.  Returns a negative value if 'a < b', zero if 'a ==
 111  * b', or positive if 'a > b'.  The ordering is lexicographical order of the
 112  * conventional way of writing out UUIDs as strings. */
 113 int
 114 uuid_compare_3way(const struct uuid *a, const struct uuid *b)
 115 {
 116     if (a->parts[0] != b->parts[0]) {
 117         return a->parts[0] > b->parts[0] ? 1 : -1;
 118     } else if (a->parts[1] != b->parts[1]) {
 119         return a->parts[1] > b->parts[1] ? 1 : -1;
 120     } else if (a->parts[2] != b->parts[2]) {
 121         return a->parts[2] > b->parts[2] ? 1 : -1;
 122     } else if (a->parts[3] != b->parts[3]) {
 123         return a->parts[3] > b->parts[3] ? 1 : -1;
 124     } else {
 125         return 0;
 126     }
 127 }
 128
 129 /* Attempts to convert string 's' into a UUID in 'uuid'.  Returns true if
 130  * successful, which will be the case only if 's' has the exact format
 131  * specified by RFC 4122.  Returns false on failure.  On failure, 'uuid' will
 132  * be set to all-zero-bits. */
 133 bool
 134 uuid_from_string(struct uuid *uuid, const char *s)
 135 {
 136     static const char template[] = "00000000-1111-1111-2222-222233333333";
 137     const char *t;
 138
 139     uuid_zero(uuid);
 140     for (t = template; ; t++, s++) {
 141         if (*t >= '0' && *t <= '3') {
 142             uint32_t *part = &uuid->parts[*t - '0'];
 143             if (!isxdigit(*s)) {
 144                 goto error;
 145             }
 146             *part = (*part << 4) + hexit_value(*s);
 147         } else if (*t != *s) {
 148             goto error;
 149         } else if (*t == 0) {
 150             return true;
 151         }
 152     }
 153
 154 error:
 155     uuid_zero(uuid);
 156     return false;
 157 }
 158 \f
 159 static void
 160 read_urandom(void *buffer, size_t n)
 161 {
 162     static const char urandom[] = "/dev/urandom";
 163     size_t bytes_read;
 164     int error;
 165     int fd;
 166
 167     fd = open(urandom, O_RDONLY);
 168     if (fd < 0) {
 169         ovs_fatal(errno, "%s: open failed", urandom);
 170     }
 171     error = read_fully(fd, buffer, n, &bytes_read);
 172     if (error == EOF) {
 173         ovs_fatal(0, "%s: unexpected end of file", urandom);
 174     } else if (error) {
 175         ovs_fatal(error, "%s: read error", urandom);
 176     }
 177     close(fd);
 178 }
 179
 180 static void
 181 do_init(void)
 182 {
 183     uint8_t sha1[SHA1_DIGEST_SIZE];
 184     struct sha1_ctx sha1_ctx;
 185     uint8_t random_seed[16];
 186     struct timeval now;
 187     pid_t pid, ppid;
 188     uid_t uid;
 189     gid_t gid;
 190
 191     /* Get seed data. */
 192     read_urandom(random_seed, sizeof random_seed);
 193     if (gettimeofday(&now, NULL)) {
 194         ovs_fatal(errno, "gettimeofday failed");
 195     }
 196     pid = getpid();
 197     ppid = getppid();
 198     uid = getuid();
 199     gid = getgid();
 200
 201     /* Convert seed into key. */
 202     sha1_init(&sha1_ctx);
 203     sha1_update(&sha1_ctx, random_seed, sizeof random_seed);
 204     sha1_update(&sha1_ctx, &pid, sizeof pid);
 205     sha1_update(&sha1_ctx, &ppid, sizeof ppid);
 206     sha1_update(&sha1_ctx, &uid, sizeof uid);
 207     sha1_update(&sha1_ctx, &gid, sizeof gid);
 208     sha1_final(&sha1_ctx, sha1);
 209
 210     /* Generate key. */
 211     BUILD_ASSERT(sizeof sha1 >= 16);
 212     aes128_schedule(&key, sha1);
 213
 214     /* Generate initial counter. */
 215     read_urandom(counter, sizeof counter);
 216 }