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 #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 int count_trailing_zeroes(shachain_index_t index)
  16 {
  17 #if HAVE_BUILTIN_CTZLL
  18         return index ? __builtin_ctzll(index) : INDEX_BITS;
  19 #else
  20         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         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         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 }