diff options
author | Hugo Landau <hlandau@openssl.org> | 2023-11-03 11:56:14 +0000 |
---|---|---|
committer | Hugo Landau <hlandau@openssl.org> | 2023-11-23 14:46:01 +0000 |
commit | abc06d53a968f9072a2d026a776f3b66944ae7f3 (patch) | |
tree | 5b09423ac26966d756f68ffd29c03aa2e5d92eb4 /ssl | |
parent | addbd743b5ceeca93dafd59600ba92b87f916e12 (diff) |
QUIC SRTM: Add SRTM
Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/22612)
Diffstat (limited to 'ssl')
-rw-r--r-- | ssl/quic/build.info | 1 | ||||
-rw-r--r-- | ssl/quic/quic_srtm.c | 520 |
2 files changed, 521 insertions, 0 deletions
diff --git a/ssl/quic/build.info b/ssl/quic/build.info index 3a9e2d55af..866f581fa9 100644 --- a/ssl/quic/build.info +++ b/ssl/quic/build.info @@ -14,3 +14,4 @@ SOURCE[$LIBSSL]=quic_tserver.c SOURCE[$LIBSSL]=quic_tls.c SOURCE[$LIBSSL]=quic_thread_assist.c SOURCE[$LIBSSL]=quic_trace.c +SOURCE[$LIBSSL]=quic_srtm.c diff --git a/ssl/quic/quic_srtm.c b/ssl/quic/quic_srtm.c new file mode 100644 index 0000000000..d3639a4cc7 --- /dev/null +++ b/ssl/quic/quic_srtm.c @@ -0,0 +1,520 @@ +/* + * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include "internal/quic_srtm.h" +#include <openssl/lhash.h> +#include <openssl/core_names.h> +#include <openssl/rand.h> + +/* + * QUIC Stateless Reset Token Manager + * ================================== + */ +typedef struct srtm_item_st SRTM_ITEM; + +#define BLINDED_SRT_LEN 16 + +DEFINE_LHASH_OF_EX(SRTM_ITEM); + +/* + * The SRTM is implemented using two LHASH instances, one matching opaque pointers to + * an item structure, and another matching a SRT-derived value to an item + * structure. Multiple items with different seq_num values under a given opaque, + * and duplicate SRTs, are handled using sorted singly-linked lists. + * + * The O(n) insert and lookup performance is tolerated on the basis that the + * total number of entries for a given opaque (total number of extant CIDs for a + * connection) should be quite small, and the QUIC protocol allows us to place a + * hard limit on this via the active_connection_id_limit TPARAM. Thus there is + * no risk of a large number of SRTs needing to be registered under a given + * opaque. + * + * It is expected one SRTM will exist per QUIC_PORT and track all SRTs across + * all connections for that QUIC_PORT. + */ +struct srtm_item_st { + SRTM_ITEM *next_by_srt_blinded; /* SORT BY opaque DESC */ + SRTM_ITEM *next_by_seq_num; /* SORT BY seq_num DESC */ + void *opaque; /* \__ unique identity for item */ + uint64_t seq_num; /* / */ + QUIC_STATELESS_RESET_TOKEN srt; + unsigned char srt_blinded[BLINDED_SRT_LEN]; /* H(srt) */ + +#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION + uint32_t debug_token; +#endif +}; + +struct quic_srtm_st { + /* Crypto context used to calculate blinded SRTs H(srt). */ + EVP_MAC *blind_mac; + EVP_MAC_CTX *blind_ctx; /* kept with key */ + + LHASH_OF(SRTM_ITEM) *items_fwd; /* (opaque) -> SRTM_ITEM */ + LHASH_OF(SRTM_ITEM) *items_rev; /* (H(srt)) -> SRTM_ITEM */ +}; + +static unsigned long items_fwd_hash(const SRTM_ITEM *item) +{ + return (unsigned long)(uintptr_t)item->opaque; +} + +static int items_fwd_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b) +{ + return a->opaque != b->opaque; +} + +static unsigned long items_rev_hash(const SRTM_ITEM *item) +{ + /* + * srt_blinded has already been through a crypto-grade hash function, so we + * can just use bits from that. + */ + unsigned long l; + + memcpy(&l, item->srt_blinded, sizeof(l)); + return l; +} + +static int items_rev_cmp(const SRTM_ITEM *a, const SRTM_ITEM *b) +{ + /* + * We don't really need to use CRYPTO_memcmp here as the relationship of + * srt_blinded to srt is already cryptographically obfuscated, but it + * doesn't hurt. + */ + return CRYPTO_memcmp(a->srt_blinded, b->srt_blinded, sizeof(a->srt_blinded)); +} + +QUIC_SRTM *ossl_quic_srtm_new(OSSL_LIB_CTX *libctx, const char *propq) +{ + QUIC_SRTM *srtm = NULL; + OSSL_PARAM params[3], *p = params; + unsigned char key[16]; + + if ((srtm = OPENSSL_zalloc(sizeof(*srtm))) == NULL) + return NULL; + + /* + * Construct our blinding context using a random key. Since this only exists + * for side channel mitigation, we don't need to make the key configurable + * and simply use a random key each time. We never reconfigure the + * EVP_MAC_CTX after setup so we don't need to keep the key around. + */ + if ((srtm->blind_mac = EVP_MAC_fetch(libctx, "CMAC", propq)) == NULL) + goto err; + + if ((srtm->blind_ctx = EVP_MAC_CTX_new(srtm->blind_mac)) == NULL) + goto err; + + *p++ = OSSL_PARAM_construct_utf8_string(OSSL_MAC_PARAM_CIPHER, + "AES-128-CBC", 12); + if (propq != NULL) + *p++ = OSSL_PARAM_construct_utf8_string(OSSL_MAC_PARAM_PROPERTIES, + (char *)propq, 0); + + *p++ = OSSL_PARAM_construct_end(); + + if (RAND_bytes_ex(libctx, key, sizeof(key), sizeof(key) * 8) != 1) + goto err; + + if (!EVP_MAC_init(srtm->blind_ctx, key, sizeof(key), params)) + goto err; + + /* Create mappings. */ + if ((srtm->items_fwd = lh_SRTM_ITEM_new(items_fwd_hash, items_fwd_cmp)) == NULL + || (srtm->items_rev = lh_SRTM_ITEM_new(items_rev_hash, items_rev_cmp)) == NULL) + goto err; + + return srtm; + +err: + /* + * No cleansing of key needed as blinding exists only for side channel + * mitigation. + */ + ossl_quic_srtm_free(srtm); + return NULL; +} + +static void srtm_free_each(SRTM_ITEM *ihead) +{ + SRTM_ITEM *inext, *item = ihead; + + for (item = item->next_by_seq_num; item != NULL; item = inext) { + inext = item->next_by_seq_num; + OPENSSL_free(item); + } + + OPENSSL_free(ihead); +} + +void ossl_quic_srtm_free(QUIC_SRTM *srtm) +{ + if (srtm == NULL) + return; + + lh_SRTM_ITEM_free(srtm->items_rev); + if (srtm->items_fwd != NULL) { + lh_SRTM_ITEM_doall(srtm->items_fwd, srtm_free_each); + lh_SRTM_ITEM_free(srtm->items_fwd); + } + + EVP_MAC_CTX_free(srtm->blind_ctx); + EVP_MAC_free(srtm->blind_mac); + OPENSSL_free(srtm); +} + +/* + * Find a SRTM_ITEM by (opaque, seq_num). Returns NULL if no match. + * If head is non-NULL, writes the head of the relevant opaque list to *head if + * there is one. + * If prev is non-NULL, writes the previous node to *prev or NULL if it is + * the first item. + */ +static SRTM_ITEM *srtm_find(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num, + SRTM_ITEM **head_p, SRTM_ITEM **prev_p) +{ + SRTM_ITEM key, *item = NULL, *prev = NULL; + + key.opaque = opaque; + + item = lh_SRTM_ITEM_retrieve(srtm->items_fwd, &key); + if (head_p != NULL) + *head_p = item; + + for (; item != NULL; prev = item, item = item->next_by_seq_num) + if (item->seq_num == seq_num) { + break; + } else if (item->seq_num < seq_num) { + /* + * List is sorted in descending order so there can't be any match + * after this. + */ + item = NULL; + break; + } + + if (prev_p != NULL) + *prev_p = prev; + + return item; +} + +/* + * Inserts a SRTM_ITEM into the singly-linked by-sequence-number linked list. + * The new head pointer is written to *new_head (which may or may not be + * unchanged). + */ +static void sorted_insert_seq_num(SRTM_ITEM *head, SRTM_ITEM *item, SRTM_ITEM **new_head) +{ + uint64_t seq_num = item->seq_num; + SRTM_ITEM *cur = head, **fixup = new_head; + + *new_head = head; + + while (cur != NULL && cur->seq_num > seq_num) { + fixup = &cur->next_by_seq_num; + cur = cur->next_by_seq_num; + } + + item->next_by_seq_num = *fixup; + *fixup = item; +} + +/* + * Inserts a SRTM_ITEM into the singly-linked by-SRT list. + * The new head pointer is written to *new_head (which may or may not be + * unchanged). + */ +static void sorted_insert_srt(SRTM_ITEM *head, SRTM_ITEM *item, SRTM_ITEM **new_head) +{ + uintptr_t opaque = (uintptr_t)item->opaque; + SRTM_ITEM *cur = head, **fixup = new_head; + + *new_head = head; + + while (cur != NULL && (uintptr_t)cur->opaque > opaque) { + fixup = &cur->next_by_srt_blinded; + cur = cur->next_by_srt_blinded; + } + + item->next_by_srt_blinded = *fixup; + *fixup = item; +} + +/* + * Computes the blinded SRT value used for internal lookup for side channel + * mitigation purposes. We compute this once as a cached value when an SRTM_ITEM + * is formed. + */ +static int srtm_compute_blinded(QUIC_SRTM *srtm, SRTM_ITEM *item, + const QUIC_STATELESS_RESET_TOKEN *token) +{ + size_t outl = 0; + + if (!EVP_MAC_init(srtm->blind_ctx, NULL, 0, NULL)) + return 0; + + if (!EVP_MAC_update(srtm->blind_ctx, (const unsigned char *)token, + sizeof(*token))) + return 0; + + if (!EVP_MAC_final(srtm->blind_ctx, item->srt_blinded, + &outl, sizeof(item->srt_blinded)) + || outl != sizeof(item->srt_blinded)) + return 0; + + return 1; +} + +int ossl_quic_srtm_add(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num, + const QUIC_STATELESS_RESET_TOKEN *token) +{ + SRTM_ITEM *item = NULL, *head = NULL, *new_head, *r_item; + + /* (opaque, seq_num) duplicates not allowed */ + if ((item = srtm_find(srtm, opaque, seq_num, &head, NULL)) != NULL) + return 0; + + if ((item = OPENSSL_zalloc(sizeof(*item))) == NULL) + return 0; + + item->opaque = opaque; + item->seq_num = seq_num; + item->srt = *token; + if (!srtm_compute_blinded(srtm, item, &item->srt)) { + OPENSSL_free(item); + return 0; + } + + /* Add to forward mapping. */ + if (head == NULL) { + /* First item under this opaque */ + lh_SRTM_ITEM_insert(srtm->items_fwd, item); + assert(!lh_SRTM_ITEM_error(srtm->items_fwd)); + } else { + sorted_insert_seq_num(head, item, &new_head); + if (new_head != head) /* head changed, update in lhash */ + lh_SRTM_ITEM_insert(srtm->items_fwd, new_head); + } + + /* Add to reverse mapping. */ + r_item = lh_SRTM_ITEM_retrieve(srtm->items_rev, item); + if (r_item == NULL) { + /* First item under this blinded SRT */ + lh_SRTM_ITEM_insert(srtm->items_rev, item); + } else { + sorted_insert_srt(r_item, item, &new_head); + if (new_head != r_item) /* head changed, update in lhash */ + lh_SRTM_ITEM_insert(srtm->items_rev, new_head); + } + + return 1; +} + +/* Remove item from reverse mapping. */ +static void srtm_remove_from_rev(QUIC_SRTM *srtm, SRTM_ITEM *item) +{ + SRTM_ITEM *rh_item; + + rh_item = lh_SRTM_ITEM_retrieve(srtm->items_rev, item); + assert(rh_item != NULL); + if (rh_item == item) { + /* + * Change lhash to point to item after this one, or remove the entry if + * this is the last one. + */ + if (item->next_by_srt_blinded != NULL) + lh_SRTM_ITEM_insert(srtm->items_rev, item->next_by_srt_blinded); + else + lh_SRTM_ITEM_delete(srtm->items_rev, item); + } else { + /* Find our entry in the SRT list */ + for (; assert(rh_item != NULL), rh_item->next_by_srt_blinded != item; + rh_item = rh_item->next_by_srt_blinded); + rh_item->next_by_srt_blinded = item->next_by_srt_blinded; + } +} + +int ossl_quic_srtm_remove(QUIC_SRTM *srtm, void *opaque, uint64_t seq_num) +{ + SRTM_ITEM *item, *prev = NULL; + + if ((item = srtm_find(srtm, opaque, seq_num, NULL, &prev)) == NULL) + /* No match */ + return 0; + + /* Remove from forward mapping. */ + if (prev == NULL) { + /* + * Change lhash to point to item after this one, or remove the entry if + * this is the last one. + */ + if (item->next_by_seq_num != NULL) + lh_SRTM_ITEM_insert(srtm->items_fwd, item->next_by_seq_num); + else + lh_SRTM_ITEM_delete(srtm->items_fwd, item); + } else { + prev->next_by_seq_num = item->next_by_seq_num; + } + + /* Remove from reverse mapping. */ + srtm_remove_from_rev(srtm, item); + + OPENSSL_free(item); + return 1; +} + +int ossl_quic_srtm_cull(QUIC_SRTM *srtm, void *opaque) +{ + SRTM_ITEM key, *item = NULL, *inext, *ihead; + + key.opaque = opaque; + + if ((ihead = lh_SRTM_ITEM_retrieve(srtm->items_fwd, &key)) == NULL) + return 1; /* nothing removed is a success condition */ + + for (item = ihead; item != NULL; item = inext) { + inext = item->next_by_seq_num; + if (item != ihead) { + srtm_remove_from_rev(srtm, item); + OPENSSL_free(item); + } + } + + lh_SRTM_ITEM_delete(srtm->items_fwd, ihead); + srtm_remove_from_rev(srtm, ihead); + OPENSSL_free(ihead); + return 1; +} + +int ossl_quic_srtm_lookup(QUIC_SRTM *srtm, + const QUIC_STATELESS_RESET_TOKEN *token, + size_t idx, + void **opaque, uint64_t *seq_num) +{ + SRTM_ITEM key, *item; + + if (!srtm_compute_blinded(srtm, &key, token)) + return 0; + + item = lh_SRTM_ITEM_retrieve(srtm->items_rev, &key); + for (; idx > 0 && item != NULL; --idx, item = item->next_by_srt_blinded); + if (item == NULL) + return 0; + + if (opaque != NULL) + *opaque = item->opaque; + if (seq_num != NULL) + *seq_num = item->seq_num; + + return 1; +} + +#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION + +static uint32_t token_next = 0x5eadbeef; +static size_t tokens_seen; + +struct check_args { + uint32_t token; + int mode; +}; + +static void check_mark(SRTM_ITEM *item, void *arg) +{ + struct check_args *arg_ = arg; + uint32_t token = arg_->token; + uint64_t prev_seq_num; + void *prev_opaque; + int have_prev = 0; + + assert(item != NULL); + + while (item != NULL) { + if (have_prev) { + assert(!(item->opaque == prev_opaque && item->seq_num == prev_seq_num)); + if (!arg_->mode) + assert(item->opaque != prev_opaque || item->seq_num < prev_seq_num); + } + + ++tokens_seen; + item->debug_token = token; + prev_opaque = item->opaque; + prev_seq_num = item->seq_num; + have_prev = 1; + + if (arg_->mode) + item = item->next_by_srt_blinded; + else + item = item->next_by_seq_num; + } +} + +static void check_count(SRTM_ITEM *item, void *arg) +{ + struct check_args *arg_ = arg; + uint32_t token = arg_->token; + + assert(item != NULL); + + while (item != NULL) { + ++tokens_seen; + assert(item->debug_token == token); + + if (arg_->mode) + item = item->next_by_seq_num; + else + item = item->next_by_srt_blinded; + } +} + +#endif + +void ossl_quic_srtm_check(const QUIC_SRTM *srtm) +{ +#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION + struct check_args args = {0}; + size_t tokens_expected, tokens_expected_old; + + args.token = token_next; + ++token_next; + + assert(srtm != NULL); + assert(srtm->blind_mac != NULL); + assert(srtm->blind_ctx != NULL); + assert(srtm->items_fwd != NULL); + assert(srtm->items_rev != NULL); + + tokens_seen = 0; + lh_SRTM_ITEM_doall_arg(srtm->items_fwd, check_mark, &args); + + tokens_expected = tokens_seen; + tokens_seen = 0; + lh_SRTM_ITEM_doall_arg(srtm->items_rev, check_count, &args); + + assert(tokens_seen == tokens_expected); + tokens_expected_old = tokens_expected; + + args.token = token_next; + ++token_next; + + args.mode = 1; + tokens_seen = 0; + lh_SRTM_ITEM_doall_arg(srtm->items_rev, check_mark, &args); + + tokens_expected = tokens_seen; + tokens_seen = 0; + lh_SRTM_ITEM_doall_arg(srtm->items_fwd, check_count, &args); + + assert(tokens_seen == tokens_expected); + assert(tokens_seen == tokens_expected_old); +#endif +} |