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