Branch data Line data Source code
1 : : /* Copyright (c) 2008, 2009, 2010, 2011, 2013 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 : 78008 : uuid_init(void)
52 : : {
53 : : static pthread_once_t once = PTHREAD_ONCE_INIT;
54 : 78008 : pthread_once(&once, do_init);
55 : 78008 : }
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 : 78008 : uuid_generate(struct uuid *uuid)
83 : : {
84 : : static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
85 : : uint64_t copy[2];
86 : :
87 : 78008 : uuid_init();
88 : :
89 : : /* Copy out the counter's current value, then increment it. */
90 : 78008 : ovs_mutex_lock(&mutex);
91 : 78008 : copy[0] = counter[0];
92 : 78008 : copy[1] = counter[1];
93 [ - + ]: 78008 : if (++counter[1] == 0) {
94 : 0 : counter[0]++;
95 : : }
96 : 78008 : ovs_mutex_unlock(&mutex);
97 : :
98 : : /* AES output is exactly 16 bytes, so we encrypt directly into 'uuid'. */
99 : 78008 : aes128_encrypt(&key, copy, uuid);
100 : :
101 : 78008 : uuid_set_bits_v4(uuid);
102 : 78008 : }
103 : :
104 : : void
105 : 99843 : uuid_set_bits_v4(struct uuid *uuid)
106 : : {
107 : : /* Set bits to indicate a random UUID. See RFC 4122 section 4.4. */
108 : 99843 : uuid->parts[2] &= ~0xc0000000;
109 : 99843 : uuid->parts[2] |= 0x80000000;
110 : 99843 : uuid->parts[1] &= ~0x0000f000;
111 : 99843 : uuid->parts[1] |= 0x00004000;
112 : 99843 : }
113 : :
114 : : /* Sets 'uuid' to all-zero-bits. */
115 : : void
116 : 349671 : uuid_zero(struct uuid *uuid)
117 : : {
118 : 349671 : uuid->parts[0] = uuid->parts[1] = uuid->parts[2] = uuid->parts[3] = 0;
119 : 349671 : }
120 : :
121 : : /* Returns true if 'uuid' is all zero, otherwise false. */
122 : : bool
123 : 69471 : uuid_is_zero(const struct uuid *uuid)
124 : : {
125 [ + - ]: 71426 : return (!uuid->parts[0] && !uuid->parts[1]
126 [ + + ][ + - ]: 71426 : && !uuid->parts[2] && !uuid->parts[3]);
[ + - ]
127 : : }
128 : :
129 : : /* Compares 'a' and 'b'. Returns a negative value if 'a < b', zero if 'a ==
130 : : * b', or positive if 'a > b'. The ordering is lexicographical order of the
131 : : * conventional way of writing out UUIDs as strings. */
132 : : int
133 : 2473489 : uuid_compare_3way(const struct uuid *a, const struct uuid *b)
134 : : {
135 [ + + ]: 2473489 : if (a->parts[0] != b->parts[0]) {
136 [ + + ]: 2211990 : return a->parts[0] > b->parts[0] ? 1 : -1;
137 [ + + ]: 261499 : } else if (a->parts[1] != b->parts[1]) {
138 [ + + ]: 80 : return a->parts[1] > b->parts[1] ? 1 : -1;
139 [ + + ]: 261419 : } else if (a->parts[2] != b->parts[2]) {
140 [ + + ]: 26 : return a->parts[2] > b->parts[2] ? 1 : -1;
141 [ + + ]: 261393 : } else if (a->parts[3] != b->parts[3]) {
142 [ + + ]: 51 : return a->parts[3] > b->parts[3] ? 1 : -1;
143 : : } else {
144 : 261342 : return 0;
145 : : }
146 : : }
147 : :
148 : : /* Attempts to convert string 's' into a UUID in 'uuid'. Returns true if
149 : : * successful, which will be the case only if 's' has the exact format
150 : : * specified by RFC 4122. Returns false on failure. On failure, 'uuid' will
151 : : * be set to all-zero-bits. */
152 : : bool
153 : 881770 : uuid_from_string(struct uuid *uuid, const char *s)
154 : : {
155 [ + + ]: 881770 : if (!uuid_from_string_prefix(uuid, s)) {
156 : 118813 : return false;
157 [ - + ]: 762957 : } else if (s[UUID_LEN] != '\0') {
158 : 0 : uuid_zero(uuid);
159 : 0 : return false;
160 : : } else {
161 : 762957 : return true;
162 : : }
163 : : }
164 : :
165 : : /* Same as uuid_from_string() but s[UUID_LEN] is not required to be a null byte
166 : : * to succeed; that is, 's' need only begin with UUID syntax, not consist
167 : : * entirely of it. */
168 : : bool
169 : 881774 : uuid_from_string_prefix(struct uuid *uuid, const char *s)
170 : : {
171 : : /* 0 1 2 3 */
172 : : /* 012345678901234567890123456789012345 */
173 : : /* ------------------------------------ */
174 : : /* 00000000-1111-1111-2222-222233333333 */
175 : :
176 : : bool ok;
177 : :
178 : 881774 : uuid->parts[0] = hexits_value(s, 8, &ok);
179 [ + + ][ + - ]: 881774 : if (!ok || s[8] != '-') {
180 : : goto error;
181 : : }
182 : :
183 : 762961 : uuid->parts[1] = hexits_value(s + 9, 4, &ok) << 16;
184 [ + - ][ + - ]: 762961 : if (!ok || s[13] != '-') {
185 : : goto error;
186 : : }
187 : :
188 : 762961 : uuid->parts[1] += hexits_value(s + 14, 4, &ok);
189 [ + - ][ + - ]: 762961 : if (!ok || s[18] != '-') {
190 : : goto error;
191 : : }
192 : :
193 : 762961 : uuid->parts[2] = hexits_value(s + 19, 4, &ok) << 16;
194 [ + - ][ + - ]: 762961 : if (!ok || s[23] != '-') {
195 : : goto error;
196 : : }
197 : :
198 : 762961 : uuid->parts[2] += hexits_value(s + 24, 4, &ok);
199 [ - + ]: 762961 : if (!ok) {
200 : 0 : goto error;
201 : : }
202 : :
203 : 762961 : uuid->parts[3] = hexits_value(s + 28, 8, &ok);
204 [ - + ]: 762961 : if (!ok) {
205 : 0 : goto error;
206 : : }
207 : 762961 : return true;
208 : :
209 : : error:
210 : 118813 : uuid_zero(uuid);
211 : 881774 : return false;
212 : : }
213 : :
214 : : static void
215 : 34760 : sha1_update_int(struct sha1_ctx *sha1_ctx, uintmax_t x)
216 : : {
217 : 34760 : sha1_update(sha1_ctx, &x, sizeof x);
218 : 34760 : }
219 : :
220 : : static void
221 : 8690 : do_init(void)
222 : : {
223 : : uint8_t sha1[SHA1_DIGEST_SIZE];
224 : : struct sha1_ctx sha1_ctx;
225 : : uint8_t random_seed[16];
226 : : struct timeval now;
227 : :
228 : : /* Get seed data. */
229 : 8690 : get_entropy_or_die(random_seed, sizeof random_seed);
230 : 8690 : xgettimeofday(&now);
231 : :
232 : : /* Convert seed into key. */
233 : 8690 : sha1_init(&sha1_ctx);
234 : 8690 : sha1_update(&sha1_ctx, random_seed, sizeof random_seed);
235 : 8690 : sha1_update(&sha1_ctx, &now, sizeof now);
236 : 8690 : sha1_update_int(&sha1_ctx, getpid());
237 : : #ifndef _WIN32
238 : 8690 : sha1_update_int(&sha1_ctx, getppid());
239 : 8690 : sha1_update_int(&sha1_ctx, getuid());
240 : 8690 : sha1_update_int(&sha1_ctx, getgid());
241 : : #endif
242 : 8690 : sha1_final(&sha1_ctx, sha1);
243 : :
244 : : /* Generate key. */
245 : : BUILD_ASSERT(sizeof sha1 >= 16);
246 : 8690 : aes128_schedule(&key, sha1);
247 : :
248 : : /* Generate initial counter. */
249 : 8690 : get_entropy_or_die(counter, sizeof counter);
250 : 8690 : }
|
