Coverage Report

Created: 2025-06-13 06:55

/src/openssl/ssl/quic/quic_srtm.c
Line
Count
Source (jump to first uncovered line)
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
69
static unsigned long items_fwd_hash(const SRTM_ITEM *item)
70
686k
{
71
686k
    return (unsigned long)(uintptr_t)item->opaque;
72
686k
}
73
74
static int items_fwd_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b)
75
227k
{
76
227k
    return a->opaque != b->opaque;
77
227k
}
78
79
static unsigned long items_rev_hash(const SRTM_ITEM *item)
80
433k
{
81
    /*
82
     * srt_blinded has already been through a crypto-grade hash function, so we
83
     * can just use bits from that.
84
     */
85
433k
    unsigned long l;
86
87
433k
    memcpy(&l, item->srt_blinded, sizeof(l));
88
433k
    return l;
89
433k
}
90
91
static int items_rev_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b)
92
110k
{
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
110k
    return memcmp(a->srt_blinded, b->srt_blinded, sizeof(a->srt_blinded));
98
110k
}
99
100
static int srtm_check_lh(QUIC_SRTM *srtm, LHASH_OF(SRTM_ITEM) *lh)
101
259k
{
102
259k
    if (lh_SRTM_ITEM_error(lh)) {
103
0
        srtm->alloc_failed = 1;
104
0
        return 0;
105
0
    }
106
107
259k
    return 1;
108
259k
}
109
110
QUIC_SRTM *ossl_quic_srtm_new(OSSL_LIB_CTX *libctx, const char *propq)
111
1.15k
{
112
1.15k
    QUIC_SRTM *srtm = NULL;
113
1.15k
    unsigned char key[16];
114
1.15k
    EVP_CIPHER *ecb = NULL;
115
116
1.15k
    if (RAND_priv_bytes_ex(libctx, key, sizeof(key), sizeof(key) * 8) != 1)
117
0
        goto err;
118
119
1.15k
    if ((srtm = OPENSSL_zalloc(sizeof(*srtm))) == NULL)
120
0
        return NULL;
121
122
    /* Use AES-128-ECB as a permutation over 128-bit SRTs. */
123
1.15k
    if ((ecb = EVP_CIPHER_fetch(libctx, "AES-128-ECB", propq)) == NULL)
124
0
        goto err;
125
126
1.15k
    if ((srtm->blind_ctx = EVP_CIPHER_CTX_new()) == NULL)
127
0
        goto err;
128
129
1.15k
    if (!EVP_EncryptInit_ex2(srtm->blind_ctx, ecb, key, NULL, NULL))
130
0
        goto err;
131
132
1.15k
    EVP_CIPHER_free(ecb);
133
1.15k
    ecb = NULL;
134
135
    /* Create mappings. */
136
1.15k
    if ((srtm->items_fwd = lh_SRTM_ITEM_new(items_fwd_hash, items_fwd_cmp)) == NULL
137
1.15k
        || (srtm->items_rev = lh_SRTM_ITEM_new(items_rev_hash, items_rev_cmp)) == NULL)
138
0
        goto err;
139
140
1.15k
    return srtm;
141
142
0
err:
143
    /*
144
     * No cleansing of key needed as blinding exists only for side channel
145
     * mitigation.
146
     */
147
0
    ossl_quic_srtm_free(srtm);
148
0
    EVP_CIPHER_free(ecb);
149
0
    return NULL;
150
1.15k
}
151
152
static void srtm_free_each(SRTM_ITEM *ihead)
153
102k
{
154
102k
    SRTM_ITEM *inext, *item = ihead;
155
156
107k
    for (item = item->next_by_seq_num; item != NULL; item = inext) {
157
5.22k
        inext = item->next_by_seq_num;
158
5.22k
        OPENSSL_free(item);
159
5.22k
    }
160
161
102k
    OPENSSL_free(ihead);
162
102k
}
163
164
void ossl_quic_srtm_free(QUIC_SRTM *srtm)
165
1.15k
{
166
1.15k
    if (srtm == NULL)
167
0
        return;
168
169
1.15k
    lh_SRTM_ITEM_free(srtm->items_rev);
170
1.15k
    if (srtm->items_fwd != NULL) {
171
1.15k
        lh_SRTM_ITEM_doall(srtm->items_fwd, srtm_free_each);
172
1.15k
        lh_SRTM_ITEM_free(srtm->items_fwd);
173
1.15k
    }
174
175
1.15k
    EVP_CIPHER_CTX_free(srtm->blind_ctx);
176
1.15k
    OPENSSL_free(srtm);
177
1.15k
}
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
377k
{
189
377k
    SRTM_ITEM key, *item = NULL, *prev = NULL;
190
191
377k
    key.opaque  = opaque;
192
193
377k
    item = lh_SRTM_ITEM_retrieve(srtm->items_fwd, &key);
194
377k
    if (head_p != NULL)
195
309k
        *head_p = item;
196
197
2.16M
    for (; item != NULL; prev = item, item = item->next_by_seq_num)
198
1.99M
        if (item->seq_num == seq_num) {
199
162k
            break;
200
1.82M
        } 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
42.4k
            item = NULL;
206
42.4k
            break;
207
42.4k
        }
