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 guaranted, 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 balanced.
48 * master secret 48 bytes
49 * protocol version 2 bytes (big endian)
50 * cipher suite 2 bytes (big endian)
51 * list prev 4 bytes (big endian)
52 * list next 4 bytes (big endian)
53 * tree left child 4 bytes (big endian)
54 * tree right child 4 bytes (big endian)
55 * tree node colour 1 byte (0 = red, 1 = black)
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 #define SESSION_ID_LEN 32
68 #define MASTER_SECRET_LEN 48
70 #define SESSION_ID_OFF 0
71 #define MASTER_SECRET_OFF 32
72 #define VERSION_OFF 80
73 #define CIPHER_SUITE_OFF 82
74 #define LIST_PREV_OFF 84
75 #define LIST_NEXT_OFF 88
76 #define TREE_LEFT_OFF 92
77 #define TREE_RIGHT_OFF 96
79 #define LRU_ENTRY_LEN 100
81 #define ADDR_NULL ((uint32_t)-1)
83 #define GETSET(name, off) \
84 static inline uint32_t get_ ## name(br_ssl_session_cache_lru *cc, uint32_t x) \
86 return br_dec32be(cc->store + x + (off)); \
88 static inline void set_ ## name(br_ssl_session_cache_lru *cc, \
89 uint32_t x, uint32_t val) \
91 br_enc32be(cc->store + x + (off), val); \
94 GETSET(prev
, LIST_PREV_OFF
)
95 GETSET(next
, LIST_NEXT_OFF
)
96 GETSET(left
, TREE_LEFT_OFF
)
97 GETSET(right
, TREE_RIGHT_OFF
)
100 * Transform the session ID by replacing the first N bytes with a HMAC
101 * value computed over these bytes, using the random key K (the HMAC
102 * value is truncated if needed). HMAC will use the same hash function
103 * as the DRBG in the SSL server context, so with SHA-256, SHA-384,
104 * or SHA-1, depending on what is available.
106 * The risk of collision is considered too small to be a concern; and
107 * the impact of a collision is low (the handshake won't succeed). This
108 * risk is much lower than any transmission error, which would lead to
109 * the same consequences.
112 mask_id(br_ssl_session_cache_lru
*cc
,
113 const unsigned char *src
, unsigned char *dst
)
115 br_hmac_key_context hkc
;
118 memcpy(dst
, src
, SESSION_ID_LEN
);
119 br_hmac_key_init(&hkc
, cc
->hash
, cc
->index_key
, sizeof cc
->index_key
);
120 br_hmac_init(&hc
, &hkc
, SESSION_ID_LEN
);
121 br_hmac_update(&hc
, src
, SESSION_ID_LEN
);
122 br_hmac_out(&hc
, dst
);
126 * Find a node by ID. Returned value is the node address, or ADDR_NULL if
127 * the node is not found.
129 * If addr_link is not NULL, then '*addr_link' is set to the address of the
130 * last followed link. If the found node is the root, then '*addr_link' is
134 find_node(br_ssl_session_cache_lru
*cc
, const unsigned char *id
,
141 while (x
!= ADDR_NULL
) {
144 r
= memcmp(id
, cc
->store
+ x
+ SESSION_ID_OFF
, SESSION_ID_LEN
);
146 y
= x
+ TREE_LEFT_OFF
;
149 if (addr_link
!= NULL
) {
154 y
= x
+ TREE_RIGHT_OFF
;
155 x
= get_right(cc
, x
);
158 if (addr_link
!= NULL
) {
165 * For node x, find its replacement upon removal.
167 * -- If node x has no child, then this returns ADDR_NULL.
168 * -- Otherwise, if node x has a left child, then the replacement is the
169 * rightmost left-descendent.
170 * -- Otherwise, the replacement is the leftmost right-descendent.
172 * If a node is returned, then '*al' is set to the address of the field
173 * that points to that node.
176 find_replacement_node(br_ssl_session_cache_lru
*cc
, uint32_t x
, uint32_t *al
)
180 y1
= get_left(cc
, x
);
181 if (y1
!= ADDR_NULL
) {
182 y2
= x
+ TREE_LEFT_OFF
;
186 z
= get_right(cc
, y1
);
187 if (z
== ADDR_NULL
) {
191 y2
= y1
+ TREE_RIGHT_OFF
;
195 y1
= get_right(cc
, x
);
196 if (y1
!= ADDR_NULL
) {
197 y2
= x
+ TREE_RIGHT_OFF
;
201 z
= get_left(cc
, y1
);
202 if (z
== ADDR_NULL
) {
206 y2
= y1
+ TREE_LEFT_OFF
;
215 set_link(br_ssl_session_cache_lru
*cc
, uint32_t alx
, uint32_t x
)
217 if (alx
== ADDR_NULL
) {
220 br_enc32be(cc
->store
+ alx
, x
);
225 remove_node(br_ssl_session_cache_lru
*cc
, uint32_t x
)
227 uint32_t alx
, y
, aly
;
230 * Find node back and its ancestor link.
232 find_node(cc
, cc
->store
+ x
+ SESSION_ID_OFF
, &alx
);
235 * Find replacement node.
237 y
= find_replacement_node(cc
, x
, &aly
);
240 * Unlink replacement node.
242 set_link(cc
, aly
, ADDR_NULL
);
245 * Link the replacement node in its new place.
247 set_link(cc
, alx
, y
);
251 lru_save(const br_ssl_session_cache_class
**ctx
,
252 br_ssl_server_context
*server_ctx
,
253 const br_ssl_session_parameters
*params
)
255 br_ssl_session_cache_lru
*cc
;
256 unsigned char id
[SESSION_ID_LEN
];
259 cc
= (br_ssl_session_cache_lru
*)ctx
;
262 * If the buffer is too small, we don't record anything. This
263 * test avoids problems in subsequent code.
265 if (cc
->store_len
< LRU_ENTRY_LEN
) {
270 * Upon the first save in a session cache instance, we obtain
271 * a random key for our indexing.
273 if (!cc
->init_done
) {
274 br_hmac_drbg_generate(&server_ctx
->eng
.rng
,
275 cc
->index_key
, sizeof cc
->index_key
);
276 cc
->hash
= br_hmac_drbg_get_hash(&server_ctx
->eng
.rng
);
279 mask_id(cc
, params
->session_id
, id
);
282 * Look for the node in the tree. If the same ID is already used,
283 * then reject it. This is a collision event, which should be
285 * Note: we do NOT record the emplacement here, because the
286 * removal of an entry may change the tree topology.
288 if (find_node(cc
, id
, NULL
) != ADDR_NULL
) {
293 * Find some room for the new parameters. If the cache is not
294 * full yet, add it to the end of the area and bump the pointer up.
295 * Otherwise, evict the list tail entry. Note that we already
296 * filtered out the case of a ridiculously small buffer that
297 * cannot hold any entry at all; thus, if there is no room for an
298 * extra entry, then the cache cannot be empty.
300 if (cc
->store_ptr
> (cc
->store_len
- LRU_ENTRY_LEN
)) {
302 * Evict tail. If the buffer has room for a single entry,
303 * then this may also be the head.
306 cc
->tail
= get_prev(cc
, x
);
307 if (cc
->tail
== ADDR_NULL
) {
308 cc
->head
= ADDR_NULL
;
310 set_next(cc
, cc
->tail
, ADDR_NULL
);
314 * Remove the node from the tree.
319 * Allocate room for new node.
322 cc
->store_ptr
+= LRU_ENTRY_LEN
;
326 * Find the emplacement for the new node, and link it.
328 find_node(cc
, id
, &alx
);
329 set_link(cc
, alx
, x
);
330 set_left(cc
, x
, ADDR_NULL
);
331 set_right(cc
, x
, ADDR_NULL
);
334 * New entry becomes new list head. It may also become the list
335 * tail if the cache was empty at that point.
337 if (cc
->head
== ADDR_NULL
) {
340 set_prev(cc
, cc
->head
, x
);
342 set_prev(cc
, x
, ADDR_NULL
);
343 set_next(cc
, x
, cc
->head
);
347 * Fill data in the entry.
349 memcpy(cc
->store
+ x
+ SESSION_ID_OFF
, id
, SESSION_ID_LEN
);
350 memcpy(cc
->store
+ x
+ MASTER_SECRET_OFF
,
351 params
->master_secret
, MASTER_SECRET_LEN
);
352 br_enc16be(cc
->store
+ x
+ VERSION_OFF
, params
->version
);
353 br_enc16be(cc
->store
+ x
+ CIPHER_SUITE_OFF
, params
->cipher_suite
);
357 lru_load(const br_ssl_session_cache_class
**ctx
,
358 br_ssl_server_context
*server_ctx
,
359 br_ssl_session_parameters
*params
)
361 br_ssl_session_cache_lru
*cc
;
362 unsigned char id
[SESSION_ID_LEN
];
366 cc
= (br_ssl_session_cache_lru
*)ctx
;
367 if (!cc
->init_done
) {
370 mask_id(cc
, params
->session_id
, id
);
371 x
= find_node(cc
, id
, NULL
);
372 if (x
!= ADDR_NULL
) {
373 params
->version
= br_dec16be(
374 cc
->store
+ x
+ VERSION_OFF
);
375 params
->cipher_suite
= br_dec16be(
376 cc
->store
+ x
+ CIPHER_SUITE_OFF
);
377 memcpy(params
->master_secret
,
378 cc
->store
+ x
+ MASTER_SECRET_OFF
,
382 * Found node is not at list head, so move
390 if (n
== ADDR_NULL
) {
395 set_prev(cc
, cc
->head
, x
);
396 set_next(cc
, x
, cc
->head
);
397 set_prev(cc
, x
, ADDR_NULL
);
405 static const br_ssl_session_cache_class lru_class
= {
406 sizeof(br_ssl_session_cache_lru
),
413 br_ssl_session_cache_lru_init(br_ssl_session_cache_lru
*cc
,
414 unsigned char *store
, size_t store_len
)
416 cc
->vtable
= &lru_class
;
418 cc
->store_len
= store_len
;
421 cc
->head
= ADDR_NULL
;
422 cc
->tail
= ADDR_NULL
;
423 cc
->root
= ADDR_NULL
;