1 #include <stddef.h>
2 #include <stdint.h>
3 #include <string.h>
4 
5 #include "address.h"
6 #include "api.h"
7 #include "fors.h"
8 #include "hash.h"
9 #include "hash_state.h"
10 #include "params.h"
11 #include "randombytes.h"
12 #include "thash.h"
13 #include "utils.h"
14 #include "wots.h"
15 
16 /**
17  * Computes the leaf at a given address. First generates the WOTS key pair,
18  * then computes leaf by hashing horizontally.
19  */
20 static void wots_gen_leaf(unsigned char *leaf, const unsigned char *sk_seed,
21                           const unsigned char *pub_seed,
22                           uint32_t addr_idx, const uint32_t tree_addr[8],
23                           const hash_state *hash_state_seeded) {
24     unsigned char pk[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_WOTS_BYTES];
25     uint32_t wots_addr[8] = {0};
26     uint32_t wots_pk_addr[8] = {0};
27 
28     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
29         wots_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_WOTS);
30     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
31         wots_pk_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_WOTSPK);
32 
33     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_subtree_addr(
34         wots_addr, tree_addr);
35     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_keypair_addr(
36         wots_addr, addr_idx);
37     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_wots_gen_pk(
38         pk, sk_seed, pub_seed, wots_addr, hash_state_seeded);
39 
40     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(
41         wots_pk_addr, wots_addr);
42     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_thash_WOTS_LEN(
43         leaf, pk, pub_seed, wots_pk_addr, hash_state_seeded);
44 }
45 
46 /*
47  * Returns the length of a secret key, in bytes
48  */
49 size_t PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_secretkeybytes(void) {
50     return PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_SECRETKEYBYTES;
51 }
52 
53 /*
54  * Returns the length of a public key, in bytes
55  */
56 size_t PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_publickeybytes(void) {
57     return PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_PUBLICKEYBYTES;
58 }
59 
60 /*
61  * Returns the length of a signature, in bytes
62  */
63 size_t PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_bytes(void) {
64     return PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_BYTES;
65 }
66 
67 /*
68  * Returns the length of the seed required to generate a key pair, in bytes
69  */
70 size_t PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_seedbytes(void) {
71     return PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_SEEDBYTES;
72 }
73 
74 /*
75  * Generates an SPX key pair given a seed of length
76  * Format sk: [SK_SEED || SK_PRF || PUB_SEED || root]
77  * Format pk: [PUB_SEED || root]
78  */
79 int PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_seed_keypair(
80     uint8_t *pk, uint8_t *sk, const uint8_t *seed) {
81     /* We do not need the auth path in key generation, but it simplifies the
82        code to have just one treehash routine that computes both root and path
83        in one function. */
84     unsigned char auth_path[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
85     uint32_t top_tree_addr[8] = {0};
86     hash_state hash_state_seeded;
87 
88     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_layer_addr(
89         top_tree_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_D - 1);
90     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
91         top_tree_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_HASHTREE);
92 
93     /* Initialize SK_SEED, SK_PRF and PUB_SEED from seed. */
94     memcpy(sk, seed, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_SEEDBYTES);
95 
96     memcpy(pk, sk + 2 * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N);
97 
98     /* This hook allows the hash function instantiation to do whatever
99        preparation or computation it needs, based on the public seed. */
100     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_initialize_hash_function(&hash_state_seeded, pk, sk);
101 
102     /* Compute root node of the top-most subtree. */
103     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_treehash_TREE_HEIGHT(
104         sk + 3 * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, auth_path, sk, sk + 2 * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, 0, 0,
105         wots_gen_leaf, top_tree_addr, &hash_state_seeded);
106 
107     memcpy(pk + PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, sk + 3 * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N);
108 
109     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_destroy_hash_function(&hash_state_seeded);
110     return 0;
111 }
112 
113 /*
114  * Generates an SPX key pair.
115  * Format sk: [SK_SEED || SK_PRF || PUB_SEED || root]
116  * Format pk: [PUB_SEED || root]
117  */
118 int PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_keypair(
119     uint8_t *pk, uint8_t *sk) {
120     unsigned char seed[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_SEEDBYTES];
121     randombytes(seed, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_CRYPTO_SEEDBYTES);
122     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_seed_keypair(
123         pk, sk, seed);
124 
125     return 0;
126 }
127 
128 /**
129  * Returns an array containing a detached signature.
130  */
131 int PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_signature(
132     uint8_t *sig, size_t *siglen,
133     const uint8_t *m, size_t mlen, const uint8_t *sk) {
134     const unsigned char *sk_seed = sk;
135     const unsigned char *sk_prf = sk + PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
136     const unsigned char *pk = sk + 2 * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
137     const unsigned char *pub_seed = pk;
138 
139     unsigned char optrand[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
140     unsigned char mhash[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_MSG_BYTES];
141     unsigned char root[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
142     uint32_t i;
143     uint64_t tree;
144     uint32_t idx_leaf;
145     uint32_t wots_addr[8] = {0};
146     uint32_t tree_addr[8] = {0};
147 
148     hash_state hash_state_seeded;
149 
150     /* This hook allows the hash function instantiation to do whatever
151        preparation or computation it needs, based on the public seed. */
152     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_initialize_hash_function(
153         &hash_state_seeded,
154         pub_seed, sk_seed);
155 
156     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
157         wots_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_WOTS);
158     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
159         tree_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_HASHTREE);
160 
161     /* Optionally, signing can be made non-deterministic using optrand.
162        This can help counter side-channel attacks that would benefit from
163        getting a large number of traces when the signer uses the same nodes. */
164     randombytes(optrand, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N);
165     /* Compute the digest randomization value. */
166     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_gen_message_random(
167         sig, sk_prf, optrand, m, mlen, &hash_state_seeded);
168 
169     /* Derive the message digest and leaf index from R, PK and M. */
170     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_hash_message(
171         mhash, &tree, &idx_leaf, sig, pk, m, mlen, &hash_state_seeded);
172     sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
173 
174     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_addr(wots_addr, tree);
175     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_keypair_addr(
176         wots_addr, idx_leaf);
177 
178     /* Sign the message hash using FORS. */
179     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_fors_sign(
180         sig, root, mhash, sk_seed, pub_seed, wots_addr, &hash_state_seeded);
181     sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_BYTES;
182 
183     for (i = 0; i < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_D; i++) {
184         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_layer_addr(tree_addr, i);
185         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_addr(tree_addr, tree);
186 
187         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_subtree_addr(
188             wots_addr, tree_addr);
189         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_keypair_addr(
190             wots_addr, idx_leaf);
191 
192         /* Compute a WOTS signature. */
193         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_wots_sign(
194             sig, root, sk_seed, pub_seed, wots_addr, &hash_state_seeded);
195         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_WOTS_BYTES;
196 
197         /* Compute the authentication path for the used WOTS leaf. */
198         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_treehash_TREE_HEIGHT(
199             root, sig, sk_seed, pub_seed, idx_leaf, 0,
200             wots_gen_leaf, tree_addr, &hash_state_seeded);
201         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
202 
203         /* Update the indices for the next layer. */
204         idx_leaf = (tree & ((1 << PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT) - 1));
205         tree = tree >> PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT;
206     }
207 
208     *siglen = PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES;
209 
210     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_destroy_hash_function(&hash_state_seeded);
211     return 0;
212 }
213 
214 /**
215  * Verifies a detached signature and message under a given public key.
216  */
217 int PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_verify(
218     const uint8_t *sig, size_t siglen,
219     const uint8_t *m, size_t mlen, const uint8_t *pk) {
220     const unsigned char *pub_seed = pk;
221     const unsigned char *pub_root = pk + PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
222     unsigned char mhash[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_MSG_BYTES];
223     unsigned char wots_pk[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_WOTS_BYTES];
224     unsigned char root[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
225     unsigned char leaf[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
226     unsigned int i;
227     uint64_t tree;
228     uint32_t idx_leaf;
229     uint32_t wots_addr[8] = {0};
230     uint32_t tree_addr[8] = {0};
231     uint32_t wots_pk_addr[8] = {0};
232 
233     hash_state hash_state_seeded;
234 
235     if (siglen != PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES) {
236         return -1;
237     }
238 
239     /* This hook allows the hash function instantiation to do whatever
240        preparation or computation it needs, based on the public seed. */
241     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_initialize_hash_function(
242         &hash_state_seeded,
243         pub_seed, NULL);
244 
245     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
246         wots_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_WOTS);
247     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
248         tree_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_HASHTREE);
249     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
250         wots_pk_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_WOTSPK);
251 
252     /* Derive the message digest and leaf index from R || PK || M. */
253     /* The additional PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N is a result of the hash domain separator. */
254     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_hash_message(
255         mhash, &tree, &idx_leaf, sig, pk, m, mlen, &hash_state_seeded);
256     sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
257 
258     /* Layer correctly defaults to 0, so no need to set_layer_addr */
259     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_addr(wots_addr, tree);
260     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_keypair_addr(
261         wots_addr, idx_leaf);
262 
263     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_fors_pk_from_sig(
264         root, sig, mhash, pub_seed, wots_addr, &hash_state_seeded);
265     sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_BYTES;
266 
267     /* For each subtree.. */
268     for (i = 0; i < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_D; i++) {
269         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_layer_addr(tree_addr, i);
270         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_addr(tree_addr, tree);
271 
272         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_subtree_addr(
273             wots_addr, tree_addr);
274         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_keypair_addr(
275             wots_addr, idx_leaf);
276 
277         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(
278             wots_pk_addr, wots_addr);
279 
280         /* The WOTS public key is only correct if the signature was correct. */
281         /* Initially, root is the FORS pk, but on subsequent iterations it is
282            the root of the subtree below the currently processed subtree. */
283         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_wots_pk_from_sig(
284             wots_pk, sig, root, pub_seed, wots_addr, &hash_state_seeded);
285         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_WOTS_BYTES;
286 
287         /* Compute the leaf node using the WOTS public key. */
288         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_thash_WOTS_LEN(
289             leaf, wots_pk, pub_seed, wots_pk_addr, &hash_state_seeded);
290 
291         /* Compute the root node of this subtree. */
292         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_compute_root(
293             root, leaf, idx_leaf, 0, sig, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT,
294             pub_seed, tree_addr, &hash_state_seeded);
295         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
296 
297         /* Update the indices for the next layer. */
298         idx_leaf = (tree & ((1 << PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT) - 1));
299         tree = tree >> PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_TREE_HEIGHT;
300     }
301 
302     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_destroy_hash_function(&hash_state_seeded);
303     /* Check if the root node equals the root node in the public key. */
304     if (memcmp(root, pub_root, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N) != 0) {
305         return -1;
306     }
307 
308     return 0;
309 }
310 
311 
312 /**
313  * Returns an array containing the signature followed by the message.
314  */
315 int PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign(
316     uint8_t *sm, size_t *smlen,
317     const uint8_t *m, size_t mlen, const uint8_t *sk) {
318     size_t siglen;
319 
320     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_signature(
321         sm, &siglen, m, mlen, sk);
322 
323     memmove(sm + PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES, m, mlen);
324     *smlen = siglen + mlen;
325 
326     return 0;
327 }
328 
329 /**
330  * Verifies a given signature-message pair under a given public key.
331  */
332 int PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_open(
333     uint8_t *m, size_t *mlen,
334     const uint8_t *sm, size_t smlen, const uint8_t *pk) {
335     /* The API caller does not necessarily know what size a signature should be
336        but SPHINCS+ signatures are always exactly PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES. */
337     if (smlen < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES) {
338         memset(m, 0, smlen);
339         *mlen = 0;
340         return -1;
341     }
342 
343     *mlen = smlen - PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES;
344 
345     if (PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_crypto_sign_verify(
346                 sm, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES, sm + PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES, *mlen, pk)) {
347         memset(m, 0, smlen);
348         *mlen = 0;
349         return -1;
350     }
351 
352     /* If verification was successful, move the message to the right place. */
353     memmove(m, sm + PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_BYTES, *mlen);
354 
355     return 0;
356 }
357