path: root/ssl/quic/quic_srtm.c

/*
 * 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 "internal/common.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_CIPHER_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 */

    /*
     * Monotonically transitions to 1 in event of allocation failure. The only
     * valid operation on such an object is to free it.
     */
    unsigned int                alloc_failed : 1;
};

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 need to use CRYPTO_memcmp here as the relationship of
     * srt_blinded to srt is already cryptographically obfuscated.
     */
    return memcmp(a->srt_blinded, b->srt_blinded, sizeof(a->srt_blinded));
}

static int srtm_check_lh(QUIC_SRTM *srtm, LHASH_OF(SRTM_ITEM) *lh)
{
    if (lh_SRTM_ITEM_error(lh)) {
        srtm->alloc_failed = 1;
        return 0;
    }

    return 1;
}

QUIC_SRTM *ossl_quic_srtm_new(OSSL_LIB_CTX *libctx, const char *propq)
{
    QUIC_SRTM *srtm = NULL;
    unsigned char key[16];
    EVP_CIPHER *ecb = NULL;

    if (RAND_priv_bytes_ex(libctx, key, sizeof(key), sizeof(key) * 8) != 1)
        goto err;

    if ((srtm = OPENSSL_zalloc(sizeof(*srtm))) == NULL)
        return NULL;

    /* Use AES-128-ECB as a permutation over 128-bit SRTs. */
    if ((ecb = EVP_CIPHER_fetch(libctx, "AES-128-ECB", propq)) == NULL)
        goto err;

    if ((srtm->blind_ctx = EVP_CIPHER_CTX_new()) == NULL)
        goto err;

    if (!EVP_EncryptInit_ex2(srtm->blind_ctx, ecb, key, NULL, NULL))
        goto err;

    EVP_CIPHER_free(ecb);
    ecb = NULL;

    /* 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);
    EVP_CIPHER_free(ecb);
    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_CIPHER_CTX_free(srtm->blind_ctx);
    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