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
GETSET(prev,LIST_PREV_OFF)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
find_node(br_ssl_session_cache_lru * cc,const unsigned char * id,uint32_t * addr_link)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
find_replacement_node(br_ssl_session_cache_lru * cc,uint32_t x,uint32_t * al)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
set_link(br_ssl_session_cache_lru * cc,uint32_t alx,uint32_t x)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
remove_node(br_ssl_session_cache_lru * cc,uint32_t x)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
lru_save(const br_ssl_session_cache_class ** ctx,br_ssl_server_context * server_ctx,const br_ssl_session_parameters * params)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
lru_load(const br_ssl_session_cache_class ** ctx,br_ssl_server_context * server_ctx,br_ssl_session_parameters * params)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
br_ssl_session_cache_lru_init(br_ssl_session_cache_lru * cc,unsigned char * store,size_t store_len)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 */
br_ssl_session_cache_lru_forget(br_ssl_session_cache_lru * cc,const unsigned char * id)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 }
538