sfinx

sphincs+ inspired signing utility
git clone git://git.finwo.net/app/sfinx
Log | Files | Refs | README | LICENSE

sfinx_ref.c (12098B)


      1 // Reference signer {{{
      2 //
      3 // Independent re-derivation of the sfinx scheme
      4 //   shares only the keccak-fast primitive with src/sfinx.c
      5 //   a second code path, not a second language, so it checks the scheme logic and
      6 //   the byte layout, not the hash (the hash is anchored by test_openssl.sh)
      7 //   nothing here is production code, all symbols are static and prefixed ref_
      8 
      9 #include <finwo/keccak-fast.h>
     10 #include <stddef.h>
     11 #include <stdint.h>
     12 #include <stdlib.h>
     13 #include <string.h>
     14 
     15 #define REF_LEN_MAX    64
     16 #define REF_DIGITS_MAX (REF_LEN_MAX + 2)
     17 #define REF_WOTS_MAX   ((REF_LEN_MAX + 2) * REF_LEN_MAX)
     18 #define REF_LEAVES_MAX (256 * REF_LEN_MAX)
     19 #define REF_KEY_MAX    1024
     20 #define REF_PARENT_MAX (2 + 256 + 2 * REF_LEN_MAX)
     21 
     22 static size_t ref_len(int bits) {
     23   switch (bits) {
     24     case 224: return 28;
     25     case 256: return 32;
     26     case 384: return 48;
     27     case 512: return 64;
     28   }
     29   return 0;
     30 }
     31 
     32 static void ref_sha3(int bits, const uint8_t *in, size_t in_len, uint8_t *out) {
     33   switch (bits) {
     34     case 224: kf_sha3_224(out, 28, in, in_len); break;
     35     case 256: kf_sha3_256(out, 32, in, in_len); break;
     36     case 384: kf_sha3_384(out, 48, in, in_len); break;
     37     case 512: kf_sha3_512(out, 64, in, in_len); break;
     38   }
     39 }
     40 
     41 static void ref_shake(const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) {
     42   kf_shake256(out, out_len, in, in_len);
     43 }
     44 
     45 static uint32_t ref_e4m4_decode(uint8_t byte) {
     46   uint8_t exponent = (uint8_t)(byte >> 4);
     47   uint8_t mantissa = (uint8_t)(byte & 0x0f);
     48   if (exponent == 0) {
     49     return mantissa;
     50   }
     51   return (uint32_t)(16 + mantissa) << (exponent - 1);
     52 }
     53 
     54 static int ref_e4m4_encode(uint32_t value, uint8_t *out) {
     55   // Brute force the small field rather than the library's shift loop
     56   for (uint32_t exponent = 0; exponent < 16; exponent++) {
     57     for (uint32_t mantissa = 0; mantissa < 16; mantissa++) {
     58       uint32_t candidate = exponent == 0 ? mantissa : (16 + mantissa) << (exponent - 1);
     59       if (candidate == value) {
     60         *out = (uint8_t)((exponent << 4) | mantissa);
     61         return 1;
     62       }
     63     }
     64   }
     65   return 0;
     66 }
     67 
     68 static uint8_t ref_mask(uint8_t bitlen, uint8_t index) {
     69   // Keep the top bitlen bits with an explicit bit walk
     70   uint8_t out = 0;
     71   for (uint8_t i = 0; i < bitlen; i++) {
     72     uint8_t bit = (uint8_t)(1u << (7 - i));
     73     if (index & bit) {
     74       out |= bit;
     75     }
     76   }
     77   return out;
     78 }
     79 
     80 static void ref_parent(int bits, uint8_t bitlen, uint8_t mask, const uint8_t *prefix, size_t prefix_len,
     81                        const uint8_t *left, const uint8_t *right, uint8_t *out) {
     82   size_t  len = ref_len(bits);
     83   uint8_t buf[REF_PARENT_MAX];
     84   size_t  at = 0;
     85   if (prefix_len > 256) {
     86     return;
     87   }
     88   buf[at++] = bitlen;
     89   buf[at++] = mask;
     90   for (size_t i = 0; i < prefix_len; i++) {
     91     buf[at++] = prefix[i];
     92   }
     93   for (size_t i = 0; i < len; i++) {
     94     buf[at++] = left[i];
     95   }
     96   for (size_t i = 0; i < len; i++) {
     97     buf[at++] = right[i];
     98   }
     99   ref_sha3(bits, buf, at, out);
    100 }
    101 
    102 static void ref_pre(int bits, const uint8_t *key, size_t key_len, uint8_t *out) {
    103   size_t len = ref_len(bits);
    104   ref_shake(key, key_len, out, (len + 2) * len);
    105 }
    106 
    107 static void ref_digits(int bits, const uint8_t *value, uint8_t *out) {
    108   size_t   len      = ref_len(bits);
    109   uint32_t checksum = 0;
    110   for (size_t i = 0; i < len; i++) {
    111     out[i] = value[i];
    112     checksum += (uint32_t)(255 - value[i]);
    113   }
    114   out[len]     = (uint8_t)((checksum >> 8) & 0xff);
    115   out[len + 1] = (uint8_t)(checksum & 0xff);
    116 }
    117 
    118 // Spell the rate out rather than reusing the library's folded constant
    119 static size_t ref_kid_len(int bits) {
    120   size_t len  = ref_len(bits);
    121   size_t rate = 200 - 2 * len;
    122   size_t room = rate - 1 - len - 2;
    123   return len < room ? len : room;
    124 }
    125 
    126 static void ref_kid(int bits, const uint8_t *suffix, size_t suffix_len, uint8_t *out) {
    127   uint8_t full[REF_LEN_MAX];
    128   size_t  k = ref_kid_len(bits);
    129   ref_sha3(bits, suffix, suffix_len, full);
    130   for (size_t i = 0; i < k; i++) {
    131     out[i] = full[i];
    132   }
    133 }
    134 
    135 static void ref_chain(int bits, uint8_t *node, const uint8_t *kid, uint8_t index, uint8_t from, uint32_t steps) {
    136   size_t  len = ref_len(bits);
    137   size_t  k   = ref_kid_len(bits);
    138   uint8_t blk[2 * REF_LEN_MAX + 2];
    139   for (uint32_t s = 0; s < steps; s++) {
    140     size_t at = 0;
    141     for (size_t i = 0; i < len; i++) {
    142       blk[at++] = node[i];
    143     }
    144     for (size_t i = 0; i < k; i++) {
    145       blk[at++] = kid[i];
    146     }
    147     blk[at++] = index;
    148     blk[at++] = (uint8_t)(from + s);
    149     ref_sha3(bits, blk, at, node);
    150   }
    151 }
    152 
    153 static void ref_pub(int bits, const uint8_t *key, size_t key_len, size_t seed_len, uint8_t *out) {
    154   size_t  len = ref_len(bits);
    155   uint8_t ends[REF_WOTS_MAX];
    156   uint8_t kid[REF_LEN_MAX];
    157   ref_pre(bits, key, key_len, ends);
    158   ref_kid(bits, key + seed_len, key_len - seed_len, kid);
    159   for (size_t i = 0; i < len + 2; i++) {
    160     ref_chain(bits, ends + i * len, kid, (uint8_t)i, 0, 256);
    161   }
    162   ref_sha3(bits, ends, (len + 2) * len, out);
    163 }
    164 
    165 static void ref_wots_sign(int bits, const uint8_t *key, size_t key_len, size_t seed_len, const uint8_t *value,
    166                           uint8_t *proof) {
    167   size_t  len = ref_len(bits);
    168   uint8_t digits[REF_DIGITS_MAX];
    169   uint8_t kid[REF_LEN_MAX];
    170   ref_pre(bits, key, key_len, proof);
    171   ref_digits(bits, value, digits);
    172   ref_kid(bits, key + seed_len, key_len - seed_len, kid);
    173   for (size_t i = 0; i < len + 2; i++) {
    174     ref_chain(bits, proof + i * len, kid, (uint8_t)i, 0, digits[i]);
    175   }
    176 }
    177 
    178 static void ref_wots_rebuild(int bits, const uint8_t *value, const uint8_t *proof, const uint8_t *kid, uint8_t *out) {
    179   size_t  len = ref_len(bits);
    180   uint8_t digits[REF_DIGITS_MAX];
    181   uint8_t ends[REF_WOTS_MAX];
    182   ref_digits(bits, value, digits);
    183   for (size_t i = 0; i < len + 2; i++) {
    184     memcpy(ends + i * len, proof + i * len, len);
    185     ref_chain(bits, ends + i * len, kid, (uint8_t)i, digits[i], 256 - digits[i]);
    186   }
    187   ref_sha3(bits, ends, (len + 2) * len, out);
    188 }
    189 
    190 static void ref_subtree(int bits, const uint8_t *seed, size_t seed_len, const uint8_t *prefix, size_t prefix_len,
    191                         uint8_t leaf_index, uint8_t *root_out, uint8_t *auth_out) {
    192   size_t  len     = ref_len(bits);
    193   size_t  key_len = seed_len + prefix_len + 1;
    194   size_t  pos     = leaf_index;
    195   uint8_t leaves[REF_LEAVES_MAX];
    196   uint8_t key[REF_KEY_MAX];
    197 
    198   if (key_len > REF_KEY_MAX) {
    199     return;
    200   }
    201   for (size_t i = 0; i < seed_len; i++) {
    202     key[i] = seed[i];
    203   }
    204   for (size_t i = 0; i < prefix_len; i++) {
    205     key[seed_len + i] = prefix[i];
    206   }
    207   for (uint32_t i = 0; i < 256; i++) {
    208     key[key_len - 1] = (uint8_t)i;
    209     ref_pub(bits, key, key_len, seed_len, leaves + (size_t)i * len);
    210   }
    211   for (uint8_t depth = 0; depth < 8; depth++) {
    212     uint8_t bitlen = (uint8_t)(7 - depth);
    213     size_t  pairs  = (size_t)1 << (7 - depth);
    214     if (auth_out) {
    215       size_t sibling = pos ^ 1u;
    216       for (size_t i = 0; i < len; i++) {
    217         auth_out[(size_t)depth * len + i] = leaves[sibling * len + i];
    218       }
    219     }
    220     for (size_t j = 0; j < pairs; j++) {
    221       uint8_t mask = ref_mask(bitlen, (uint8_t)(j << (8 - bitlen)));
    222       ref_parent(bits, bitlen, mask, prefix, prefix_len, leaves + (2 * j) * len, leaves + (2 * j + 1) * len,
    223                  leaves + j * len);
    224     }
    225     pos >>= 1;
    226   }
    227   for (size_t i = 0; i < len; i++) {
    228     root_out[i] = leaves[i];
    229   }
    230 }
    231 
    232 static size_t ref_signature_len(int bits, size_t path_len) {
    233   size_t len = ref_len(bits);
    234   if (len == 0) {
    235     return 0;
    236   }
    237   if (path_len == 0) {
    238     return 2 + (len + 2) * len;
    239   }
    240   return 2 + path_len + path_len * (len + 10) * len;
    241 }
    242 
    243 static void ref_single_pub(int bits, const uint8_t *seed, size_t seed_len, uint8_t *out) {
    244   ref_pub(bits, seed, seed_len, seed_len, out);
    245 }
    246 
    247 static void ref_single_sign(int bits, const uint8_t *seed, size_t seed_len, const uint8_t *msg, size_t msg_len,
    248                             uint8_t *sig) {
    249   size_t  len = ref_len(bits);
    250   uint8_t org[REF_LEN_MAX];
    251   ref_sha3(bits, msg, msg_len, org);
    252   ref_e4m4_encode(0, sig);
    253   ref_e4m4_encode((uint32_t)len, sig + 1);
    254   ref_wots_sign(bits, seed, seed_len, seed_len, org, sig + 2);
    255 }
    256 
    257 static void ref_tree_pub(int bits, const uint8_t *seed, size_t seed_len, size_t path_len, uint8_t *out) {
    258   uint8_t prefix;
    259   ref_e4m4_encode((uint32_t)path_len, &prefix);
    260   ref_subtree(bits, seed, seed_len, &prefix, 1, 0, out, NULL);
    261 }
    262 
    263 static void ref_tree_sign(int bits, const uint8_t *seed, size_t seed_len, const uint8_t *path, size_t path_len,
    264                           const uint8_t *msg, size_t msg_len, uint8_t *sig) {
    265   size_t   len = ref_len(bits);
    266   size_t   c   = len + 2;
    267   size_t   at  = 0;
    268   uint8_t  value[REF_LEN_MAX];
    269   uint8_t  root[REF_LEN_MAX];
    270   uint8_t  auth[8 * REF_LEN_MAX];
    271   uint8_t  key[REF_KEY_MAX];
    272   uint8_t  npath[REF_KEY_MAX];
    273   uint8_t *joined = malloc(path_len + msg_len);
    274 
    275   if (!joined || seed_len + path_len + 2 > REF_KEY_MAX) {
    276     free(joined);
    277     return;
    278   }
    279   memcpy(joined, path, path_len);
    280   memcpy(joined + path_len, msg, msg_len);
    281   ref_sha3(bits, joined, path_len + msg_len, value);
    282   free(joined);
    283 
    284   ref_e4m4_encode((uint32_t)path_len, sig);
    285   at = 1;
    286   for (size_t i = 0; i < path_len; i++) {
    287     sig[at++] = path[i];
    288   }
    289   ref_e4m4_encode((uint32_t)len, sig + at);
    290   at += 1;
    291 
    292   ref_e4m4_encode((uint32_t)path_len, npath);
    293   for (size_t i = 0; i < path_len; i++) {
    294     npath[1 + i] = path[i];
    295   }
    296   for (size_t i = 0; i < seed_len; i++) {
    297     key[i] = seed[i];
    298   }
    299   for (size_t i = 0; i <= path_len; i++) {
    300     key[seed_len + i] = npath[i];
    301   }
    302 
    303   for (size_t k = path_len; k >= 1; k--) {
    304     ref_subtree(bits, seed, seed_len, npath, k, npath[k], root, auth);
    305     ref_wots_sign(bits, key, seed_len + k + 1, seed_len, value, sig + at);
    306     at += c * len;
    307     for (size_t i = 0; i < 8 * len; i++) {
    308       sig[at++] = auth[i];
    309     }
    310     for (size_t i = 0; i < len; i++) {
    311       value[i] = root[i];
    312     }
    313   }
    314 }
    315 
    316 static int ref_verify(const uint8_t *pub, size_t pub_len, const uint8_t *msg, size_t msg_len, const uint8_t *sig,
    317                       size_t sig_len) {
    318   size_t   path_len;
    319   size_t   len;
    320   size_t   c;
    321   size_t   at;
    322   size_t   pos;
    323   int      bits;
    324   uint8_t  value[REF_LEN_MAX];
    325   uint8_t  leaf[REF_LEN_MAX];
    326   uint8_t  root[REF_LEN_MAX];
    327   uint8_t *joined;
    328 
    329   if (sig_len < 2) {
    330     return 0;
    331   }
    332   path_len = ref_e4m4_decode(sig[0]);
    333   at       = 1 + path_len;
    334   if (at + 1 > sig_len) {
    335     return 0;
    336   }
    337   len = ref_e4m4_decode(sig[at]);
    338   if (len == 28) {
    339     bits = 224;
    340   } else if (len == 32) {
    341     bits = 256;
    342   } else if (len == 48) {
    343     bits = 384;
    344   } else if (len == 64) {
    345     bits = 512;
    346   } else {
    347     return 0;
    348   }
    349   if (len != pub_len || sig_len != ref_signature_len(bits, path_len)) {
    350     return 0;
    351   }
    352   c  = len + 2;
    353   at = 2 + path_len;
    354 
    355   if (path_len == 0) {
    356     uint8_t kid[REF_LEN_MAX];
    357     ref_sha3(bits, msg, msg_len, value);
    358     ref_kid(bits, NULL, 0, kid);
    359     ref_wots_rebuild(bits, value, sig + at, kid, leaf);
    360     return memcmp(leaf, pub, len) == 0;
    361   }
    362 
    363   joined = malloc(path_len + msg_len);
    364   if (!joined) {
    365     return 0;
    366   }
    367   memcpy(joined, sig + 1, path_len);
    368   memcpy(joined + path_len, msg, msg_len);
    369   ref_sha3(bits, joined, path_len + msg_len, value);
    370   free(joined);
    371 
    372   for (size_t k = path_len; k >= 1; k--) {
    373     uint8_t kid[REF_LEN_MAX];
    374     ref_kid(bits, sig, k + 1, kid);
    375     ref_wots_rebuild(bits, value, sig + at, kid, leaf);
    376     at += c * len;
    377     pos = sig[k];
    378     for (size_t i = 0; i < len; i++) {
    379       root[i] = leaf[i];
    380     }
    381     for (uint8_t depth = 0; depth < 8; depth++) {
    382       uint8_t        bitlen  = (uint8_t)(7 - depth);
    383       uint8_t        mask    = ref_mask(bitlen, (uint8_t)((pos >> 1) << (8 - bitlen)));
    384       const uint8_t *sibling = sig + at + (size_t)depth * len;
    385       uint8_t        tmp[REF_LEN_MAX];
    386       if (pos & 1) {
    387         ref_parent(bits, bitlen, mask, sig, k, sibling, root, tmp);
    388       } else {
    389         ref_parent(bits, bitlen, mask, sig, k, root, sibling, tmp);
    390       }
    391       memcpy(root, tmp, len);
    392       pos >>= 1;
    393     }
    394     at += 8 * len;
    395     if (k == 1) {
    396       return memcmp(root, pub, len) == 0;
    397     }
    398     memcpy(value, root, len);
    399   }
    400   return 0;
    401 }
    402 // }}}
    403 
    404 // vim:fdm=marker:fdl=0