summaryrefslogtreecommitdiff
path: root/xmss_fast.c
diff options
context:
space:
mode:
Diffstat (limited to 'xmss_fast.c')
-rw-r--r--xmss_fast.c1099
1 files changed, 1099 insertions, 0 deletions
diff --git a/xmss_fast.c b/xmss_fast.c
new file mode 100644
index 000000000..7ddc92f83
--- /dev/null
+++ b/xmss_fast.c
@@ -0,0 +1,1099 @@
1/*
2xmss_fast.c version 20160722
3Andreas Hülsing
4Joost Rijneveld
5Public 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 */
30static 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 */
47int 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 */
66void 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 */
84int 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 */
105static 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 */
146static 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
157static 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 */
172static 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
243static 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 */
290static 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 **/
339static 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 **/
377static 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 */
440static 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 */
516int 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 */
545int 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 */
657int 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
731fail:
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 */
744int 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 */
781int 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 */
964int 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
1093fail:
1094 *msglen = sig_msg_len;
1095 for (i = 0; i < *msglen; i++)
1096 msg[i] = 0;
1097 *msglen = -1;
1098 return -1;
1099}