208
209
377k
    if (prev_p != NULL)
210
67.3k
        *prev_p = prev;
211
212
377k
    return item;
213
377k
}
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
44.4k
{
222
44.4k
    uint64_t seq_num = item->seq_num;
223
44.4k
    SRTM_ITEM *cur = head, **fixup = new_head;
224
225
44.4k
    *new_head = head;
226
227
384k
    while (cur != NULL && cur->seq_num > seq_num) {
228
339k
        fixup = &cur->next_by_seq_num;
229
339k
        cur = cur->next_by_seq_num;
230
339k
    }
231
232
44.4k
    item->next_by_seq_num = *fixup;
233
44.4k
    *fixup = item;
234
44.4k
}
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
10.6k
{
243
10.6k
    uintptr_t opaque = (uintptr_t)item->opaque;
244
10.6k
    SRTM_ITEM *cur = head, **fixup = new_head;
245
246
10.6k
    *new_head = head;
247
248
120k
    while (cur != NULL && (uintptr_t)cur->opaque > opaque) {
249
109k
        fixup = &cur->next_by_srt_blinded;
250
109k
        cur = cur->next_by_srt_blinded;
251
109k
    }
252
253
10.6k
    item->next_by_srt_blinded = *fixup;
254
10.6k
    *fixup = item;
255
10.6k
}
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
207k
{
265
207k
    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
207k
    if (!EVP_EncryptUpdate(srtm->blind_ctx, item->srt_blinded, &outl,
273
207k
                           (const unsigned char *)token, sizeof(*token)))
274
0
        return 0;
275
276
207k
    if (!ossl_assert(outl == sizeof(*token)))
277
0
        return 0;
278
279
207k
    return 1;
280
207k
}
281
282
int ossl_quic_srtm_add(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num,
283
                       const QUIC_STATELESS_RESET_TOKEN *token)
