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