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 * We need to keep the tree balanced because an attacker could make
58 * handshakes, selecting some specific sessions (by reusing them) to
59 * try to make us make an imbalanced tree that makes lookups expensive
60 * (a denial-of-service attack that would persist as long as the cache
61 * remains, i.e. even after the attacker made all his connections).
62 * To do that, we replace the session ID (or the start of the session ID)
63 * with a HMAC value computed over the replaced part; the hash function
64 * implementation and the key are obtained from the server context upon
67 * Theoretically, an attacker could use the exact timing of the lookup
68 * to infer the current tree topology, and try to revive entries to make
69 * it as unbalanced as possible. However, since the session ID are
70 * chosen randomly by the server, and the attacker cannot see the
71 * indexing values and must thus rely on blind selection, it should be
72 * exponentially difficult for the attacker to maintain a large
75 #define SESSION_ID_LEN 32
76 #define MASTER_SECRET_LEN 48
78 #define SESSION_ID_OFF 0
79 #define MASTER_SECRET_OFF 32
80 #define VERSION_OFF 80
81 #define CIPHER_SUITE_OFF 82
82 #define LIST_PREV_OFF 84
83 #define LIST_NEXT_OFF 88
84 #define TREE_LEFT_OFF 92
85 #define TREE_RIGHT_OFF 96
87 #define LRU_ENTRY_LEN 100
89 #define ADDR_NULL ((uint32_t)-1)
91 #define GETSET(name, off) \
92 static inline uint32_t get_ ## name(br_ssl_session_cache_lru *cc, uint32_t x) \
94 return br_dec32be(cc->store + x + (off)); \
96 static inline void set_ ## name(br_ssl_session_cache_lru *cc, \
97 uint32_t x, uint32_t val) \
99 br_enc32be(cc->store + x + (off), val); \
102 GETSET(prev
, LIST_PREV_OFF
)
103 GETSET(next
, LIST_NEXT_OFF
)
104 GETSET(left
, TREE_LEFT_OFF
)
105 GETSET(right
, TREE_RIGHT_OFF
)
108 * Transform the session ID by replacing the first N bytes with a HMAC
109 * value computed over these bytes, using the random key K (the HMAC
110 * value is truncated if needed). HMAC will use the same hash function
111 * as the DRBG in the SSL server context, so with SHA-256, SHA-384,
112 * or SHA-1, depending on what is available.
114 * The risk of collision is considered too small to be a concern; and
115 * the impact of a collision is low (the handshake won't succeed). This
116 * risk is much lower than any transmission error, which would lead to
117 * the same consequences.
119 * Source and destination arrays msut be disjoint.
122 mask_id(br_ssl_session_cache_lru
*cc
,
123 const unsigned char *src
, unsigned char *dst
)
125 br_hmac_key_context hkc
;
128 memcpy(dst
, src
, SESSION_ID_LEN
);
129 br_hmac_key_init(&hkc
, cc
->hash
, cc
->index_key
, sizeof cc
->index_key
);
130 br_hmac_init(&hc
, &hkc
, SESSION_ID_LEN
);
131 br_hmac_update(&hc
, src
, SESSION_ID_LEN
);
132 br_hmac_out(&hc
, dst
);
136 * Find a node by ID. Returned value is the node address, or ADDR_NULL if
137 * the node is not found.
139 * If addr_link is not NULL, then '*addr_link' is set to the address of the
140 * last followed link. If the found node is the root, or if the tree is
141 * empty, then '*addr_link' is set to ADDR_NULL.
144 find_node(br_ssl_session_cache_lru
*cc
, const unsigned char *id
,
151 while (x
!= ADDR_NULL
) {
154 r
= memcmp(id
, cc
->store
+ x
+ SESSION_ID_OFF
, SESSION_ID_LEN
);
156 y
= x
+ TREE_LEFT_OFF
;
159 if (addr_link
!= NULL
) {
164 y
= x
+ TREE_RIGHT_OFF
;
165 x
= get_right(cc
, x
);
168 if (addr_link
!= NULL
) {
175 * For node x, find its replacement upon removal.
177 * -- If node x has no child, then this returns ADDR_NULL.
178 * -- Otherwise, if node x has a left child, then the replacement is the
179 * rightmost left-descendent.
180 * -- Otherwise, the replacement is the leftmost right-descendent.
182 * If a node is returned, then '*al' is set to the address of the field
183 * that points to that node. Otherwise (node x has no child), '*al' is
186 * Note that the replacement node, when found, is always a descendent
187 * of node 'x', so it cannot be the tree root. Thus, '*al' can be set
188 * to ADDR_NULL only when no node is found and ADDR_NULL is returned.
191 find_replacement_node(br_ssl_session_cache_lru
*cc
, uint32_t x
, uint32_t *al
)
195 y1
= get_left(cc
, x
);
196 if (y1
!= ADDR_NULL
) {
197 y2
= x
+ TREE_LEFT_OFF
;
201 z
= get_right(cc
, y1
);
202 if (z
== ADDR_NULL
) {
206 y2
= y1
+ TREE_RIGHT_OFF
;
210 y1
= get_right(cc
, x
);
211 if (y1
!= ADDR_NULL
) {
212 y2
= x
+ TREE_RIGHT_OFF
;
216 z
= get_left(cc
, y1
);
217 if (z
== ADDR_NULL
) {
221 y2
= y1
+ TREE_LEFT_OFF
;
230 * Set the link at address 'alx' to point to node 'x'. If 'alx' is
231 * ADDR_NULL, then this sets the tree root to 'x'.
234 set_link(br_ssl_session_cache_lru
*cc
, uint32_t alx
, uint32_t x
)
236 if (alx
== ADDR_NULL
) {
239 br_enc32be(cc
->store
+ alx
, x
);
244 * Remove node 'x' from the tree. This function shall not be called if
245 * node 'x' is not part of the tree.
248 remove_node(br_ssl_session_cache_lru
*cc
, uint32_t x
)
250 uint32_t alx
, y
, aly
;
256 * - If we remove the root, then the tree becomes empty.
258 * - If the removed node has no child, then we can simply remove
259 * it, with nothing else to do.
261 * - Otherwise, the removed node must be replaced by either its
262 * rightmost left-descendent, or its leftmost right-descendent.
263 * The replacement node itself must be removed from its current
264 * place. By definition, that replacement node has either no
265 * child, or at most a single child that will replace it in the
270 * Find node back and its ancestor link. If the node was the
271 * root, then alx is set to ADDR_NULL.
273 find_node(cc
, cc
->store
+ x
+ SESSION_ID_OFF
, &alx
);
276 * Find replacement node 'y', and 'aly' is set to the address of
277 * the link to that replacement node. If the removed node has no
278 * child, then both 'y' and 'aly' are set to ADDR_NULL.
280 y
= find_replacement_node(cc
, x
, &aly
);
282 if (y
!= ADDR_NULL
) {
286 * The unlinked replacement node may have one child (but
287 * not two) that takes its place.
290 if (z
== ADDR_NULL
) {
291 z
= get_right(cc
, y
);
293 set_link(cc
, aly
, z
);
296 * Link the replacement node in its new place, overwriting
297 * the current link to the node 'x' (which removes 'x').
299 set_link(cc
, alx
, y
);
302 * The replacement node adopts the left and right children
303 * of the removed node. Note that this also works even if
304 * the replacement node was a direct descendent of the
305 * removed node, since we unlinked it previously.
307 set_left(cc
, y
, get_left(cc
, x
));
308 set_right(cc
, y
, get_right(cc
, x
));
311 * No replacement, we simply unlink the node 'x'.
313 set_link(cc
, alx
, ADDR_NULL
);
318 lru_save(const br_ssl_session_cache_class
**ctx
,
319 br_ssl_server_context
*server_ctx
,
320 const br_ssl_session_parameters
*params
)
322 br_ssl_session_cache_lru
*cc
;
323 unsigned char id
[SESSION_ID_LEN
];
326 cc
= (br_ssl_session_cache_lru
*)ctx
;
329 * If the buffer is too small, we don't record anything. This
330 * test avoids problems in subsequent code.
332 if (cc
->store_len
< LRU_ENTRY_LEN
) {
337 * Upon the first save in a session cache instance, we obtain
338 * a random key for our indexing.
340 if (!cc
->init_done
) {
341 br_hmac_drbg_generate(&server_ctx
->eng
.rng
,
342 cc
->index_key
, sizeof cc
->index_key
);
343 cc
->hash
= br_hmac_drbg_get_hash(&server_ctx
->eng
.rng
);
346 mask_id(cc
, params
->session_id
, id
);
349 * Look for the node in the tree. If the same ID is already used,
350 * then reject it. This is a collision event, which should be
352 * Note: we do NOT record the emplacement here, because the
353 * removal of an entry may change the tree topology.
355 if (find_node(cc
, id
, NULL
) != ADDR_NULL
) {
360 * Find some room for the new parameters. If the cache is not
361 * full yet, add it to the end of the area and bump the pointer up.
362 * Otherwise, evict the list tail entry. Note that we already
363 * filtered out the case of a ridiculously small buffer that
364 * cannot hold any entry at all; thus, if there is no room for an
365 * extra entry, then the cache cannot be empty.
367 if (cc
->store_ptr
> (cc
->store_len
- LRU_ENTRY_LEN
)) {
369 * Evict tail. If the buffer has room for a single entry,
370 * then this may also be the head.
373 cc
->tail
= get_prev(cc
, x
);
374 if (cc
->tail
== ADDR_NULL
) {
375 cc
->head
= ADDR_NULL
;
377 set_next(cc
, cc
->tail
, ADDR_NULL
);
381 * Remove the node from the tree.
386 * Allocate room for new node.
389 cc
->store_ptr
+= LRU_ENTRY_LEN
;
393 * Find the emplacement for the new node, and link it.
395 find_node(cc
, id
, &alx
);
396 set_link(cc
, alx
, x
);
397 set_left(cc
, x
, ADDR_NULL
);
398 set_right(cc
, x
, ADDR_NULL
);
401 * New entry becomes new list head. It may also become the list
402 * tail if the cache was empty at that point.
404 if (cc
->head
== ADDR_NULL
) {
407 set_prev(cc
, cc
->head
, x
);
409 set_prev(cc
, x
, ADDR_NULL
);
410 set_next(cc
, x
, cc
->head
);
414 * Fill data in the entry.
416 memcpy(cc
->store
+ x
+ SESSION_ID_OFF
, id
, SESSION_ID_LEN
);
417 memcpy(cc
->store
+ x
+ MASTER_SECRET_OFF
,
418 params
->master_secret
, MASTER_SECRET_LEN
);
419 br_enc16be(cc
->store
+ x
+ VERSION_OFF
, params
->version
);
420 br_enc16be(cc
->store
+ x
+ CIPHER_SUITE_OFF
, params
->cipher_suite
);
424 lru_load(const br_ssl_session_cache_class
**ctx
,
425 br_ssl_server_context
*server_ctx
,
426 br_ssl_session_parameters
*params
)
428 br_ssl_session_cache_lru
*cc
;
429 unsigned char id
[SESSION_ID_LEN
];
433 cc
= (br_ssl_session_cache_lru
*)ctx
;
434 if (!cc
->init_done
) {
437 mask_id(cc
, params
->session_id
, id
);
438 x
= find_node(cc
, id
, NULL
);
439 if (x
!= ADDR_NULL
) {
440 params
->version
= br_dec16be(
441 cc
->store
+ x
+ VERSION_OFF
);
442 params
->cipher_suite
= br_dec16be(
443 cc
->store
+ x
+ CIPHER_SUITE_OFF
);
444 memcpy(params
->master_secret
,
445 cc
->store
+ x
+ MASTER_SECRET_OFF
,
449 * Found node is not at list head, so move
457 if (n
== ADDR_NULL
) {
462 set_prev(cc
, cc
->head
, x
);
463 set_next(cc
, x
, cc
->head
);
464 set_prev(cc
, x
, ADDR_NULL
);
472 static const br_ssl_session_cache_class lru_class
= {
473 sizeof(br_ssl_session_cache_lru
),
480 br_ssl_session_cache_lru_init(br_ssl_session_cache_lru
*cc
,
481 unsigned char *store
, size_t store_len
)
483 cc
->vtable
= &lru_class
;
485 cc
->store_len
= store_len
;
488 cc
->head
= ADDR_NULL
;
489 cc
->tail
= ADDR_NULL
;
490 cc
->root
= ADDR_NULL
;