1 // SPDX-License-Identifier: BSD-2-Clause
2 /*
3 * Copyright (c) 2017, Linaro Limited
4 */
5
6 #include <assert.h>
7 #include <config.h>
8 #include <crypto/crypto.h>
9 #include <initcall.h>
10 #include <kernel/tee_common_otp.h>
11 #include <stdlib.h>
12 #include <string_ext.h>
13 #include <string.h>
14 #include <tee/fs_htree.h>
15 #include <tee/tee_fs_key_manager.h>
16 #include <tee/tee_fs_rpc.h>
17 #include <utee_defines.h>
18 #include <util.h>
19
20 #define TEE_FS_HTREE_CHIP_ID_SIZE 32
21 #define TEE_FS_HTREE_HASH_ALG TEE_ALG_SHA256
22 #define TEE_FS_HTREE_TSK_SIZE TEE_FS_HTREE_HASH_SIZE
23 #define TEE_FS_HTREE_ENC_ALG TEE_ALG_AES_ECB_NOPAD
24 #define TEE_FS_HTREE_ENC_SIZE TEE_AES_BLOCK_SIZE
25 #define TEE_FS_HTREE_SSK_SIZE TEE_FS_HTREE_HASH_SIZE
26
27 #define TEE_FS_HTREE_AUTH_ENC_ALG TEE_ALG_AES_GCM
28 #define TEE_FS_HTREE_HMAC_ALG TEE_ALG_HMAC_SHA256
29
30 #define BLOCK_NUM_TO_NODE_ID(num) ((num) + 1)
31
32 #define NODE_ID_TO_BLOCK_NUM(id) ((id) - 1)
33
34 /*
35 * The hash tree is implemented as a binary tree with the purpose to ensure
36 * integrity of the data in the nodes. The data in the nodes their turn
37 * provides both integrity and confidentiality of the data blocks.
38 *
39 * The hash tree is saved in a file as:
40 * +----------------------------+
41 * | htree_image.0 |
42 * | htree_image.1 |
43 * +----------------------------+
44 * | htree_node_image.1.0 |
45 * | htree_node_image.1.1 |
46 * +----------------------------+
47 * | htree_node_image.2.0 |
48 * | htree_node_image.2.1 |
49 * +----------------------------+
50 * | htree_node_image.3.0 |
51 * | htree_node_image.3.1 |
52 * +----------------------------+
53 * | htree_node_image.4.0 |
54 * | htree_node_image.4.1 |
55 * +----------------------------+
56 * ...
57 *
58 * htree_image is the header of the file, there's two instances of it. One
59 * which is committed and the other is used when updating the file. Which
60 * is committed is indicated by the "counter" field, the one with the
61 * largest value is selected.
62 *
63 * htree_node_image is a node in the hash tree, each node has two instances
64 * which is committed is decided by the parent node .flag bit
65 * HTREE_NODE_COMMITTED_CHILD. Which version is the committed version of
66 * node 1 is determined by the by the lowest bit of the counter field in
67 * the header.
68 *
69 * Note that nodes start counting at 1 while blocks at 0, this means that
70 * block 0 is represented by node 1.
71 *
72 * Where different elements are stored in the file is managed by the file
73 * system.
74 */
75
76 #define HTREE_NODE_COMMITTED_BLOCK BIT32(0)
77 /* n is 0 or 1 */
78 #define HTREE_NODE_COMMITTED_CHILD(n) BIT32(1 + (n))
79
80 struct htree_node {
81 size_t id;
82 bool dirty;
83 bool block_updated;
84 struct tee_fs_htree_node_image node;
85 struct htree_node *parent;
86 struct htree_node *child[2];
87 };
88
89 struct tee_fs_htree {
90 struct htree_node root;
91 struct tee_fs_htree_image head;
92 uint8_t fek[TEE_FS_HTREE_FEK_SIZE];
93 struct tee_fs_htree_imeta imeta;
94 bool dirty;
95 const TEE_UUID *uuid;
96 const struct tee_fs_htree_storage *stor;
97 void *stor_aux;
98 };
99
100 struct traverse_arg;
101 typedef TEE_Result (*traverse_cb_t)(struct traverse_arg *targ,
102 struct htree_node *node);
103 struct traverse_arg {
104 struct tee_fs_htree *ht;
105 traverse_cb_t cb;
106 void *arg;
107 };
108
rpc_read(struct tee_fs_htree * ht,enum tee_fs_htree_type type,size_t idx,size_t vers,void * data,size_t dlen)109 static TEE_Result rpc_read(struct tee_fs_htree *ht, enum tee_fs_htree_type type,
110 size_t idx, size_t vers, void *data, size_t dlen)
111 {
112 TEE_Result res;
113 struct tee_fs_rpc_operation op;
114 size_t bytes;
115 void *p;
116
117 res = ht->stor->rpc_read_init(ht->stor_aux, &op, type, idx, vers, &p);
118 if (res != TEE_SUCCESS)
119 return res;
120
121 res = ht->stor->rpc_read_final(&op, &bytes);
122 if (res != TEE_SUCCESS)
123 return res;
124
125 if (bytes != dlen)
126 return TEE_ERROR_CORRUPT_OBJECT;
127
128 memcpy(data, p, dlen);
129 return TEE_SUCCESS;
130 }
131
rpc_read_head(struct tee_fs_htree * ht,size_t vers,struct tee_fs_htree_image * head)132 static TEE_Result rpc_read_head(struct tee_fs_htree *ht, size_t vers,
133 struct tee_fs_htree_image *head)
134 {
135 return rpc_read(ht, TEE_FS_HTREE_TYPE_HEAD, 0, vers,
136 head, sizeof(*head));
137 }
138
rpc_read_node(struct tee_fs_htree * ht,size_t node_id,size_t vers,struct tee_fs_htree_node_image * node)139 static TEE_Result rpc_read_node(struct tee_fs_htree *ht, size_t node_id,
140 size_t vers,
141 struct tee_fs_htree_node_image *node)
142 {
143 return rpc_read(ht, TEE_FS_HTREE_TYPE_NODE, node_id - 1, vers,
144 node, sizeof(*node));
145 }
146
rpc_write(struct tee_fs_htree * ht,enum tee_fs_htree_type type,size_t idx,size_t vers,const void * data,size_t dlen)147 static TEE_Result rpc_write(struct tee_fs_htree *ht,
148 enum tee_fs_htree_type type, size_t idx,
149 size_t vers, const void *data, size_t dlen)
150 {
151 TEE_Result res;
152 struct tee_fs_rpc_operation op;
153 void *p;
154
155 res = ht->stor->rpc_write_init(ht->stor_aux, &op, type, idx, vers, &p);
156 if (res != TEE_SUCCESS)
157 return res;
158
159 memcpy(p, data, dlen);
160 return ht->stor->rpc_write_final(&op);
161 }
162
rpc_write_head(struct tee_fs_htree * ht,size_t vers,const struct tee_fs_htree_image * head)163 static TEE_Result rpc_write_head(struct tee_fs_htree *ht, size_t vers,
164 const struct tee_fs_htree_image *head)
165 {
166 return rpc_write(ht, TEE_FS_HTREE_TYPE_HEAD, 0, vers,
167 head, sizeof(*head));
168 }
169
rpc_write_node(struct tee_fs_htree * ht,size_t node_id,size_t vers,const struct tee_fs_htree_node_image * node)170 static TEE_Result rpc_write_node(struct tee_fs_htree *ht, size_t node_id,
171 size_t vers,
172 const struct tee_fs_htree_node_image *node)
173 {
174 return rpc_write(ht, TEE_FS_HTREE_TYPE_NODE, node_id - 1, vers,
175 node, sizeof(*node));
176 }
177
traverse_post_order(struct traverse_arg * targ,struct htree_node * node)178 static TEE_Result traverse_post_order(struct traverse_arg *targ,
179 struct htree_node *node)
180 {
181 TEE_Result res;
182
183 /*
184 * This function is recursing but not very deep, only with Log(N)
185 * maximum depth.
186 */
187
188 if (!node)
189 return TEE_SUCCESS;
190
191 res = traverse_post_order(targ, node->child[0]);
192 if (res != TEE_SUCCESS)
193 return res;
194
195 res = traverse_post_order(targ, node->child[1]);
196 if (res != TEE_SUCCESS)
197 return res;
198
199 return targ->cb(targ, node);
200 }
201
htree_traverse_post_order(struct tee_fs_htree * ht,traverse_cb_t cb,void * arg)202 static TEE_Result htree_traverse_post_order(struct tee_fs_htree *ht,
203 traverse_cb_t cb, void *arg)
204 {
205 struct traverse_arg targ = { ht, cb, arg };
206
207 return traverse_post_order(&targ, &ht->root);
208 }
209
node_id_to_level(size_t node_id)210 static size_t node_id_to_level(size_t node_id)
211 {
212 assert(node_id && node_id < UINT_MAX);
213 /* Calculate level of the node, root node (1) has level 1 */
214 return sizeof(unsigned int) * 8 - __builtin_clz(node_id);
215 }
216
find_closest_node(struct tee_fs_htree * ht,size_t node_id)217 static struct htree_node *find_closest_node(struct tee_fs_htree *ht,
218 size_t node_id)
219 {
220 struct htree_node *node = &ht->root;
221 size_t level = node_id_to_level(node_id);
222 size_t n;
223
224 /* n = 1 because root node is level 1 */
225 for (n = 1; n < level; n++) {
226 struct htree_node *child;
227 size_t bit_idx;
228
229 /*
230 * The difference between levels of the current node and
231 * the node we're looking for tells which bit decides
232 * direction in the tree.
233 *
234 * As the first bit has index 0 we'll subtract 1
235 */
236 bit_idx = level - n - 1;
237 child = node->child[((node_id >> bit_idx) & 1)];
238 if (!child)
239 return node;
240 node = child;
241 }
242
243 return node;
244 }
245
find_node(struct tee_fs_htree * ht,size_t node_id)246 static struct htree_node *find_node(struct tee_fs_htree *ht, size_t node_id)
247 {
248 struct htree_node *node = find_closest_node(ht, node_id);
249
250 if (node && node->id == node_id)
251 return node;
252 return NULL;
253 }
254
get_node(struct tee_fs_htree * ht,bool create,size_t node_id,struct htree_node ** node_ret)255 static TEE_Result get_node(struct tee_fs_htree *ht, bool create,
256 size_t node_id, struct htree_node **node_ret)
257 {
258 struct htree_node *node;
259 struct htree_node *nc;
260 size_t n;
261
262 node = find_closest_node(ht, node_id);
263 if (!node)
264 return TEE_ERROR_GENERIC;
265 if (node->id == node_id)
266 goto ret_node;
267
268 /*
269 * Trying to read beyond end of file should be caught earlier than
270 * here.
271 */
272 if (!create)
273 return TEE_ERROR_GENERIC;
274
275 /*
276 * Add missing nodes, some nodes may already be there. When we've
277 * processed the range all nodes up to node_id will be in the tree.
278 */
279 for (n = node->id + 1; n <= node_id; n++) {
280 node = find_closest_node(ht, n);
281 if (node->id == n)
282 continue;
283 /* Node id n should be a child of node */
284 assert((n >> 1) == node->id);
285 assert(!node->child[n & 1]);
286
287 nc = calloc(1, sizeof(*nc));
288 if (!nc)
289 return TEE_ERROR_OUT_OF_MEMORY;
290 nc->id = n;
291 nc->parent = node;
292 node->child[n & 1] = nc;
293 node = nc;
294 }
295
296 if (node->id > ht->imeta.max_node_id)
297 ht->imeta.max_node_id = node->id;
298
299 ret_node:
300 *node_ret = node;
301 return TEE_SUCCESS;
302 }
303
get_idx_from_counter(uint32_t counter0,uint32_t counter1)304 static int get_idx_from_counter(uint32_t counter0, uint32_t counter1)
305 {
306 if (!(counter0 & 1)) {
307 if (!(counter1 & 1))
308 return 0;
309 if (counter0 > counter1)
310 return 0;
311 else
312 return 1;
313 }
314
315 if (counter1 & 1)
316 return 1;
317 else
318 return -1;
319 }
320
init_head_from_data(struct tee_fs_htree * ht,const uint8_t * hash,uint32_t min_counter)321 static TEE_Result init_head_from_data(struct tee_fs_htree *ht,
322 const uint8_t *hash, uint32_t min_counter)
323 {
324 TEE_Result res;
325 int idx;
326
327 if (hash) {
328 for (idx = 0;; idx++) {
329 res = rpc_read_node(ht, 1, idx, &ht->root.node);
330 if (res != TEE_SUCCESS)
331 return res;
332
333 if (!memcmp(ht->root.node.hash, hash,
334 sizeof(ht->root.node.hash))) {
335 res = rpc_read_head(ht, idx, &ht->head);
336 if (res != TEE_SUCCESS)
337 return res;
338 break;
339 }
340
341 if (idx)
342 return TEE_ERROR_CORRUPT_OBJECT;
343 }
344 } else {
345 struct tee_fs_htree_image head[2];
346
347 for (idx = 0; idx < 2; idx++) {
348 res = rpc_read_head(ht, idx, head + idx);
349 if (res != TEE_SUCCESS)
350 return res;
351 }
352
353 idx = get_idx_from_counter(head[0].counter, head[1].counter);
354 if (idx < 0)
355 return TEE_ERROR_SECURITY;
356
357 res = rpc_read_node(ht, 1, idx, &ht->root.node);
358 if (res != TEE_SUCCESS)
359 return res;
360
361 ht->head = head[idx];
362 }
363
364 if (ht->head.counter < min_counter)
365 return TEE_ERROR_SECURITY;
366
367 ht->root.id = 1;
368
369 return TEE_SUCCESS;
370 }
371
init_tree_from_data(struct tee_fs_htree * ht)372 static TEE_Result init_tree_from_data(struct tee_fs_htree *ht)
373 {
374 TEE_Result res;
375 struct tee_fs_htree_node_image node_image;
376 struct htree_node *node;
377 struct htree_node *nc;
378 size_t committed_version;
379 size_t node_id = 2;
380
381 while (node_id <= ht->imeta.max_node_id) {
382 node = find_node(ht, node_id >> 1);
383 if (!node)
384 return TEE_ERROR_GENERIC;
385 committed_version = !!(node->node.flags &
386 HTREE_NODE_COMMITTED_CHILD(node_id & 1));
387
388 res = rpc_read_node(ht, node_id, committed_version,
389 &node_image);
390 if (res != TEE_SUCCESS)
391 return res;
392
393 res = get_node(ht, true, node_id, &nc);
394 if (res != TEE_SUCCESS)
395 return res;
396 nc->node = node_image;
397 node_id++;
398 }
399
400 return TEE_SUCCESS;
401 }
402
calc_node_hash(struct htree_node * node,struct tee_fs_htree_meta * meta,void * ctx,uint8_t * digest)403 static TEE_Result calc_node_hash(struct htree_node *node,
404 struct tee_fs_htree_meta *meta, void *ctx,
405 uint8_t *digest)
406 {
407 TEE_Result res;
408 uint8_t *ndata = (uint8_t *)&node->node + sizeof(node->node.hash);
409 size_t nsize = sizeof(node->node) - sizeof(node->node.hash);
410
411 res = crypto_hash_init(ctx);
412 if (res != TEE_SUCCESS)
413 return res;
414
415 res = crypto_hash_update(ctx, ndata, nsize);
416 if (res != TEE_SUCCESS)
417 return res;
418
419 if (meta) {
420 res = crypto_hash_update(ctx, (void *)meta, sizeof(*meta));
421 if (res != TEE_SUCCESS)
422 return res;
423 }
424
425 if (node->child[0]) {
426 res = crypto_hash_update(ctx, node->child[0]->node.hash,
427 sizeof(node->child[0]->node.hash));
428 if (res != TEE_SUCCESS)
429 return res;
430 }
431
432 if (node->child[1]) {
433 res = crypto_hash_update(ctx, node->child[1]->node.hash,
434 sizeof(node->child[1]->node.hash));
435 if (res != TEE_SUCCESS)
436 return res;
437 }
438
439 return crypto_hash_final(ctx, digest, TEE_FS_HTREE_HASH_SIZE);
440 }
441
authenc_init(void ** ctx_ret,TEE_OperationMode mode,struct tee_fs_htree * ht,struct tee_fs_htree_node_image * ni,size_t payload_len)442 static TEE_Result authenc_init(void **ctx_ret, TEE_OperationMode mode,
443 struct tee_fs_htree *ht,
444 struct tee_fs_htree_node_image *ni,
445 size_t payload_len)
446 {
447 TEE_Result res = TEE_SUCCESS;
448 const uint32_t alg = TEE_FS_HTREE_AUTH_ENC_ALG;
449 void *ctx;
450 size_t aad_len = TEE_FS_HTREE_FEK_SIZE + TEE_FS_HTREE_IV_SIZE;
451 uint8_t *iv;
452
453 if (ni) {
454 iv = ni->iv;
455 } else {
456 iv = ht->head.iv;
457 aad_len += sizeof(ht->head.counter);
458
459 /*
460 * With CFG_REE_FS_HTREE_HASH_SIZE_COMPAT, hash data passed
461 * for AAD is truncated to TEE_FS_HTREE_FEK_SIZE bytes so
462 * use the correct size aad_len computation.
463 */
464 if (IS_ENABLED(CFG_REE_FS_HTREE_HASH_SIZE_COMPAT))
465 aad_len += TEE_FS_HTREE_FEK_SIZE;
466 else
467 aad_len += TEE_FS_HTREE_HASH_SIZE;
468 }
469
470 if (mode == TEE_MODE_ENCRYPT) {
471 res = crypto_rng_read(iv, TEE_FS_HTREE_IV_SIZE);
472 if (res != TEE_SUCCESS)
473 return res;
474 }
475
476 res = crypto_authenc_alloc_ctx(&ctx, alg);
477 if (res != TEE_SUCCESS)
478 return res;
479
480 res = crypto_authenc_init(ctx, mode, ht->fek, TEE_FS_HTREE_FEK_SIZE, iv,
481 TEE_FS_HTREE_IV_SIZE, TEE_FS_HTREE_TAG_SIZE,
482 aad_len, payload_len);
483 if (res != TEE_SUCCESS)
484 goto err_free;
485
486 if (!ni) {
487 size_t hash_size = TEE_FS_HTREE_HASH_SIZE;
488
489 if (IS_ENABLED(CFG_REE_FS_HTREE_HASH_SIZE_COMPAT))
490 hash_size = TEE_FS_HTREE_FEK_SIZE;
491
492 res = crypto_authenc_update_aad(ctx, mode, ht->root.node.hash,
493 hash_size);
494 if (res != TEE_SUCCESS)
495 goto err;
496
497 res = crypto_authenc_update_aad(ctx, mode,
498 (void *)&ht->head.counter,
499 sizeof(ht->head.counter));
500 if (res != TEE_SUCCESS)
501 goto err;
502 }
503
504 res = crypto_authenc_update_aad(ctx, mode, ht->head.enc_fek,
505 TEE_FS_HTREE_FEK_SIZE);
506 if (res != TEE_SUCCESS)
507 goto err;
508
509 res = crypto_authenc_update_aad(ctx, mode, iv, TEE_FS_HTREE_IV_SIZE);
510 if (res != TEE_SUCCESS)
511 goto err;
512
513 *ctx_ret = ctx;
514
515 return TEE_SUCCESS;
516 err:
517 crypto_authenc_final(ctx);
518 err_free:
519 crypto_authenc_free_ctx(ctx);
520 return res;
521 }
522
authenc_decrypt_final(void * ctx,const uint8_t * tag,const void * crypt,size_t len,void * plain)523 static TEE_Result authenc_decrypt_final(void *ctx, const uint8_t *tag,
524 const void *crypt, size_t len,
525 void *plain)
526 {
527 TEE_Result res;
528 size_t out_size = len;
529
530 res = crypto_authenc_dec_final(ctx, crypt, len, plain, &out_size, tag,
531 TEE_FS_HTREE_TAG_SIZE);
532 crypto_authenc_final(ctx);
533 crypto_authenc_free_ctx(ctx);
534
535 if (res == TEE_SUCCESS && out_size != len)
536 return TEE_ERROR_GENERIC;
537 if (res == TEE_ERROR_MAC_INVALID)
538 return TEE_ERROR_CORRUPT_OBJECT;
539
540 return res;
541 }
542
authenc_encrypt_final(void * ctx,uint8_t * tag,const void * plain,size_t len,void * crypt)543 static TEE_Result authenc_encrypt_final(void *ctx, uint8_t *tag,
544 const void *plain, size_t len,
545 void *crypt)
546 {
547 TEE_Result res;
548 size_t out_size = len;
549 size_t out_tag_size = TEE_FS_HTREE_TAG_SIZE;
550
551 res = crypto_authenc_enc_final(ctx, plain, len, crypt, &out_size, tag,
552 &out_tag_size);
553 crypto_authenc_final(ctx);
554 crypto_authenc_free_ctx(ctx);
555
556 if (res == TEE_SUCCESS &&
557 (out_size != len || out_tag_size != TEE_FS_HTREE_TAG_SIZE))
558 return TEE_ERROR_GENERIC;
559
560 return res;
561 }
562
verify_root(struct tee_fs_htree * ht)563 static TEE_Result verify_root(struct tee_fs_htree *ht)
564 {
565 TEE_Result res;
566 void *ctx;
567
568 res = tee_fs_fek_crypt(ht->uuid, TEE_MODE_DECRYPT, ht->head.enc_fek,
569 sizeof(ht->fek), ht->fek);
570 if (res != TEE_SUCCESS)
571 return res;
572
573 res = authenc_init(&ctx, TEE_MODE_DECRYPT, ht, NULL, sizeof(ht->imeta));
574 if (res != TEE_SUCCESS)
575 return res;
576
577 return authenc_decrypt_final(ctx, ht->head.tag, ht->head.imeta,
578 sizeof(ht->imeta), &ht->imeta);
579 }
580
verify_node(struct traverse_arg * targ,struct htree_node * node)581 static TEE_Result verify_node(struct traverse_arg *targ,
582 struct htree_node *node)
583 {
584 void *ctx = targ->arg;
585 TEE_Result res;
586 uint8_t digest[TEE_FS_HTREE_HASH_SIZE];
587
588 if (node->parent)
589 res = calc_node_hash(node, NULL, ctx, digest);
590 else
591 res = calc_node_hash(node, &targ->ht->imeta.meta, ctx, digest);
592 if (res == TEE_SUCCESS &&
593 consttime_memcmp(digest, node->node.hash, sizeof(digest)))
594 return TEE_ERROR_CORRUPT_OBJECT;
595
596 return res;
597 }
598
verify_tree(struct tee_fs_htree * ht)599 static TEE_Result verify_tree(struct tee_fs_htree *ht)
600 {
601 TEE_Result res;
602 void *ctx;
603
604 res = crypto_hash_alloc_ctx(&ctx, TEE_FS_HTREE_HASH_ALG);
605 if (res != TEE_SUCCESS)
606 return res;
607
608 res = htree_traverse_post_order(ht, verify_node, ctx);
609 crypto_hash_free_ctx(ctx);
610
611 return res;
612 }
613
init_root_node(struct tee_fs_htree * ht)614 static TEE_Result init_root_node(struct tee_fs_htree *ht)
615 {
616 TEE_Result res;
617 void *ctx;
618
619 res = crypto_hash_alloc_ctx(&ctx, TEE_FS_HTREE_HASH_ALG);
620 if (res != TEE_SUCCESS)
621 return res;
622
623 ht->root.id = 1;
624 ht->root.dirty = true;
625
626 res = calc_node_hash(&ht->root, &ht->imeta.meta, ctx,
627 ht->root.node.hash);
628 crypto_hash_free_ctx(ctx);
629
630 return res;
631 }
632
create_and_sync(struct tee_fs_htree ** ht_arg,uint8_t * hash,uint32_t min_counter)633 static TEE_Result create_and_sync(struct tee_fs_htree **ht_arg,
634 uint8_t *hash,
635 uint32_t min_counter)
636 {
637 TEE_Result res = TEE_ERROR_GENERIC;
638 struct tee_fs_htree *ht = *ht_arg;
639 const struct tee_fs_htree_image dummy_head = {
640 .counter = min_counter,
641 };
642
643 if (!ht)
644 return TEE_ERROR_GENERIC;
645
646 res = crypto_rng_read(ht->fek, sizeof(ht->fek));
647 if (res != TEE_SUCCESS)
648 return res;
649
650 res = tee_fs_fek_crypt(ht->uuid, TEE_MODE_ENCRYPT, ht->fek,
651 sizeof(ht->fek), ht->head.enc_fek);
652 if (res != TEE_SUCCESS)
653 return res;
654
655 res = init_root_node(ht);
656 if (res != TEE_SUCCESS)
657 return res;
658
659 ht->dirty = true;
660 res = tee_fs_htree_sync_to_storage(ht_arg, hash, NULL);
661 if (res != TEE_SUCCESS)
662 return res;
663
664 return rpc_write_head(*ht_arg, 0, &dummy_head);
665 }
666
ht_head_is_partially_done(const struct tee_fs_htree_image * head)667 static bool ht_head_is_partially_done(const struct tee_fs_htree_image *head)
668 {
669 uint8_t zero_tag[TEE_FS_HTREE_TAG_SIZE] = {0};
670
671 return head->counter == 0 &&
672 !memcmp(head->tag, zero_tag, sizeof(head->tag));
673 }
674
tee_fs_htree_open(bool create,uint8_t * hash,uint32_t min_counter,const TEE_UUID * uuid,const struct tee_fs_htree_storage * stor,void * stor_aux,struct tee_fs_htree ** ht_ret)675 TEE_Result tee_fs_htree_open(bool create, uint8_t *hash, uint32_t min_counter,
676 const TEE_UUID *uuid,
677 const struct tee_fs_htree_storage *stor,
678 void *stor_aux, struct tee_fs_htree **ht_ret)
679 {
680 TEE_Result res;
681 struct tee_fs_htree *ht = calloc(1, sizeof(*ht));
682
683 if (!ht)
684 return TEE_ERROR_OUT_OF_MEMORY;
685
686 ht->uuid = uuid;
687 ht->stor = stor;
688 ht->stor_aux = stor_aux;
689
690 if (create) {
691 res = create_and_sync(&ht, hash, min_counter);
692 } else {
693 res = init_head_from_data(ht, hash, min_counter);
694 if (res != TEE_SUCCESS)
695 goto out;
696
697 /*
698 * If a power loss occurred during hash tree creation, the
699 * head may not have been written and counter is still 0.
700 * Re-initialze the hash tree.
701 */
702 if (ht_head_is_partially_done(&ht->head)) {
703 res = create_and_sync(&ht, hash, min_counter);
704 if (res != TEE_SUCCESS)
705 goto out;
706 }
707
708 res = verify_root(ht);
709 if (res != TEE_SUCCESS)
710 goto out;
711
712 res = init_tree_from_data(ht);
713 if (res != TEE_SUCCESS)
714 goto out;
715
716 res = verify_tree(ht);
717 }
718 out:
719 if (res == TEE_SUCCESS)
720 *ht_ret = ht;
721 else
722 tee_fs_htree_close(&ht);
723 return res;
724 }
725
tee_fs_htree_get_meta(struct tee_fs_htree * ht)726 struct tee_fs_htree_meta *tee_fs_htree_get_meta(struct tee_fs_htree *ht)
727 {
728 return &ht->imeta.meta;
729 }
730
tee_fs_htree_meta_set_dirty(struct tee_fs_htree * ht)731 void tee_fs_htree_meta_set_dirty(struct tee_fs_htree *ht)
732 {
733 ht->dirty = true;
734 ht->root.dirty = true;
735 }
736
free_node(struct traverse_arg * targ __unused,struct htree_node * node)737 static TEE_Result free_node(struct traverse_arg *targ __unused,
738 struct htree_node *node)
739 {
740 if (node->parent)
741 free(node);
742 return TEE_SUCCESS;
743 }
744
tee_fs_htree_close(struct tee_fs_htree ** ht)745 void tee_fs_htree_close(struct tee_fs_htree **ht)
746 {
747 if (!*ht)
748 return;
749 htree_traverse_post_order(*ht, free_node, NULL);
750 free(*ht);
751 *ht = NULL;
752 }
753
htree_sync_node_to_storage(struct traverse_arg * targ,struct htree_node * node)754 static TEE_Result htree_sync_node_to_storage(struct traverse_arg *targ,
755 struct htree_node *node)
756 {
757 TEE_Result res;
758 uint8_t vers;
759 struct tee_fs_htree_meta *meta = NULL;
760
761 /*
762 * The node can be dirty while the block isn't updated due to
763 * updated children, but if block is updated the node has to be
764 * dirty.
765 */
766 assert(node->dirty >= node->block_updated);
767
768 if (!node->dirty)
769 return TEE_SUCCESS;
770
771 if (node->parent) {
772 uint32_t f = HTREE_NODE_COMMITTED_CHILD(node->id & 1);
773
774 node->parent->dirty = true;
775 node->parent->node.flags ^= f;
776 vers = !!(node->parent->node.flags & f);
777 } else {
778 /*
779 * Counter isn't updated yet, it's increased just before
780 * writing the header.
781 */
782 vers = !(targ->ht->head.counter & 1);
783 meta = &targ->ht->imeta.meta;
784 }
785
786 res = calc_node_hash(node, meta, targ->arg, node->node.hash);
787 if (res != TEE_SUCCESS)
788 return res;
789
790 node->dirty = false;
791 node->block_updated = false;
792
793 return rpc_write_node(targ->ht, node->id, vers, &node->node);
794 }
795
update_root(struct tee_fs_htree * ht)796 static TEE_Result update_root(struct tee_fs_htree *ht)
797 {
798 TEE_Result res;
799 void *ctx;
800
801 ht->head.counter++;
802
803 res = authenc_init(&ctx, TEE_MODE_ENCRYPT, ht, NULL, sizeof(ht->imeta));
804 if (res != TEE_SUCCESS)
805 return res;
806
807 return authenc_encrypt_final(ctx, ht->head.tag, &ht->imeta,
808 sizeof(ht->imeta), &ht->head.imeta);
809 }
810
tee_fs_htree_sync_to_storage(struct tee_fs_htree ** ht_arg,uint8_t * hash,uint32_t * counter)811 TEE_Result tee_fs_htree_sync_to_storage(struct tee_fs_htree **ht_arg,
812 uint8_t *hash, uint32_t *counter)
813 {
814 TEE_Result res;
815 struct tee_fs_htree *ht = *ht_arg;
816 void *ctx;
817
818 if (!ht)
819 return TEE_ERROR_CORRUPT_OBJECT;
820
821 if (!ht->dirty)
822 return TEE_SUCCESS;
823
824 res = crypto_hash_alloc_ctx(&ctx, TEE_FS_HTREE_HASH_ALG);
825 if (res != TEE_SUCCESS)
826 return res;
827
828 res = htree_traverse_post_order(ht, htree_sync_node_to_storage, ctx);
829 if (res != TEE_SUCCESS)
830 goto out;
831
832 /* All the nodes are written to storage now. Time to update root. */
833 res = update_root(ht);
834 if (res != TEE_SUCCESS)
835 goto out;
836
837 res = rpc_write_head(ht, ht->head.counter & 1, &ht->head);
838 if (res != TEE_SUCCESS)
839 goto out;
840
841 ht->dirty = false;
842 if (hash)
843 memcpy(hash, ht->root.node.hash, sizeof(ht->root.node.hash));
844 if (counter)
845 *counter = ht->head.counter;
846 out:
847 crypto_hash_free_ctx(ctx);
848 if (res != TEE_SUCCESS)
849 tee_fs_htree_close(ht_arg);
850 return res;
851 }
852
get_block_node(struct tee_fs_htree * ht,bool create,size_t block_num,struct htree_node ** node)853 static TEE_Result get_block_node(struct tee_fs_htree *ht, bool create,
854 size_t block_num, struct htree_node **node)
855 {
856 TEE_Result res;
857 struct htree_node *nd;
858
859 res = get_node(ht, create, BLOCK_NUM_TO_NODE_ID(block_num), &nd);
860 if (res == TEE_SUCCESS)
861 *node = nd;
862
863 return res;
864 }
865
tee_fs_htree_write_block(struct tee_fs_htree ** ht_arg,size_t block_num,const void * block)866 TEE_Result tee_fs_htree_write_block(struct tee_fs_htree **ht_arg,
867 size_t block_num, const void *block)
868 {
869 struct tee_fs_htree *ht = *ht_arg;
870 TEE_Result res;
871 struct tee_fs_rpc_operation op;
872 struct htree_node *node = NULL;
873 uint8_t block_vers;
874 void *ctx;
875 void *enc_block;
876
877 if (!ht)
878 return TEE_ERROR_CORRUPT_OBJECT;
879
880 res = get_block_node(ht, true, block_num, &node);
881 if (res != TEE_SUCCESS)
882 goto out;
883
884 if (!node->block_updated)
885 node->node.flags ^= HTREE_NODE_COMMITTED_BLOCK;
886
887 block_vers = !!(node->node.flags & HTREE_NODE_COMMITTED_BLOCK);
888 res = ht->stor->rpc_write_init(ht->stor_aux, &op,
889 TEE_FS_HTREE_TYPE_BLOCK, block_num,
890 block_vers, &enc_block);
891 if (res != TEE_SUCCESS)
892 goto out;
893
894 res = authenc_init(&ctx, TEE_MODE_ENCRYPT, ht, &node->node,
895 ht->stor->block_size);
896 if (res != TEE_SUCCESS)
897 goto out;
898 res = authenc_encrypt_final(ctx, node->node.tag, block,
899 ht->stor->block_size, enc_block);
900 if (res != TEE_SUCCESS)
901 goto out;
902
903 res = ht->stor->rpc_write_final(&op);
904 if (res != TEE_SUCCESS)
905 goto out;
906
907 node->block_updated = true;
908 node->dirty = true;
909 ht->dirty = true;
910 out:
911 if (res != TEE_SUCCESS)
912 tee_fs_htree_close(ht_arg);
913 return res;
914 }
915
tee_fs_htree_read_block(struct tee_fs_htree ** ht_arg,size_t block_num,void * block)916 TEE_Result tee_fs_htree_read_block(struct tee_fs_htree **ht_arg,
917 size_t block_num, void *block)
918 {
919 struct tee_fs_htree *ht = *ht_arg;
920 TEE_Result res;
921 struct tee_fs_rpc_operation op;
922 struct htree_node *node;
923 uint8_t block_vers;
924 size_t len;
925 void *ctx;
926 void *enc_block;
927
928 if (!ht)
929 return TEE_ERROR_CORRUPT_OBJECT;
930
931 res = get_block_node(ht, false, block_num, &node);
932 if (res != TEE_SUCCESS)
933 goto out;
934
935 block_vers = !!(node->node.flags & HTREE_NODE_COMMITTED_BLOCK);
936 res = ht->stor->rpc_read_init(ht->stor_aux, &op,
937 TEE_FS_HTREE_TYPE_BLOCK, block_num,
938 block_vers, &enc_block);
939 if (res != TEE_SUCCESS)
940 goto out;
941
942 res = ht->stor->rpc_read_final(&op, &len);
943 if (res != TEE_SUCCESS)
944 goto out;
945 if (len != ht->stor->block_size) {
946 res = TEE_ERROR_CORRUPT_OBJECT;
947 goto out;
948 }
949
950 res = authenc_init(&ctx, TEE_MODE_DECRYPT, ht, &node->node,
951 ht->stor->block_size);
952 if (res != TEE_SUCCESS)
953 goto out;
954
955 res = authenc_decrypt_final(ctx, node->node.tag, enc_block,
956 ht->stor->block_size, block);
957 out:
958 if (res != TEE_SUCCESS)
959 tee_fs_htree_close(ht_arg);
960 return res;
961 }
962
tee_fs_htree_truncate(struct tee_fs_htree ** ht_arg,size_t block_num)963 TEE_Result tee_fs_htree_truncate(struct tee_fs_htree **ht_arg, size_t block_num)
964 {
965 struct tee_fs_htree *ht = *ht_arg;
966 size_t node_id = BLOCK_NUM_TO_NODE_ID(block_num);
967 struct htree_node *node;
968
969 if (!ht)
970 return TEE_ERROR_CORRUPT_OBJECT;
971
972 while (node_id < ht->imeta.max_node_id) {
973 node = find_closest_node(ht, ht->imeta.max_node_id);
974 assert(node && node->id == ht->imeta.max_node_id);
975 assert(!node->child[0] && !node->child[1]);
976 assert(node->parent);
977 assert(node->parent->child[node->id & 1] == node);
978 node->parent->child[node->id & 1] = NULL;
979 free(node);
980 ht->imeta.max_node_id--;
981 ht->dirty = true;
982 }
983
984 return TEE_SUCCESS;
985 }
986