1 #include <stddef.h> 2 #include <string.h> 3 4 #include "address.h" 5 #include "hash.h" 6 #include "hash_state.h" 7 #include "params.h" 8 #include "thash.h" 9 #include "utils.h" 10 11 /** 12 * Converts the value of 'in' to 'outlen' bytes in big-endian byte order. 13 */ 14 void PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_ull_to_bytes( 15 unsigned char *out, size_t outlen, unsigned long long in) { 16 17 /* Iterate over out in decreasing order, for big-endianness. */ 18 for (size_t i = outlen; i > 0; i--) { 19 out[i - 1] = in & 0xff; 20 in = in >> 8; 21 } 22 } 23 24 /** 25 * Converts the inlen bytes in 'in' from big-endian byte order to an integer. 26 */ 27 unsigned long long PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_bytes_to_ull( 28 const unsigned char *in, size_t inlen) { 29 unsigned long long retval = 0; 30 31 for (size_t i = 0; i < inlen; i++) { 32 retval |= ((unsigned long long)in[i]) << (8 * (inlen - 1 - i)); 33 } 34 return retval; 35 } 36 37 /** 38 * Computes a root node given a leaf and an auth path. 39 * Expects address to be complete other than the tree_height and tree_index. 40 */ 41 void PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_compute_root( 42 unsigned char *root, const unsigned char *leaf, 43 uint32_t leaf_idx, uint32_t idx_offset, 44 const unsigned char *auth_path, uint32_t tree_height, 45 const unsigned char *pub_seed, uint32_t addr[8], 46 const hash_state *hash_state_seeded) { 47 uint32_t i; 48 unsigned char buffer[2 * PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N]; 49 50 /* If leaf_idx is odd (last bit = 1), current path element is a right child 51 and auth_path has to go left. Otherwise it is the other way around. */ 52 if (leaf_idx & 1) { 53 memcpy(buffer + PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, leaf, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 54 memcpy(buffer, auth_path, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 55 } else { 56 memcpy(buffer, leaf, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 57 memcpy(buffer + PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, auth_path, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 58 } 59 auth_path += PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N; 60 61 for (i = 0; i < tree_height - 1; i++) { 62 leaf_idx >>= 1; 63 idx_offset >>= 1; 64 /* Set the address of the node we're creating. */ 65 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_set_tree_height(addr, i + 1); 66 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_set_tree_index( 67 addr, leaf_idx + idx_offset); 68 69 /* Pick the right or left neighbor, depending on parity of the node. */ 70 if (leaf_idx & 1) { 71 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_thash_2( 72 buffer + PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, buffer, pub_seed, addr, hash_state_seeded); 73 memcpy(buffer, auth_path, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 74 } else { 75 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_thash_2( 76 buffer, buffer, pub_seed, addr, hash_state_seeded); 77 memcpy(buffer + PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, auth_path, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 78 } 79 auth_path += PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N; 80 } 81 82 /* The last iteration is exceptional; we do not copy an auth_path node. */ 83 leaf_idx >>= 1; 84 idx_offset >>= 1; 85 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_set_tree_height(addr, tree_height); 86 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_set_tree_index( 87 addr, leaf_idx + idx_offset); 88 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_thash_2( 89 root, buffer, pub_seed, addr, hash_state_seeded); 90 } 91 92 /** 93 * For a given leaf index, computes the authentication path and the resulting 94 * root node using Merkle's TreeHash algorithm. 95 * Expects the layer and tree parts of the tree_addr to be set, as well as the 96 * tree type (i.e. PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_ADDR_TYPE_HASHTREE or PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_ADDR_TYPE_FORSTREE). 97 * Applies the offset idx_offset to indices before building addresses, so that 98 * it is possible to continue counting indices across trees. 99 */ 100 static void PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_treehash( 101 unsigned char *root, unsigned char *auth_path, 102 unsigned char *stack, unsigned int *heights, 103 const unsigned char *sk_seed, const unsigned char *pub_seed, 104 uint32_t leaf_idx, uint32_t idx_offset, uint32_t tree_height, 105 void (*gen_leaf)( 106 unsigned char * /* leaf */, 107 const unsigned char * /* sk_seed */, 108 const unsigned char * /* pub_seed */, 109 uint32_t /* addr_idx */, const uint32_t[8] /* tree_addr */, 110 const hash_state * /* hash_state_seeded */), 111 uint32_t tree_addr[8], 112 const hash_state *hash_state_seeded) { 113 114 unsigned int offset = 0; 115 uint32_t idx; 116 uint32_t tree_idx; 117 118 for (idx = 0; idx < (uint32_t)(1 << tree_height); idx++) { 119 /* Add the next leaf node to the stack. */ 120 gen_leaf(stack + offset * PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, 121 sk_seed, pub_seed, idx + idx_offset, tree_addr, 122 hash_state_seeded); 123 offset++; 124 heights[offset - 1] = 0; 125 126 /* If this is a node we need for the auth path.. */ 127 if ((leaf_idx ^ 0x1) == idx) { 128 memcpy(auth_path, stack + (offset - 1)*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 129 } 130 131 /* While the top-most nodes are of equal height.. */ 132 while (offset >= 2 && heights[offset - 1] == heights[offset - 2]) { 133 /* Compute index of the new node, in the next layer. */ 134 tree_idx = (idx >> (heights[offset - 1] + 1)); 135 136 /* Set the address of the node we're creating. */ 137 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_set_tree_height( 138 tree_addr, heights[offset - 1] + 1); 139 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_set_tree_index( 140 tree_addr, tree_idx + (idx_offset >> (heights[offset - 1] + 1))); 141 /* Hash the top-most nodes from the stack together. */ 142 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_thash_2( 143 stack + (offset - 2)*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, stack + (offset - 2)*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, 144 pub_seed, tree_addr, hash_state_seeded); 145 offset--; 146 /* Note that the top-most node is now one layer higher. */ 147 heights[offset - 1]++; 148 149 /* If this is a node we need for the auth path.. */ 150 if (((leaf_idx >> heights[offset - 1]) ^ 0x1) == tree_idx) { 151 memcpy(auth_path + heights[offset - 1]*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, 152 stack + (offset - 1)*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 153 } 154 } 155 } 156 memcpy(root, stack, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N); 157 } 158 159 /* The wrappers below ensure that we use fixed-size buffers on the stack */ 160 161 void PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_treehash_FORS_HEIGHT( 162 unsigned char *root, unsigned char *auth_path, 163 const unsigned char *sk_seed, const unsigned char *pub_seed, 164 uint32_t leaf_idx, uint32_t idx_offset, 165 void (*gen_leaf)( 166 unsigned char * /* leaf */, 167 const unsigned char * /* sk_seed */, 168 const unsigned char * /* pub_seed */, 169 uint32_t /* addr_idx */, const uint32_t[8] /* tree_addr */, 170 const hash_state * /* hash_state_seeded */), 171 uint32_t tree_addr[8], const hash_state *hash_state_seeded) { 172 173 unsigned char stack[(PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_FORS_HEIGHT + 1)*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N]; 174 unsigned int heights[PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_FORS_HEIGHT + 1]; 175 176 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_treehash( 177 root, auth_path, stack, heights, sk_seed, pub_seed, 178 leaf_idx, idx_offset, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_FORS_HEIGHT, gen_leaf, tree_addr, hash_state_seeded); 179 } 180 181 void PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_treehash_TREE_HEIGHT( 182 unsigned char *root, unsigned char *auth_path, 183 const unsigned char *sk_seed, const unsigned char *pub_seed, 184 uint32_t leaf_idx, uint32_t idx_offset, 185 void (*gen_leaf)( 186 unsigned char * /* leaf */, 187 const unsigned char * /* sk_seed */, 188 const unsigned char * /* pub_seed */, 189 uint32_t /* addr_idx */, const uint32_t[8] /* tree_addr */, 190 const hash_state * /* hash_state_seeded */), 191 uint32_t tree_addr[8], const hash_state *hash_state_seeded) { 192 193 unsigned char stack[(PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_TREE_HEIGHT + 1)*PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_N]; 194 unsigned int heights[PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_TREE_HEIGHT + 1]; 195 196 PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_treehash( 197 root, auth_path, stack, heights, sk_seed, pub_seed, 198 leaf_idx, idx_offset, PQCLEAN_SPHINCSSHAKE256128SSIMPLE_CLEAN_TREE_HEIGHT, gen_leaf, tree_addr, hash_state_seeded); 199 } 200