1 #include <stdint.h>
2 #include <stdlib.h>
3 #include <string.h>
4 
5 #include "address.h"
6 #include "fors.h"
7 #include "hash.h"
8 #include "hash_state.h"
9 #include "thash.h"
10 #include "utils.h"
11 
fors_gen_sk(unsigned char * sk,const unsigned char * sk_seed,uint32_t fors_leaf_addr[8],const hash_state * hash_state_seeded)12 static void fors_gen_sk(unsigned char *sk, const unsigned char *sk_seed,
13                         uint32_t fors_leaf_addr[8], const hash_state *hash_state_seeded) {
14     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_prf_addr(
15         sk, sk_seed, fors_leaf_addr, hash_state_seeded);
16 }
17 
fors_sk_to_leaf(unsigned char * leaf,const unsigned char * sk,const unsigned char * pub_seed,uint32_t fors_leaf_addr[8],const hash_state * hash_state_seeded)18 static void fors_sk_to_leaf(unsigned char *leaf, const unsigned char *sk,
19                             const unsigned char *pub_seed,
20                             uint32_t fors_leaf_addr[8],
21                             const hash_state *hash_state_seeded) {
22     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_thash_1(
23         leaf, sk, pub_seed, fors_leaf_addr, hash_state_seeded);
24 }
25 
fors_gen_leaf(unsigned char * leaf,const unsigned char * sk_seed,const unsigned char * pub_seed,uint32_t addr_idx,const uint32_t fors_tree_addr[8],const hash_state * hash_state_seeded)26 static void fors_gen_leaf(unsigned char *leaf, const unsigned char *sk_seed,
27                           const unsigned char *pub_seed,
28                           uint32_t addr_idx, const uint32_t fors_tree_addr[8],
29                           const hash_state *hash_state_seeded) {
30     uint32_t fors_leaf_addr[8] = {0};
31 
32     /* Only copy the parts that must be kept in fors_leaf_addr. */
33     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(
34         fors_leaf_addr, fors_tree_addr);
35     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
36         fors_leaf_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_FORSTREE);
37     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_index(
38         fors_leaf_addr, addr_idx);
39 
40     fors_gen_sk(leaf, sk_seed, fors_leaf_addr, hash_state_seeded);
41     fors_sk_to_leaf(leaf, leaf, pub_seed, fors_leaf_addr, hash_state_seeded);
42 }
43 
44 /**
45  * Interprets m as PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT-bit unsigned integers.
46  * Assumes m contains at least PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES bits.
47  * Assumes indices has space for PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES integers.
48  */
message_to_indices(uint32_t * indices,const unsigned char * m)49 static void message_to_indices(uint32_t *indices, const unsigned char *m) {
50     unsigned int i, j;
51     unsigned int offset = 0;
52 
53     for (i = 0; i < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES; i++) {
54         indices[i] = 0;
55         for (j = 0; j < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT; j++) {
56             indices[i] ^= (((uint32_t)m[offset >> 3] >> (offset & 0x7)) & 0x1) << j;
57             offset++;
58         }
59     }
60 }
61 
62 /**
63  * Signs a message m, deriving the secret key from sk_seed and the FTS address.
64  * Assumes m contains at least PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES bits.
65  */
PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_fors_sign(unsigned char * sig,unsigned char * pk,const unsigned char * m,const unsigned char * sk_seed,const unsigned char * pub_seed,const uint32_t fors_addr[8],const hash_state * hash_state_seeded)66 void PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_fors_sign(
67     unsigned char *sig, unsigned char *pk,
68     const unsigned char *m,
69     const unsigned char *sk_seed, const unsigned char *pub_seed,
70     const uint32_t fors_addr[8], const hash_state *hash_state_seeded) {
71     uint32_t indices[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES];
72     unsigned char roots[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
73     uint32_t fors_tree_addr[8] = {0};
74     uint32_t fors_pk_addr[8] = {0};
75     uint32_t idx_offset;
76     unsigned int i;
77 
78     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(
79         fors_tree_addr, fors_addr);
80     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(
81         fors_pk_addr, fors_addr);
82 
83     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
84         fors_tree_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_FORSTREE);
85     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(
86         fors_pk_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_FORSPK);
87 
88     message_to_indices(indices, m);
89 
90     for (i = 0; i < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES; i++) {
91         idx_offset = i * (1 << PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT);
92 
93         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_height(
94             fors_tree_addr, 0);
95         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_index(
96             fors_tree_addr, indices[i] + idx_offset);
97 
98         /* Include the secret key part that produces the selected leaf node. */
99         fors_gen_sk(sig, sk_seed, fors_tree_addr, hash_state_seeded);
100         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
101 
102         /* Compute the authentication path for this leaf node. */
103         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_treehash_FORS_HEIGHT(
104             roots + i * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, sig, sk_seed, pub_seed,
105             indices[i], idx_offset, fors_gen_leaf, fors_tree_addr,
106             hash_state_seeded);
107         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT;
108     }
109 
110     /* Hash horizontally across all tree roots to derive the public key. */
111     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_thash_FORS_TREES(
112         pk, roots, pub_seed, fors_pk_addr, hash_state_seeded);
113 }
114 
115 /**
116  * Derives the FORS public key from a signature.
117  * This can be used for verification by comparing to a known public key, or to
118  * subsequently verify a signature on the derived public key. The latter is the
119  * typical use-case when used as an FTS below an OTS in a hypertree.
120  * Assumes m contains at least PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES bits.
121  */
PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_fors_pk_from_sig(unsigned char * pk,const unsigned char * sig,const unsigned char * m,const unsigned char * pub_seed,const uint32_t fors_addr[8],const hash_state * hash_state_seeded)122 void PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_fors_pk_from_sig(
123     unsigned char *pk,
124     const unsigned char *sig, const unsigned char *m,
125     const unsigned char *pub_seed, const uint32_t fors_addr[8],
126     const hash_state *hash_state_seeded) {
127     uint32_t indices[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES];
128     unsigned char roots[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
129     unsigned char leaf[PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N];
130     uint32_t fors_tree_addr[8] = {0};
131     uint32_t fors_pk_addr[8] = {0};
132     uint32_t idx_offset;
133     unsigned int i;
134 
135     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(fors_tree_addr, fors_addr);
136     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_copy_keypair_addr(fors_pk_addr, fors_addr);
137 
138     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(fors_tree_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_FORSTREE);
139     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_type(fors_pk_addr, PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_ADDR_TYPE_FORSPK);
140 
141     message_to_indices(indices, m);
142 
143     for (i = 0; i < PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_TREES; i++) {
144         idx_offset = i * (1 << PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT);
145 
146         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_height(fors_tree_addr, 0);
147         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_set_tree_index(fors_tree_addr, indices[i] + idx_offset);
148 
149         /* Derive the leaf from the included secret key part. */
150         fors_sk_to_leaf(leaf, sig, pub_seed, fors_tree_addr, hash_state_seeded);
151         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N;
152 
153         /* Derive the corresponding root node of this tree. */
154         PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_compute_root(roots + i * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N, leaf, indices[i], idx_offset, sig,
155                 PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT, pub_seed, fors_tree_addr, hash_state_seeded);
156         sig += PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_N * PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_FORS_HEIGHT;
157     }
158 
159     /* Hash horizontally across all tree roots to derive the public key. */
160     PQCLEAN_SPHINCSSHAKE256256SSIMPLE_CLEAN_thash_FORS_TREES(pk, roots, pub_seed, fors_pk_addr, hash_state_seeded);
161 }
162