1 #include <stdint.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 #include "wots.h"
11
12 // TODO clarify address expectations, and make them more uniform.
13 // TODO i.e. do we expect types to be set already?
14 // TODO and do we expect modifications or copies?
15
16 /**
17 * Computes the starting value for a chain, i.e. the secret key.
18 * Expects the address to be complete up to the chain address.
19 */
wots_gen_sk(unsigned char * sk,const unsigned char * sk_seed,uint32_t wots_addr[8],const hash_state * hash_state_seeded)20 static void wots_gen_sk(unsigned char *sk, const unsigned char *sk_seed,
21 uint32_t wots_addr[8],
22 const hash_state *hash_state_seeded) {
23 /* Make sure that the hash address is actually zeroed. */
24 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_set_hash_addr(wots_addr, 0);
25
26 /* Generate sk element. */
27 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_prf_addr(sk, sk_seed, wots_addr, hash_state_seeded);
28 }
29
30 /**
31 * Computes the chaining function.
32 * out and in have to be n-byte arrays.
33 *
34 * Interprets in as start-th value of the chain.
35 * addr has to contain the address of the chain.
36 */
gen_chain(unsigned char * out,const unsigned char * in,unsigned int start,unsigned int steps,const unsigned char * pub_seed,uint32_t addr[8],const hash_state * hash_state_seeded)37 static void gen_chain(unsigned char *out, const unsigned char *in,
38 unsigned int start, unsigned int steps,
39 const unsigned char *pub_seed, uint32_t addr[8],
40 const hash_state *hash_state_seeded) {
41 uint32_t i;
42
43 /* Initialize out with the value at position 'start'. */
44 memcpy(out, in, PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N);
45
46 /* Iterate 'steps' calls to the hash function. */
47 for (i = start; i < (start + steps) && i < PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_W; i++) {
48 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_set_hash_addr(addr, i);
49 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_thash_1(
50 out, out, pub_seed, addr, hash_state_seeded);
51 }
52 }
53
54 /**
55 * base_w algorithm as described in draft.
56 * Interprets an array of bytes as integers in base w.
57 * This only works when log_w is a divisor of 8.
58 */
base_w(unsigned int * output,const size_t out_len,const unsigned char * input)59 static void base_w(unsigned int *output, const size_t out_len,
60 const unsigned char *input) {
61 size_t in = 0;
62 size_t out = 0;
63 unsigned char total = 0;
64 unsigned int bits = 0;
65 size_t consumed;
66
67 for (consumed = 0; consumed < out_len; consumed++) {
68 if (bits == 0) {
69 total = input[in];
70 in++;
71 bits += 8;
72 }
73 bits -= PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LOGW;
74 output[out] = (unsigned int)((total >> bits) & (PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_W - 1));
75 out++;
76 }
77 }
78
79 /* Computes the WOTS+ checksum over a message (in base_w). */
wots_checksum(unsigned int * csum_base_w,const unsigned int * msg_base_w)80 static void wots_checksum(unsigned int *csum_base_w,
81 const unsigned int *msg_base_w) {
82 unsigned int csum = 0;
83 unsigned char csum_bytes[(PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN2 * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LOGW + 7) / 8];
84 unsigned int i;
85
86 /* Compute checksum. */
87 for (i = 0; i < PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN1; i++) {
88 csum += PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_W - 1 - msg_base_w[i];
89 }
90
91 /* Convert checksum to base_w. */
92 /* Make sure expected empty zero bits are the least significant bits. */
93 csum = csum << (8 - ((PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN2 * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LOGW) % 8));
94 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_ull_to_bytes(
95 csum_bytes, sizeof(csum_bytes), csum);
96 base_w(csum_base_w, PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN2, csum_bytes);
97 }
98
99 /* Takes a message and derives the matching chain lengths. */
chain_lengths(unsigned int * lengths,const unsigned char * msg)100 static void chain_lengths(unsigned int *lengths, const unsigned char *msg) {
101 base_w(lengths, PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN1, msg);
102 wots_checksum(lengths + PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN1, lengths);
103 }
104
105 /**
106 * WOTS key generation. Takes a 32 byte sk_seed, expands it to WOTS private key
107 * elements and computes the corresponding public key.
108 * It requires the seed pub_seed (used to generate bitmasks and hash keys)
109 * and the address of this WOTS key pair.
110 *
111 * Writes the computed public key to 'pk'.
112 */
PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_wots_gen_pk(unsigned char * pk,const unsigned char * sk_seed,const unsigned char * pub_seed,uint32_t addr[8],const hash_state * hash_state_seeded)113 void PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_wots_gen_pk(
114 unsigned char *pk, const unsigned char *sk_seed,
115 const unsigned char *pub_seed, uint32_t addr[8],
116 const hash_state *hash_state_seeded) {
117 uint32_t i;
118
119 for (i = 0; i < PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN; i++) {
120 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_set_chain_addr(addr, i);
121 wots_gen_sk(pk + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N, sk_seed, addr, hash_state_seeded);
122 gen_chain(pk + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N, pk + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N,
123 0, PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_W - 1, pub_seed, addr, hash_state_seeded);
124 }
125 }
126
127 /**
128 * Takes a n-byte message and the 32-byte sk_see to compute a signature 'sig'.
129 */
PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_wots_sign(unsigned char * sig,const unsigned char * msg,const unsigned char * sk_seed,const unsigned char * pub_seed,uint32_t addr[8],const hash_state * hash_state_seeded)130 void PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_wots_sign(
131 unsigned char *sig, const unsigned char *msg,
132 const unsigned char *sk_seed, const unsigned char *pub_seed,
133 uint32_t addr[8], const hash_state *hash_state_seeded) {
134 unsigned int lengths[PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN];
135 uint32_t i;
136
137 chain_lengths(lengths, msg);
138
139 for (i = 0; i < PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN; i++) {
140 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_set_chain_addr(addr, i);
141 wots_gen_sk(sig + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N, sk_seed, addr, hash_state_seeded);
142 gen_chain(sig + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N, sig + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N, 0, lengths[i], pub_seed, addr, hash_state_seeded);
143 }
144 }
145
146 /**
147 * Takes a WOTS signature and an n-byte message, computes a WOTS public key.
148 *
149 * Writes the computed public key to 'pk'.
150 */
PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_wots_pk_from_sig(unsigned char * pk,const unsigned char * sig,const unsigned char * msg,const unsigned char * pub_seed,uint32_t addr[8],const hash_state * hash_state_seeded)151 void PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_wots_pk_from_sig(
152 unsigned char *pk,
153 const unsigned char *sig, const unsigned char *msg,
154 const unsigned char *pub_seed, uint32_t addr[8],
155 const hash_state *hash_state_seeded) {
156 unsigned int lengths[PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN];
157 uint32_t i;
158
159 chain_lengths(lengths, msg);
160
161 for (i = 0; i < PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_LEN; i++) {
162 PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_set_chain_addr(addr, i);
163 gen_chain(pk + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N, sig + i * PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_N,
164 lengths[i], PQCLEAN_SPHINCSSHA256192SROBUST_CLEAN_WOTS_W - 1 - lengths[i], pub_seed, addr,
165 hash_state_seeded);
166 }
167 }
168