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