int xmssmt_sign()

in xmss_fast.c [787:965]
115 lines of code
16 McCabe index (conditional complexity)

int xmssmt_sign(unsigned char *sk, bds_state *states, unsigned char *wots_sigs, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg, unsigned long long msglen, const xmssmt_params *params)
{
  unsigned int n = params->n;
  
  unsigned int tree_h = params->xmss_par.h;
  unsigned int h = params->h;
  unsigned int k = params->xmss_par.k;
  unsigned int idx_len = params->index_len;
  uint64_t idx_tree;
  uint32_t idx_leaf;
  uint64_t i, j;
  int needswap_upto = -1;
  unsigned int updates;

  unsigned char sk_seed[n];
  unsigned char sk_prf[n];
  unsigned char pub_seed[n];
  // Init working params
  unsigned char R[n];
  unsigned char msg_h[n];
  unsigned char hash_key[3*n];
  unsigned char ots_seed[n];
  uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
  uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
  unsigned char idx_bytes_32[32];
  bds_state tmp;

  // Extract SK 
  unsigned long long idx = 0;
  for (i = 0; i < idx_len; i++) {
    idx |= ((unsigned long long)sk[i]) << 8*(idx_len - 1 - i);
  }

  memcpy(sk_seed, sk+idx_len, n);
  memcpy(sk_prf, sk+idx_len+n, n);
  memcpy(pub_seed, sk+idx_len+2*n, n);

  // Update SK
  for (i = 0; i < idx_len; i++) {
    sk[i] = ((idx + 1) >> 8*(idx_len - 1 - i)) & 255;
  }
  // -- Secret key for this non-forward-secure version is now updated.
  // -- A productive implementation should use a file handle instead and write the updated secret key at this point!


  // ---------------------------------
  // Message Hashing
  // ---------------------------------

  // Message Hash:
  // First compute pseudorandom value
  to_byte(idx_bytes_32, idx, 32);
  prf(R, idx_bytes_32, sk_prf, n);
  // Generate hash key (R || root || idx)
  memcpy(hash_key, R, n);
  memcpy(hash_key+n, sk+idx_len+3*n, n);
  to_byte(hash_key+2*n, idx, n);
  
  // Then use it for message digest
  h_msg(msg_h, msg, msglen, hash_key, 3*n, n);

  // Start collecting signature
  *sig_msg_len = 0;

  // Copy index to signature
  for (i = 0; i < idx_len; i++) {
    sig_msg[i] = (idx >> 8*(idx_len - 1 - i)) & 255;
  }

  sig_msg += idx_len;
  *sig_msg_len += idx_len;

  // Copy R to signature
  for (i = 0; i < n; i++)
    sig_msg[i] = R[i];

  sig_msg += n;
  *sig_msg_len += n;

  // ----------------------------------
  // Now we start to "really sign"
  // ----------------------------------

  // Handle lowest layer separately as it is slightly different...

  // Prepare Address
  setType(ots_addr, 0);
  idx_tree = idx >> tree_h;
  idx_leaf = (idx & ((1 << tree_h)-1));
  setLayerADRS(ots_addr, 0);
  setTreeADRS(ots_addr, idx_tree);
  setOTSADRS(ots_addr, idx_leaf);

  // Compute seed for OTS key pair
  get_seed(ots_seed, sk_seed, n, ots_addr);

  // Compute WOTS signature
  wots_sign(sig_msg, msg_h, ots_seed, &(params->xmss_par.wots_par), pub_seed, ots_addr);

  sig_msg += params->xmss_par.wots_par.keysize;
  *sig_msg_len += params->xmss_par.wots_par.keysize;

  memcpy(sig_msg, states[0].auth, tree_h*n);
  sig_msg += tree_h*n;
  *sig_msg_len += tree_h*n;

  // prepare signature of remaining layers
  for (i = 1; i < params->d; i++) {
    // put WOTS signature in place
    memcpy(sig_msg, wots_sigs + (i-1)*params->xmss_par.wots_par.keysize, params->xmss_par.wots_par.keysize);

    sig_msg += params->xmss_par.wots_par.keysize;
    *sig_msg_len += params->xmss_par.wots_par.keysize;

    // put AUTH nodes in place
    memcpy(sig_msg, states[i].auth, tree_h*n);
    sig_msg += tree_h*n;
    *sig_msg_len += tree_h*n;
  }

  updates = (tree_h - k) >> 1;

  setTreeADRS(addr, (idx_tree + 1));
  // mandatory update for NEXT_0 (does not count towards h-k/2) if NEXT_0 exists
  if ((1 + idx_tree) * (1 << tree_h) + idx_leaf < (1ULL << h)) {
    bds_state_update(&states[params->d], sk_seed, &(params->xmss_par), pub_seed, addr);
  }

  for (i = 0; i < params->d; i++) {
    // check if we're not at the end of a tree
    if (! (((idx + 1) & ((1ULL << ((i+1)*tree_h)) - 1)) == 0)) {
      idx_leaf = (idx >> (tree_h * i)) & ((1 << tree_h)-1);
      idx_tree = (idx >> (tree_h * (i+1)));
      setLayerADRS(addr, i);
      setTreeADRS(addr, idx_tree);
      if (i == (unsigned int) (needswap_upto + 1)) {
        bds_round(&states[i], idx_leaf, sk_seed, &(params->xmss_par), pub_seed, addr);
      }
      updates = bds_treehash_update(&states[i], updates, sk_seed, &(params->xmss_par), pub_seed, addr);
      setTreeADRS(addr, (idx_tree + 1));
      // if a NEXT-tree exists for this level;
      if ((1 + idx_tree) * (1 << tree_h) + idx_leaf < (1ULL << (h - tree_h * i))) {
        if (i > 0 && updates > 0 && states[params->d + i].next_leaf < (1ULL << h)) {
          bds_state_update(&states[params->d + i], sk_seed, &(params->xmss_par), pub_seed, addr);
          updates--;
        }
      }
    }
    else if (idx < (1ULL << h) - 1) {
      memcpy(&tmp, states+params->d + i, sizeof(bds_state));
      memcpy(states+params->d + i, states + i, sizeof(bds_state));
      memcpy(states + i, &tmp, sizeof(bds_state));

      setLayerADRS(ots_addr, (i+1));
      setTreeADRS(ots_addr, ((idx + 1) >> ((i+2) * tree_h)));
      setOTSADRS(ots_addr, (((idx >> ((i+1) * tree_h)) + 1) & ((1 << tree_h)-1)));

      get_seed(ots_seed, sk+params->index_len, n, ots_addr);
      wots_sign(wots_sigs + i*params->xmss_par.wots_par.keysize, states[i].stack, ots_seed, &(params->xmss_par.wots_par), pub_seed, ots_addr);

      states[params->d + i].stackoffset = 0;
      states[params->d + i].next_leaf = 0;

      updates--; // WOTS-signing counts as one update
      needswap_upto = i;
      for (j = 0; j < tree_h-k; j++) {
        states[i].treehash[j].completed = 1;
      }
    }
  }

  //Whipe secret elements?
  //zerobytes(tsk, CRYPTO_SECRETKEYBYTES);

  memcpy(sig_msg, msg, msglen);
  *sig_msg_len += msglen;

  return 0;
}