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