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