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 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 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 */ 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 */ 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 */ 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 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 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 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