1 #include <string.h>
2
3 #include "address.h"
4 #include "params.h"
5 #include "thashx8.h"
6 #include "utils.h"
7
8 #include "utilsx8.h"
9
10 /**
11 * For a given leaf index, computes the authentication path and the resulting
12 * root node using Merkle's TreeHash algorithm.
13 * Expects the layer and tree parts of the tree_addr to be set, as well as the
14 * tree type (i.e. PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_ADDR_TYPE_HASHTREE or PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_ADDR_TYPE_FORSTREE).
15 * Applies the offset idx_offset to indices before building addresses, so that
16 * it is possible to continue counting indices across trees.
17 */
treehashx8(unsigned char * rootx8,unsigned char * auth_pathx8,unsigned char * stackx8,unsigned int * heights,const unsigned char * sk_seed,const unsigned char * pub_seed,const uint32_t leaf_idx[8],uint32_t idx_offset[8],uint32_t tree_height,void (* gen_leafx8)(unsigned char *,unsigned char *,unsigned char *,unsigned char *,unsigned char *,unsigned char *,unsigned char *,unsigned char *,const unsigned char *,const unsigned char *,uint32_t,uint32_t,uint32_t,uint32_t,uint32_t,uint32_t,uint32_t,uint32_t,const uint32_t[8],const hash_state *),uint32_t tree_addrx8[8* 8],const hash_state * state_seeded)18 static void treehashx8(unsigned char *rootx8, unsigned char *auth_pathx8,
19 unsigned char *stackx8, unsigned int *heights,
20 const unsigned char *sk_seed, const unsigned char *pub_seed,
21 const uint32_t leaf_idx[8], uint32_t idx_offset[8],
22 uint32_t tree_height,
23 void (*gen_leafx8)(
24 unsigned char * /* leaf0 */,
25 unsigned char * /* leaf1 */,
26 unsigned char * /* leaf2 */,
27 unsigned char * /* leaf3 */,
28 unsigned char * /* leaf4 */,
29 unsigned char * /* leaf5 */,
30 unsigned char * /* leaf6 */,
31 unsigned char * /* leaf7 */,
32 const unsigned char * /* sk_seed */,
33 const unsigned char * /* pub_seed */,
34 uint32_t /* addr_idx0 */,
35 uint32_t /* addr_idx1 */,
36 uint32_t /* addr_idx2 */,
37 uint32_t /* addr_idx3 */,
38 uint32_t /* addr_idx4 */,
39 uint32_t /* addr_idx5 */,
40 uint32_t /* addr_idx6 */,
41 uint32_t /* addr_idx7 */,
42 const uint32_t[8] /* tree_addr */,
43 const hash_state * /* state_seeded */),
44 uint32_t tree_addrx8[8 * 8],
45 const hash_state *state_seeded) {
46 unsigned int offset = 0;
47 uint32_t idx;
48 uint32_t tree_idx;
49 unsigned int j;
50
51 for (idx = 0; idx < (uint32_t)(1 << tree_height); idx++) {
52 /* Add the next leaf node to the stack. */
53 gen_leafx8(stackx8 + 0 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
54 stackx8 + 1 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
55 stackx8 + 2 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
56 stackx8 + 3 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
57 stackx8 + 4 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
58 stackx8 + 5 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
59 stackx8 + 6 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
60 stackx8 + 7 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + offset * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
61 sk_seed, pub_seed,
62 idx + idx_offset[0],
63 idx + idx_offset[1],
64 idx + idx_offset[2],
65 idx + idx_offset[3],
66 idx + idx_offset[4],
67 idx + idx_offset[5],
68 idx + idx_offset[6],
69 idx + idx_offset[7],
70 tree_addrx8,
71 state_seeded);
72 offset++;
73 heights[offset - 1] = 0;
74
75 /* If this is a node we need for the auth path.. */
76 for (j = 0; j < 8; j++) {
77 if ((leaf_idx[j] ^ 0x1) == idx) {
78 memcpy(auth_pathx8 + j * tree_height * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
79 stackx8 + j * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N, PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N);
80 }
81 }
82
83 /* While the top-most nodes are of equal height.. */
84 while (offset >= 2 && heights[offset - 1] == heights[offset - 2]) {
85 /* Compute index of the new node, in the next layer. */
86 tree_idx = (idx >> (heights[offset - 1] + 1));
87
88 /* Set the address of the node we're creating. */
89 for (j = 0; j < 8; j++) {
90 PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_set_tree_height(tree_addrx8 + j * 8, heights[offset - 1] + 1);
91 PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_set_tree_index(tree_addrx8 + j * 8,
92 tree_idx + (idx_offset[j] >> (heights[offset - 1] + 1)));
93 }
94 /* Hash the top-most nodes from the stack together. */
95 PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_thashx8_2(stackx8 + 0 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
96 stackx8 + 1 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
97 stackx8 + 2 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
98 stackx8 + 3 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
99 stackx8 + 4 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
100 stackx8 + 5 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
101 stackx8 + 6 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
102 stackx8 + 7 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
103 stackx8 + 0 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
104 stackx8 + 1 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
105 stackx8 + 2 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
106 stackx8 + 3 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
107 stackx8 + 4 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
108 stackx8 + 5 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
109 stackx8 + 6 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
110 stackx8 + 7 * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 2)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
111 pub_seed, tree_addrx8, state_seeded);
112 offset--;
113 /* Note that the top-most node is now one layer higher. */
114 heights[offset - 1]++;
115
116 /* If this is a node we need for the auth path.. */
117 for (j = 0; j < 8; j++) {
118 if (((leaf_idx[j] >> heights[offset - 1]) ^ 0x1) == tree_idx) {
119 memcpy(auth_pathx8 + j * tree_height * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + heights[offset - 1]*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N,
120 stackx8 + j * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N + (offset - 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N, PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N);
121 }
122 }
123 }
124 }
125
126 for (j = 0; j < 8; j++) {
127 memcpy(rootx8 + j * PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N, stackx8 + j * (tree_height + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N, PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N);
128 }
129 }
130
131 /* The wrappers below ensure we used fixed-size buffers on the stack (no VLAs) */
132
133
134 #define treehashx8_variant(name, size) \
135 void PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_treehashx8_##name( \
136 unsigned char *rootx8, unsigned char *auth_pathx8, \
137 const unsigned char *sk_seed, const unsigned char *pub_seed, \
138 const uint32_t leaf_idx[8], uint32_t idx_offset[8], \
139 void (*gen_leafx8)( \
140 unsigned char* /* leaf0 */, \
141 unsigned char* /* leaf1 */, \
142 unsigned char* /* leaf2 */, \
143 unsigned char* /* leaf3 */, \
144 unsigned char* /* leaf4 */, \
145 unsigned char* /* leaf5 */, \
146 unsigned char* /* leaf6 */, \
147 unsigned char* /* leaf7 */, \
148 const unsigned char* /* sk_seed */, \
149 const unsigned char* /* pub_seed */, \
150 uint32_t /* addr_idx0 */, \
151 uint32_t /* addr_idx1 */, \
152 uint32_t /* addr_idx2 */, \
153 uint32_t /* addr_idx3 */, \
154 uint32_t /* addr_idx4 */, \
155 uint32_t /* addr_idx5 */, \
156 uint32_t /* addr_idx6 */, \
157 uint32_t /* addr_idx7 */, \
158 const uint32_t[8] /* tree_addr */, \
159 const hash_state* /* state_seeded */), \
160 uint32_t tree_addrx8[8*8], \
161 const hash_state *state_seeded) \
162 { \
163 const uint32_t tree_height = (size); \
164 unsigned char stackx8[8*((size) + 1)*PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_N]; \
165 unsigned int heights[(size) + 1]; \
166 treehashx8(rootx8, auth_pathx8, stackx8, heights, sk_seed, pub_seed, \
167 leaf_idx, idx_offset, tree_height, gen_leafx8, tree_addrx8, state_seeded); \
168 }
169
170 treehashx8_variant(FORS_HEIGHT, PQCLEAN_SPHINCSSHA256128FROBUST_AVX2_FORS_HEIGHT)
171
172 #undef treehashx8_variant
173