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