1 /*
2 * Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include <string.h>
11 #include <openssl/crypto.h>
12 #include "slh_dsa_local.h"
13 #include "slh_dsa_key.h"
14
15 /* For the parameter sets defined there is only one w value */
16 #define SLH_WOTS_LOGW 4
17 #define SLH_WOTS_W 16
18 #define SLH_WOTS_LEN1(n) (2 * (n))
19 #define SLH_WOTS_LEN2 3
20 #define SLH_WOTS_CHECKSUM_LEN ((SLH_WOTS_LEN2 + SLH_WOTS_LOGW + 7) / 8)
21 #define SLH_WOTS_LEN_MAX SLH_WOTS_LEN(SLH_MAX_N)
22 #define NIBBLE_MASK 15
23 #define NIBBLE_SHIFT 4
24
25 /*
26 * @brief Convert a byte array to a byte array of (4 bit) nibbles
27 * This is a Variant of the FIPS 205 Algorithm 4 base_2^b function.
28 *
29 * @param in A byte message to convert
30 * @param in_len The size of |in|.
31 * @param out The returned array of nibbles, with a size of 2*|in_len|
32 */
slh_bytes_to_nibbles(const uint8_t * in,size_t in_len,uint8_t * out)33 static ossl_inline void slh_bytes_to_nibbles(const uint8_t *in, size_t in_len,
34 uint8_t *out)
35 {
36 size_t consumed = 0;
37
38 for (consumed = 0; consumed < in_len; consumed++) {
39 *out++ = (*in >> NIBBLE_SHIFT);
40 *out++ = (*in++ & NIBBLE_MASK);
41 }
42 }
43
44 /*
45 * With w = 16 the maximum checksum is 0xF * n which fits into 12 bits
46 * which is 3 nibbles.
47 *
48 * This is effectively a cutdown version of Algorithm 7: steps 3 to 6
49 * which does a complicated base2^b(tobyte()) operation.
50 */
compute_checksum_nibbles(const uint8_t * in,size_t in_len,uint8_t * out)51 static ossl_inline void compute_checksum_nibbles(const uint8_t *in, size_t in_len,
52 uint8_t *out)
53 {
54 size_t i;
55 uint16_t csum = 0;
56
57 /* Compute checksum */
58 for (i = 0; i < in_len; ++i)
59 csum += in[i];
60 /*
61 * This line is effectively the same as doing csum += NIBBLE_MASK - in[i]
62 * in the loop above.
63 */
64 csum = (uint16_t)(NIBBLE_MASK * in_len) - csum;
65
66 /* output checksum as 3 nibbles */
67 out[0] = (csum >> (2 * NIBBLE_SHIFT)) & NIBBLE_MASK;
68 out[1] = (csum >> NIBBLE_SHIFT) & NIBBLE_MASK;
69 out[2] = csum & NIBBLE_MASK;
70 }
71
72 /**
73 * @brief WOTS+ Chaining function
74 * See FIPS 205 Section 5 Algorithm 5
75 *
76 * Iterates using a hash function on the input |steps| times starting at index
77 * |start|. (Internally the |adrs| hash address is used to update the chaining
78 * index).
79 *
80 * @param ctx Contains SLH_DSA algorithm functions and constants.
81 * @param in An input string of |n| bytes
82 * @param start_index The chaining start index
83 * @param steps The number of iterations starting from |start_index|
84 * Note |start_index| + |steps| < w
85 * (where w = 16 indicates the length of the hash chains)
86 * @param pk_seed A public key seed (which is added to the hash)
87 * @param adrs An ADRS object which has a type of WOTS_HASH, and has a layer
88 * address, tree address, key pair address and chain address
89 * @params wpkt A WPACKET object to write the hash chain to (n bytes are written)
90 * @returns 1 on success, or 0 on error.
91 */
slh_wots_chain(SLH_DSA_HASH_CTX * ctx,const uint8_t * in,uint8_t start_index,uint8_t steps,const uint8_t * pk_seed,uint8_t * adrs,WPACKET * wpkt)92 static int slh_wots_chain(SLH_DSA_HASH_CTX *ctx, const uint8_t *in,
93 uint8_t start_index, uint8_t steps,
94 const uint8_t *pk_seed, uint8_t *adrs, WPACKET *wpkt)
95 {
96 const SLH_DSA_KEY *key = ctx->key;
97 SLH_HASH_FUNC_DECLARE(key, hashf);
98 SLH_ADRS_FUNC_DECLARE(key, adrsf);
99 SLH_HASH_FN_DECLARE(hashf, F);
100 SLH_ADRS_FN_DECLARE(adrsf, set_hash_address);
101 size_t j = start_index, end_index;
102 size_t n = key->params->n;
103 uint8_t *tmp; /* Pointer into the |wpkt| buffer */
104 size_t tmp_len = n;
105
106 if (steps == 0)
107 return WPACKET_memcpy(wpkt, in, n);
108
109 if (!WPACKET_allocate_bytes(wpkt, tmp_len, &tmp))
110 return 0;
111
112 set_hash_address(adrs, j++);
113 if (!F(ctx, pk_seed, adrs, in, n, tmp, tmp_len))
114 return 0;
115
116 end_index = start_index + steps;
117 for (; j < end_index; ++j) {
118 set_hash_address(adrs, j);
119 if (!F(ctx, pk_seed, adrs, tmp, n, tmp, tmp_len))
120 return 0;
121 }
122 return 1;
123 }
124
125 /**
126 * @brief WOTS+ Public key generation.
127 * See FIPS 205 Section 5.1 Algorithm 6
128 *
129 * @param ctx Contains SLH_DSA algorithm functions and constants.
130 * @param sk_seed A private key seed of size |n|
131 * @param pk_seed A public key seed of size |n|
132 * @param adrs An ADRS object containing the layer address, tree address and
133 * keypair address of the WOTS+ public key to generate.
134 * @param pk_out The generated public key of size |n|
135 * @param pk_out_len The maximum size of |pk_out|
136 * @returns 1 on success, or 0 on error.
137 */
ossl_slh_wots_pk_gen(SLH_DSA_HASH_CTX * ctx,const uint8_t * sk_seed,const uint8_t * pk_seed,uint8_t * adrs,uint8_t * pk_out,size_t pk_out_len)138 int ossl_slh_wots_pk_gen(SLH_DSA_HASH_CTX *ctx,
139 const uint8_t *sk_seed, const uint8_t *pk_seed,
140 uint8_t *adrs, uint8_t *pk_out, size_t pk_out_len)
141 {
142 int ret = 0;
143 const SLH_DSA_KEY *key = ctx->key;
144 size_t n = key->params->n;
145 size_t i, len = SLH_WOTS_LEN(n); /* 2 * n + 3 */
146 uint8_t sk[SLH_MAX_N];
147 uint8_t tmp[SLH_WOTS_LEN_MAX * SLH_MAX_N];
148 WPACKET pkt, *tmp_wpkt = &pkt; /* Points to the |tmp| buffer */
149 size_t tmp_len = 0;
150
151 SLH_HASH_FUNC_DECLARE(key, hashf);
152 SLH_ADRS_FUNC_DECLARE(key, adrsf);
153 SLH_HASH_FN_DECLARE(hashf, PRF);
154 SLH_ADRS_FN_DECLARE(adrsf, set_chain_address);
155 SLH_ADRS_DECLARE(sk_adrs);
156 SLH_ADRS_DECLARE(wots_pk_adrs);
157
158 if (!WPACKET_init_static_len(tmp_wpkt, tmp, sizeof(tmp), 0))
159 return 0;
160 adrsf->copy(sk_adrs, adrs);
161 adrsf->set_type_and_clear(sk_adrs, SLH_ADRS_TYPE_WOTS_PRF);
162 adrsf->copy_keypair_address(sk_adrs, adrs);
163
164 for (i = 0; i < len; ++i) { /* len = 2n + 3 */
165 set_chain_address(sk_adrs, i);
166 if (!PRF(ctx, pk_seed, sk_seed, sk_adrs, sk, sizeof(sk)))
167 goto end;
168
169 set_chain_address(adrs, i);
170 if (!slh_wots_chain(ctx, sk, 0, NIBBLE_MASK, pk_seed, adrs, tmp_wpkt))
171 goto end;
172 }
173
174 if (!WPACKET_get_total_written(tmp_wpkt, &tmp_len)) /* should be n * (2 * n + 3) */
175 goto end;
176 adrsf->copy(wots_pk_adrs, adrs);
177 adrsf->set_type_and_clear(wots_pk_adrs, SLH_ADRS_TYPE_WOTS_PK);
178 adrsf->copy_keypair_address(wots_pk_adrs, adrs);
179 ret = hashf->T(ctx, pk_seed, wots_pk_adrs, tmp, tmp_len, pk_out, pk_out_len);
180 end:
181 WPACKET_finish(tmp_wpkt);
182 OPENSSL_cleanse(tmp, sizeof(tmp));
183 OPENSSL_cleanse(sk, n);
184 return ret;
185 }
186
187 /**
188 * @brief WOTS+ Signature generation
189 * See FIPS 205 Section 5.2 Algorithm 7
190 *
191 * The returned signature size is len * |n| bytes (where len = 2 * |n| + 3).
192 *
193 * @param ctx Contains SLH_DSA algorithm functions and constants.
194 * @param msg An input message of size |n| bytes.
195 * The message is either an XMSS or FORS public key
196 * @param sk_seed The private key seed of size |n| bytes
197 * @param pk_seed The public key seed of size |n| bytes
198 * @param adrs An address containing the layer address, tree address and key
199 * pair address. The size is either 32 or 22 bytes.
200 * @param sig_wpkt A WPACKET object to write the signature to.
201 * @returns 1 on success, or 0 on error.
202 */
ossl_slh_wots_sign(SLH_DSA_HASH_CTX * ctx,const uint8_t * msg,const uint8_t * sk_seed,const uint8_t * pk_seed,uint8_t * adrs,WPACKET * sig_wpkt)203 int ossl_slh_wots_sign(SLH_DSA_HASH_CTX *ctx, const uint8_t *msg,
204 const uint8_t *sk_seed, const uint8_t *pk_seed,
205 uint8_t *adrs, WPACKET *sig_wpkt)
206 {
207 int ret = 0;
208 const SLH_DSA_KEY *key = ctx->key;
209 uint8_t msg_and_csum_nibbles[SLH_WOTS_LEN_MAX]; /* size is >= 2 * n + 3 */
210 uint8_t sk[SLH_MAX_N];
211 size_t i;
212 size_t n = key->params->n;
213 size_t len1 = SLH_WOTS_LEN1(n); /* 2 * n = the msg length in nibbles */
214 size_t len = len1 + SLH_WOTS_LEN2; /* 2 * n + 3 (3 checksum nibbles) */
215
216 SLH_ADRS_DECLARE(sk_adrs);
217 SLH_HASH_FUNC_DECLARE(key, hashf);
218 SLH_ADRS_FUNC_DECLARE(key, adrsf);
219 SLH_HASH_FN_DECLARE(hashf, PRF);
220 SLH_ADRS_FN_DECLARE(adrsf, set_chain_address);
221
222 /*
223 * Convert n message bytes to 2*n base w=16 integers
224 * i.e. Convert message to an array of 2*n nibbles.
225 */
226 slh_bytes_to_nibbles(msg, n, msg_and_csum_nibbles);
227 /* Compute a 12 bit checksum and add it to the end */
228 compute_checksum_nibbles(msg_and_csum_nibbles, len1, msg_and_csum_nibbles + len1);
229
230 adrsf->copy(sk_adrs, adrs);
231 adrsf->set_type_and_clear(sk_adrs, SLH_ADRS_TYPE_WOTS_PRF);
232 adrsf->copy_keypair_address(sk_adrs, adrs);
233
234 for (i = 0; i < len; ++i) {
235 set_chain_address(sk_adrs, i);
236 /* compute chain i secret */
237 if (!PRF(ctx, pk_seed, sk_seed, sk_adrs, sk, sizeof(sk)))
238 goto err;
239 set_chain_address(adrs, i);
240 /* compute chain i signature */
241 if (!slh_wots_chain(ctx, sk, 0, msg_and_csum_nibbles[i],
242 pk_seed, adrs, sig_wpkt))
243 goto err;
244 }
245 ret = 1;
246 err:
247 return ret;
248 }
249
250 /**
251 * @brief Compute a candidate WOTS+ public key from a message and signature
252 * See FIPS 205 Section 5.3 Algorithm 8
253 *
254 * The size of the signature is len * |n| bytes (where len = 2 * |n| + 3).
255 *
256 * @param ctx Contains SLH_DSA algorithm functions and constants.
257 * @param sig_rpkt A PACKET object to read a WOTS+ signature from
258 * @param msg A message of size |n| bytes.
259 * @param pk_seed The public key seed of size |n|.
260 * @param adrs An ADRS object containing the layer address, tree address and
261 * key pair address that of the WOTS+ key used to sign the message.
262 * @param pk_out The returned public key candidate of size |n|
263 * @param pk_out_len The maximum size of |pk_out|
264 * @returns 1 on success, or 0 on error.
265 */
ossl_slh_wots_pk_from_sig(SLH_DSA_HASH_CTX * ctx,PACKET * sig_rpkt,const uint8_t * msg,const uint8_t * pk_seed,uint8_t * adrs,uint8_t * pk_out,size_t pk_out_len)266 int ossl_slh_wots_pk_from_sig(SLH_DSA_HASH_CTX *ctx,
267 PACKET *sig_rpkt, const uint8_t *msg,
268 const uint8_t *pk_seed, uint8_t *adrs,
269 uint8_t *pk_out, size_t pk_out_len)
270 {
271 int ret = 0;
272 const SLH_DSA_KEY *key = ctx->key;
273 uint8_t msg_and_csum_nibbles[SLH_WOTS_LEN_MAX];
274 size_t i;
275 size_t n = key->params->n;
276 size_t len1 = SLH_WOTS_LEN1(n);
277 size_t len = len1 + SLH_WOTS_LEN2; /* 2n + 3 */
278 const uint8_t *sig_i; /* Pointer into |sig_rpkt| buffer */
279 uint8_t tmp[SLH_WOTS_LEN_MAX * SLH_MAX_N];
280 WPACKET pkt, *tmp_pkt = &pkt;
281 size_t tmp_len = 0;
282
283 SLH_HASH_FUNC_DECLARE(key, hashf);
284 SLH_ADRS_FUNC_DECLARE(key, adrsf);
285 SLH_ADRS_FN_DECLARE(adrsf, set_chain_address);
286 SLH_ADRS_DECLARE(wots_pk_adrs);
287
288 if (!WPACKET_init_static_len(tmp_pkt, tmp, sizeof(tmp), 0))
289 return 0;
290
291 slh_bytes_to_nibbles(msg, n, msg_and_csum_nibbles);
292 compute_checksum_nibbles(msg_and_csum_nibbles, len1, msg_and_csum_nibbles + len1);
293
294 /* Compute the end nodes for each of the chains */
295 for (i = 0; i < len; ++i) {
296 set_chain_address(adrs, i);
297 if (!PACKET_get_bytes(sig_rpkt, &sig_i, n)
298 || !slh_wots_chain(ctx, sig_i, msg_and_csum_nibbles[i],
299 NIBBLE_MASK - msg_and_csum_nibbles[i],
300 pk_seed, adrs, tmp_pkt))
301 goto err;
302 }
303 /* compress the computed public key value */
304 adrsf->copy(wots_pk_adrs, adrs);
305 adrsf->set_type_and_clear(wots_pk_adrs, SLH_ADRS_TYPE_WOTS_PK);
306 adrsf->copy_keypair_address(wots_pk_adrs, adrs);
307 if (!WPACKET_get_total_written(tmp_pkt, &tmp_len))
308 goto err;
309 ret = hashf->T(ctx, pk_seed, wots_pk_adrs, tmp, tmp_len,
310 pk_out, pk_out_len);
311 err:
312 if (!WPACKET_finish(tmp_pkt))
313 ret = 0;
314 return ret;
315 }
316