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) \ 96static inline uint32_t get_ ## name(br_ssl_session_cache_lru *cc, uint32_t x) \ 97{ \ 98 return br_dec32be(cc->store + x + (off)); \ 99} \ 100static 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 106GETSET(prev, LIST_PREV_OFF) 107GETSET(next, LIST_NEXT_OFF) 108GETSET(left, TREE_LEFT_OFF) 109GETSET(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 */ 125static void 126mask_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 */ 147static uint32_t 148find_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 */ 194static uint32_t 195find_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 */ 237static inline void 238set_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 */ 251static void 252remove_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 321static void 322lru_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 427static int 428lru_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 486static 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 */ 493void 494br_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 */ 508void 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} 538