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