2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
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:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
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
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.
35 * Two concurrent data structures are maintained:
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).
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
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)
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.
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
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
79 #define SESSION_ID_LEN 32
80 #define MASTER_SECRET_LEN 48
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
91 #define LRU_ENTRY_LEN 100
93 #define ADDR_NULL ((uint32_t)-1)
95 #define GETSET(name, off) \
96 static inline uint32_t get_ ## name(br_ssl_session_cache_lru *cc, uint32_t x) \
98 return br_dec32be(cc->store + x + (off)); \
100 static inline void set_ ## name(br_ssl_session_cache_lru *cc, \
101 uint32_t x, uint32_t val) \
103 br_enc32be(cc->store + x + (off), val); \
106 GETSET(prev
, LIST_PREV_OFF
)
107 GETSET(next
, LIST_NEXT_OFF
)
108 GETSET(left
, TREE_LEFT_OFF
)
109 GETSET(right
, TREE_RIGHT_OFF
)
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.
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.
123 * Source and destination arrays msut be disjoint.
126 mask_id(br_ssl_session_cache_lru
*cc
,
127 const unsigned char *src
, unsigned char *dst
)
129 br_hmac_key_context hkc
;
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
);
140 * Find a node by ID. Returned value is the node address, or ADDR_NULL if
141 * the node is not found.
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.
148 find_node(br_ssl_session_cache_lru
*cc
, const unsigned char *id
,
155 while (x
!= ADDR_NULL
) {
158 r
= memcmp(id
, cc
->store
+ x
+ SESSION_ID_OFF
, SESSION_ID_LEN
);
160 y
= x
+ TREE_LEFT_OFF
;
163 if (addr_link
!= NULL
) {
168 y
= x
+ TREE_RIGHT_OFF
;
169 x
= get_right(cc
, x
);
172 if (addr_link
!= NULL
) {
179 * For node x, find its replacement upon removal.
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.
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
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.
195 find_replacement_node(br_ssl_session_cache_lru
*cc
, uint32_t x
, uint32_t *al
)
199 y1
= get_left(cc
, x
);
200 if (y1
!= ADDR_NULL
) {
201 y2
= x
+ TREE_LEFT_OFF
;
205 z
= get_right(cc
, y1
);
206 if (z
== ADDR_NULL
) {
210 y2
= y1
+ TREE_RIGHT_OFF
;
214 y1
= get_right(cc
, x
);
215 if (y1
!= ADDR_NULL
) {
216 y2
= x
+ TREE_RIGHT_OFF
;
220 z
= get_left(cc
, y1
);
221 if (z
== ADDR_NULL
) {
225 y2
= y1
+ TREE_LEFT_OFF
;
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'.
238 set_link(br_ssl_session_cache_lru
*cc
, uint32_t alx
, uint32_t x
)
240 if (alx
== ADDR_NULL
) {
243 br_enc32be(cc
->store
+ alx
, x
);
248 * Remove node 'x' from the tree. This function shall not be called if
249 * node 'x' is not part of the tree.
252 remove_node(br_ssl_session_cache_lru
*cc
, uint32_t x
)
254 uint32_t alx
, y
, aly
;
260 * - If we remove the root, then the tree becomes empty.
262 * - If the removed node has no child, then we can simply remove
263 * it, with nothing else to do.
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
274 * Find node back and its ancestor link. If the node was the
275 * root, then alx is set to ADDR_NULL.
277 find_node(cc
, cc
->store
+ x
+ SESSION_ID_OFF
, &alx
);
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.
284 y
= find_replacement_node(cc
, x
, &aly
);
286 if (y
!= ADDR_NULL
) {
290 * The unlinked replacement node may have one child (but
291 * not two) that takes its place.
294 if (z
== ADDR_NULL
) {
295 z
= get_right(cc
, y
);
297 set_link(cc
, aly
, z
);
300 * Link the replacement node in its new place, overwriting
301 * the current link to the node 'x' (which removes 'x').
303 set_link(cc
, alx
, y
);
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.
311 set_left(cc
, y
, get_left(cc
, x
));
312 set_right(cc
, y
, get_right(cc
, x
));
315 * No replacement, we simply unlink the node 'x'.
317 set_link(cc
, alx
, ADDR_NULL
);
322 lru_save(const br_ssl_session_cache_class
**ctx
,
323 br_ssl_server_context
*server_ctx
,
324 const br_ssl_session_parameters
*params
)
326 br_ssl_session_cache_lru
*cc
;
327 unsigned char id
[SESSION_ID_LEN
];
330 cc
= (br_ssl_session_cache_lru
*)ctx
;
333 * If the buffer is too small, we don't record anything. This
334 * test avoids problems in subsequent code.
336 if (cc
->store_len
< LRU_ENTRY_LEN
) {
341 * Upon the first save in a session cache instance, we obtain
342 * a random key for our indexing.
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
);
350 mask_id(cc
, params
->session_id
, id
);
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
356 * Note: we do NOT record the emplacement here, because the
357 * removal of an entry may change the tree topology.
359 if (find_node(cc
, id
, NULL
) != ADDR_NULL
) {
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.
371 if (cc
->store_ptr
> (cc
->store_len
- LRU_ENTRY_LEN
)) {
373 * Evict tail. If the buffer has room for a single entry,
374 * then this may also be the head.
377 cc
->tail
= get_prev(cc
, x
);
378 if (cc
->tail
== ADDR_NULL
) {
379 cc
->head
= ADDR_NULL
;
381 set_next(cc
, cc
->tail
, ADDR_NULL
);
385 * Remove the node from the tree.
390 * Allocate room for new node.
393 cc
->store_ptr
+= LRU_ENTRY_LEN
;
397 * Find the emplacement for the new node, and link it.
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
);
405 * New entry becomes new list head. It may also become the list
406 * tail if the cache was empty at that point.
408 if (cc
->head
== ADDR_NULL
) {
411 set_prev(cc
, cc
->head
, x
);
413 set_prev(cc
, x
, ADDR_NULL
);
414 set_next(cc
, x
, cc
->head
);
418 * Fill data in the entry.
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
);
428 lru_load(const br_ssl_session_cache_class
**ctx
,
429 br_ssl_server_context
*server_ctx
,
430 br_ssl_session_parameters
*params
)
432 br_ssl_session_cache_lru
*cc
;
433 unsigned char id
[SESSION_ID_LEN
];
437 cc
= (br_ssl_session_cache_lru
*)ctx
;
438 if (!cc
->init_done
) {
441 mask_id(cc
, params
->session_id
, id
);
442 x
= find_node(cc
, id
, NULL
);
443 if (x
!= ADDR_NULL
) {
446 version
= br_dec16be(cc
->store
+ x
+ VERSION_OFF
);
449 * Entry is disabled, we pretend we did not find it.
450 * Notably, we don't move it to the front of the
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
,
463 * Found node is not at list head, so move
471 if (n
== ADDR_NULL
) {
476 set_prev(cc
, cc
->head
, x
);
477 set_next(cc
, x
, cc
->head
);
478 set_prev(cc
, x
, ADDR_NULL
);
486 static const br_ssl_session_cache_class lru_class
= {
487 sizeof(br_ssl_session_cache_lru
),
494 br_ssl_session_cache_lru_init(br_ssl_session_cache_lru
*cc
,
495 unsigned char *store
, size_t store_len
)
497 cc
->vtable
= &lru_class
;
499 cc
->store_len
= store_len
;
502 cc
->head
= ADDR_NULL
;
503 cc
->tail
= ADDR_NULL
;
504 cc
->root
= ADDR_NULL
;
507 /* see bearssl_ssl.h */
508 void br_ssl_session_cache_lru_forget(
509 br_ssl_session_cache_lru
*cc
, const unsigned char *id
)
511 unsigned char mid
[SESSION_ID_LEN
];
515 * If the cache is not initialised yet, then it is empty, and
516 * there is nothing to forget.
518 if (!cc
->init_done
) {
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
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.
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);