ssl/quic/quic_srtm.c

   1 /*
   2  * Copyright 2023 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
  69 static unsigned long items_fwd_hash(const SRTM_ITEM *item)
  70 {
  71     return (unsigned long)(uintptr_t)item->opaque;
  72 }
  73
  74 static int items_fwd_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b)
  75 {
  76     return a->opaque != b->opaque;
  77 }
  78
  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
  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
 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
 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
 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
 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  */
 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  */
 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  */
 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  */
 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
 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. */
 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
 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
 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
 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
 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
 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
 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 }