1 /* 2 * Copyright 2023-2025 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_lcidm.h" 11 #include "internal/quic_types.h" 12 #include "internal/quic_vlint.h" 13 #include "internal/common.h" 14 #include "crypto/siphash.h" 15 #include <openssl/lhash.h> 16 #include <openssl/rand.h> 17 #include <openssl/err.h> 18 19 /* 20 * QUIC Local Connection ID Manager 21 * ================================ 22 */ 23 24 typedef struct quic_lcidm_conn_st QUIC_LCIDM_CONN; 25 26 enum { 27 LCID_TYPE_ODCID, /* This LCID is the ODCID from the peer */ 28 LCID_TYPE_INITIAL, /* This is our Initial SCID */ 29 LCID_TYPE_NCID /* This LCID was issued via a NCID frame */ 30 }; 31 32 typedef struct quic_lcid_st { 33 QUIC_CONN_ID cid; 34 uint64_t seq_num; 35 36 /* copy of the hash key from lcidm */ 37 uint64_t *hash_key; 38 39 /* Back-pointer to the owning QUIC_LCIDM_CONN structure. */ 40 QUIC_LCIDM_CONN *conn; 41 42 /* LCID_TYPE_* */ 43 unsigned int type : 2; 44 } QUIC_LCID; 45 46 DEFINE_LHASH_OF_EX(QUIC_LCID); 47 DEFINE_LHASH_OF_EX(QUIC_LCIDM_CONN); 48 49 struct quic_lcidm_conn_st { 50 size_t num_active_lcid; 51 LHASH_OF(QUIC_LCID) *lcids; 52 void *opaque; 53 QUIC_LCID *odcid_lcid_obj; 54 uint64_t next_seq_num; 55 56 /* Have we enrolled an ODCID? */ 57 unsigned int done_odcid : 1; 58 }; 59 60 struct quic_lcidm_st { 61 OSSL_LIB_CTX *libctx; 62 uint64_t hash_key[2]; /* random key for siphash */ 63 LHASH_OF(QUIC_LCID) *lcids; /* (QUIC_CONN_ID) -> (QUIC_LCID *) */ 64 LHASH_OF(QUIC_LCIDM_CONN) *conns; /* (void *opaque) -> (QUIC_LCIDM_CONN *) */ 65 size_t lcid_len; /* Length in bytes for all LCIDs */ 66 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 67 QUIC_CONN_ID next_lcid; 68 #endif 69 }; 70 71 static unsigned long lcid_hash(const QUIC_LCID *lcid_obj) 72 { 73 SIPHASH siphash = {0, }; 74 unsigned long hashval = 0; 75 76 if (!SipHash_set_hash_size(&siphash, sizeof(unsigned long))) 77 goto out; 78 if (!SipHash_Init(&siphash, (uint8_t *)lcid_obj->hash_key, 0, 0)) 79 goto out; 80 SipHash_Update(&siphash, lcid_obj->cid.id, lcid_obj->cid.id_len); 81 if (!SipHash_Final(&siphash, (unsigned char *)&hashval, 82 sizeof(unsigned long))) 83 goto out; 84 out: 85 return hashval; 86 } 87 88 static int lcid_comp(const QUIC_LCID *a, const QUIC_LCID *b) 89 { 90 return !ossl_quic_conn_id_eq(&a->cid, &b->cid); 91 } 92 93 static unsigned long lcidm_conn_hash(const QUIC_LCIDM_CONN *conn) 94 { 95 return (unsigned long)(uintptr_t)conn->opaque; 96 } 97 98 static int lcidm_conn_comp(const QUIC_LCIDM_CONN *a, const QUIC_LCIDM_CONN *b) 99 { 100 return a->opaque != b->opaque; 101 } 102 103 QUIC_LCIDM *ossl_quic_lcidm_new(OSSL_LIB_CTX *libctx, size_t lcid_len) 104 { 105 QUIC_LCIDM *lcidm = NULL; 106 107 if (lcid_len > QUIC_MAX_CONN_ID_LEN) 108 goto err; 109 110 if ((lcidm = OPENSSL_zalloc(sizeof(*lcidm))) == NULL) 111 goto err; 112 113 /* generate a random key for the hash tables hash function */ 114 if (!RAND_bytes_ex(libctx, (unsigned char *)&lcidm->hash_key, 115 sizeof(uint64_t) * 2, 0)) 116 goto err; 117 118 if ((lcidm->lcids = lh_QUIC_LCID_new(lcid_hash, lcid_comp)) == NULL) 119 goto err; 120 121 if ((lcidm->conns = lh_QUIC_LCIDM_CONN_new(lcidm_conn_hash, 122 lcidm_conn_comp)) == NULL) 123 goto err; 124 125 lcidm->libctx = libctx; 126 lcidm->lcid_len = lcid_len; 127 return lcidm; 128 129 err: 130 if (lcidm != NULL) { 131 lh_QUIC_LCID_free(lcidm->lcids); 132 lh_QUIC_LCIDM_CONN_free(lcidm->conns); 133 OPENSSL_free(lcidm); 134 } 135 return NULL; 136 } 137 138 static void lcidm_delete_conn(QUIC_LCIDM *lcidm, QUIC_LCIDM_CONN *conn); 139 140 static void lcidm_delete_conn_(QUIC_LCIDM_CONN *conn, void *arg) 141 { 142 lcidm_delete_conn((QUIC_LCIDM *)arg, conn); 143 } 144 145 void ossl_quic_lcidm_free(QUIC_LCIDM *lcidm) 146 { 147 if (lcidm == NULL) 148 return; 149 150 /* 151 * Calling OPENSSL_lh_delete during a doall call is unsafe with our 152 * current LHASH implementation for several reasons: 153 * 154 * - firstly, because deletes can cause the hashtable to be contracted, 155 * resulting in rehashing which might cause items in later buckets to 156 * move to earlier buckets, which might cause doall to skip an item, 157 * resulting in a memory leak; 158 * 159 * - secondly, because doall in general is not safe across hashtable 160 * size changes, as it caches hashtable size and pointer values 161 * while operating. 162 * 163 * The fix for this is to disable hashtable contraction using the following 164 * call, which guarantees that no rehashing will occur so long as we only 165 * call delete and not insert. 166 */ 167 lh_QUIC_LCIDM_CONN_set_down_load(lcidm->conns, 0); 168 169 lh_QUIC_LCIDM_CONN_doall_arg(lcidm->conns, lcidm_delete_conn_, lcidm); 170 171 lh_QUIC_LCID_free(lcidm->lcids); 172 lh_QUIC_LCIDM_CONN_free(lcidm->conns); 173 OPENSSL_free(lcidm); 174 } 175 176 static QUIC_LCID *lcidm_get0_lcid(const QUIC_LCIDM *lcidm, const QUIC_CONN_ID *lcid) 177 { 178 QUIC_LCID key; 179 180 key.cid = *lcid; 181 key.hash_key = (uint64_t *)lcidm->hash_key; 182 183 if (key.cid.id_len > QUIC_MAX_CONN_ID_LEN) 184 return NULL; 185 186 return lh_QUIC_LCID_retrieve(lcidm->lcids, &key); 187 } 188 189 static QUIC_LCIDM_CONN *lcidm_get0_conn(const QUIC_LCIDM *lcidm, void *opaque) 190 { 191 QUIC_LCIDM_CONN key; 192 193 key.opaque = opaque; 194 195 return lh_QUIC_LCIDM_CONN_retrieve(lcidm->conns, &key); 196 } 197 198 static QUIC_LCIDM_CONN *lcidm_upsert_conn(const QUIC_LCIDM *lcidm, void *opaque) 199 { 200 QUIC_LCIDM_CONN *conn = lcidm_get0_conn(lcidm, opaque); 201 202 if (conn != NULL) 203 return conn; 204 205 if ((conn = OPENSSL_zalloc(sizeof(*conn))) == NULL) 206 goto err; 207 208 if ((conn->lcids = lh_QUIC_LCID_new(lcid_hash, lcid_comp)) == NULL) 209 goto err; 210 211 conn->opaque = opaque; 212 213 lh_QUIC_LCIDM_CONN_insert(lcidm->conns, conn); 214 if (lh_QUIC_LCIDM_CONN_error(lcidm->conns)) 215 goto err; 216 217 return conn; 218 219 err: 220 if (conn != NULL) { 221 lh_QUIC_LCID_free(conn->lcids); 222 OPENSSL_free(conn); 223 } 224 return NULL; 225 } 226 227 static void lcidm_delete_conn_lcid(QUIC_LCIDM *lcidm, QUIC_LCID *lcid_obj) 228 { 229 lh_QUIC_LCID_delete(lcidm->lcids, lcid_obj); 230 lh_QUIC_LCID_delete(lcid_obj->conn->lcids, lcid_obj); 231 assert(lcid_obj->conn->num_active_lcid > 0); 232 --lcid_obj->conn->num_active_lcid; 233 OPENSSL_free(lcid_obj); 234 } 235 236 /* doall_arg wrapper */ 237 static void lcidm_delete_conn_lcid_(QUIC_LCID *lcid_obj, void *arg) 238 { 239 lcidm_delete_conn_lcid((QUIC_LCIDM *)arg, lcid_obj); 240 } 241 242 static void lcidm_delete_conn(QUIC_LCIDM *lcidm, QUIC_LCIDM_CONN *conn) 243 { 244 /* See comment in ossl_quic_lcidm_free */ 245 lh_QUIC_LCID_set_down_load(conn->lcids, 0); 246 247 lh_QUIC_LCID_doall_arg(conn->lcids, lcidm_delete_conn_lcid_, lcidm); 248 lh_QUIC_LCIDM_CONN_delete(lcidm->conns, conn); 249 lh_QUIC_LCID_free(conn->lcids); 250 OPENSSL_free(conn); 251 } 252 253 static QUIC_LCID *lcidm_conn_new_lcid(QUIC_LCIDM *lcidm, QUIC_LCIDM_CONN *conn, 254 const QUIC_CONN_ID *lcid) 255 { 256 QUIC_LCID *lcid_obj = NULL; 257 258 if (lcid->id_len > QUIC_MAX_CONN_ID_LEN) 259 return NULL; 260 261 if ((lcid_obj = OPENSSL_zalloc(sizeof(*lcid_obj))) == NULL) 262 goto err; 263 264 lcid_obj->cid = *lcid; 265 lcid_obj->conn = conn; 266 lcid_obj->hash_key = lcidm->hash_key; 267 268 lh_QUIC_LCID_insert(conn->lcids, lcid_obj); 269 if (lh_QUIC_LCID_error(conn->lcids)) 270 goto err; 271 272 lh_QUIC_LCID_insert(lcidm->lcids, lcid_obj); 273 if (lh_QUIC_LCID_error(lcidm->lcids)) { 274 lh_QUIC_LCID_delete(conn->lcids, lcid_obj); 275 goto err; 276 } 277 278 ++conn->num_active_lcid; 279 return lcid_obj; 280 281 err: 282 OPENSSL_free(lcid_obj); 283 return NULL; 284 } 285 286 size_t ossl_quic_lcidm_get_lcid_len(const QUIC_LCIDM *lcidm) 287 { 288 return lcidm->lcid_len; 289 } 290 291 size_t ossl_quic_lcidm_get_num_active_lcid(const QUIC_LCIDM *lcidm, 292 void *opaque) 293 { 294 QUIC_LCIDM_CONN *conn; 295 296 conn = lcidm_get0_conn(lcidm, opaque); 297 if (conn == NULL) 298 return 0; 299 300 return conn->num_active_lcid; 301 } 302 303 static int lcidm_generate_cid(QUIC_LCIDM *lcidm, 304 QUIC_CONN_ID *cid) 305 { 306 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 307 int i; 308 309 lcidm->next_lcid.id_len = (unsigned char)lcidm->lcid_len; 310 *cid = lcidm->next_lcid; 311 312 for (i = lcidm->lcid_len - 1; i >= 0; --i) 313 if (++lcidm->next_lcid.id[i] != 0) 314 break; 315 316 return 1; 317 #else 318 return ossl_quic_gen_rand_conn_id(lcidm->libctx, lcidm->lcid_len, cid); 319 #endif 320 } 321 322 static int lcidm_generate(QUIC_LCIDM *lcidm, 323 void *opaque, 324 unsigned int type, 325 QUIC_CONN_ID *lcid_out, 326 uint64_t *seq_num) 327 { 328 QUIC_LCIDM_CONN *conn; 329 QUIC_LCID key, *lcid_obj; 330 size_t i; 331 #define MAX_RETRIES 8 332 333 if ((conn = lcidm_upsert_conn(lcidm, opaque)) == NULL) 334 return 0; 335 336 if ((type == LCID_TYPE_INITIAL && conn->next_seq_num > 0) 337 || conn->next_seq_num > OSSL_QUIC_VLINT_MAX) 338 return 0; 339 340 i = 0; 341 do { 342 if (i++ >= MAX_RETRIES) 343 /* 344 * Too many retries; should not happen but if it does, don't loop 345 * endlessly. 346 */ 347 return 0; 348 349 if (!lcidm_generate_cid(lcidm, lcid_out)) 350 return 0; 351 352 key.cid = *lcid_out; 353 key.hash_key = lcidm->hash_key; 354 355 /* If a collision occurs, retry. */ 356 } while (lh_QUIC_LCID_retrieve(lcidm->lcids, &key) != NULL); 357 358 if ((lcid_obj = lcidm_conn_new_lcid(lcidm, conn, lcid_out)) == NULL) 359 return 0; 360 361 lcid_obj->seq_num = conn->next_seq_num; 362 lcid_obj->type = type; 363 364 if (seq_num != NULL) 365 *seq_num = lcid_obj->seq_num; 366 367 ++conn->next_seq_num; 368 return 1; 369 } 370 371 int ossl_quic_lcidm_enrol_odcid(QUIC_LCIDM *lcidm, 372 void *opaque, 373 const QUIC_CONN_ID *initial_odcid) 374 { 375 QUIC_LCIDM_CONN *conn; 376 QUIC_LCID key, *lcid_obj; 377 378 if (initial_odcid == NULL || initial_odcid->id_len < QUIC_MIN_ODCID_LEN 379 || initial_odcid->id_len > QUIC_MAX_CONN_ID_LEN) 380 return 0; 381 382 if ((conn = lcidm_upsert_conn(lcidm, opaque)) == NULL) 383 return 0; 384 385 if (conn->done_odcid) 386 return 0; 387 388 key.cid = *initial_odcid; 389 key.hash_key = lcidm->hash_key; 390 if (lh_QUIC_LCID_retrieve(lcidm->lcids, &key) != NULL) 391 return 0; 392 393 if ((lcid_obj = lcidm_conn_new_lcid(lcidm, conn, initial_odcid)) == NULL) 394 return 0; 395 396 lcid_obj->seq_num = LCIDM_ODCID_SEQ_NUM; 397 lcid_obj->type = LCID_TYPE_ODCID; 398 399 conn->odcid_lcid_obj = lcid_obj; 400 conn->done_odcid = 1; 401 return 1; 402 } 403 404 int ossl_quic_lcidm_generate_initial(QUIC_LCIDM *lcidm, 405 void *opaque, 406 QUIC_CONN_ID *initial_lcid) 407 { 408 return lcidm_generate(lcidm, opaque, LCID_TYPE_INITIAL, 409 initial_lcid, NULL); 410 } 411 412 int ossl_quic_lcidm_bind_channel(QUIC_LCIDM *lcidm, void *opaque, 413 const QUIC_CONN_ID *lcid) 414 { 415 QUIC_LCIDM_CONN *conn; 416 QUIC_LCID *lcid_obj; 417 418 /* 419 * the plan is simple: 420 * make sure the lcid is still unused. 421 * do the same business as ossl_quic_lcidm_gnerate_initial() does, 422 * except we will use lcid instead of generating a new one. 423 */ 424 if (ossl_quic_lcidm_lookup(lcidm, lcid, NULL, NULL) != 0) 425 return 0; 426 427 if ((conn = lcidm_upsert_conn(lcidm, opaque)) == NULL) 428 return 0; 429 430 if ((lcid_obj = lcidm_conn_new_lcid(lcidm, conn, lcid)) == NULL) { 431 lcidm_delete_conn(lcidm, conn); 432 return 0; 433 } 434 435 lcid_obj->seq_num = conn->next_seq_num; 436 lcid_obj->type = LCID_TYPE_INITIAL; 437 conn->next_seq_num++; 438 439 return 1; 440 } 441 442 int ossl_quic_lcidm_generate(QUIC_LCIDM *lcidm, 443 void *opaque, 444 OSSL_QUIC_FRAME_NEW_CONN_ID *ncid_frame) 445 { 446 ncid_frame->seq_num = 0; 447 ncid_frame->retire_prior_to = 0; 448 449 return lcidm_generate(lcidm, opaque, LCID_TYPE_NCID, 450 &ncid_frame->conn_id, 451 &ncid_frame->seq_num); 452 } 453 454 int ossl_quic_lcidm_retire_odcid(QUIC_LCIDM *lcidm, void *opaque) 455 { 456 QUIC_LCIDM_CONN *conn; 457 458 if ((conn = lcidm_upsert_conn(lcidm, opaque)) == NULL) 459 return 0; 460 461 if (conn->odcid_lcid_obj == NULL) 462 return 0; 463 464 lcidm_delete_conn_lcid(lcidm, conn->odcid_lcid_obj); 465 conn->odcid_lcid_obj = NULL; 466 return 1; 467 } 468 469 struct retire_args { 470 QUIC_LCID *earliest_seq_num_lcid_obj; 471 uint64_t earliest_seq_num, retire_prior_to; 472 }; 473 474 static void retire_for_conn(QUIC_LCID *lcid_obj, void *arg) 475 { 476 struct retire_args *args = arg; 477 478 /* ODCID LCID cannot be retired via this API */ 479 if (lcid_obj->type == LCID_TYPE_ODCID 480 || lcid_obj->seq_num >= args->retire_prior_to) 481 return; 482 483 if (lcid_obj->seq_num < args->earliest_seq_num) { 484 args->earliest_seq_num = lcid_obj->seq_num; 485 args->earliest_seq_num_lcid_obj = lcid_obj; 486 } 487 } 488 489 int ossl_quic_lcidm_retire(QUIC_LCIDM *lcidm, 490 void *opaque, 491 uint64_t retire_prior_to, 492 const QUIC_CONN_ID *containing_pkt_dcid, 493 QUIC_CONN_ID *retired_lcid, 494 uint64_t *retired_seq_num, 495 int *did_retire) 496 { 497 QUIC_LCIDM_CONN key, *conn; 498 struct retire_args args = {0}; 499 500 key.opaque = opaque; 501 502 if (did_retire == NULL) 503 return 0; 504 505 *did_retire = 0; 506 if ((conn = lh_QUIC_LCIDM_CONN_retrieve(lcidm->conns, &key)) == NULL) 507 return 1; 508 509 args.retire_prior_to = retire_prior_to; 510 args.earliest_seq_num = UINT64_MAX; 511 512 lh_QUIC_LCID_doall_arg(conn->lcids, retire_for_conn, &args); 513 if (args.earliest_seq_num_lcid_obj == NULL) 514 return 1; 515 516 if (containing_pkt_dcid != NULL 517 && ossl_quic_conn_id_eq(&args.earliest_seq_num_lcid_obj->cid, 518 containing_pkt_dcid)) 519 return 0; 520 521 *did_retire = 1; 522 if (retired_lcid != NULL) 523 *retired_lcid = args.earliest_seq_num_lcid_obj->cid; 524 if (retired_seq_num != NULL) 525 *retired_seq_num = args.earliest_seq_num_lcid_obj->seq_num; 526 527 lcidm_delete_conn_lcid(lcidm, args.earliest_seq_num_lcid_obj); 528 return 1; 529 } 530 531 int ossl_quic_lcidm_cull(QUIC_LCIDM *lcidm, void *opaque) 532 { 533 QUIC_LCIDM_CONN key, *conn; 534 535 key.opaque = opaque; 536 537 if ((conn = lh_QUIC_LCIDM_CONN_retrieve(lcidm->conns, &key)) == NULL) 538 return 0; 539 540 lcidm_delete_conn(lcidm, conn); 541 return 1; 542 } 543 544 int ossl_quic_lcidm_lookup(QUIC_LCIDM *lcidm, 545 const QUIC_CONN_ID *lcid, 546 uint64_t *seq_num, 547 void **opaque) 548 { 549 QUIC_LCID *lcid_obj; 550 551 if (lcid == NULL) 552 return 0; 553 554 if ((lcid_obj = lcidm_get0_lcid(lcidm, lcid)) == NULL) 555 return 0; 556 557 if (seq_num != NULL) 558 *seq_num = lcid_obj->seq_num; 559 560 if (opaque != NULL) 561 *opaque = lcid_obj->conn->opaque; 562 563 return 1; 564 } 565 566 int ossl_quic_lcidm_debug_remove(QUIC_LCIDM *lcidm, 567 const QUIC_CONN_ID *lcid) 568 { 569 QUIC_LCID key, *lcid_obj; 570 571 key.cid = *lcid; 572 key.hash_key = lcidm->hash_key; 573 if ((lcid_obj = lh_QUIC_LCID_retrieve(lcidm->lcids, &key)) == NULL) 574 return 0; 575 576 lcidm_delete_conn_lcid(lcidm, lcid_obj); 577 return 1; 578 } 579 580 int ossl_quic_lcidm_debug_add(QUIC_LCIDM *lcidm, void *opaque, 581 const QUIC_CONN_ID *lcid, 582 uint64_t seq_num) 583 { 584 QUIC_LCIDM_CONN *conn; 585 QUIC_LCID key, *lcid_obj; 586 587 if (lcid == NULL || lcid->id_len > QUIC_MAX_CONN_ID_LEN) 588 return 0; 589 590 if ((conn = lcidm_upsert_conn(lcidm, opaque)) == NULL) 591 return 0; 592 593 key.cid = *lcid; 594 key.hash_key = lcidm->hash_key; 595 if (lh_QUIC_LCID_retrieve(lcidm->lcids, &key) != NULL) 596 return 0; 597 598 if ((lcid_obj = lcidm_conn_new_lcid(lcidm, conn, lcid)) == NULL) 599 return 0; 600 601 lcid_obj->seq_num = seq_num; 602 lcid_obj->type = LCID_TYPE_NCID; 603 return 1; 604 } 605 606 int ossl_quic_lcidm_get_unused_cid(QUIC_LCIDM *lcidm, QUIC_CONN_ID *cid) 607 { 608 int i; 609 610 for (i = 0; i < 10; i++) { 611 if (lcidm_generate_cid(lcidm, cid) 612 && lcidm_get0_lcid(lcidm, cid) == NULL) 613 return 1; /* not found <=> radomly generated cid is unused */ 614 } 615 616 return 0; 617 } 618