blob: 993e661f67079fe73054c039061231c21b329607 [file] [log] [blame]
djm@openbsd.org001aa552018-04-10 00:10:49 +00001/* $OpenBSD: xmss_wots.c,v 1.3 2018/04/10 00:10:49 djm Exp $ */
markus@openbsd.org1b11ea72018-02-23 15:58:37 +00002/*
3wots.c version 20160722
4Andreas Hülsing
5Joost Rijneveld
6Public domain.
7*/
8
Damien Millerf8854742018-02-26 12:18:14 +11009#include "includes.h"
Darren Tucker941e0d32018-02-28 19:59:35 +110010#ifdef WITH_XMSS
Damien Millerf8854742018-02-26 12:18:14 +110011
markus@openbsd.org1b11ea72018-02-23 15:58:37 +000012#include <stdlib.h>
Darren Tuckerc7ef4a32018-02-26 17:42:56 +110013#ifdef HAVE_STDINT_H
Damien Millercfc18972019-10-09 09:06:35 +110014# include <stdint.h>
Darren Tuckerc7ef4a32018-02-26 17:42:56 +110015#endif
markus@openbsd.org1b11ea72018-02-23 15:58:37 +000016#include <limits.h>
17#include "xmss_commons.h"
18#include "xmss_hash.h"
19#include "xmss_wots.h"
20#include "xmss_hash_address.h"
21
22
23/* libm-free version of log2() for wots */
24static inline int
25wots_log2(uint32_t v)
26{
27 int b;
28
29 for (b = sizeof (v) * CHAR_BIT - 1; b >= 0; b--) {
30 if ((1U << b) & v) {
31 return b;
32 }
33 }
34 return 0;
35}
36
37void
38wots_set_params(wots_params *params, int n, int w)
39{
40 params->n = n;
41 params->w = w;
42 params->log_w = wots_log2(params->w);
43 params->len_1 = (CHAR_BIT * n) / params->log_w;
44 params->len_2 = (wots_log2(params->len_1 * (w - 1)) / params->log_w) + 1;
45 params->len = params->len_1 + params->len_2;
46 params->keysize = params->len * params->n;
47}
48
49/**
50 * Helper method for pseudorandom key generation
51 * Expands an n-byte array into a len*n byte array
52 * this is done using PRF
53 */
54static void expand_seed(unsigned char *outseeds, const unsigned char *inseed, const wots_params *params)
55{
56 uint32_t i = 0;
57 unsigned char ctr[32];
58 for(i = 0; i < params->len; i++){
59 to_byte(ctr, i, 32);
60 prf((outseeds + (i*params->n)), ctr, inseed, params->n);
61 }
62}
63
64/**
65 * Computes the chaining function.
66 * out and in have to be n-byte arrays
67 *
djm@openbsd.org001aa552018-04-10 00:10:49 +000068 * interprets in as start-th value of the chain
markus@openbsd.org1b11ea72018-02-23 15:58:37 +000069 * addr has to contain the address of the chain
70 */
71static void gen_chain(unsigned char *out, const unsigned char *in, unsigned int start, unsigned int steps, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
72{
73 uint32_t i, j;
74 for (j = 0; j < params->n; j++)
75 out[j] = in[j];
76
77 for (i = start; i < (start+steps) && i < params->w; i++) {
78 setHashADRS(addr, i);
79 hash_f(out, out, pub_seed, addr, params->n);
80 }
81}
82
83/**
84 * base_w algorithm as described in draft.
85 *
86 *
87 */
88static void base_w(int *output, const int out_len, const unsigned char *input, const wots_params *params)
89{
90 int in = 0;
91 int out = 0;
92 uint32_t total = 0;
93 int bits = 0;
94 int consumed = 0;
95
96 for (consumed = 0; consumed < out_len; consumed++) {
97 if (bits == 0) {
98 total = input[in];
99 in++;
100 bits += 8;
101 }
102 bits -= params->log_w;
103 output[out] = (total >> bits) & (params->w - 1);
104 out++;
105 }
106}
107
108void wots_pkgen(unsigned char *pk, const unsigned char *sk, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
109{
110 uint32_t i;
111 expand_seed(pk, sk, params);
112 for (i=0; i < params->len; i++) {
113 setChainADRS(addr, i);
114 gen_chain(pk+i*params->n, pk+i*params->n, 0, params->w-1, params, pub_seed, addr);
115 }
116}
117
118
119int wots_sign(unsigned char *sig, const unsigned char *msg, const unsigned char *sk, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
120{
121 //int basew[params->len];
122 int csum = 0;
123 uint32_t i = 0;
124 int *basew = calloc(params->len, sizeof(int));
125 if (basew == NULL)
126 return -1;
127
128 base_w(basew, params->len_1, msg, params);
129
130 for (i=0; i < params->len_1; i++) {
131 csum += params->w - 1 - basew[i];
132 }
133
134 csum = csum << (8 - ((params->len_2 * params->log_w) % 8));
135
136 int len_2_bytes = ((params->len_2 * params->log_w) + 7) / 8;
137
138 unsigned char csum_bytes[len_2_bytes];
139 to_byte(csum_bytes, csum, len_2_bytes);
140
141 int csum_basew[params->len_2];
142 base_w(csum_basew, params->len_2, csum_bytes, params);
143
144 for (i = 0; i < params->len_2; i++) {
145 basew[params->len_1 + i] = csum_basew[i];
146 }
147
148 expand_seed(sig, sk, params);
149
150 for (i = 0; i < params->len; i++) {
151 setChainADRS(addr, i);
152 gen_chain(sig+i*params->n, sig+i*params->n, 0, basew[i], params, pub_seed, addr);
153 }
154 free(basew);
155 return 0;
156}
157
158int wots_pkFromSig(unsigned char *pk, const unsigned char *sig, const unsigned char *msg, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
159{
160 int csum = 0;
161 uint32_t i = 0;
162 int *basew = calloc(params->len, sizeof(int));
163 if (basew == NULL)
164 return -1;
165
166 base_w(basew, params->len_1, msg, params);
167
168 for (i=0; i < params->len_1; i++) {
169 csum += params->w - 1 - basew[i];
170 }
171
172 csum = csum << (8 - ((params->len_2 * params->log_w) % 8));
173
174 int len_2_bytes = ((params->len_2 * params->log_w) + 7) / 8;
175
176 unsigned char csum_bytes[len_2_bytes];
177 to_byte(csum_bytes, csum, len_2_bytes);
178
179 int csum_basew[params->len_2];
180 base_w(csum_basew, params->len_2, csum_bytes, params);
181
182 for (i = 0; i < params->len_2; i++) {
183 basew[params->len_1 + i] = csum_basew[i];
184 }
185 for (i=0; i < params->len; i++) {
186 setChainADRS(addr, i);
187 gen_chain(pk+i*params->n, sig+i*params->n, basew[i], params->w-1-basew[i], params, pub_seed, addr);
188 }
189 free(basew);
190 return 0;
191}
Darren Tuckera10d8552018-02-27 14:45:17 +1100192#endif /* WITH_XMSS */