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