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