1/* $NetBSD: xmss_fast.c,v 1.2 2018/04/06 18:59:00 christos Exp $ */ 2/* $OpenBSD: xmss_fast.c,v 1.3 2018/03/22 07:06:11 markus Exp $ */ 3/* 4xmss_fast.c version 20160722 5Andreas H��lsing 6Joost Rijneveld 7Public domain. 8*/ 9#include "includes.h" 10__RCSID("$NetBSD: xmss_fast.c,v 1.2 2018/04/06 18:59:00 christos Exp $"); 11 12#include <stdlib.h> 13#include <string.h> 14#include <stdint.h> 15 16#include "xmss_fast.h" 17#include "crypto_api.h" 18#include "xmss_wots.h" 19#include "xmss_hash.h" 20 21#include "xmss_commons.h" 22#include "xmss_hash_address.h" 23// For testing 24#include "stdio.h" 25 26 27 28/** 29 * Used for pseudorandom keygeneration, 30 * generates the seed for the WOTS keypair at address addr 31 * 32 * takes n byte sk_seed and returns n byte seed using 32 byte address addr. 33 */ 34static void get_seed(unsigned char *seed, const unsigned char *sk_seed, int n, uint32_t addr[8]) 35{ 36 unsigned char bytes[32]; 37 // Make sure that chain addr, hash addr, and key bit are 0! 38 setChainADRS(addr,0); 39 setHashADRS(addr,0); 40 setKeyAndMask(addr,0); 41 // Generate pseudorandom value 42 addr_to_byte(bytes, addr); 43 prf(seed, bytes, sk_seed, n); 44} 45 46/** 47 * Initialize xmss params struct 48 * parameter names are the same as in the draft 49 * parameter k is K as used in the BDS algorithm 50 */ 51int xmss_set_params(xmss_params *params, int n, int h, int w, int k) 52{ 53 if (k >= h || k < 2 || (h - k) % 2) { 54 fprintf(stderr, "For BDS traversal, H - K must be even, with H > K >= 2!\n"); 55 return 1; 56 } 57 params->h = h; 58 params->n = n; 59 params->k = k; 60 wots_params wots_par; 61 wots_set_params(&wots_par, n, w); 62 params->wots_par = wots_par; 63 return 0; 64} 65 66/** 67 * Initialize BDS state struct 68 * parameter names are the same as used in the description of the BDS traversal 69 */ 70void xmss_set_bds_state(bds_state *state, unsigned char *stack, int stackoffset, unsigned char *stacklevels, unsigned char *auth, unsigned char *keep, treehash_inst *treehash, unsigned char *retain, int next_leaf) 71{ 72 state->stack = stack; 73 state->stackoffset = stackoffset; 74 state->stacklevels = stacklevels; 75 state->auth = auth; 76 state->keep = keep; 77 state->treehash = treehash; 78 state->retain = retain; 79 state->next_leaf = next_leaf; 80} 81 82/** 83 * Initialize xmssmt_params struct 84 * parameter names are the same as in the draft 85 * 86 * Especially h is the total tree height, i.e. the XMSS trees have height h/d 87 */ 88int xmssmt_set_params(xmssmt_params *params, int n, int h, int d, int w, int k) 89{ 90 if (h % d) { 91 fprintf(stderr, "d must divide h without remainder!\n"); 92 return 1; 93 } 94 params->h = h; 95 params->d = d; 96 params->n = n; 97 params->index_len = (h + 7) / 8; 98 xmss_params xmss_par; 99 if (xmss_set_params(&xmss_par, n, (h/d), w, k)) { 100 return 1; 101 } 102 params->xmss_par = xmss_par; 103 return 0; 104} 105 106/** 107 * Computes a leaf from a WOTS public key using an L-tree. 108 */ 109static void l_tree(unsigned char *leaf, unsigned char *wots_pk, const xmss_params *params, const unsigned char *pub_seed, uint32_t addr[8]) 110{ 111 unsigned int l = params->wots_par.len; 112 unsigned int n = params->n; 113 uint32_t i = 0; 114 uint32_t height = 0; 115 uint32_t bound; 116 117 //ADRS.setTreeHeight(0); 118 setTreeHeight(addr, height); 119 120 while (l > 1) { 121 bound = l >> 1; //floor(l / 2); 122 for (i = 0; i < bound; i++) { 123 //ADRS.setTreeIndex(i); 124 setTreeIndex(addr, i); 125 //wots_pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS); 126 hash_h(wots_pk+i*n, wots_pk+i*2*n, pub_seed, addr, n); 127 } 128 //if ( l % 2 == 1 ) { 129 if (l & 1) { 130 //pk[floor(l / 2) + 1] = pk[l]; 131 memcpy(wots_pk+(l>>1)*n, wots_pk+(l-1)*n, n); 132 //l = ceil(l / 2); 133 l=(l>>1)+1; 134 } 135 else { 136 //l = ceil(l / 2); 137 l=(l>>1); 138 } 139 //ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); 140 height++; 141 setTreeHeight(addr, height); 142 } 143 //return pk[0]; 144 memcpy(leaf, wots_pk, n); 145} 146 147/** 148 * Computes the leaf at a given address. First generates the WOTS key pair, then computes leaf using l_tree. As this happens position independent, we only require that addr encodes the right ltree-address. 149 */ 150static void gen_leaf_wots(unsigned char *leaf, const unsigned char *sk_seed, const xmss_params *params, const unsigned char *pub_seed, uint32_t ltree_addr[8], uint32_t ots_addr[8]) 151{ 152 unsigned char seed[params->n]; 153 unsigned char pk[params->wots_par.keysize]; 154 155 get_seed(seed, sk_seed, params->n, ots_addr); 156 wots_pkgen(pk, seed, &(params->wots_par), pub_seed, ots_addr); 157 158 l_tree(leaf, pk, params, pub_seed, ltree_addr); 159} 160 161static int treehash_minheight_on_stack(bds_state* state, const xmss_params *params, const treehash_inst *treehash) { 162 unsigned int r = params->h, i; 163 for (i = 0; i < treehash->stackusage; i++) { 164 if (state->stacklevels[state->stackoffset - i - 1] < r) { 165 r = state->stacklevels[state->stackoffset - i - 1]; 166 } 167 } 168 return r; 169} 170 171/** 172 * Merkle's TreeHash algorithm. The address only needs to initialize the first 78 bits of addr. Everything else will be set by treehash. 173 * Currently only used for key generation. 174 * 175 */ 176static void treehash_setup(unsigned char *node, int height, int index, bds_state *state, const unsigned char *sk_seed, const xmss_params *params, const unsigned char *pub_seed, const uint32_t addr[8]) 177{ 178 unsigned int idx = index; 179 unsigned int n = params->n; 180 unsigned int h = params->h; 181 unsigned int k = params->k; 182 // use three different addresses because at this point we use all three formats in parallel 183 uint32_t ots_addr[8]; 184 uint32_t ltree_addr[8]; 185 uint32_t node_addr[8]; 186 // only copy layer and tree address parts 187 memcpy(ots_addr, addr, 12); 188 // type = ots 189 setType(ots_addr, 0); 190 memcpy(ltree_addr, addr, 12); 191 setType(ltree_addr, 1); 192 memcpy(node_addr, addr, 12); 193 setType(node_addr, 2); 194 195 uint32_t lastnode, i; 196 unsigned char stack[(height+1)*n]; 197 unsigned int stacklevels[height+1]; 198 unsigned int stackoffset=0; 199 unsigned int nodeh; 200 201 lastnode = idx+(1<<height); 202 203 for (i = 0; i < h-k; i++) { 204 state->treehash[i].h = i; 205 state->treehash[i].completed = 1; 206 state->treehash[i].stackusage = 0; 207 } 208 209 i = 0; 210 for (; idx < lastnode; idx++) { 211 setLtreeADRS(ltree_addr, idx); 212 setOTSADRS(ots_addr, idx); 213 gen_leaf_wots(stack+stackoffset*n, sk_seed, params, pub_seed, ltree_addr, ots_addr); 214 stacklevels[stackoffset] = 0; 215 stackoffset++; 216 if (h - k > 0 && i == 3) { 217 memcpy(state->treehash[0].node, stack+stackoffset*n, n); 218 } 219 while (stackoffset>1 && stacklevels[stackoffset-1] == stacklevels[stackoffset-2]) 220 { 221 nodeh = stacklevels[stackoffset-1]; 222 if (i >> nodeh == 1) { 223 memcpy(state->auth + nodeh*n, stack+(stackoffset-1)*n, n); 224 } 225 else { 226 if (nodeh < h - k && i >> nodeh == 3) { 227 memcpy(state->treehash[nodeh].node, stack+(stackoffset-1)*n, n); 228 } 229 else if (nodeh >= h - k) { 230 memcpy(state->retain + ((1 << (h - 1 - nodeh)) + nodeh - h + (((i >> nodeh) - 3) >> 1)) * n, stack+(stackoffset-1)*n, n); 231 } 232 } 233 setTreeHeight(node_addr, stacklevels[stackoffset-1]); 234 setTreeIndex(node_addr, (idx >> (stacklevels[stackoffset-1]+1))); 235 hash_h(stack+(stackoffset-2)*n, stack+(stackoffset-2)*n, pub_seed, 236 node_addr, n); 237 stacklevels[stackoffset-2]++; 238 stackoffset--; 239 } 240 i++; 241 } 242 243 for (i = 0; i < n; i++) 244 node[i] = stack[i]; 245} 246 247static void treehash_update(treehash_inst *treehash, bds_state *state, const unsigned char *sk_seed, const xmss_params *params, const unsigned char *pub_seed, const uint32_t addr[8]) { 248 int n = params->n; 249 250 uint32_t ots_addr[8]; 251 uint32_t ltree_addr[8]; 252 uint32_t node_addr[8]; 253 // only copy layer and tree address parts 254 memcpy(ots_addr, addr, 12); 255 // type = ots 256 setType(ots_addr, 0); 257 memcpy(ltree_addr, addr, 12); 258 setType(ltree_addr, 1); 259 memcpy(node_addr, addr, 12); 260 setType(node_addr, 2); 261 262 setLtreeADRS(ltree_addr, treehash->next_idx); 263 setOTSADRS(ots_addr, treehash->next_idx); 264 265 unsigned char nodebuffer[2 * n]; 266 unsigned int nodeheight = 0; 267 gen_leaf_wots(nodebuffer, sk_seed, params, pub_seed, ltree_addr, ots_addr); 268 while (treehash->stackusage > 0 && state->stacklevels[state->stackoffset-1] == nodeheight) { 269 memcpy(nodebuffer + n, nodebuffer, n); 270 memcpy(nodebuffer, state->stack + (state->stackoffset-1)*n, n); 271 setTreeHeight(node_addr, nodeheight); 272 setTreeIndex(node_addr, (treehash->next_idx >> (nodeheight+1))); 273 hash_h(nodebuffer, nodebuffer, pub_seed, node_addr, n); 274 nodeheight++; 275 treehash->stackusage--; 276 state->stackoffset--; 277 } 278 if (nodeheight == treehash->h) { // this also implies stackusage == 0 279 memcpy(treehash->node, nodebuffer, n); 280 treehash->completed = 1; 281 } 282 else { 283 memcpy(state->stack + state->stackoffset*n, nodebuffer, n); 284 treehash->stackusage++; 285 state->stacklevels[state->stackoffset] = nodeheight; 286 state->stackoffset++; 287 treehash->next_idx++; 288 } 289} 290 291/** 292 * Computes a root node given a leaf and an authapth 293 */ 294static void validate_authpath(unsigned char *root, const unsigned char *leaf, unsigned long leafidx, const unsigned char *authpath, const xmss_params *params, const unsigned char *pub_seed, uint32_t addr[8]) 295{ 296 unsigned int n = params->n; 297 298 uint32_t i, j; 299 unsigned char buffer[2*n]; 300 301 // If leafidx is odd (last bit = 1), current path element is a right child and authpath has to go to the left. 302 // Otherwise, it is the other way around 303 if (leafidx & 1) { 304 for (j = 0; j < n; j++) 305 buffer[n+j] = leaf[j]; 306 for (j = 0; j < n; j++) 307 buffer[j] = authpath[j]; 308 } 309 else { 310 for (j = 0; j < n; j++) 311 buffer[j] = leaf[j]; 312 for (j = 0; j < n; j++) 313 buffer[n+j] = authpath[j]; 314 } 315 authpath += n; 316 317 for (i=0; i < params->h-1; i++) { 318 setTreeHeight(addr, i); 319 leafidx >>= 1; 320 setTreeIndex(addr, leafidx); 321 if (leafidx&1) { 322 hash_h(buffer+n, buffer, pub_seed, addr, n); 323 for (j = 0; j < n; j++) 324 buffer[j] = authpath[j]; 325 } 326 else { 327 hash_h(buffer, buffer, pub_seed, addr, n); 328 for (j = 0; j < n; j++) 329 buffer[j+n] = authpath[j]; 330 } 331 authpath += n; 332 } 333 setTreeHeight(addr, (params->h-1)); 334 leafidx >>= 1; 335 setTreeIndex(addr, leafidx); 336 hash_h(root, buffer, pub_seed, addr, n); 337} 338 339/** 340 * Performs one treehash update on the instance that needs it the most. 341 * Returns 1 if such an instance was not found 342 **/ 343static char bds_treehash_update(bds_state *state, unsigned int updates, const unsigned char *sk_seed, const xmss_params *params, unsigned char *pub_seed, const uint32_t addr[8]) { 344 uint32_t i, j; 345 unsigned int level, l_min, low; 346 unsigned int h = params->h; 347 unsigned int k = params->k; 348 unsigned int used = 0; 349 350 for (j = 0; j < updates; j++) { 351 l_min = h; 352 level = h - k; 353 for (i = 0; i < h - k; i++) { 354 if (state->treehash[i].completed) { 355 low = h; 356 } 357 else if (state->treehash[i].stackusage == 0) { 358 low = i; 359 } 360 else { 361 low = treehash_minheight_on_stack(state, params, &(state->treehash[i])); 362 } 363 if (low < l_min) { 364 level = i; 365 l_min = low; 366 } 367 } 368 if (level == h - k) { 369 break; 370 } 371 treehash_update(&(state->treehash[level]), state, sk_seed, params, pub_seed, addr); 372 used++; 373 } 374 return updates - used; 375} 376 377/** 378 * Updates the state (typically NEXT_i) by adding a leaf and updating the stack 379 * Returns 1 if all leaf nodes have already been processed 380 **/ 381static char bds_state_update(bds_state *state, const unsigned char *sk_seed, const xmss_params *params, unsigned char *pub_seed, const uint32_t addr[8]) { 382 uint32_t ltree_addr[8]; 383 uint32_t node_addr[8]; 384 uint32_t ots_addr[8]; 385 386 int n = params->n; 387 int h = params->h; 388 int k = params->k; 389 390 int nodeh; 391 int idx = state->next_leaf; 392 if (idx == 1 << h) { 393 return 1; 394 } 395 396 // only copy layer and tree address parts 397 memcpy(ots_addr, addr, 12); 398 // type = ots 399 setType(ots_addr, 0); 400 memcpy(ltree_addr, addr, 12); 401 setType(ltree_addr, 1); 402 memcpy(node_addr, addr, 12); 403 setType(node_addr, 2); 404 405 setOTSADRS(ots_addr, idx); 406 setLtreeADRS(ltree_addr, idx); 407 408 gen_leaf_wots(state->stack+state->stackoffset*n, sk_seed, params, pub_seed, ltree_addr, ots_addr); 409 410 state->stacklevels[state->stackoffset] = 0; 411 state->stackoffset++; 412 if (h - k > 0 && idx == 3) { 413 memcpy(state->treehash[0].node, state->stack+state->stackoffset*n, n); 414 } 415 while (state->stackoffset>1 && state->stacklevels[state->stackoffset-1] == state->stacklevels[state->stackoffset-2]) { 416 nodeh = state->stacklevels[state->stackoffset-1]; 417 if (idx >> nodeh == 1) { 418 memcpy(state->auth + nodeh*n, state->stack+(state->stackoffset-1)*n, n); 419 } 420 else { 421 if (nodeh < h - k && idx >> nodeh == 3) { 422 memcpy(state->treehash[nodeh].node, state->stack+(state->stackoffset-1)*n, n); 423 } 424 else if (nodeh >= h - k) { 425 memcpy(state->retain + ((1 << (h - 1 - nodeh)) + nodeh - h + (((idx >> nodeh) - 3) >> 1)) * n, state->stack+(state->stackoffset-1)*n, n); 426 } 427 } 428 setTreeHeight(node_addr, state->stacklevels[state->stackoffset-1]); 429 setTreeIndex(node_addr, (idx >> (state->stacklevels[state->stackoffset-1]+1))); 430 hash_h(state->stack+(state->stackoffset-2)*n, state->stack+(state->stackoffset-2)*n, pub_seed, node_addr, n); 431 432 state->stacklevels[state->stackoffset-2]++; 433 state->stackoffset--; 434 } 435 state->next_leaf++; 436 return 0; 437} 438 439/** 440 * Returns the auth path for node leaf_idx and computes the auth path for the 441 * next leaf node, using the algorithm described by Buchmann, Dahmen and Szydlo 442 * in "Post Quantum Cryptography", Springer 2009. 443 */ 444static void bds_round(bds_state *state, const unsigned long leaf_idx, const unsigned char *sk_seed, const xmss_params *params, unsigned char *pub_seed, uint32_t addr[8]) 445{ 446 unsigned int i; 447 unsigned int n = params->n; 448 unsigned int h = params->h; 449 unsigned int k = params->k; 450 451 unsigned int tau = h; 452 unsigned int startidx; 453 unsigned int offset, rowidx; 454 unsigned char buf[2 * n]; 455 456 uint32_t ots_addr[8]; 457 uint32_t ltree_addr[8]; 458 uint32_t node_addr[8]; 459 // only copy layer and tree address parts 460 memcpy(ots_addr, addr, 12); 461 // type = ots 462 setType(ots_addr, 0); 463 memcpy(ltree_addr, addr, 12); 464 setType(ltree_addr, 1); 465 memcpy(node_addr, addr, 12); 466 setType(node_addr, 2); 467 468 for (i = 0; i < h; i++) { 469 if (! ((leaf_idx >> i) & 1)) { 470 tau = i; 471 break; 472 } 473 } 474 475 if (tau > 0) { 476 memcpy(buf, state->auth + (tau-1) * n, n); 477 // we need to do this before refreshing state->keep to prevent overwriting 478 memcpy(buf + n, state->keep + ((tau-1) >> 1) * n, n); 479 } 480 if (!((leaf_idx >> (tau + 1)) & 1) && (tau < h - 1)) { 481 memcpy(state->keep + (tau >> 1)*n, state->auth + tau*n, n); 482 } 483 if (tau == 0) { 484 setLtreeADRS(ltree_addr, leaf_idx); 485 setOTSADRS(ots_addr, leaf_idx); 486 gen_leaf_wots(state->auth, sk_seed, params, pub_seed, ltree_addr, ots_addr); 487 } 488 else { 489 setTreeHeight(node_addr, (tau-1)); 490 setTreeIndex(node_addr, leaf_idx >> tau); 491 hash_h(state->auth + tau * n, buf, pub_seed, node_addr, n); 492 for (i = 0; i < tau; i++) { 493 if (i < h - k) { 494 memcpy(state->auth + i * n, state->treehash[i].node, n); 495 } 496 else { 497 offset = (1 << (h - 1 - i)) + i - h; 498 rowidx = ((leaf_idx >> i) - 1) >> 1; 499 memcpy(state->auth + i * n, state->retain + (offset + rowidx) * n, n); 500 } 501 } 502 503 for (i = 0; i < ((tau < h - k) ? tau : (h - k)); i++) { 504 startidx = leaf_idx + 1 + 3 * (1 << i); 505 if (startidx < 1U << h) { 506 state->treehash[i].h = i; 507 state->treehash[i].next_idx = startidx; 508 state->treehash[i].completed = 0; 509 state->treehash[i].stackusage = 0; 510 } 511 } 512 } 513} 514 515/* 516 * Generates a XMSS key pair for a given parameter set. 517 * Format sk: [(32bit) idx || SK_SEED || SK_PRF || PUB_SEED || root] 518 * Format pk: [root || PUB_SEED] omitting algo oid. 519 */ 520int xmss_keypair(unsigned char *pk, unsigned char *sk, bds_state *state, xmss_params *params) 521{ 522 unsigned int n = params->n; 523 // Set idx = 0 524 sk[0] = 0; 525 sk[1] = 0; 526 sk[2] = 0; 527 sk[3] = 0; 528 // Init SK_SEED (n byte), SK_PRF (n byte), and PUB_SEED (n byte) 529 randombytes(sk+4, 3*n); 530 // Copy PUB_SEED to public key 531 memcpy(pk+n, sk+4+2*n, n); 532 533 uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 534 535 // Compute root 536 treehash_setup(pk, params->h, 0, state, sk+4, params, sk+4+2*n, addr); 537 // copy root to sk 538 memcpy(sk+4+3*n, pk, n); 539 return 0; 540} 541 542/** 543 * Signs a message. 544 * Returns 545 * 1. an array containing the signature followed by the message AND 546 * 2. an updated secret key! 547 * 548 */ 549int xmss_sign(unsigned char *sk, bds_state *state, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg, unsigned long long msglen, const xmss_params *params) 550{ 551 unsigned int h = params->h; 552 unsigned int n = params->n; 553 unsigned int k = params->k; 554 uint16_t i = 0; 555 556 // Extract SK 557 unsigned long idx = ((unsigned long)sk[0] << 24) | ((unsigned long)sk[1] << 16) | ((unsigned long)sk[2] << 8) | sk[3]; 558 unsigned char sk_seed[n]; 559 memcpy(sk_seed, sk+4, n); 560 unsigned char sk_prf[n]; 561 memcpy(sk_prf, sk+4+n, n); 562 unsigned char pub_seed[n]; 563 memcpy(pub_seed, sk+4+2*n, n); 564 565 // index as 32 bytes string 566 unsigned char idx_bytes_32[32]; 567 to_byte(idx_bytes_32, idx, 32); 568 569 unsigned char hash_key[3*n]; 570 571 // Update SK 572 sk[0] = ((idx + 1) >> 24) & 255; 573 sk[1] = ((idx + 1) >> 16) & 255; 574 sk[2] = ((idx + 1) >> 8) & 255; 575 sk[3] = (idx + 1) & 255; 576 // -- Secret key for this non-forward-secure version is now updated. 577 // -- A productive implementation should use a file handle instead and write the updated secret key at this point! 578 579 // Init working params 580 unsigned char R[n]; 581 unsigned char msg_h[n]; 582 unsigned char ots_seed[n]; 583 uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 584 585 // --------------------------------- 586 // Message Hashing 587 // --------------------------------- 588 589 // Message Hash: 590 // First compute pseudorandom value 591 prf(R, idx_bytes_32, sk_prf, n); 592 // Generate hash key (R || root || idx) 593 memcpy(hash_key, R, n); 594 memcpy(hash_key+n, sk+4+3*n, n); 595 to_byte(hash_key+2*n, idx, n); 596 // Then use it for message digest 597 h_msg(msg_h, msg, msglen, hash_key, 3*n, n); 598 599 // Start collecting signature 600 *sig_msg_len = 0; 601 602 // Copy index to signature 603 sig_msg[0] = (idx >> 24) & 255; 604 sig_msg[1] = (idx >> 16) & 255; 605 sig_msg[2] = (idx >> 8) & 255; 606 sig_msg[3] = idx & 255; 607 608 sig_msg += 4; 609 *sig_msg_len += 4; 610 611 // Copy R to signature 612 for (i = 0; i < n; i++) 613 sig_msg[i] = R[i]; 614 615 sig_msg += n; 616 *sig_msg_len += n; 617 618 // ---------------------------------- 619 // Now we start to "really sign" 620 // ---------------------------------- 621 622 // Prepare Address 623 setType(ots_addr, 0); 624 setOTSADRS(ots_addr, idx); 625 626 // Compute seed for OTS key pair 627 get_seed(ots_seed, sk_seed, n, ots_addr); 628 629 // Compute WOTS signature 630 wots_sign(sig_msg, msg_h, ots_seed, &(params->wots_par), pub_seed, ots_addr); 631 632 sig_msg += params->wots_par.keysize; 633 *sig_msg_len += params->wots_par.keysize; 634 635 // the auth path was already computed during the previous round 636 memcpy(sig_msg, state->auth, h*n); 637 638 if (idx < (1U << h) - 1) { 639 bds_round(state, idx, sk_seed, params, pub_seed, ots_addr); 640 bds_treehash_update(state, (h - k) >> 1, sk_seed, params, pub_seed, ots_addr); 641 } 642 643/* TODO: save key/bds state here! */ 644 645 sig_msg += params->h*n; 646 *sig_msg_len += params->h*n; 647 648 //Whipe secret elements? 649 //zerobytes(tsk, CRYPTO_SECRETKEYBYTES); 650 651 652 memcpy(sig_msg, msg, msglen); 653 *sig_msg_len += msglen; 654 655 return 0; 656} 657 658/** 659 * Verifies a given message signature pair under a given public key. 660 */ 661int xmss_sign_open(unsigned char *msg, unsigned long long *msglen, const unsigned char *sig_msg, unsigned long long sig_msg_len, const unsigned char *pk, const xmss_params *params) 662{ 663 unsigned int n = params->n; 664 665 unsigned long long i, m_len; 666 unsigned long idx=0; 667 unsigned char wots_pk[params->wots_par.keysize]; 668 unsigned char pkhash[n]; 669 unsigned char root[n]; 670 unsigned char msg_h[n]; 671 unsigned char hash_key[3*n]; 672 673 unsigned char pub_seed[n]; 674 memcpy(pub_seed, pk+n, n); 675 676 // Init addresses 677 uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 678 uint32_t ltree_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 679 uint32_t node_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 680 681 setType(ots_addr, 0); 682 setType(ltree_addr, 1); 683 setType(node_addr, 2); 684 685 // Extract index 686 idx = ((unsigned long)sig_msg[0] << 24) | ((unsigned long)sig_msg[1] << 16) | ((unsigned long)sig_msg[2] << 8) | sig_msg[3]; 687 printf("verify:: idx = %lu\n", idx); 688 689 // Generate hash key (R || root || idx) 690 memcpy(hash_key, sig_msg+4,n); 691 memcpy(hash_key+n, pk, n); 692 to_byte(hash_key+2*n, idx, n); 693 694 sig_msg += (n+4); 695 sig_msg_len -= (n+4); 696 697 // hash message 698 unsigned long long tmp_sig_len = params->wots_par.keysize+params->h*n; 699 m_len = sig_msg_len - tmp_sig_len; 700 h_msg(msg_h, sig_msg + tmp_sig_len, m_len, hash_key, 3*n, n); 701 702 //----------------------- 703 // Verify signature 704 //----------------------- 705 706 // Prepare Address 707 setOTSADRS(ots_addr, idx); 708 // Check WOTS signature 709 wots_pkFromSig(wots_pk, sig_msg, msg_h, &(params->wots_par), pub_seed, ots_addr); 710 711 sig_msg += params->wots_par.keysize; 712 sig_msg_len -= params->wots_par.keysize; 713 714 // Compute Ltree 715 setLtreeADRS(ltree_addr, idx); 716 l_tree(pkhash, wots_pk, params, pub_seed, ltree_addr); 717 718 // Compute root 719 validate_authpath(root, pkhash, idx, sig_msg, params, pub_seed, node_addr); 720 721 sig_msg += params->h*n; 722 sig_msg_len -= params->h*n; 723 724 for (i = 0; i < n; i++) 725 if (root[i] != pk[i]) 726 goto fail; 727 728 *msglen = sig_msg_len; 729 for (i = 0; i < *msglen; i++) 730 msg[i] = sig_msg[i]; 731 732 return 0; 733 734 735fail: 736 *msglen = sig_msg_len; 737 for (i = 0; i < *msglen; i++) 738 msg[i] = 0; 739 *msglen = -1; 740 return -1; 741} 742 743/* 744 * Generates a XMSSMT key pair for a given parameter set. 745 * Format sk: [(ceil(h/8) bit) idx || SK_SEED || SK_PRF || PUB_SEED || root] 746 * Format pk: [root || PUB_SEED] omitting algo oid. 747 */ 748int xmssmt_keypair(unsigned char *pk, unsigned char *sk, bds_state *states, unsigned char *wots_sigs, xmssmt_params *params) 749{ 750 unsigned int n = params->n; 751 unsigned int i; 752 unsigned char ots_seed[params->n]; 753 // Set idx = 0 754 for (i = 0; i < params->index_len; i++) { 755 sk[i] = 0; 756 } 757 // Init SK_SEED (n byte), SK_PRF (n byte), and PUB_SEED (n byte) 758 randombytes(sk+params->index_len, 3*n); 759 // Copy PUB_SEED to public key 760 memcpy(pk+n, sk+params->index_len+2*n, n); 761 762 // Set address to point on the single tree on layer d-1 763 uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 764 setLayerADRS(addr, (params->d-1)); 765 // Set up state and compute wots signatures for all but topmost tree root 766 for (i = 0; i < params->d - 1; i++) { 767 // Compute seed for OTS key pair 768 treehash_setup(pk, params->xmss_par.h, 0, states + i, sk+params->index_len, &(params->xmss_par), pk+n, addr); 769 setLayerADRS(addr, (i+1)); 770 get_seed(ots_seed, sk+params->index_len, n, addr); 771 wots_sign(wots_sigs + i*params->xmss_par.wots_par.keysize, pk, ots_seed, &(params->xmss_par.wots_par), pk+n, addr); 772 } 773 treehash_setup(pk, params->xmss_par.h, 0, states + i, sk+params->index_len, &(params->xmss_par), pk+n, addr); 774 memcpy(sk+params->index_len+3*n, pk, n); 775 return 0; 776} 777 778/** 779 * Signs a message. 780 * Returns 781 * 1. an array containing the signature followed by the message AND 782 * 2. an updated secret key! 783 * 784 */ 785int xmssmt_sign(unsigned char *sk, bds_state *states, unsigned char *wots_sigs, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg, unsigned long long msglen, const xmssmt_params *params) 786{ 787 unsigned int n = params->n; 788 789 unsigned int tree_h = params->xmss_par.h; 790 unsigned int h = params->h; 791 unsigned int k = params->xmss_par.k; 792 unsigned int idx_len = params->index_len; 793 uint64_t idx_tree; 794 uint32_t idx_leaf; 795 uint64_t i, j; 796 int needswap_upto = -1; 797 unsigned int updates; 798 799 unsigned char sk_seed[n]; 800 unsigned char sk_prf[n]; 801 unsigned char pub_seed[n]; 802 // Init working params 803 unsigned char R[n]; 804 unsigned char msg_h[n]; 805 unsigned char hash_key[3*n]; 806 unsigned char ots_seed[n]; 807 uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 808 uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 809 unsigned char idx_bytes_32[32]; 810 bds_state tmp; 811 812 // Extract SK 813 unsigned long long idx = 0; 814 for (i = 0; i < idx_len; i++) { 815 idx |= ((unsigned long long)sk[i]) << 8*(idx_len - 1 - i); 816 } 817 818 memcpy(sk_seed, sk+idx_len, n); 819 memcpy(sk_prf, sk+idx_len+n, n); 820 memcpy(pub_seed, sk+idx_len+2*n, n); 821 822 // Update SK 823 for (i = 0; i < idx_len; i++) { 824 sk[i] = ((idx + 1) >> 8*(idx_len - 1 - i)) & 255; 825 } 826 // -- Secret key for this non-forward-secure version is now updated. 827 // -- A productive implementation should use a file handle instead and write the updated secret key at this point! 828 829 830 // --------------------------------- 831 // Message Hashing 832 // --------------------------------- 833 834 // Message Hash: 835 // First compute pseudorandom value 836 to_byte(idx_bytes_32, idx, 32); 837 prf(R, idx_bytes_32, sk_prf, n); 838 // Generate hash key (R || root || idx) 839 memcpy(hash_key, R, n); 840 memcpy(hash_key+n, sk+idx_len+3*n, n); 841 to_byte(hash_key+2*n, idx, n); 842 843 // Then use it for message digest 844 h_msg(msg_h, msg, msglen, hash_key, 3*n, n); 845 846 // Start collecting signature 847 *sig_msg_len = 0; 848 849 // Copy index to signature 850 for (i = 0; i < idx_len; i++) { 851 sig_msg[i] = (idx >> 8*(idx_len - 1 - i)) & 255; 852 } 853 854 sig_msg += idx_len; 855 *sig_msg_len += idx_len; 856 857 // Copy R to signature 858 for (i = 0; i < n; i++) 859 sig_msg[i] = R[i]; 860 861 sig_msg += n; 862 *sig_msg_len += n; 863 864 // ---------------------------------- 865 // Now we start to "really sign" 866 // ---------------------------------- 867 868 // Handle lowest layer separately as it is slightly different... 869 870 // Prepare Address 871 setType(ots_addr, 0); 872 idx_tree = idx >> tree_h; 873 idx_leaf = (idx & ((1 << tree_h)-1)); 874 setLayerADRS(ots_addr, 0); 875 setTreeADRS(ots_addr, idx_tree); 876 setOTSADRS(ots_addr, idx_leaf); 877 878 // Compute seed for OTS key pair 879 get_seed(ots_seed, sk_seed, n, ots_addr); 880 881 // Compute WOTS signature 882 wots_sign(sig_msg, msg_h, ots_seed, &(params->xmss_par.wots_par), pub_seed, ots_addr); 883 884 sig_msg += params->xmss_par.wots_par.keysize; 885 *sig_msg_len += params->xmss_par.wots_par.keysize; 886 887 memcpy(sig_msg, states[0].auth, tree_h*n); 888 sig_msg += tree_h*n; 889 *sig_msg_len += tree_h*n; 890 891 // prepare signature of remaining layers 892 for (i = 1; i < params->d; i++) { 893 // put WOTS signature in place 894 memcpy(sig_msg, wots_sigs + (i-1)*params->xmss_par.wots_par.keysize, params->xmss_par.wots_par.keysize); 895 896 sig_msg += params->xmss_par.wots_par.keysize; 897 *sig_msg_len += params->xmss_par.wots_par.keysize; 898 899 // put AUTH nodes in place 900 memcpy(sig_msg, states[i].auth, tree_h*n); 901 sig_msg += tree_h*n; 902 *sig_msg_len += tree_h*n; 903 } 904 905 updates = (tree_h - k) >> 1; 906 907 setTreeADRS(addr, (idx_tree + 1)); 908 // mandatory update for NEXT_0 (does not count towards h-k/2) if NEXT_0 exists 909 if ((1 + idx_tree) * (1 << tree_h) + idx_leaf < (1ULL << h)) { 910 bds_state_update(&states[params->d], sk_seed, &(params->xmss_par), pub_seed, addr); 911 } 912 913 for (i = 0; i < params->d; i++) { 914 // check if we're not at the end of a tree 915 if (! (((idx + 1) & ((1ULL << ((i+1)*tree_h)) - 1)) == 0)) { 916 idx_leaf = (idx >> (tree_h * i)) & ((1 << tree_h)-1); 917 idx_tree = (idx >> (tree_h * (i+1))); 918 setLayerADRS(addr, i); 919 setTreeADRS(addr, idx_tree); 920 if (i == (unsigned int) (needswap_upto + 1)) { 921 bds_round(&states[i], idx_leaf, sk_seed, &(params->xmss_par), pub_seed, addr); 922 } 923 updates = bds_treehash_update(&states[i], updates, sk_seed, &(params->xmss_par), pub_seed, addr); 924 setTreeADRS(addr, (idx_tree + 1)); 925 // if a NEXT-tree exists for this level; 926 if ((1 + idx_tree) * (1 << tree_h) + idx_leaf < (1ULL << (h - tree_h * i))) { 927 if (i > 0 && updates > 0 && states[params->d + i].next_leaf < (1ULL << h)) { 928 bds_state_update(&states[params->d + i], sk_seed, &(params->xmss_par), pub_seed, addr); 929 updates--; 930 } 931 } 932 } 933 else if (idx < (1ULL << h) - 1) { 934 memcpy(&tmp, states+params->d + i, sizeof(bds_state)); 935 memcpy(states+params->d + i, states + i, sizeof(bds_state)); 936 memcpy(states + i, &tmp, sizeof(bds_state)); 937 938 setLayerADRS(ots_addr, (i+1)); 939 setTreeADRS(ots_addr, ((idx + 1) >> ((i+2) * tree_h))); 940 setOTSADRS(ots_addr, (((idx >> ((i+1) * tree_h)) + 1) & ((1 << tree_h)-1))); 941 942 get_seed(ots_seed, sk+params->index_len, n, ots_addr); 943 wots_sign(wots_sigs + i*params->xmss_par.wots_par.keysize, states[i].stack, ots_seed, &(params->xmss_par.wots_par), pub_seed, ots_addr); 944 945 states[params->d + i].stackoffset = 0; 946 states[params->d + i].next_leaf = 0; 947 948 updates--; // WOTS-signing counts as one update 949 needswap_upto = i; 950 for (j = 0; j < tree_h-k; j++) { 951 states[i].treehash[j].completed = 1; 952 } 953 } 954 } 955 956 //Whipe secret elements? 957 //zerobytes(tsk, CRYPTO_SECRETKEYBYTES); 958 959 memcpy(sig_msg, msg, msglen); 960 *sig_msg_len += msglen; 961 962 return 0; 963} 964 965/** 966 * Verifies a given message signature pair under a given public key. 967 */ 968int xmssmt_sign_open(unsigned char *msg, unsigned long long *msglen, const unsigned char *sig_msg, unsigned long long sig_msg_len, const unsigned char *pk, const xmssmt_params *params) 969{ 970 unsigned int n = params->n; 971 972 unsigned int tree_h = params->xmss_par.h; 973 unsigned int idx_len = params->index_len; 974 uint64_t idx_tree; 975 uint32_t idx_leaf; 976 977 unsigned long long i, m_len; 978 unsigned long long idx=0; 979 unsigned char wots_pk[params->xmss_par.wots_par.keysize]; 980 unsigned char pkhash[n]; 981 unsigned char root[n]; 982 unsigned char msg_h[n]; 983 unsigned char hash_key[3*n]; 984 985 unsigned char pub_seed[n]; 986 memcpy(pub_seed, pk+n, n); 987 988 // Init addresses 989 uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 990 uint32_t ltree_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 991 uint32_t node_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 992 993 // Extract index 994 for (i = 0; i < idx_len; i++) { 995 idx |= ((unsigned long long)sig_msg[i]) << (8*(idx_len - 1 - i)); 996 } 997 printf("verify:: idx = %llu\n", idx); 998 sig_msg += idx_len; 999 sig_msg_len -= idx_len; 1000 1001 // Generate hash key (R || root || idx) 1002 memcpy(hash_key, sig_msg,n); 1003 memcpy(hash_key+n, pk, n); 1004 to_byte(hash_key+2*n, idx, n); 1005 1006 sig_msg += n; 1007 sig_msg_len -= n; 1008 1009 1010 // hash message (recall, R is now on pole position at sig_msg 1011 unsigned long long tmp_sig_len = (params->d * params->xmss_par.wots_par.keysize) + (params->h * n); 1012 m_len = sig_msg_len - tmp_sig_len; 1013 h_msg(msg_h, sig_msg + tmp_sig_len, m_len, hash_key, 3*n, n); 1014 1015 1016 //----------------------- 1017 // Verify signature 1018 //----------------------- 1019 1020 // Prepare Address 1021 idx_tree = idx >> tree_h; 1022 idx_leaf = (idx & ((1 << tree_h)-1)); 1023 setLayerADRS(ots_addr, 0); 1024 setTreeADRS(ots_addr, idx_tree); 1025 setType(ots_addr, 0); 1026 1027 memcpy(ltree_addr, ots_addr, 12); 1028 setType(ltree_addr, 1); 1029 1030 memcpy(node_addr, ltree_addr, 12); 1031 setType(node_addr, 2); 1032 1033 setOTSADRS(ots_addr, idx_leaf); 1034 1035 // Check WOTS signature 1036 wots_pkFromSig(wots_pk, sig_msg, msg_h, &(params->xmss_par.wots_par), pub_seed, ots_addr); 1037 1038 sig_msg += params->xmss_par.wots_par.keysize; 1039 sig_msg_len -= params->xmss_par.wots_par.keysize; 1040 1041 // Compute Ltree 1042 setLtreeADRS(ltree_addr, idx_leaf); 1043 l_tree(pkhash, wots_pk, &(params->xmss_par), pub_seed, ltree_addr); 1044 1045 // Compute root 1046 validate_authpath(root, pkhash, idx_leaf, sig_msg, &(params->xmss_par), pub_seed, node_addr); 1047 1048 sig_msg += tree_h*n; 1049 sig_msg_len -= tree_h*n; 1050 1051 for (i = 1; i < params->d; i++) { 1052 // Prepare Address 1053 idx_leaf = (idx_tree & ((1 << tree_h)-1)); 1054 idx_tree = idx_tree >> tree_h; 1055 1056 setLayerADRS(ots_addr, i); 1057 setTreeADRS(ots_addr, idx_tree); 1058 setType(ots_addr, 0); 1059 1060 memcpy(ltree_addr, ots_addr, 12); 1061 setType(ltree_addr, 1); 1062 1063 memcpy(node_addr, ltree_addr, 12); 1064 setType(node_addr, 2); 1065 1066 setOTSADRS(ots_addr, idx_leaf); 1067 1068 // Check WOTS signature 1069 wots_pkFromSig(wots_pk, sig_msg, root, &(params->xmss_par.wots_par), pub_seed, ots_addr); 1070 1071 sig_msg += params->xmss_par.wots_par.keysize; 1072 sig_msg_len -= params->xmss_par.wots_par.keysize; 1073 1074 // Compute Ltree 1075 setLtreeADRS(ltree_addr, idx_leaf); 1076 l_tree(pkhash, wots_pk, &(params->xmss_par), pub_seed, ltree_addr); 1077 1078 // Compute root 1079 validate_authpath(root, pkhash, idx_leaf, sig_msg, &(params->xmss_par), pub_seed, node_addr); 1080 1081 sig_msg += tree_h*n; 1082 sig_msg_len -= tree_h*n; 1083 1084 } 1085 1086 for (i = 0; i < n; i++) 1087 if (root[i] != pk[i]) 1088 goto fail; 1089 1090 *msglen = sig_msg_len; 1091 for (i = 0; i < *msglen; i++) 1092 msg[i] = sig_msg[i]; 1093 1094 return 0; 1095 1096 1097fail: 1098 *msglen = sig_msg_len; 1099 for (i = 0; i < *msglen; i++) 1100 msg[i] = 0; 1101 *msglen = -1; 1102 return -1; 1103} 1104