contrib/bearssl/src/ssl/ssl_lru.c

   1 /*
   2  * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "inner.h"
  26
  27 /*
  28  * Each entry consists in a fixed number of bytes. Entries are concatenated
  29  * in the store block. "Addresses" are really offsets in the block,
  30  * expressed over 32 bits (so the cache may have size at most 4 GB, which
  31  * "ought to be enough for everyone"). The "null address" is 0xFFFFFFFF.
  32  * Note that since the storage block alignment is in no way guaranteed, we
  33  * perform only accesses that can handle unaligned data.
  34  *
  35  * Two concurrent data structures are maintained:
  36  *
  37  * -- Entries are organised in a doubly-linked list; saved entries are added
  38  * at the head, and loaded entries are moved to the head. Eviction uses
  39  * the list tail (this is the LRU algorithm).
  40  *
  41  * -- Entries are indexed with a binary tree: all left descendants of a
  42  * node have a lower session ID (in lexicographic order), while all
  43  * right descendants have a higher session ID. The tree is heuristically
  44  * balanced.
  45  *
  46  * Entry format:
  47  *
  48  *   session ID          32 bytes
  49  *   master secret       48 bytes
  50  *   protocol version    2 bytes (big endian)
  51  *   cipher suite        2 bytes (big endian)
  52  *   list prev           4 bytes (big endian)
  53  *   list next           4 bytes (big endian)
  54  *   tree left child     4 bytes (big endian)
  55  *   tree right child    4 bytes (big endian)
  56  *
  57  * If an entry has a protocol version set to 0, then it is "disabled":
  58  * it was a session pushed to the cache at some point, but it has
  59  * been explicitly removed.
  60  *
  61  * We need to keep the tree balanced because an attacker could make
  62  * handshakes, selecting some specific sessions (by reusing them) to
  63  * try to make us make an imbalanced tree that makes lookups expensive
  64  * (a denial-of-service attack that would persist as long as the cache
  65  * remains, i.e. even after the attacker made all his connections).
  66  * To do that, we replace the session ID (or the start of the session ID)
  67  * with a HMAC value computed over the replaced part; the hash function
  68  * implementation and the key are obtained from the server context upon
  69  * first save() call.
  70  *
  71  * Theoretically, an attacker could use the exact timing of the lookup
  72  * to infer the current tree topology, and try to revive entries to make
  73  * it as unbalanced as possible. However, since the session ID are
  74  * chosen randomly by the server, and the attacker cannot see the
  75  * indexing values and must thus rely on blind selection, it should be
  76  * exponentially difficult for the attacker to maintain a large
  77  * imbalance.
  78  */
  79 #define SESSION_ID_LEN       32
  80 #define MASTER_SECRET_LEN    48
  81
  82 #define SESSION_ID_OFF        0
  83 #define MASTER_SECRET_OFF    32
  84 #define VERSION_OFF          80
  85 #define CIPHER_SUITE_OFF     82
  86 #define LIST_PREV_OFF        84
  87 #define LIST_NEXT_OFF        88
  88 #define TREE_LEFT_OFF        92
  89 #define TREE_RIGHT_OFF       96
  90
  91 #define LRU_ENTRY_LEN       100
  92
  93 #define ADDR_NULL   ((uint32_t)-1)
  94
  95 #define GETSET(name, off) \
  96 static inline uint32_t get_ ## name(br_ssl_session_cache_lru *cc, uint32_t x) \
  97 { \
  98         return br_dec32be(cc->store + x + (off)); \
  99 } \
 100 static inline void set_ ## name(br_ssl_session_cache_lru *cc, \
 101         uint32_t x, uint32_t val) \
 102 { \
 103         br_enc32be(cc->store + x + (off), val); \
 104 }
 105
 106 GETSET(prev, LIST_PREV_OFF)
 107 GETSET(next, LIST_NEXT_OFF)
 108 GETSET(left, TREE_LEFT_OFF)
 109 GETSET(right, TREE_RIGHT_OFF)
 110
 111 /*
 112  * Transform the session ID by replacing the first N bytes with a HMAC
 113  * value computed over these bytes, using the random key K (the HMAC
 114  * value is truncated if needed). HMAC will use the same hash function
 115  * as the DRBG in the SSL server context, so with SHA-256, SHA-384,
 116  * or SHA-1, depending on what is available.
 117  *
 118  * The risk of collision is considered too small to be a concern; and
 119  * the impact of a collision is low (the handshake won't succeed). This
 120  * risk is much lower than any transmission error, which would lead to
 121  * the same consequences.
 122  *
 123  * Source and destination arrays msut be disjoint.
 124  */
 125 static void
 126 mask_id(br_ssl_session_cache_lru *cc,
 127         const unsigned char *src, unsigned char *dst)
 128 {
 129         br_hmac_key_context hkc;
 130         br_hmac_context hc;
 131
 132         memcpy(dst, src, SESSION_ID_LEN);
 133         br_hmac_key_init(&hkc, cc->hash, cc->index_key, sizeof cc->index_key);
 134         br_hmac_init(&hc, &hkc, SESSION_ID_LEN);
 135         br_hmac_update(&hc, src, SESSION_ID_LEN);
 136         br_hmac_out(&hc, dst);
 137 }
 138
 139 /*
 140  * Find a node by ID. Returned value is the node address, or ADDR_NULL if
 141  * the node is not found.
 142  *
 143  * If addr_link is not NULL, then '*addr_link' is set to the address of the
 144  * last followed link. If the found node is the root, or if the tree is
 145  * empty, then '*addr_link' is set to ADDR_NULL.
 146  */
 147 static uint32_t
 148 find_node(br_ssl_session_cache_lru *cc, const unsigned char *id,
 149         uint32_t *addr_link)
 150 {
 151         uint32_t x, y;
 152
 153         x = cc->root;
 154         y = ADDR_NULL;
 155         while (x != ADDR_NULL) {
 156                 int r;
 157
 158                 r = memcmp(id, cc->store + x + SESSION_ID_OFF, SESSION_ID_LEN);
 159                 if (r < 0) {
 160                         y = x + TREE_LEFT_OFF;
 161                         x = get_left(cc, x);
 162                 } else if (r == 0) {
 163                         if (addr_link != NULL) {
 164                                 *addr_link = y;
 165                         }
 166                         return x;
 167                 } else {
 168                         y = x + TREE_RIGHT_OFF;
 169                         x = get_right(cc, x);
 170                 }
 171         }
 172         if (addr_link != NULL) {
 173                 *addr_link = y;
 174         }
 175         return ADDR_NULL;
 176 }
 177
 178 /*
 179  * For node x, find its replacement upon removal.
 180  *
 181  *  -- If node x has no child, then this returns ADDR_NULL.
 182  *  -- Otherwise, if node x has a left child, then the replacement is the
 183  *     rightmost left-descendent.
 184  *  -- Otherwise, the replacement is the leftmost right-descendent.
 185  *
 186  * If a node is returned, then '*al' is set to the address of the field
 187  * that points to that node. Otherwise (node x has no child), '*al' is
 188  * set to ADDR_NULL.
 189  *
 190  * Note that the replacement node, when found, is always a descendent
 191  * of node 'x', so it cannot be the tree root. Thus, '*al' can be set
 192  * to ADDR_NULL only when no node is found and ADDR_NULL is returned.
 193  */
 194 static uint32_t
 195 find_replacement_node(br_ssl_session_cache_lru *cc, uint32_t x, uint32_t *al)
 196 {
 197         uint32_t y1, y2;
 198
 199         y1 = get_left(cc, x);
 200         if (y1 != ADDR_NULL) {
 201                 y2 = x + TREE_LEFT_OFF;
 202                 for (;;) {
 203                         uint32_t z;
 204
 205                         z = get_right(cc, y1);
 206                         if (z == ADDR_NULL) {
 207                                 *al = y2;
 208                                 return y1;
 209                         }
 210                         y2 = y1 + TREE_RIGHT_OFF;
 211                         y1 = z;
 212                 }
 213         }
 214         y1 = get_right(cc, x);
 215         if (y1 != ADDR_NULL) {
 216                 y2 = x + TREE_RIGHT_OFF;
 217                 for (;;) {
 218                         uint32_t z;
 219
 220                         z = get_left(cc, y1);
 221                         if (z == ADDR_NULL) {
 222                                 *al = y2;
 223                                 return y1;
 224                         }
 225                         y2 = y1 + TREE_LEFT_OFF;
 226                         y1 = z;
 227                 }
 228         }
 229         *al = ADDR_NULL;
 230         return ADDR_NULL;
 231 }
 232
 233 /*
 234  * Set the link at address 'alx' to point to node 'x'. If 'alx' is
 235  * ADDR_NULL, then this sets the tree root to 'x'.
 236  */
 237 static inline void
 238 set_link(br_ssl_session_cache_lru *cc, uint32_t alx, uint32_t x)
 239 {
 240         if (alx == ADDR_NULL) {
 241                 cc->root = x;
 242         } else {
 243                 br_enc32be(cc->store + alx, x);
 244         }
 245 }
 246
 247 /*
 248  * Remove node 'x' from the tree. This function shall not be called if
 249  * node 'x' is not part of the tree.
 250  */
 251 static void
 252 remove_node(br_ssl_session_cache_lru *cc, uint32_t x)
 253 {
 254         uint32_t alx, y, aly;
 255
 256         /*
 257          * Removal algorithm:
 258          * ------------------
 259          *
 260          * - If we remove the root, then the tree becomes empty.
 261          *
 262          * - If the removed node has no child, then we can simply remove
 263          *   it, with nothing else to do.
 264          *
 265          * - Otherwise, the removed node must be replaced by either its
 266          *   rightmost left-descendent, or its leftmost right-descendent.
 267          *   The replacement node itself must be removed from its current
 268          *   place. By definition, that replacement node has either no
 269          *   child, or at most a single child that will replace it in the
 270          *   tree.
 271          */
 272
 273         /*
 274          * Find node back and its ancestor link. If the node was the
 275          * root, then alx is set to ADDR_NULL.
 276          */
 277         find_node(cc, cc->store + x + SESSION_ID_OFF, &alx);
 278
 279         /*
 280          * Find replacement node 'y', and 'aly' is set to the address of
 281          * the link to that replacement node. If the removed node has no
 282          * child, then both 'y' and 'aly' are set to ADDR_NULL.
 283          */
 284         y = find_replacement_node(cc, x, &aly);
 285
 286         if (y != ADDR_NULL) {
 287                 uint32_t z;
 288
 289                 /*
 290                  * The unlinked replacement node may have one child (but
 291                  * not two) that takes its place.
 292                  */
 293                 z = get_left(cc, y);
 294                 if (z == ADDR_NULL) {
 295                         z = get_right(cc, y);
 296                 }
 297                 set_link(cc, aly, z);
 298
 299                 /*
 300                  * Link the replacement node in its new place, overwriting
 301                  * the current link to the node 'x' (which removes 'x').
 302                  */
 303                 set_link(cc, alx, y);
 304
 305                 /*
 306                  * The replacement node adopts the left and right children
 307                  * of the removed node. Note that this also works even if
 308                  * the replacement node was a direct descendent of the
 309                  * removed node, since we unlinked it previously.
 310                  */
 311                 set_left(cc, y, get_left(cc, x));
 312                 set_right(cc, y, get_right(cc, x));
 313         } else {
 314                 /*
 315                  * No replacement, we simply unlink the node 'x'.
 316                  */
 317                 set_link(cc, alx, ADDR_NULL);
 318         }
 319 }
 320
 321 static void
 322 lru_save(const br_ssl_session_cache_class **ctx,
 323         br_ssl_server_context *server_ctx,
 324         const br_ssl_session_parameters *params)
 325 {
 326         br_ssl_session_cache_lru *cc;
 327         unsigned char id[SESSION_ID_LEN];
 328         uint32_t x, alx;
 329
 330         cc = (br_ssl_session_cache_lru *)ctx;
 331
 332         /*
 333          * If the buffer is too small, we don't record anything. This
 334          * test avoids problems in subsequent code.
 335          */
 336         if (cc->store_len < LRU_ENTRY_LEN) {
 337                 return;
 338         }
 339
 340         /*
 341          * Upon the first save in a session cache instance, we obtain
 342          * a random key for our indexing.
 343          */
 344         if (!cc->init_done) {
 345                 br_hmac_drbg_generate(&server_ctx->eng.rng,
 346                         cc->index_key, sizeof cc->index_key);
 347                 cc->hash = br_hmac_drbg_get_hash(&server_ctx->eng.rng);
 348                 cc->init_done = 1;
 349         }
 350         mask_id(cc, params->session_id, id);
 351
 352         /*
 353          * Look for the node in the tree. If the same ID is already used,
 354          * then reject it. This is a collision event, which should be
 355          * exceedingly rare.
 356          * Note: we do NOT record the emplacement here, because the
 357          * removal of an entry may change the tree topology.
 358          */
 359         if (find_node(cc, id, NULL) != ADDR_NULL) {
 360                 return;
 361         }
 362
 363         /*
 364          * Find some room for the new parameters. If the cache is not
 365          * full yet, add it to the end of the area and bump the pointer up.
 366          * Otherwise, evict the list tail entry. Note that we already
 367          * filtered out the case of a ridiculously small buffer that
 368          * cannot hold any entry at all; thus, if there is no room for an
 369          * extra entry, then the cache cannot be empty.
 370          */
 371         if (cc->store_ptr > (cc->store_len - LRU_ENTRY_LEN)) {
 372                 /*
 373                  * Evict tail. If the buffer has room for a single entry,
 374                  * then this may also be the head.
 375                  */
 376                 x = cc->tail;
 377                 cc->tail = get_prev(cc, x);
 378                 if (cc->tail == ADDR_NULL) {
 379                         cc->head = ADDR_NULL;
 380                 } else {
 381                         set_next(cc, cc->tail, ADDR_NULL);
 382                 }
 383
 384                 /*
 385                  * Remove the node from the tree.
 386                  */
 387                 remove_node(cc, x);
 388         } else {
 389                 /*
 390                  * Allocate room for new node.
 391                  */
 392                 x = cc->store_ptr;
 393                 cc->store_ptr += LRU_ENTRY_LEN;
 394         }
 395
 396         /*
 397          * Find the emplacement for the new node, and link it.
 398          */
 399         find_node(cc, id, &alx);
 400         set_link(cc, alx, x);
 401         set_left(cc, x, ADDR_NULL);
 402         set_right(cc, x, ADDR_NULL);
 403
 404         /*
 405          * New entry becomes new list head. It may also become the list
 406          * tail if the cache was empty at that point.
 407          */
 408         if (cc->head == ADDR_NULL) {
 409                 cc->tail = x;
 410         } else {
 411                 set_prev(cc, cc->head, x);
 412         }
 413         set_prev(cc, x, ADDR_NULL);
 414         set_next(cc, x, cc->head);
 415         cc->head = x;
 416
 417         /*
 418          * Fill data in the entry.
 419          */
 420         memcpy(cc->store + x + SESSION_ID_OFF, id, SESSION_ID_LEN);
 421         memcpy(cc->store + x + MASTER_SECRET_OFF,
 422                 params->master_secret, MASTER_SECRET_LEN);
 423         br_enc16be(cc->store + x + VERSION_OFF, params->version);
 424         br_enc16be(cc->store + x + CIPHER_SUITE_OFF, params->cipher_suite);
 425 }
 426
 427 static int
 428 lru_load(const br_ssl_session_cache_class **ctx,
 429         br_ssl_server_context *server_ctx,
 430         br_ssl_session_parameters *params)
 431 {
 432         br_ssl_session_cache_lru *cc;
 433         unsigned char id[SESSION_ID_LEN];
 434         uint32_t x;
 435
 436         (void)server_ctx;
 437         cc = (br_ssl_session_cache_lru *)ctx;
 438         if (!cc->init_done) {
 439                 return 0;
 440         }
 441         mask_id(cc, params->session_id, id);
 442         x = find_node(cc, id, NULL);
 443         if (x != ADDR_NULL) {
 444                 unsigned version;
 445
 446                 version = br_dec16be(cc->store + x + VERSION_OFF);
 447                 if (version == 0) {
 448                         /*
 449                          * Entry is disabled, we pretend we did not find it.
 450                          * Notably, we don't move it to the front of the
 451                          * LRU list.
 452                          */
 453                         return 0;
 454                 }
 455                 params->version = version;
 456                 params->cipher_suite = br_dec16be(
 457                         cc->store + x + CIPHER_SUITE_OFF);
 458                 memcpy(params->master_secret,
 459                         cc->store + x + MASTER_SECRET_OFF,
 460                         MASTER_SECRET_LEN);
 461                 if (x != cc->head) {
 462                         /*
 463                          * Found node is not at list head, so move
 464                          * it to the head.
 465                          */
 466                         uint32_t p, n;
 467
 468                         p = get_prev(cc, x);
 469                         n = get_next(cc, x);
 470                         set_next(cc, p, n);
 471                         if (n == ADDR_NULL) {
 472                                 cc->tail = p;
 473                         } else {
 474                                 set_prev(cc, n, p);
 475                         }
 476                         set_prev(cc, cc->head, x);
 477                         set_next(cc, x, cc->head);
 478                         set_prev(cc, x, ADDR_NULL);
 479                         cc->head = x;
 480                 }
 481                 return 1;
 482         }
 483         return 0;
 484 }
 485
 486 static const br_ssl_session_cache_class lru_class = {
 487         sizeof(br_ssl_session_cache_lru),
 488         &lru_save,
 489         &lru_load
 490 };
 491
 492 /* see inner.h */
 493 void
 494 br_ssl_session_cache_lru_init(br_ssl_session_cache_lru *cc,
 495         unsigned char *store, size_t store_len)
 496 {
 497         cc->vtable = &lru_class;
 498         cc->store = store;
 499         cc->store_len = store_len;
 500         cc->store_ptr = 0;
 501         cc->init_done = 0;
 502         cc->head = ADDR_NULL;
 503         cc->tail = ADDR_NULL;
 504         cc->root = ADDR_NULL;
 505 }
 506
 507 /* see bearssl_ssl.h */
 508 void br_ssl_session_cache_lru_forget(
 509         br_ssl_session_cache_lru *cc, const unsigned char *id)
 510 {
 511         unsigned char mid[SESSION_ID_LEN];
 512         uint32_t addr;
 513
 514         /*
 515          * If the cache is not initialised yet, then it is empty, and
 516          * there is nothing to forget.
 517          */
 518         if (!cc->init_done) {
 519                 return;
 520         }
 521
 522         /*
 523          * Look for the node in the tree. If found, the entry is marked
 524          * as "disabled"; it will be reused in due course, as it ages
 525          * through the list.
 526          *
 527          * We do not go through the complex moves of actually releasing
 528          * the entry right away because explicitly forgetting sessions
 529          * should be a rare event, meant mostly for testing purposes,
 530          * so this is not worth the extra code size.
 531          */
 532         mask_id(cc, id, mid);
 533         addr = find_node(cc, mid, NULL);
 534         if (addr != ADDR_NULL) {
 535                 br_enc16be(cc->store + addr + VERSION_OFF, 0);
 536         }
 537 }