1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// SPDX-License-Identifier: MIT
/*
* This includes some computation methods that are shared between different
* subsystems of the HSS signature package
*/
#include <string.h>
#include "hss_internal.h"
#include "hss.h"
#include "hash.h"
#include "hss_thread.h"
#include "lm_ots_common.h"
#include "lm_ots.h"
#include "endian.h"
#include "hss_derive.h"
/* Count the number of 1 bits at the end (lsbits) of the integer */
/* Do it in the obvious way; straightline code may be faster (no */
/* unpredictable jumps, which are costly), but that would be less scrutable */
/* (and this code is "fast enough") */
static int trailing_1_bits(merkle_index_t n) {
int i;
for (i=0; n&1; n>>=1, i++)
;
return i;
}
/*
* Compute the value of an internal node within a Merkle tree
*/
static enum hss_error_code hss_compute_internal_node( unsigned char *dest,
merkle_index_t node_num,
const unsigned char *seed,
param_set_t lm_type,
param_set_t lm_ots_type,
unsigned h,
unsigned leaf_level,
const unsigned char *I) {
unsigned hash_size = hss_hash_length(h);
/* We're store intermediate nodes here */
unsigned char stack[ MAX_HASH * MAX_MERKLE_HEIGHT];
merkle_index_t tree_size = (merkle_index_t)1 << leaf_level;
merkle_index_t r = node_num;
int levels_to_bottom = 0;
if (r == 0) return hss_error_internal; /* So no to infinite loops */
while (r < tree_size) {
r <<= 1;
levels_to_bottom++;
}
merkle_index_t q = r - tree_size;
merkle_index_t i;
unsigned ots_len = (unsigned)lm_ots_get_public_key_len(lm_ots_type);
unsigned char pub_key[ LEAF_MAX_LEN ];
memcpy( pub_key + LEAF_I, I, I_LEN );
SET_D( pub_key + LEAF_D, D_LEAF );
struct seed_derive derive;
if (!hss_seed_derive_init( &derive, lm_type, lm_ots_type,
I, seed)) {
return hss_error_bad_param_set;
}
for (i=0;; i++, r++, q++) {
/* Generate the next OTS public key */
hss_seed_derive_set_q( &derive, q );
if (!lm_ots_generate_public_key(lm_ots_type, I,
q, &derive, pub_key + LEAF_PK, ots_len)) {
return hss_error_bad_param_set; /* The only reason the above */
/* could fail */
}
/*
* For the subtree which this leaf node forms the final piece, put the
* destination to where we'll want it, either on the stack, or if this
* is the final piece, to where the caller specified
*/
unsigned char *current_buf;
int stack_offset = trailing_1_bits( i );
if (stack_offset == levels_to_bottom) {
current_buf = dest;
} else {
current_buf = &stack[stack_offset * hash_size ];
}
/* Hash it to form the leaf node */
put_bigendian( pub_key + LEAF_R, r, 4);
union hash_context ctx;
hss_hash_ctx( current_buf, h, &ctx, pub_key, LEAF_LEN(hash_size) );
/* Work up the stack, combining right nodes with the left nodes */
/* that we've already computed */
int sp;
for (sp = 1; sp <= stack_offset; sp++) {
hss_combine_internal_nodes( current_buf,
&stack[(sp-1) * hash_size], current_buf,
h, I, hash_size,
r >> sp );
}
/* We're not at a left branch, or at the target node */
/* Because we've set current_buf to point to where we want to place */
/* the result of this loop, we don't need to memcpy it */
/* Check if this was the last leaf (and so we've just computed the */
/* target node) */
if (stack_offset == levels_to_bottom) {
/* We're at the target node; the node we were asked to compute */
/* We've already placed the value into dest, so we're all done */
break;
}
}
hss_seed_derive_done( &derive );
return hss_error_none;
}
/*
* Combine adjacent left and right nodes within the Merkle tree
* together
*/
void hss_combine_internal_nodes( unsigned char *dest,
const unsigned char *left_node, const unsigned char *right_node,
int h, const unsigned char *I, unsigned hash_size,
merkle_index_t node_num) {
unsigned char hash_val[ INTR_MAX_LEN ];
memcpy( hash_val + INTR_I, I, I_LEN );
put_bigendian( hash_val + INTR_R, node_num, 4 );
SET_D( hash_val + INTR_D, D_INTR );
memcpy( hash_val + INTR_PK, left_node, hash_size );
memcpy( hash_val + INTR_PK + hash_size, right_node, hash_size );
union hash_context ctx;
hss_hash_ctx( dest, h, &ctx, hash_val, INTR_LEN(hash_size) );
}
/*
* This computes an array of intermediate Merkle nodes given by data
* This may be run in a worker (non-main) thread
*/
void hss_gen_intermediate_tree(const void *data,
struct thread_collection *col) {
const struct intermed_tree_detail *d = data;
unsigned hash_len = hss_hash_length(d->h);
unsigned i;
for (i=0; i<d->node_count; i++) {
unsigned char result[ MAX_HASH ];
enum hss_error_code status = hss_compute_internal_node( result,
d->node_num + i,
d->seed,
d->lm_type,
d->lm_ots_type,
d->h,
d->tree_height,
d->I);
/* Report the results */
hss_thread_before_write(col);
if (status == hss_error_none) {
/* Copy out the resulting hash */
memcpy( d->dest + i*hash_len, result, hash_len );
} else {
/* Something went wrong; report the bad news */
*d->got_error = status;
hss_thread_after_write(col); /* No point in working more */
return;
}
hss_thread_after_write(col);
}
}