1 /* Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
24 #include <sys/types.h>
33 static struct aes128 key;
34 static uint64_t counter[2];
35 BUILD_ASSERT_DECL(sizeof counter == 16);
37 static void do_init(void);
40 * Initialize the UUID module. Aborts the program with an error message if
41 * initialization fails (which should never happen on a properly configured
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.
59 /* Generates a new random UUID in 'uuid'.
61 * We go to some trouble to ensure as best we can that the generated UUID has
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
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.
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.
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.
84 uuid_generate(struct uuid *uuid)
88 /* Increment the counter. */
89 if (++counter[1] == 0) {
93 /* AES output is exactly 16 bytes, so we encrypt directly into 'uuid'. */
94 aes128_encrypt(&key, counter, uuid);
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;
103 /* Sets 'uuid' to all-zero-bits. */
105 uuid_zero(struct uuid *uuid)
107 uuid->parts[0] = uuid->parts[1] = uuid->parts[2] = uuid->parts[3] = 0;
110 /* Returns true if 'uuid' is all zero, otherwise false. */
112 uuid_is_zero(const struct uuid *uuid)
114 return (!uuid->parts[0] && !uuid->parts[1]
115 && !uuid->parts[2] && !uuid->parts[3]);
118 /* Compares 'a' and 'b'. Returns a negative value if 'a < b', zero if 'a ==
119 * b', or positive if 'a > b'. The ordering is lexicographical order of the
120 * conventional way of writing out UUIDs as strings. */
122 uuid_compare_3way(const struct uuid *a, const struct uuid *b)
124 if (a->parts[0] != b->parts[0]) {
125 return a->parts[0] > b->parts[0] ? 1 : -1;
126 } else if (a->parts[1] != b->parts[1]) {
127 return a->parts[1] > b->parts[1] ? 1 : -1;
128 } else if (a->parts[2] != b->parts[2]) {
129 return a->parts[2] > b->parts[2] ? 1 : -1;
130 } else if (a->parts[3] != b->parts[3]) {
131 return a->parts[3] > b->parts[3] ? 1 : -1;
137 /* Attempts to convert string 's' into a UUID in 'uuid'. Returns true if
138 * successful, which will be the case only if 's' has the exact format
139 * specified by RFC 4122. Returns false on failure. On failure, 'uuid' will
140 * be set to all-zero-bits. */
142 uuid_from_string(struct uuid *uuid, const char *s)
144 if (!uuid_from_string_prefix(uuid, s)) {
146 } else if (s[UUID_LEN] != '\0') {
154 /* Same as uuid_from_string() but s[UUID_LEN] is not required to be a null byte
155 * to succeed; that is, 's' need only begin with UUID syntax, not consist
158 uuid_from_string_prefix(struct uuid *uuid, const char *s)
161 /* 012345678901234567890123456789012345 */
162 /* ------------------------------------ */
163 /* 00000000-1111-1111-2222-222233333333 */
167 uuid->parts[0] = hexits_value(s, 8, &ok);
168 if (!ok || s[8] != '-') {
172 uuid->parts[1] = hexits_value(s + 9, 4, &ok) << 16;
173 if (!ok || s[13] != '-') {
177 uuid->parts[1] += hexits_value(s + 14, 4, &ok);
178 if (!ok || s[18] != '-') {
182 uuid->parts[2] = hexits_value(s + 19, 4, &ok) << 16;
183 if (!ok || s[23] != '-') {
187 uuid->parts[2] += hexits_value(s + 24, 4, &ok);
192 uuid->parts[3] = hexits_value(s + 28, 8, &ok);
206 uint8_t sha1[SHA1_DIGEST_SIZE];
207 struct sha1_ctx sha1_ctx;
208 uint8_t random_seed[16];
215 get_entropy_or_die(random_seed, sizeof random_seed);
222 /* Convert seed into key. */
223 sha1_init(&sha1_ctx);
224 sha1_update(&sha1_ctx, random_seed, sizeof random_seed);
225 sha1_update(&sha1_ctx, &pid, sizeof pid);
226 sha1_update(&sha1_ctx, &ppid, sizeof ppid);
227 sha1_update(&sha1_ctx, &uid, sizeof uid);
228 sha1_update(&sha1_ctx, &gid, sizeof gid);
229 sha1_final(&sha1_ctx, sha1);
232 BUILD_ASSERT(sizeof sha1 >= 16);
233 aes128_schedule(&key, sha1);
235 /* Generate initial counter. */
236 get_entropy_or_die(counter, sizeof counter);