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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
// SPDX-License-Identifier: MIT
#if !defined( HSS_INTERNAL_H_ )
#define HSS_INTERNAL_H_
#include <stdlib.h>
#include "common_defs.h"
#include "hss.h"
#include "config.h"
#include "lms_namespace.h"
/*
* This is the central internal include file for the functions that make up
* this subsystem. It should not be used by applications
*/
#define PARAM_SET_COMPRESS_LEN 1 /* We assume that we can compress the */
/* lm_type and the lm_ots type for a */
/* single level into 1 byte */
#define PARM_SET_END 0xff /* We set this marker in the parameter set */
/* when fewer than the maximum levels are used */
/*
* The internal structure of a private key
*/
#define PRIVATE_KEY_INDEX 0
#define PRIVATE_KEY_INDEX_LEN 8 /* 2**64 signatures should be enough for */
/* everyone */
#define PRIVATE_KEY_PARAM_SET (PRIVATE_KEY_INDEX + PRIVATE_KEY_INDEX_LEN)
#define PRIVATE_KEY_PARAM_SET_LEN (PARAM_SET_COMPRESS_LEN * MAX_HSS_LEVELS)
#define PRIVATE_KEY_SEED (PRIVATE_KEY_PARAM_SET + PRIVATE_KEY_PARAM_SET_LEN)
#if SECRET_METHOD == 2
#define PRIVATE_KEY_SEED_LEN (SEED_LEN + I_LEN)
#else
#define PRIVATE_KEY_SEED_LEN SEED_LEN
#endif
#define PRIVATE_KEY_LEN (PRIVATE_KEY_SEED + PRIVATE_KEY_SEED_LEN) /* That's */
/* 48 bytes */
struct merkle_level;
struct hss_working_key {
unsigned levels;
enum hss_error_code status; /* What is the status of this key */
/* hss_error_none if everything looks ok */
/* Otherwise, the error code we report if */
/* we try to use this key to sign */
sequence_t reserve_count; /* The value written to the private key */
/* Will be higher than the 'current count' */
/* if some signaures are 'reserved' */
sequence_t max_count; /* The maximum count we can ever have */
unsigned autoreserve; /* How many signatures to attempt to */
/* reserve if the signing process hits */
/* the end of the current reservation */
size_t signature_len; /* The length of the HSS signature */
unsigned char *stack; /* The stack memory used by the subtrees */
/* The private key (in its entirety) */
unsigned char private_key[PRIVATE_KEY_LEN];
/* The pointer to the seed (contained within the private key) */
/* Warning: nonsyntaxic macro; need to be careful how we use this */
#define working_key_seed private_key + PRIVATE_KEY_SEED
size_t siglen[MAX_HSS_LEVELS]; /* The lengths of the signatures */
/* generated by the various levels */
size_t signed_pk_len[MAX_HSS_LEVELS]; /* The lengths of the signed */
/* public keys for the various levels */
unsigned char *signed_pk[MAX_HSS_LEVELS]; /* The current signed public */
/* keys for the nontop levels */
/* Each array element is that level's */
/* current root value, signed by the */
/* previous level. Unused for the */
/* topmost level */
struct merkle_level *tree[MAX_HSS_LEVELS]; /* The structures that manage */
/* each individual level */
};
#define MIN_SUBTREE 2 /* All subtrees (other than the root subtree) have */
/* at least 2 levels */
#define MAX_SUBLEVELS ((MAX_MERKLE_HEIGHT + MIN_SUBTREE - 1) / MIN_SUBTREE)
#if MAX_SUBLEVELS > (1 << (MIN_MERKLE_HEIGHT-1)) - 2
#error We need to rethink our parent tree update logic, as there is a
#error possibility we do not give the tree enough updates between signatures
/* One possible fix would be to increase the subtree size for extremely */
/* tall trees */
#endif
struct merkle_level {
unsigned level; /* Total number of levels */
unsigned h, hash_size; /* Hash function, width */
param_set_t lm_type;
param_set_t lm_ots_type; /* OTS parameter */
merkle_index_t current_index; /* The number of signatures this tree has */
/* generated so far */
merkle_index_t max_index; /* 1<<level - 1 */
unsigned sublevels; /* Total number of levels of subtrees */
unsigned subtree_size; /* Height up each subtree */
unsigned top_subtree_size; /* The top subtree might be shorter */
unsigned update_count;
/* For nonbottom trees, we get a chance to update ourselves during */
/* (some) signature operations. This flag indicates what we do */
/* with that chance */
#define UPDATE_NEXT 0 /* We update our NEXT_TREE */
#define UPDATE_PARENT 1 /* We kick the update to our parent tree */
#define UPDATE_BUILDING 2 /* For 2 .. 2 + sublevels - 2, we update the */
/* BUILDING_TREE subtree i-1 */
#define UPDATE_DONE 255 /* We've done all the updates we need to until */
/* the next signature operation */
/* For every subtree level, we have up to 3 different subtrees: */
/* ACTIVE_TREE; this is the subtree that the current authentication */
/* path goes through. It is always fully populated */
/* BUILDING_TREE; this is the subtree that is the next in line */
/* within the current Merkle tree. We gradually populate it as */
/* we generate signatures for the current subtree. When the */
/* authentication path shifts to this, this subtree will be */
/* fully populated, and we'll swap ACTIVE and BUILDING subtrees */
/* NEXT_TREE; this is the first subtree in the next Merkle tree. */
/* We gradually populate the NEXT_TREE's as we generate */
/* signatures for the current Merkle tree. When the current */
/* Merkle tree runs out, the NEXT_TREE's will be fully */
/* populated, and we'll swap ACTIVE and NEXT subtrees */
#define ACTIVE_TREE 0 /* The tree in the active path */
#define BUILDING_TREE 1 /* The tree in the next active path */
#define NEXT_TREE 2 /* The tree at the start of the next Merkle tree */
#define NUM_SUBTREE 3 /* Maximum number of subtrees we have at each level */
struct subtree *subtree[MAX_SUBLEVELS][NUM_SUBTREE];
/* The I values for the current Merkle tree, and the next one */
unsigned char I[I_LEN], I_next[I_LEN];
/* The seed values for the current Merkle tree, and the next one */
unsigned char seed[SEED_LEN], seed_next[SEED_LEN];
};
/*
* This stands for a single subtree */
struct subtree {
merkle_index_t current_index; /* For BUILDING_TREE, the number of OTS */
/* public key's we've generated so far */
/* For NEXT_TREE, 0 if haven't started on */
/* this subtree */
/* MAX_SUBINDEX if we've finished it */
/* Else number of OTS public keys so far */
/* For ACTIVE_TREE, unused; we'll use */
/* merkle_tree::current_index to */
/* determine where the authentication */
/* path currently is */
#define MAX_SUBINDEX (~(merkle_index_t)0)
merkle_index_t left_leaf; /* The index of the leftmost leaf below */
/* this subtree (0..2**tree->levels) */
unsigned level; /* The level that the root of this subtree */
/* is within the larger Merkle tree */
unsigned levels_below; /* The number of levels below this subtree */
/* in the Merkle tree */
unsigned char *stack; /* Pointer to the stack used when */
/* generating nodes; will be a pointer */
/* into the hss_working_key::stack array */
/* Used to incrementally compute bottom */
/* node values */
unsigned char nodes[1]; /* The actual subtree node values */
/* 2*(1<<subtree_size) - 1 of them */
};
/* Internal function to compress a list of parameters into a short format */
/* that we use internally */
bool hss_compress_param_set( unsigned char *compressed,
int levels,
const param_set_t *lm_type,
const param_set_t *lm_ots_type,
size_t len_compressed );
/* Internal function to generate the root seed, I value (based on the */
/* private seed). We do this (rather than selecting them at random) so */
/* that we don't need to store them in our private key; we can recompute */
bool hss_generate_root_seed_I_value(unsigned char *seed, unsigned char *I,
const unsigned char *master_seed);
/* Internal function to generate the seed, I value for a child Merkle tree */
/* (based on the seed, I value of the parent. We do this (rather than */
/* selecting them at random) so we have consistent values between reboots */
bool hss_generate_child_seed_I_value( unsigned char *seed, unsigned char *I,
const unsigned char *parent_seed,
const unsigned char *parent_I, merkle_index_t index,
param_set_t parent_lm, param_set_t parent_ots );
/* Combine two internal nodes */
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);
bool hss_create_signed_public_key(unsigned char *signed_key,
size_t len_signature,
struct merkle_level *tree,
struct merkle_level *parent,
struct hss_working_key *w);
/* Used to generate the bottom nodes of a subtree in parallel */
struct intermed_tree_detail {
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; /* Hash function */
unsigned tree_height;
const unsigned char *I;
unsigned node_count;
enum hss_error_code *got_error;
};
struct thread_collection;
void hss_gen_intermediate_tree(const void *data,
struct thread_collection *col);
#include "hss_zeroize.h"
/*
* Given a tree height (and whether it's the top level, and the hash size),
* this returns the subtree size that yields the least amount of memory
*/
int hss_smallest_subtree_size(int tree_height, int i, int n);
/*
* Here's the routine that a thread runs to verify its part of the signature
*/
struct verify_detail {
enum hss_error_code *got_error;
const unsigned char *public_key;
const void *message;
size_t message_len;
const unsigned char *signature;
size_t signature_len;
};
void validate_internal_sig(const void *data,
struct thread_collection *col);
struct seed_derive;
void lm_ots_generate_randomizer(unsigned char *c, unsigned n,
struct seed_derive *seed);
#endif /* HSS_INTERNAL_H_ */