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