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(shachain_index_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(shachain_index_t from, shachain_index_t to)
  29 {
  30         shachain_index_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 = ~((1ULL << count_trailing_zeroes(from))-1);
  38         return ((from ^ to) & mask) == 0;
  39 }
  40
  41 static void derive(shachain_index_t from, shachain_index_t to,
  42                    const struct sha256 *from_hash,
  43                    struct sha256 *hash)
  44 {
  45         shachain_index_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, shachain_index_t index,
  64                         struct sha256 *hash)
  65 {
  66         derive(0, index, seed, hash);
  67 }
  68
  69 void shachain_init(struct shachain *chain)
  70 {
  71         chain->num_valid = 0;
  72         chain->min_index = 0;
  73 }
  74
  75 bool shachain_add_hash(struct shachain *chain,
  76                        shachain_index_t index, const struct sha256 *hash)
  77 {
  78         unsigned int i, pos;
  79
  80         /* You have to insert them in order! */
  81         assert(index == chain->min_index - 1 ||
  82                (index == (shachain_index_t)(UINT64_MAX >> (64 - SHACHAIN_BITS))
  83                 && chain->num_valid == 0));
  84
  85         pos = count_trailing_zeroes(index);
  86
  87         /* All derivable answers must be valid. */
  88         /* FIXME: Is it sufficient to check just the next answer? */
  89         for (i = 0; i < pos; i++) {
  90                 struct sha256 expect;
  91
  92                 /* Make sure the others derive as expected! */
  93                 derive(index, chain->known[i].index, hash, &expect);
  94                 if (memcmp(&expect, &chain->known[i].hash, sizeof(expect)))
  95                         return false;
  96         }
  97
  98         chain->known[pos].index = index;
  99         chain->known[pos].hash = *hash;
 100         if (pos + 1 > chain->num_valid)
 101                 chain->num_valid = pos + 1;
 102         chain->min_index = index;
 103         return true;
 104 }
 105
 106 bool shachain_get_hash(const struct shachain *chain,
 107                        shachain_index_t index, struct sha256 *hash)
 108 {
 109         unsigned int i;
 110
 111         for (i = 0; i < chain->num_valid; i++) {
 112                 /* If we can get from key to index only by resetting bits,
 113                  * we can derive from it => index has no bits key doesn't. */
 114                 if (!can_derive(chain->known[i].index, index))
 115                         continue;
 116
 117                 derive(chain->known[i].index, index, &chain->known[i].hash,
 118                        hash);
 119                 return true;
 120         }
 121         return false;
 122 }