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
|
#include "crypto.h"
#include <string.h>
#include <openssl/hmac.h>
#include <openssl/sha.h>
/* return true iff [b, bprime] encloses a */
bool encloses(int b, int bprime, int a)
{
return (b < a && a < bprime) || (bprime <= b && b < a) || (a < bprime && bprime <= b);
}
hash_t hash_node(const struct iomt_node *node)
{
return sha256(node, sizeof(*node));
}
hash_t hmac_sha256(const void *data, size_t datalen, const void *key, size_t keylen)
{
hash_t h;
HMAC(EVP_sha256(), key, keylen, data, datalen, h.hash, NULL);
return h;
}
hash_t sha256(const void *data, size_t datalen)
{
hash_t h;
SHA256(data, datalen, h.hash);
return h;
}
bool is_zero(hash_t u)
{
/* constant-time comparison */
volatile char c = 0;
for(int i = 0; i < 32; ++i)
c |= u.hash[i];
return c == 0;
}
void dump_hash(hash_t u)
{
for(int i = 0; i < 32; ++i)
printf("%02x", u.hash[i]);
printf("\n");
}
bool hash_equals(hash_t a, hash_t b)
{
return !memcmp(a.hash, b.hash, 32);
}
hash_t hash_xor(hash_t a, hash_t b)
{
for(int i = 0; i < 32; ++i)
a.hash[i] ^= b.hash[i];
return a;
}
void hash_zero(hash_t *h)
{
for(int i = 0; i < 32; ++i)
h->hash[i] = 0;
}
/* NOTE: we fail to distinguish between intermediate and leaf
* nodes, making a second-preimage attack possible */
/* order: 0: u is left, v is right, 1: u is right, v is left */
hash_t merkle_parent(hash_t u, hash_t v, int order)
{
if(is_zero(u))
return v;
if(is_zero(v))
return u;
/* append and hash */
SHA256_CTX ctx;
hash_t h;
SHA256_Init(&ctx);
if(order != 0)
SHA256_Update(&ctx, v.hash, 32);
SHA256_Update(&ctx, u.hash, 32);
if(order == 0)
SHA256_Update(&ctx, v.hash, 32);
SHA256_Final(h.hash, &ctx);
return h;
}
/* Calculate the root of a Merkle tree given the leaf node v, and n
* complementary nodes, ordered from the closest node (the sibling
* leaf node at the bottom of the tree) to most distant (the opposite
* half of the tree). orders[i] represents whether each complementarty
* node is a left or right child, which is necessary to compute the
* proper hash value at each stage. This is the f_bt() algorithm
* described in Mohanty et al. */
/* orders: 0 indiciates that the complementary node is LEFT child, 1:
* node is RIGHT child */
hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t n)
{
hash_t parent = node;
for(size_t i = 0; i < n; ++i)
parent = merkle_parent(comp[i], parent, orders[i]);
return parent;
}
/* convert the first 8 bytes (little endian) to a 64-bit int */
uint64_t hash_to_u64(hash_t h)
{
uint64_t ret = 0;
for(int i = 0; i < 8; ++i)
ret |= h.hash[i] << (i * 8);
return ret;
}
|