xref: /openssl/ssl/quic/quic_srtm.c (revision b6461792)
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