284
309k
{
285
309k
    SRTM_ITEM *item = NULL, *head = NULL, *new_head, *r_item;
286
287
309k
    if (srtm->alloc_failed)
288
0
        return 0;
289
290
    /* (opaque, seq_num) duplicates not allowed */
291
309k
    if ((item = srtm_find(srtm, opaque, seq_num, &head, NULL)) != NULL)
292
159k
        return 0;
293
294
150k
    if ((item = OPENSSL_zalloc(sizeof(*item))) == NULL)
295
0
        return 0;
296
297
150k
    item->opaque    = opaque;
298
150k
    item->seq_num   = seq_num;
299
150k
    item->srt       = *token;
300
150k
    if (!srtm_compute_blinded(srtm, item, &item->srt)) {
301
0
        OPENSSL_free(item);
302
0
        return 0;
303
0
    }
304
305
    /* Add to forward mapping. */
306
150k
    if (head == NULL) {
307
        /* First item under this opaque */
308
105k
        lh_SRTM_ITEM_insert(srtm->items_fwd, item);
309
105k
        if (!srtm_check_lh(srtm, srtm->items_fwd)) {
310
0
            OPENSSL_free(item);
311
0
            return 0;
312
0
        }
313
105k
    } else {
314
44.4k
        sorted_insert_seq_num(head, item, &new_head);
315
44.4k
        if (new_head != head) { /* head changed, update in lhash */
316
7.51k
            lh_SRTM_ITEM_insert(srtm->items_fwd, new_head);
317
7.51k
            if (!srtm_check_lh(srtm, srtm->items_fwd)) {
318
0
                OPENSSL_free(item);
319
0
                return 0;
320
0
            }
321
7.51k
        }
322
44.4k
    }
323
324
    /* Add to reverse mapping. */
325
150k
    r_item = lh_SRTM_ITEM_retrieve(srtm->items_rev, item);
326
150k
    if (r_item == NULL) {
327
        /* First item under this blinded SRT */
328
139k
        lh_SRTM_ITEM_insert(srtm->items_rev, item);
329
139k
        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
0
            return 0;
337
139k
    } else {
338
10.6k
        sorted_insert_srt(r_item, item, &new_head);
339
10.6k
        if (new_head != r_item) { /* head changed, update in lhash */
340
4.41k
            lh_SRTM_ITEM_insert(srtm->items_rev, new_head);
341
4.41k
            if (!srtm_check_lh(srtm, srtm->items_rev))
342
                /* As above. */
343
0
                return 0;
344
4.41k
        }
345
10.6k
    }
346
347
150k
    return 1;
348
150k
}
349
350
/* Remove item from reverse mapping. */
351
static int srtm_remove_from_rev(QUIC_SRTM *srtm, SRTM_ITEM *item)
352
43.0k
{
353
43.0k
    SRTM_ITEM *rh_item;
354
355
43.0k
    rh_item = lh_SRTM_ITEM_retrieve(srtm->items_rev, item);
356
43.0k
    assert(rh_item != NULL);
357
43.0k
    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
39.4k
        if (item->next_by_srt_blinded != NULL) {
363
1.72k
            lh_SRTM_ITEM_insert(srtm->items_rev, item->next_by_srt_blinded);
364
1.72k
            if (!srtm_check_lh(srtm, srtm->items_rev))
365
0
                return 0;
366
37.7k
        } else {
367
37.7k
            lh_SRTM_ITEM_delete(srtm->items_rev, item);
368
37.7k
        }
369
39.4k
    } else {
370
        /* Find our entry in the SRT list */
371
29.6k
        for (; rh_item->next_by_srt_blinded != item;
372
26.0k
               rh_item = rh_item->next_by_srt_blinded);
373
3.57k
        rh_item->next_by_srt_blinded = item->next_by_srt_blinded;
374
3.57k
    }
375
376
43.0k
    return 1;
377
43.0k
}
378
379
int ossl_quic_srtm_remove(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num)
380
67.3k
{
381
67.3k
    SRTM_ITEM *item, *prev = NULL;
382
383
67.3k
    if (srtm->alloc_failed)
384
0
        return 0;
385
386
67.3k
    if ((item = srtm_find(srtm, opaque, seq_num, NULL, &prev)) == NULL)
387
        /* No match */
388
64.2k
        return 0;
389
390
    /* Remove from forward mapping. */
391
3.05k
    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
1.22k
        if (item->next_by_seq_num != NULL) {
397
226
            lh_SRTM_ITEM_insert(srtm->items_fwd, item->next_by_seq_num);
398
226
            if (!srtm_check_lh(srtm, srtm->items_fwd))
399
0
                return 0;
400
999
        } else {
401
999
            lh_SRTM_ITEM_delete(srtm->items_fwd, item);
402
999
        }
403
1.83k
    } else {
404
1.83k
        prev->next_by_seq_num = item->next_by_seq_num;
405
1.83k
    }
406
407
    /* Remove from reverse mapping. */
408
3.05k
    if (!srtm_remove_from_rev(srtm, item))
409
0
        return 0;
410
411
3.05k
    OPENSSL_free(item);
412
3.05k
    return 1;
