xref: /openssh-portable/xmss_wots.c (revision cfc1897a)
1 /* $OpenBSD: xmss_wots.c,v 1.3 2018/04/10 00:10:49 djm Exp $ */
2 /*
3 wots.c version 20160722
4 Andreas Hülsing
5 Joost Rijneveld
6 Public domain.
7 */
8 
9 #include "includes.h"
10 #ifdef WITH_XMSS
11 
12 #include <stdlib.h>
13 #ifdef HAVE_STDINT_H
14 # include <stdint.h>
15 #endif
16 #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 */
24 static inline int
wots_log2(uint32_t v)25 wots_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 
37 void
wots_set_params(wots_params * params,int n,int w)38 wots_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  */
expand_seed(unsigned char * outseeds,const unsigned char * inseed,const wots_params * params)54 static 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  *
68  * interprets in as start-th value of the chain
69  * addr has to contain the address of the chain
70  */
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])71 static 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  */
base_w(int * output,const int out_len,const unsigned char * input,const wots_params * params)88 static 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 
wots_pkgen(unsigned char * pk,const unsigned char * sk,const wots_params * params,const unsigned char * pub_seed,uint32_t addr[8])108 void 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 
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])119 int 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 
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])158 int 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 }
192 #endif /* WITH_XMSS */
193