crypto/openssh/xmss_wots.c

   1 /* $OpenBSD: xmss_wots.c,v 1.2 2018/02/26 03:56:44 dtucker 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  * interpretes 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 */