1 /*
2 * Copyright 2023-2024 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include "internal/quic_srtm.h"
11 #include "internal/common.h"
12 #include <openssl/lhash.h>
13 #include <openssl/core_names.h>
14 #include <openssl/rand.h>
15
16 /*
17 * QUIC Stateless Reset Token Manager
18 * ==================================
19 */
20 typedef struct srtm_item_st SRTM_ITEM;
21
22 #define BLINDED_SRT_LEN 16
23
24 DEFINE_LHASH_OF_EX(SRTM_ITEM);
25
26 /*
27 * The SRTM is implemented using two LHASH instances, one matching opaque pointers to
28 * an item structure, and another matching a SRT-derived value to an item
29 * structure. Multiple items with different seq_num values under a given opaque,
30 * and duplicate SRTs, are handled using sorted singly-linked lists.
31 *
32 * The O(n) insert and lookup performance is tolerated on the basis that the
33 * total number of entries for a given opaque (total number of extant CIDs for a
34 * connection) should be quite small, and the QUIC protocol allows us to place a
35 * hard limit on this via the active_connection_id_limit TPARAM. Thus there is
36 * no risk of a large number of SRTs needing to be registered under a given
37 * opaque.
38 *
39 * It is expected one SRTM will exist per QUIC_PORT and track all SRTs across
40 * all connections for that QUIC_PORT.
41 */
42 struct srtm_item_st {
43 SRTM_ITEM *next_by_srt_blinded; /* SORT BY opaque DESC */
44 SRTM_ITEM *next_by_seq_num; /* SORT BY seq_num DESC */
45 void *opaque; /* \__ unique identity for item */
46 uint64_t seq_num; /* / */
47 QUIC_STATELESS_RESET_TOKEN srt;
48 unsigned char srt_blinded[BLINDED_SRT_LEN]; /* H(srt) */
49
50 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
51 uint32_t debug_token;
52 #endif
53 };
54
55 struct quic_srtm_st {
56 /* Crypto context used to calculate blinded SRTs H(srt). */
57 EVP_CIPHER_CTX *blind_ctx; /* kept with key */
58
59 LHASH_OF(SRTM_ITEM) *items_fwd; /* (opaque) -> SRTM_ITEM */
60 LHASH_OF(SRTM_ITEM) *items_rev; /* (H(srt)) -> SRTM_ITEM */
61
62 /*
63 * Monotonically transitions to 1 in event of allocation failure. The only
64 * valid operation on such an object is to free it.
65 */
66 unsigned int alloc_failed : 1;
67 };
68
items_fwd_hash(const SRTM_ITEM * item)69 static unsigned long items_fwd_hash(const SRTM_ITEM *item)
70 {
71 return (unsigned long)(uintptr_t)item->opaque;
72 }
73
items_fwd_cmp(const SRTM_ITEM * a,const SRTM_ITEM * b)74 static int items_fwd_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b)
75 {
76 return a->opaque != b->opaque;
77 }
78
items_rev_hash(const SRTM_ITEM * item)79 static unsigned long items_rev_hash(const SRTM_ITEM *item)
80 {
81 /*
82 * srt_blinded has already been through a crypto-grade hash function, so we
83 * can just use bits from that.
84 */
85 unsigned long l;
86
87 memcpy(&l, item->srt_blinded, sizeof(l));
88 return l;
89 }
90
items_rev_cmp(const SRTM_ITEM * a,const SRTM_ITEM * b)91 static int items_rev_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b)
92 {
93 /*
94 * We don't need to use CRYPTO_memcmp here as the relationship of
95 * srt_blinded to srt is already cryptographically obfuscated.
96 */
97 return memcmp(a->srt_blinded, b->srt_blinded, sizeof(a->srt_blinded));
98 }
99
srtm_check_lh(QUIC_SRTM * srtm,LHASH_OF (SRTM_ITEM)* lh)100 static int srtm_check_lh(QUIC_SRTM *srtm, LHASH_OF(SRTM_ITEM) *lh)
101 {
102 if (lh_SRTM_ITEM_error(lh)) {
103 srtm->alloc_failed = 1;
104 return 0;
105 }
106
107 return 1;
108 }
109
ossl_quic_srtm_new(OSSL_LIB_CTX * libctx,const char * propq)110 QUIC_SRTM *ossl_quic_srtm_new(OSSL_LIB_CTX *libctx, const char *propq)
111 {
112 QUIC_SRTM *srtm = NULL;
113 unsigned char key[16];
114 EVP_CIPHER *ecb = NULL;
115
116 if (RAND_priv_bytes_ex(libctx, key, sizeof(key), sizeof(key) * 8) != 1)
117 goto err;
118
119 if ((srtm = OPENSSL_zalloc(sizeof(*srtm))) == NULL)
120 return NULL;
121
122 /* Use AES-128-ECB as a permutation over 128-bit SRTs. */
123 if ((ecb = EVP_CIPHER_fetch(libctx, "AES-128-ECB", propq)) == NULL)
124 goto err;
125
126 if ((srtm->blind_ctx = EVP_CIPHER_CTX_new()) == NULL)
127 goto err;
128
129 if (!EVP_EncryptInit_ex2(srtm->blind_ctx, ecb, key, NULL, NULL))
130 goto err;
131
132 EVP_CIPHER_free(ecb);
133 ecb = NULL;
134
135 /* Create mappings. */
136 if ((srtm->items_fwd = lh_SRTM_ITEM_new(items_fwd_hash, items_fwd_cmp)) == NULL
137 || (srtm->items_rev = lh_SRTM_ITEM_new(items_rev_hash, items_rev_cmp)) == NULL)
138 goto err;
139
140 return srtm;
141
142 err:
143 /*
144 * No cleansing of key needed as blinding exists only for side channel
145 * mitigation.
146 */
147 ossl_quic_srtm_free(srtm);
148 EVP_CIPHER_free(ecb);
149 return NULL;
150 }
151
srtm_free_each(SRTM_ITEM * ihead)152 static void srtm_free_each(SRTM_ITEM *ihead)
153 {
154 SRTM_ITEM *inext, *item = ihead;
155
156 for (item = item->next_by_seq_num; item != NULL; item = inext) {
157 inext = item->next_by_seq_num;
158 OPENSSL_free(item);
159 }
160
161 OPENSSL_free(ihead);
162 }
163
ossl_quic_srtm_free(QUIC_SRTM * srtm)164 void ossl_quic_srtm_free(QUIC_SRTM *srtm)
165 {
166 if (srtm == NULL)
167 return;
168
169 lh_SRTM_ITEM_free(srtm->items_rev);
170 if (srtm->items_fwd != NULL) {
171 lh_SRTM_ITEM_doall(srtm->items_fwd, srtm_free_each);
172 lh_SRTM_ITEM_free(srtm->items_fwd);
173 }
174
175 EVP_CIPHER_CTX_free(srtm->blind_ctx);
176 OPENSSL_free(srtm);
177 }
178
179 /*
180 * Find a SRTM_ITEM by (opaque, seq_num). Returns NULL if no match.
181 * If head is non-NULL, writes the head of the relevant opaque list to *head if
182 * there is one.
183 * If prev is non-NULL, writes the previous node to *prev or NULL if it is
184 * the first item.
185 */
srtm_find(QUIC_SRTM * srtm,void * opaque,uint64_t seq_num,SRTM_ITEM ** head_p,SRTM_ITEM ** prev_p)186 static SRTM_ITEM *srtm_find(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num,
187 SRTM_ITEM **head_p, SRTM_ITEM **prev_p)
188 {
189 SRTM_ITEM key, *item = NULL, *prev = NULL;
190
191 key.opaque = opaque;
192
193 item = lh_SRTM_ITEM_retrieve(srtm->items_fwd, &key);
194 if (head_p != NULL)
195 *head_p = item;
196
197 for (; item != NULL; prev = item, item = item->next_by_seq_num)
198 if (item->seq_num == seq_num) {
199 break;
200 } else if (item->seq_num < seq_num) {
201 /*
202 * List is sorted in descending order so there can't be any match
203 * after this.
204 */
205 item = NULL;
206 break;
207 }
208
209 if (prev_p != NULL)
210 *prev_p = prev;
211
212 return item;
213 }
214
215 /*
216 * Inserts a SRTM_ITEM into the singly-linked by-sequence-number linked list.
217 * The new head pointer is written to *new_head (which may or may not be
218 * unchanged).
219 */
sorted_insert_seq_num(SRTM_ITEM * head,SRTM_ITEM * item,SRTM_ITEM ** new_head)220 static void sorted_insert_seq_num(SRTM_ITEM *head, SRTM_ITEM *item, SRTM_ITEM **new_head)
221 {
222 uint64_t seq_num = item->seq_num;
223 SRTM_ITEM *cur = head, **fixup = new_head;
224
225 *new_head = head;
226
227 while (cur != NULL && cur->seq_num > seq_num) {
228 fixup = &cur->next_by_seq_num;
229 cur = cur->next_by_seq_num;
230 }
231
232 item->next_by_seq_num = *fixup;
233 *fixup = item;
234 }
235
236 /*
237 * Inserts a SRTM_ITEM into the singly-linked by-SRT list.
238 * The new head pointer is written to *new_head (which may or may not be
239 * unchanged).
240 */
sorted_insert_srt(SRTM_ITEM * head,SRTM_ITEM * item,SRTM_ITEM ** new_head)241 static void sorted_insert_srt(SRTM_ITEM *head, SRTM_ITEM *item, SRTM_ITEM **new_head)
242 {
243 uintptr_t opaque = (uintptr_t)item->opaque;
244 SRTM_ITEM *cur = head, **fixup = new_head;
245
246 *new_head = head;
247
248 while (cur != NULL && (uintptr_t)cur->opaque > opaque) {
249 fixup = &cur->next_by_srt_blinded;
250 cur = cur->next_by_srt_blinded;
251 }
252
253 item->next_by_srt_blinded = *fixup;
254 *fixup = item;
255 }
256
257 /*
258 * Computes the blinded SRT value used for internal lookup for side channel
259 * mitigation purposes. We compute this once as a cached value when an SRTM_ITEM
260 * is formed.
261 */
srtm_compute_blinded(QUIC_SRTM * srtm,SRTM_ITEM * item,const QUIC_STATELESS_RESET_TOKEN * token)262 static int srtm_compute_blinded(QUIC_SRTM *srtm, SRTM_ITEM *item,
263 const QUIC_STATELESS_RESET_TOKEN *token)
264 {
265 int outl = 0;
266
267 /*
268 * We use AES-128-ECB as a permutation using a random key to facilitate
269 * blinding for side-channel purposes. Encrypt the token as a single AES
270 * block.
271 */
272 if (!EVP_EncryptUpdate(srtm->blind_ctx, item->srt_blinded, &outl,
273 (const unsigned char *)token, sizeof(*token)))
274 return 0;
275
276 if (!ossl_assert(outl == sizeof(*token)))
277 return 0;
278
279 return 1;
280 }
281
ossl_quic_srtm_add(QUIC_SRTM * srtm,void * opaque,uint64_t seq_num,const QUIC_STATELESS_RESET_TOKEN * token)282 int ossl_quic_srtm_add(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num,
283 const QUIC_STATELESS_RESET_TOKEN *token)
284 {
285 SRTM_ITEM *item = NULL, *head = NULL, *new_head, *r_item;
286
287 if (srtm->alloc_failed)
288 return 0;
289
290 /* (opaque, seq_num) duplicates not allowed */
291 if ((item = srtm_find(srtm, opaque, seq_num, &head, NULL)) != NULL)
292 return 0;
293
294 if ((item = OPENSSL_zalloc(sizeof(*item))) == NULL)
295 return 0;
296
297 item->opaque = opaque;
298 item->seq_num = seq_num;
299 item->srt = *token;
300 if (!srtm_compute_blinded(srtm, item, &item->srt)) {
301 OPENSSL_free(item);
302 return 0;
303 }
304
305 /* Add to forward mapping. */
306 if (head == NULL) {
307 /* First item under this opaque */
308 lh_SRTM_ITEM_insert(srtm->items_fwd, item);
309 if (!srtm_check_lh(srtm, srtm->items_fwd)) {
310 OPENSSL_free(item);
311 return 0;
312 }
313 } else {
314 sorted_insert_seq_num(head, item, &new_head);
315 if (new_head != head) { /* head changed, update in lhash */
316 lh_SRTM_ITEM_insert(srtm->items_fwd, new_head);
317 if (!srtm_check_lh(srtm, srtm->items_fwd)) {
318 OPENSSL_free(item);
319 return 0;
320 }
321 }
322 }
323
324 /* Add to reverse mapping. */
325 r_item = lh_SRTM_ITEM_retrieve(srtm->items_rev, item);
326 if (r_item == NULL) {
327 /* First item under this blinded SRT */
328 lh_SRTM_ITEM_insert(srtm->items_rev, item);
329 if (!srtm_check_lh(srtm, srtm->items_rev))
330 /*
331 * Can't free the item now as we would have to undo the insertion
332 * into the forward mapping which would require an insert operation
333 * to restore the previous value. which might also fail. However,
334 * the item will be freed OK when we free the entire SRTM.
335 */
336 return 0;
337 } else {
338 sorted_insert_srt(r_item, item, &new_head);
339 if (new_head != r_item) { /* head changed, update in lhash */
340 lh_SRTM_ITEM_insert(srtm->items_rev, new_head);
341 if (!srtm_check_lh(srtm, srtm->items_rev))
342 /* As above. */
343 return 0;
344 }
345 }
346
347 return 1;
348 }
349
350 /* Remove item from reverse mapping. */
srtm_remove_from_rev(QUIC_SRTM * srtm,SRTM_ITEM * item)351 static int srtm_remove_from_rev(QUIC_SRTM *srtm, SRTM_ITEM *item)
352 {
353 SRTM_ITEM *rh_item;
354
355 rh_item = lh_SRTM_ITEM_retrieve(srtm->items_rev, item);
356 assert(rh_item != NULL);
357 if (rh_item == item) {
358 /*
359 * Change lhash to point to item after this one, or remove the entry if
360 * this is the last one.
361 */
362 if (item->next_by_srt_blinded != NULL) {
363 lh_SRTM_ITEM_insert(srtm->items_rev, item->next_by_srt_blinded);
364 if (!srtm_check_lh(srtm, srtm->items_rev))
365 return 0;
366 } else {
367 lh_SRTM_ITEM_delete(srtm->items_rev, item);
368 }
369 } else {
370 /* Find our entry in the SRT list */
371 for (; rh_item->next_by_srt_blinded != item;
372 rh_item = rh_item->next_by_srt_blinded);
373 rh_item->next_by_srt_blinded = item->next_by_srt_blinded;
374 }
375
376 return 1;
377 }
378
ossl_quic_srtm_remove(QUIC_SRTM * srtm,void * opaque,uint64_t seq_num)379 int ossl_quic_srtm_remove(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num)
380 {
381 SRTM_ITEM *item, *prev = NULL;
382
383 if (srtm->alloc_failed)
384 return 0;
385
386 if ((item = srtm_find(srtm, opaque, seq_num, NULL, &prev)) == NULL)
387 /* No match */
388 return 0;
389
390 /* Remove from forward mapping. */
391 if (prev == NULL) {
392 /*
393 * Change lhash to point to item after this one, or remove the entry if
394 * this is the last one.
395 */
396 if (item->next_by_seq_num != NULL) {
397 lh_SRTM_ITEM_insert(srtm->items_fwd, item->next_by_seq_num);
398 if (!srtm_check_lh(srtm, srtm->items_fwd))
399 return 0;
400 } else {
401 lh_SRTM_ITEM_delete(srtm->items_fwd, item);
402 }
403 } else {
404 prev->next_by_seq_num = item->next_by_seq_num;
405 }
406
407 /* Remove from reverse mapping. */
408 if (!srtm_remove_from_rev(srtm, item))
409 return 0;
410
411 OPENSSL_free(item);
412 return 1;
413 }
414
ossl_quic_srtm_cull(QUIC_SRTM * srtm,void * opaque)415 int ossl_quic_srtm_cull(QUIC_SRTM *srtm, void *opaque)
416 {
417 SRTM_ITEM key, *item = NULL, *inext, *ihead;
418
419 key.opaque = opaque;
420
421 if (srtm->alloc_failed)
422 return 0;
423
424 if ((ihead = lh_SRTM_ITEM_retrieve(srtm->items_fwd, &key)) == NULL)
425 return 1; /* nothing removed is a success condition */
426
427 for (item = ihead; item != NULL; item = inext) {
428 inext = item->next_by_seq_num;
429 if (item != ihead) {
430 srtm_remove_from_rev(srtm, item);
431 OPENSSL_free(item);
432 }
433 }
434
435 lh_SRTM_ITEM_delete(srtm->items_fwd, ihead);
436 srtm_remove_from_rev(srtm, ihead);
437 OPENSSL_free(ihead);
438 return 1;
439 }
440
ossl_quic_srtm_lookup(QUIC_SRTM * srtm,const QUIC_STATELESS_RESET_TOKEN * token,size_t idx,void ** opaque,uint64_t * seq_num)441 int ossl_quic_srtm_lookup(QUIC_SRTM *srtm,
442 const QUIC_STATELESS_RESET_TOKEN *token,
443 size_t idx,
444 void **opaque, uint64_t *seq_num)
445 {
446 SRTM_ITEM key, *item;
447
448 if (srtm->alloc_failed)
449 return 0;
450
451 if (!srtm_compute_blinded(srtm, &key, token))
452 return 0;
453
454 item = lh_SRTM_ITEM_retrieve(srtm->items_rev, &key);
455 for (; idx > 0 && item != NULL; --idx, item = item->next_by_srt_blinded);
456 if (item == NULL)
457 return 0;
458
459 if (opaque != NULL)
460 *opaque = item->opaque;
461 if (seq_num != NULL)
462 *seq_num = item->seq_num;
463
464 return 1;
465 }
466
467 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
468
469 static uint32_t token_next = 0x5eadbeef;
470 static size_t tokens_seen;
471
472 struct check_args {
473 uint32_t token;
474 int mode;
475 };
476
check_mark(SRTM_ITEM * item,void * arg)477 static void check_mark(SRTM_ITEM *item, void *arg)
478 {
479 struct check_args *arg_ = arg;
480 uint32_t token = arg_->token;
481 uint64_t prev_seq_num = 0;
482 void *prev_opaque = NULL;
483 int have_prev = 0;
484
485 assert(item != NULL);
486
487 while (item != NULL) {
488 if (have_prev) {
489 assert(!(item->opaque == prev_opaque && item->seq_num == prev_seq_num));
490 if (!arg_->mode)
491 assert(item->opaque != prev_opaque || item->seq_num < prev_seq_num);
492 }
493
494 ++tokens_seen;
495 item->debug_token = token;
496 prev_opaque = item->opaque;
497 prev_seq_num = item->seq_num;
498 have_prev = 1;
499
500 if (arg_->mode)
501 item = item->next_by_srt_blinded;
502 else
503 item = item->next_by_seq_num;
504 }
505 }
506
check_count(SRTM_ITEM * item,void * arg)507 static void check_count(SRTM_ITEM *item, void *arg)
508 {
509 struct check_args *arg_ = arg;
510 uint32_t token = arg_->token;
511
512 assert(item != NULL);
513
514 while (item != NULL) {
515 ++tokens_seen;
516 assert(item->debug_token == token);
517
518 if (arg_->mode)
519 item = item->next_by_seq_num;
520 else
521 item = item->next_by_srt_blinded;
522 }
523 }
524
525 #endif
526
ossl_quic_srtm_check(const QUIC_SRTM * srtm)527 void ossl_quic_srtm_check(const QUIC_SRTM *srtm)
528 {
529 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
530 struct check_args args = {0};
531 size_t tokens_expected, tokens_expected_old;
532
533 args.token = token_next;
534 ++token_next;
535
536 assert(srtm != NULL);
537 assert(srtm->blind_ctx != NULL);
538 assert(srtm->items_fwd != NULL);
539 assert(srtm->items_rev != NULL);
540
541 tokens_seen = 0;
542 lh_SRTM_ITEM_doall_arg(srtm->items_fwd, check_mark, &args);
543
544 tokens_expected = tokens_seen;
545 tokens_seen = 0;
546 lh_SRTM_ITEM_doall_arg(srtm->items_rev, check_count, &args);
547
548 assert(tokens_seen == tokens_expected);
549 tokens_expected_old = tokens_expected;
550
551 args.token = token_next;
552 ++token_next;
553
554 args.mode = 1;
555 tokens_seen = 0;
556 lh_SRTM_ITEM_doall_arg(srtm->items_rev, check_mark, &args);
557
558 tokens_expected = tokens_seen;
559 tokens_seen = 0;
560 lh_SRTM_ITEM_doall_arg(srtm->items_fwd, check_count, &args);
561
562 assert(tokens_seen == tokens_expected);
563 assert(tokens_seen == tokens_expected_old);
564 #endif
565 }
566
