Coverage Report

Created: 2026-11-16 07:12

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