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