413
3.05k
}
414
415
int ossl_quic_srtm_cull(QUIC_SRTM *srtm, void *opaque)
416
192k
{
417
192k
    SRTM_ITEM key, *item = NULL, *inext, *ihead;
418
419
192k
    key.opaque = opaque;
420
421
192k
    if (srtm->alloc_failed)
422
0
        return 0;
423
424
192k
    if ((ihead = lh_SRTM_ITEM_retrieve(srtm->items_fwd, &key)) == NULL)
425
189k
        return 1; /* nothing removed is a success condition */
426
427
42.7k
    for (item = ihead; item != NULL; item = inext) {
428
39.9k
        inext = item->next_by_seq_num;
429
39.9k
        if (item != ihead) {
430
37.2k
            srtm_remove_from_rev(srtm, item);
431
37.2k
            OPENSSL_free(item);
432
37.2k
        }
433
39.9k
    }
434
435
2.75k
    lh_SRTM_ITEM_delete(srtm->items_fwd, ihead);
436
2.75k
    srtm_remove_from_rev(srtm, ihead);
437
2.75k
    OPENSSL_free(ihead);
438
2.75k
    return 1;
439
192k
}
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
56.8k
{
446
56.8k
    SRTM_ITEM key, *item;
447
448
56.8k
    if (srtm->alloc_failed)
449
0
        return 0;
450
451
56.8k
    if (!srtm_compute_blinded(srtm, &key, token))
452
0
        return 0;
453
454
56.8k
    item = lh_SRTM_ITEM_retrieve(srtm->items_rev, &key);
455
97.8k
    for (; idx > 0 && item != NULL; --idx, item = item->next_by_srt_blinded);
456
56.8k
    if (item == NULL)
457
56.5k
        return 0;
458
459
358
    if (opaque != NULL)
460
0
        *opaque     = item->opaque;
461
358
    if (seq_num != NULL)
462
0
        *seq_num    = item->seq_num;
463
464
358
    return 1;
465
56.8k
}
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
449M
{
479
449M
    struct check_args *arg_ = arg;
480
449M
    uint32_t token = arg_->token;
481
449M
    uint64_t prev_seq_num = 0;
482
449M
    void *prev_opaque = NULL;
483
449M
    int have_prev = 0;
484
485
449M
    assert(item != NULL);
486
487
939M
    while (item != NULL) {
488
489M
        if (have_prev) {
489
39.6M
            assert(!(item->opaque == prev_opaque && item->seq_num == prev_seq_num));
490
39.6M
            if (!arg_->mode)
491
17.3M
                assert(item->opaque != prev_opaque || item->seq_num < prev_seq_num);
492
39.6M
        }
493
494
489M
        ++tokens_seen;
495
489M
        item->debug_token = token;
496
489M
        prev_opaque  = item->opaque;
497
489M
        prev_seq_num = item->seq_num;
498
489M
        have_prev = 1;
499
500
489M
        if (arg_->mode)
501
244M
            item = item->next_by_srt_blinded;
502
244M
        else
503
244M
            item = item->next_by_seq_num;
504
489M
    }
505
449M
}
506
507
static void check_count(SRTM_ITEM *item, void *arg)
508
449M
{
509
449M
    struct check_args *arg_ = arg;
510
449M
    uint32_t token = arg_->token;
511
512
449M
    assert(item != NULL);
513
514
939M
    while (item != NULL) {
515
489M
        ++tokens_seen;
516
489M
        assert(item->debug_token == token);
517
518
489M
        if (arg_->mode)
519
244M
            item = item->next_by_seq_num;
520
244M
        else
521
244M
            item = item->next_by_srt_blinded;
522
489M
    }
523
449M
}
524
525
#endif
526
527
void ossl_quic_srtm_check(const QUIC_SRTM *srtm)
528
626k
{
529
626k
#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
530
626k
    struct check_args args = {0};
531
626k
    size_t tokens_expected, tokens_expected_old;
532
533
626k
    args.token = token_next;
534
626k
    ++token_next;
535
536
626k
    assert(srtm != NULL);
537
626k
    assert(srtm->blind_ctx != NULL);
538
626k
    assert(srtm->items_fwd != NULL);
539
626k
    assert(srtm->items_rev != NULL);
540
541
626k
    tokens_seen = 0;
542
626k
    lh_SRTM_ITEM_doall_arg(srtm->items_fwd, check_mark, &args);
543
544
626k
    tokens_expected = tokens_seen;
545
626k
    tokens_seen = 0;
546
626k
    lh_SRTM_ITEM_doall_arg(srtm->items_rev, check_count, &args);
547
548
626k
    assert(tokens_seen == tokens_expected);
549
626k
    tokens_expected_old = tokens_expected;
550
551
626k
    args.token = token_next;
552
626k
    ++token_next;
553
554
626k
    args.mode = 1;
555
626k
    tokens_seen = 0;
556
626k
    lh_SRTM_ITEM_doall_arg(srtm->items_rev, check_mark, &args);
557
558
626k
    tokens_expected = tokens_seen;
559
626k
    tokens_seen = 0;
560
626k
    lh_SRTM_ITEM_doall_arg(srtm->items_fwd, check_count, &args);
561
562
626k
    assert(tokens_seen == tokens_expected);
563
626k
    assert(tokens_seen == tokens_expected_old);
564
626k
#endif
565
626k
}