aboutsummaryrefslogtreecommitdiff
path: root/crypto.h
blob: 3d824e61a1a5c7915498ab3ecb8b3f63493dca0a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#ifndef CSAA_CRYPTO_H
#define CSAA_CRYPTO_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

/* Various useful cryptographic functions; shared between TM and SP. */

/* we use SHA256 for h() */
typedef struct hash_t {
    /* a hash of all zeros is given a special meaning */
    unsigned char hash[32];
} hash_t;

struct iomt_node {
    uint64_t idx, next_idx; /* idx cannot be zero */
    hash_t val; /* all zero indicates placeholder */
};

struct iomt {
    int mt_leafcount, mt_logleaves; /* mt_logleaves must equal 2^mt_leafcount */

    /* Each level of the IOMT is stored sequentially from left to
     * right, top to bottom, as follows:
     *
     *  [0]: root
     *  [1]: root left child
     *  [2]: root right child
     *  [3]: left child of [1]
     *  [4]: right child of [1]
     *  [5]: left child of [2]
     *  [6]: right child of [2],
     *
     * and so on.
     */
    hash_t *mt_nodes; /* this has 2 * mt_leafcount - 1 elements. Note
                       * that the bottom level consists of hashes of
                       * the leaf nodes. */

    struct iomt_node *mt_leaves;
};

/* guaranteed to be zero */
static const struct hash_t hash_null = { { 0 } };

bool encloses(uint64_t b, uint64_t bprime, uint64_t a);
bool hash_equals(hash_t a, hash_t b);
bool is_zero(hash_t u);

hash_t hash_node(const struct iomt_node *node);
hash_t hash_xor(hash_t a, hash_t b);

hash_t sha256(const void *data, size_t datalen);
hash_t hmac_sha256(const void *data, size_t datalen, const void *key, size_t keylen);

hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t n);
hash_t merkle_parent(hash_t u, hash_t v, int order);

/* Calculate the indicies of the complementary nodes to a
 * leaf. `leafidx' is 0 for the rightmost leaf node. This function
 * will return an array with a length equal to the number of levels in
 * the tree minus one (the root is not a complentary node). The 0th
 * element of the returned array will be the index of the immediate
 * sibling, while the 1st element will be the index of the
 * complementary node one level above the leaf node, and so on. Note
 * that logleaves = log2(nleaves). If `orders' is not NULL, the
 * function will additionally allocate an array of `logleaves' *
 * sizeof(int) with each element representing whether each
 * complementary node is a left or right child. */
int *bintree_complement(int leafidx, int logleaves, int **orders);
int *bintree_complement_ordersonly(int leafidx, int logleaves);

/* Return an array of indices of tree nodes that are dependent on a
 * given leaf node. Will be ordered from nearest relative to root. */
int *bintree_ancestors(int leafidx, int logleaves);

hash_t *merkle_complement(const struct iomt *tree, int leafidx, int **orders);

hash_t *lookup_nodes(const hash_t *nodes, const int *indices, int n);
void restore_nodes(hash_t *nodes, const int *indices, const hash_t *values, int n);

/* This function is prefixed merkle_ because it does not know about
 * any IOMT-specific properties (though it is still passed an iomt
 * struct) */
void merkle_update(struct iomt *tree, uint64_t leafidx, hash_t newval, hash_t **old_dep);

struct iomt *iomt_new(int logleaves);
struct iomt *iomt_dup(const struct iomt *tree);
void iomt_free(struct iomt *tree);

/* Find a leaf with IOMT index `idx' and change its value, propagating
 * up the tree. */
void iomt_update(struct iomt *tree, uint64_t idx, hash_t newval);

/* Set all the fields of a leaf node (not an IOMT index!) */
void iomt_update_leaf_full(struct iomt *tree, uint64_t leafidx,
                           uint64_t new_idx, uint64_t new_next_idx, hash_t new_val);
void iomt_update_leaf_idx(struct iomt *tree, uint64_t leafidx,
                          uint64_t new_idx);
void iomt_update_leaf_nextidx(struct iomt *tree, uint64_t leafidx,
                              uint64_t new_next_idx);
void iomt_update_leaf_hash(struct iomt *tree, uint64_t leafidx,
                           hash_t new_val);

/* Create an IOMT where the leaves are the hash of file lines */
struct iomt *iomt_from_lines(const char *filename);

void iomt_fill(struct iomt *tree);
void iomt_dump(const struct iomt *tree);

/* All linear searches... slow! */
struct iomt_node *iomt_find_leaf(const struct iomt *tree, uint64_t idx);
struct iomt_node *iomt_find_encloser(const struct iomt *tree, uint64_t idx);
struct iomt_node *iomt_find_leaf_or_encloser(const struct iomt *tree, uint64_t idx);

int bintree_parent(int idx);
int bintree_sibling(int idx);

uint64_t hash_to_u64(hash_t h);
hash_t u64_to_hash(uint64_t n);
void dump_hash(hash_t u);

struct hashstring {
    char str[32 * 2 + 1];
};

struct hashstring hash_format(hash_t h, int n);

hash_t crypt_secret(hash_t encrypted_secret,
                    uint64_t file_idx, uint64_t file_counter,
                    const void *key, size_t keylen);

hash_t calc_lambda(hash_t gamma, const struct iomt *buildcode, const struct iomt *composefile, hash_t kf);

/* self-test */
void crypto_test(void);
#endif