c6bd37e8f55c76cd72a2720669e8083d4d4585fe
[ccan] / ccan / crypto / shachain / shachain.c
1 /* MIT (BSD) license - see LICENSE file for details */
2 #include <ccan/crypto/shachain/shachain.h>
3 #include <ccan/ilog/ilog.h>
4 #include <limits.h>
5 #include <string.h>
6 #include <assert.h>
7
8 #define INDEX_BITS ((sizeof(shachain_index_t)) * CHAR_BIT)
9
10 static void change_bit(unsigned char *arr, size_t index)
11 {
12         arr[index / CHAR_BIT] ^= (1 << (index % CHAR_BIT));
13 }
14
15 static unsigned int count_trailing_zeroes(shachain_index_t index)
16 {
17 #if HAVE_BUILTIN_CTZLL
18         return index ? (unsigned int)__builtin_ctzll(index) : INDEX_BITS;
19 #else
20         unsigned int i;
21
22         for (i = 0; i < INDEX_BITS; i++) {
23                 if (index & (1ULL << i))
24                         break;
25         }
26         return i;
27 #endif
28 }
29
30 static bool can_derive(shachain_index_t from, shachain_index_t to)
31 {
32         shachain_index_t mask;
33
34         /* Corner case: can always derive from seed. */
35         if (from == 0)
36                 return true;
37
38         /* Leading bits must be the same */
39         mask = ~((1ULL << count_trailing_zeroes(from))-1);
40         return ((from ^ to) & mask) == 0;
41 }
42
43 static void derive(shachain_index_t from, shachain_index_t to,
44                    const struct sha256 *from_hash,
45                    struct sha256 *hash)
46 {
47         shachain_index_t branches;
48         int i;
49
50         assert(can_derive(from, to));
51
52         /* We start with the first hash. */
53         *hash = *from_hash;
54
55         /* This represents the bits set in to, and not from. */
56         branches = from ^ to;
57         for (i = ilog64(branches) - 1; i >= 0; i--) {
58                 if (((branches >> i) & 1)) {
59                         change_bit(hash->u.u8, i);
60                         sha256(hash, hash, sizeof(*hash));
61                 }
62         }
63 }
64
65 void shachain_from_seed(const struct sha256 *seed, shachain_index_t index,
66                         struct sha256 *hash)
67 {
68         derive(0, index, seed, hash);
69 }
70
71 void shachain_init(struct shachain *chain)
72 {
73         chain->num_valid = 0;
74         chain->min_index = 0;
75 }
76
77 bool shachain_add_hash(struct shachain *chain,
78                        shachain_index_t index, const struct sha256 *hash)
79 {
80         unsigned int i, pos;
81
82         /* You have to insert them in order! */
83         assert(index == chain->min_index - 1 ||
84                (index == (shachain_index_t)(-1ULL) && chain->num_valid == 0));
85
86         pos = count_trailing_zeroes(index);
87
88         /* All derivable answers must be valid. */
89         /* FIXME: Is it sufficient to check just the next answer? */
90         for (i = 0; i < pos; i++) {
91                 struct sha256 expect;
92
93                 /* Make sure the others derive as expected! */
94                 derive(index, chain->known[i].index, hash, &expect);
95                 if (memcmp(&expect, &chain->known[i].hash, sizeof(expect)))
96                         return false;
97         }
98
99         chain->known[pos].index = index;
100         chain->known[pos].hash = *hash;
101         if (pos + 1 > chain->num_valid)
102                 chain->num_valid = pos + 1;
103         chain->min_index = index;
104         return true;
105 }
106
107 bool shachain_get_hash(const struct shachain *chain,
108                        shachain_index_t index, struct sha256 *hash)
109 {
110         unsigned int i;
111
112         for (i = 0; i < chain->num_valid; i++) {
113                 /* If we can get from key to index only by resetting bits,
114                  * we can derive from it => index has no bits key doesn't. */
115                 if (!can_derive(chain->known[i].index, index))
116                         continue;
117
118                 derive(chain->known[i].index, index, &chain->known[i].hash,
119                        hash);
120                 return true;
121         }
122         return false;
123 }