Implement hash-based signatures, per draft-mcgrew-hash-sigs-08.txt

16 files changed, 3207 insertions, 29 deletions

diff --git a/Makefile b/Makefile
index 59236af..6934f95 100644
--- a/Makefile
+++ b/Makefile
@@ -34,7 +34,7 @@ STATIC_CORE_STATE_BLOCKS = 32
 STATIC_HASH_STATE_BLOCKS = 32
 STATIC_HMAC_STATE_BLOCKS = 16
 STATIC_PKEY_STATE_BLOCKS = 256
-STATIC_KS_VOLATILE_SLOTS = 128
+STATIC_KS_VOLATILE_SLOTS = 1280
 
 LIB		= libhal.a
 
@@ -93,7 +93,7 @@ endif
 # makefile, so the working definition of "always want" is sometimes
 # just "building this is harmless even if we don't use it."
 
-OBJ += errorstrings.o hash.o asn1.o ecdsa.o rsa.o xdr.o slip.o
+OBJ += errorstrings.o hash.o asn1.o ecdsa.o rsa.o hashsig.o xdr.o slip.o
 OBJ += rpc_api.o rpc_hash.o uuid.o rpc_pkcs1.o crc32.o locks.o logging.o
 
 # Object files to build when we're on a platform with direct access
@@ -220,6 +220,7 @@ CFLAGS		+= -DHAL_STATIC_CORE_STATE_BLOCKS=${STATIC_CORE_STATE_BLOCKS}
 CFLAGS		+= -DHAL_STATIC_HASH_STATE_BLOCKS=${STATIC_HASH_STATE_BLOCKS}
 CFLAGS		+= -DHAL_STATIC_HMAC_STATE_BLOCKS=${STATIC_HMAC_STATE_BLOCKS}
 CFLAGS		+= -DHAL_STATIC_PKEY_STATE_BLOCKS=${STATIC_PKEY_STATE_BLOCKS}
+CFLAGS		+= -DHAL_STATIC_KS_VOLATILE_SLOTS=${STATIC_KS_VOLATILE_SLOTS}
 CFLAGS		+= -I${CRYPTECH_ROOT}/sw/libhal
 CFLAGS		+= -I${LIBTFM_BLD}
 
@@ -272,6 +273,7 @@ novena-eim.o hal_io_eim.o:					novena-eim.h
 slip.o rpc_client_serial.o rpc_server_serial.o:			slip_internal.h
 ${OBJ}:								verilog_constants.h
 rpc_client.o rpc_server.o xdr.o:				xdr_internal.h
+hashsig.o:                                                      hashsig.h
 
 last_gasp_pin_internal.h:
 	./utils/last_gasp_default_pin >$@
diff --git a/asn1.c b/asn1.c
index 1f4a14a..37318a9 100644
--- a/asn1.c
+++ b/asn1.c
@@ -77,6 +77,10 @@ const uint8_t hal_asn1_oid_aesKeyWrap[] = { 0x60, 0x86, 0x48, 0x01, 0x65, 0x03,
 const size_t hal_asn1_oid_aesKeyWrap_len = sizeof(hal_asn1_oid_aesKeyWrap);
 #endif
 
+/* from draft-housley-cms-mts-hash-sig-07.txt */
+const uint8_t hal_asn1_oid_mts_hashsig[] = { 0x2A, 0x86, 0x48, 0x86, 0xF7, 0x0D, 0x01, 0x09, 0x10, 0x03, 0x11 };
+const size_t hal_asn1_oid_mts_hashsig_len = sizeof(hal_asn1_oid_mts_hashsig);
+
 /*
  * Encode tag and length fields of an ASN.1 object.
  *
@@ -932,6 +936,12 @@ hal_error_t hal_asn1_guess_key_type(hal_key_type_t *type,
     return err;
   }
 
+  if (alg_oid_len == hal_asn1_oid_mts_hashsig_len && memcmp(alg_oid, hal_asn1_oid_mts_hashsig, alg_oid_len) == 0) {
+    *type = public ? HAL_KEY_TYPE_HASHSIG_PUBLIC : HAL_KEY_TYPE_HASHSIG_PRIVATE;
+    *curve = HAL_CURVE_NONE;
+    return HAL_OK;
+  }
+
   *type = HAL_KEY_TYPE_NONE;
   *curve = HAL_CURVE_NONE;
   return HAL_ERROR_UNSUPPORTED_KEY;
diff --git a/asn1_internal.h b/asn1_internal.h
index bba4503..23d8a77 100644
--- a/asn1_internal.h
+++ b/asn1_internal.h
@@ -102,6 +102,9 @@ extern const size_t  hal_asn1_oid_ecPublicKey_len;
 extern const uint8_t hal_asn1_oid_aesKeyWrap[];
 extern const size_t  hal_asn1_oid_aesKeyWrap_len;
 
+extern const uint8_t hal_asn1_oid_mts_hashsig[];
+extern const size_t hal_asn1_oid_mts_hashsig_len;
+
 /*
  * Transcoding functions.
  */
diff --git a/hal.h b/hal.h
index a614335..8797a4f 100644
--- a/hal.h
+++ b/hal.h
@@ -161,6 +161,7 @@
   DEFINE_HAL_ERROR(HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE, "Wrong block type in keystore")                 \
   DEFINE_HAL_ERROR(HAL_ERROR_RPC_PROTOCOL_ERROR,        "RPC protocol error")                           \
   DEFINE_HAL_ERROR(HAL_ERROR_NOT_IMPLEMENTED,           "Not implemented")                              \
+  DEFINE_HAL_ERROR(HAL_ERROR_HASHSIG_KEY_EXHAUSTED,     "Key exhausted")                                \
   END_OF_HAL_ERROR_LIST
 
 /* Marker to forestall silly line continuation errors */
@@ -226,8 +227,6 @@ extern hal_addr_t hal_core_base(const hal_core_t *core);
 extern hal_core_t * hal_core_iterate(hal_core_t *core);
 extern void hal_core_reset_table(void);
 extern hal_error_t hal_core_alloc(const char *name, hal_core_t **core);
-extern hal_error_t hal_core_alloc2(const char *name1, hal_core_t **pcore1,
-                                   const char *name2, hal_core_t **pcore2);
 extern void hal_core_free(hal_core_t *core);
 extern void hal_critical_section_start(void);
 extern void hal_critical_section_end(void);
@@ -413,7 +412,11 @@ typedef enum {
   HAL_KEY_TYPE_RSA_PRIVATE,
   HAL_KEY_TYPE_RSA_PUBLIC,
   HAL_KEY_TYPE_EC_PRIVATE,
-  HAL_KEY_TYPE_EC_PUBLIC
+  HAL_KEY_TYPE_EC_PUBLIC,
+  HAL_KEY_TYPE_HASHSIG_PRIVATE,
+  HAL_KEY_TYPE_HASHSIG_PUBLIC,
+  HAL_KEY_TYPE_HASHSIG_LMS,
+  HAL_KEY_TYPE_HASHSIG_LMOTS,
 } hal_key_type_t;
 
 typedef enum {
@@ -794,6 +797,18 @@ extern hal_error_t hal_rpc_pkey_generate_ec(const hal_client_handle_t client,
                                             const hal_curve_name_t curve,
                                             const hal_key_flags_t flags);
 
+typedef enum lmots_algorithm_type lmots_algorithm_t;
+typedef enum lms_algorithm_type lms_algorithm_t;
+
+extern hal_error_t hal_rpc_pkey_generate_hashsig(const hal_client_handle_t client,
+                                                 const hal_session_handle_t session,
+                                                 hal_pkey_handle_t *pkey,
+                                                 hal_uuid_t *name,
+                                                 const size_t hss_levels,
+                                                 const lms_algorithm_t lms_type,
+                                                 const lmots_algorithm_t lmots_type,
+                                                 const hal_key_flags_t flags);
+
 extern hal_error_t hal_rpc_pkey_close(const hal_pkey_handle_t pkey);
 
 extern hal_error_t hal_rpc_pkey_delete(const hal_pkey_handle_t pkey);
diff --git a/hal_internal.h b/hal_internal.h
index ac51cfb..d3bf706 100644
--- a/hal_internal.h
+++ b/hal_internal.h
@@ -48,7 +48,7 @@
  */
 
 /*
- * htonl is not available in arm-none-eabi headers or libc.
+ * htonl and htons are not available in arm-none-eabi headers or libc.
  */
 #ifndef STM32F4XX
 #include <arpa/inet.h>
@@ -62,10 +62,18 @@ inline uint32_t htonl(uint32_t w)
         ((w & 0x00ff0000) >> 8) +
         ((w & 0xff000000) >> 24);
 }
+inline uint16_t htons(uint16_t w)
+{
+    return
+        ((w & 0x00ff) << 8) +
+        ((w & 0xff00) >> 8);
+}
 #else                           /* big endian */
 #define htonl(x) (x)
+#define htons(x) (x)
 #endif
 #define ntohl htonl
+#define ntohs htons
 #endif
 
 /*
@@ -281,6 +289,15 @@ typedef struct {
                               const hal_curve_name_t curve,
                               const hal_key_flags_t flags);
 
+  hal_error_t  (*generate_hashsig)(const hal_client_handle_t client,
+                                   const hal_session_handle_t session,
+                                   hal_pkey_handle_t *pkey,
+                                   hal_uuid_t *name,
+                                   const size_t hss_levels,
+                                   const lms_algorithm_t lms_type,
+                                   const lmots_algorithm_t lmots_type,
+                                   const hal_key_flags_t flags);
+
   hal_error_t  (*close)(const hal_pkey_handle_t pkey);
 
   hal_error_t  (*delete)(const hal_pkey_handle_t pkey);
@@ -420,14 +437,14 @@ static inline hal_crc32_t hal_crc32_finalize(hal_crc32_t crc)
 #if 0
 #define HAL_KS_WRAPPED_KEYSIZE  ((2373 + 15) & ~7)
 #else
-#warning Temporary test hack to HAL_KS_WRAPPED_KEYSIZE, clean this up
+//#warning Temporary test hack to HAL_KS_WRAPPED_KEYSIZE, clean this up
 //
 // See how much of the problem we're having with pkey support for the
 // new modexpa7 components is just this buffer size being too small.
 //
 #define HAL_KS_WRAPPED_KEYSIZE  ((2373 + 6 * 4096 / 8 + 6 * 4 + 15) & ~7)
-#if HAL_KS_WRAPPED_KEYSIZE + 8 > 4096
-#warning HAL_KS_WRAPPED_KEYSIZE is too big for a single 4096-octet block
+#if HAL_KS_WRAPPED_KEYSIZE + 8 > 8192
+#warning HAL_KS_WRAPPED_KEYSIZE is too big for a single 8192-octet block
 #endif
 #endif
 
@@ -648,9 +665,10 @@ typedef enum {
     RPC_FUNC_PKEY_GET_ATTRIBUTES,
     RPC_FUNC_PKEY_EXPORT,
     RPC_FUNC_PKEY_IMPORT,
+    RPC_FUNC_PKEY_GENERATE_HASHSIG,
 } rpc_func_num_t;
 
-#define RPC_VERSION 0x01010000          /* 1.1.0.0 */
+#define RPC_VERSION 0x01010100          /* 1.1.1.0 */
 
 /*
  * RPC client locality. These have to be defines rather than an enum,
@@ -667,7 +685,7 @@ typedef enum {
  */
 
 #ifndef HAL_RPC_MAX_PKT_SIZE
-#define HAL_RPC_MAX_PKT_SIZE    4096
+#define HAL_RPC_MAX_PKT_SIZE    16384
 #endif
 
 /*
diff --git a/hashsig.c b/hashsig.c
new file mode 100644
index 0000000..13f20c6
--- /dev/null
+++ b/hashsig.c
@@ -0,0 +1,1811 @@
+/*
+ * hashsig.c
+ * ---------
+ * Implementation of draft-mcgrew-hash-sigs-08.txt
+ *
+ * Copyright (c) 2018, NORDUnet A/S All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * - Redistributions of source code must retain the above copyright notice,
+ *   this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ *
+ * - Neither the name of the NORDUnet nor the names of its contributors may
+ *   be used to endorse or promote products derived from this software
+ *   without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+ * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "hal.h"
+#include "hashsig.h"
+#include "ks.h"
+#include "asn1_internal.h"
+#include "xdr_internal.h"
+
+typedef struct { uint8_t bytes[32]; } bytestring32;
+typedef struct { uint8_t bytes[16]; } bytestring16;
+
+#define D_PBLC 0x8080
+#define D_MESG 0x8181
+#define D_LEAF 0x8282
+#define D_INTR 0x8383
+
+#define u32str(X) htonl(X)
+#define u16str(X) htons(X)
+#define u8str(X) (X & 0xff)
+
+#define check(op) do { hal_error_t _err = (op); if (_err != HAL_OK) return _err; } while (0)
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * XDR extensions
+ */
+
+static inline hal_error_t hal_xdr_encode_bytestring32(uint8_t ** const outbuf, const uint8_t * const limit, const bytestring32 * const value)
+{
+    return hal_xdr_encode_fixed_opaque(outbuf, limit, (const uint8_t *)value, sizeof(bytestring32));
+}
+
+static inline hal_error_t hal_xdr_decode_bytestring32_ptr(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring32 **value)
+{
+    return hal_xdr_decode_fixed_opaque_ptr(inbuf, limit, (const uint8_t ** const)value, sizeof(bytestring32));
+}
+
+static inline hal_error_t hal_xdr_decode_bytestring32(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring32 * const value)
+{
+    return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t * const)value, sizeof(bytestring32));
+}
+
+static inline hal_error_t hal_xdr_encode_bytestring16(uint8_t ** const outbuf, const uint8_t * const limit, const bytestring16 *value)
+{
+    return hal_xdr_encode_fixed_opaque(outbuf, limit, (const uint8_t *)value, sizeof(bytestring16));
+}
+
+static inline hal_error_t hal_xdr_decode_bytestring16_ptr(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 **value)
+{
+    return hal_xdr_decode_fixed_opaque_ptr(inbuf, limit, (const uint8_t ** const)value, sizeof(bytestring16));
+}
+
+static inline hal_error_t hal_xdr_decode_bytestring16(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 * const value)
+{
+    return hal_xdr_decode_fixed_opaque(inbuf, limit, (uint8_t * const)value, sizeof(bytestring16));
+}
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * ASN.1 extensions
+ */
+
+#define hal_asn1_encode_size_t(n, der, der_len, der_max)                \
+    hal_asn1_encode_uint32((const uint32_t)n, der, der_len, der_max)
+
+#define hal_asn1_decode_size_t(np, der, der_len, der_max)               \
+    hal_asn1_decode_uint32((uint32_t *)np, der, der_len, der_max)
+
+#define hal_asn1_encode_lms_algorithm(type, der, der_len, der_max)      \
+    hal_asn1_encode_uint32((const uint32_t)type, der, der_len, der_max)
+
+#define hal_asn1_decode_lms_algorithm(type, der, der_len, der_max)      \
+    hal_asn1_decode_uint32((uint32_t *)type, der, der_len, der_max)
+
+#define hal_asn1_encode_lmots_algorithm(type, der, der_len, der_max)    \
+    hal_asn1_encode_uint32((const uint32_t)type, der, der_len, der_max)
+
+#define hal_asn1_decode_lmots_algorithm(type, der, der_len, der_max)    \
+    hal_asn1_decode_uint32((uint32_t *)type, der, der_len, der_max)
+
+#define hal_asn1_encode_uuid(data, der, der_len, der_max)               \
+    hal_asn1_encode_octet_string((const uint8_t * const)data, sizeof(hal_uuid_t), der, der_len, der_max)
+
+#define hal_asn1_decode_uuid(data, der, der_len, der_max)               \
+    hal_asn1_decode_octet_string((uint8_t *)data, sizeof(hal_uuid_t), der, der_len, der_max)
+
+#define hal_asn1_encode_bytestring16(data, der, der_len, der_max)       \
+    hal_asn1_encode_octet_string((const uint8_t * const)data, sizeof(bytestring16), der, der_len, der_max)
+
+#define hal_asn1_decode_bytestring16(data, der, der_len, der_max)       \
+    hal_asn1_decode_octet_string((uint8_t *)data, sizeof(bytestring16), der, der_len, der_max)
+
+#define hal_asn1_encode_bytestring32(data, der, der_len, der_max)       \
+    hal_asn1_encode_octet_string((const uint8_t * const)data, sizeof(bytestring32), der, der_len, der_max)
+
+#define hal_asn1_decode_bytestring32(data, der, der_len, der_max)       \
+    hal_asn1_decode_octet_string((uint8_t *)data, sizeof(bytestring32), der, der_len, der_max)
+
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * LM-OTS
+ */
+
+static uint8_t coef1(const uint8_t * const S, const size_t i);
+static uint8_t coef2(const uint8_t * const S, const size_t i);
+static uint8_t coef4(const uint8_t * const S, const size_t i);
+static uint8_t coef8(const uint8_t * const S, const size_t i);
+
+typedef const struct lmots_parameter_set {
+    lmots_algorithm_t type;
+    size_t                  n, w,  w2,   p, ls;
+    uint8_t (*coef)(const uint8_t * const S, const size_t i);
+} lmots_parameter_t;
+static lmots_parameter_t lmots_parameters[] = {
+    { lmots_sha256_n32_w1, 32, 1,   2, 265, 7, coef1 },
+    { lmots_sha256_n32_w2, 32, 2,   4, 133, 6, coef2 },
+    { lmots_sha256_n32_w4, 32, 4,  16,  67, 4, coef4 },
+    { lmots_sha256_n32_w8, 32, 8, 256,  34, 0, coef8 },
+};
+
+typedef struct lmots_key {
+    hal_key_type_t type;
+    lmots_parameter_t *lmots;
+    bytestring16 I;
+    size_t q;
+    bytestring32 * x;
+    bytestring32 K;
+} lmots_key_t;
+
+static inline lmots_parameter_t *lmots_select_parameter_set(const lmots_algorithm_t lmots_type)
+{
+    if (lmots_type < lmots_sha256_n32_w1 || lmots_type > lmots_sha256_n32_w8)
+        return NULL;
+    else
+        return &lmots_parameters[lmots_type - lmots_sha256_n32_w1];
+}
+
+static inline size_t lmots_private_key_len(lmots_parameter_t * const lmots)
+{
+    /* u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */
+    return 2 * sizeof(uint32_t) + sizeof(bytestring16) + (lmots->p * lmots->n);
+}
+
+static inline size_t lmots_public_key_len(lmots_parameter_t * const lmots)
+{
+    /* u32str(type) || I || u32str(q) || K */
+    return 2 * sizeof(uint32_t) + sizeof(bytestring16) + lmots->n;
+}
+
+static inline size_t lmots_signature_len(lmots_parameter_t * const lmots)
+{
+    /* u32str(type) || C || y[0] || ... || y[p-1] */
+    return sizeof(uint32_t) + (lmots->p + 1) * lmots->n;
+}
+
+#if RPC_CLIENT == RPC_CLIENT_LOCAL
+/* Given a key with most fields filled in, generate the lmots private and
+ * public key components.
+ * Let the caller worry about storage.
+ */
+static hal_error_t lmots_generate(lmots_key_t * const key)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMOTS || key->lmots == NULL || key->x == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 0: Generating a Private Key
+
+//  3. set n and p according to the typecode and Table 1
+
+    size_t n = key->lmots->n;
+    size_t p = key->lmots->p;
+    size_t w2 = key->lmots->w2;
+
+//  4. compute the array x as follows:
+//     for ( i = 0; i < p; i = i + 1 ) {
+//       set x[i] to a uniformly random n-byte string
+//     }
+
+    for (size_t i = 0; i < p; ++i)
+        check(hal_rpc_get_random(&key->x[i], n));
+
+//   Algorithm 1: Generating a One Time Signature Public Key From a
+//   Private Key
+
+//   4. compute the string K as follows:
+
+    uint8_t statebuf[512];
+    hal_hash_state_t *state = NULL;
+    bytestring32 y[p];
+    uint32_t l;
+    uint16_t s;
+    uint8_t b;
+
+//      for ( i = 0; i < p; i = i + 1 ) {
+    for (size_t i = 0; i < p; ++i) {
+
+//        tmp = x[i]
+        bytestring32 tmp;
+        memcpy(&tmp, &key->x[i], sizeof(tmp));
+
+//        for ( j = 0; j < 2^w - 1; j = j + 1 ) {
+        for (size_t j = 0; j < w2 - 1; ++j) {
+
+//           tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
+            check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+            check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+            l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+            s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+            b = u8str(j); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b)));
+            check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp)));
+            check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp)));
+        }
+
+//        y[i] = tmp
+        memcpy(&y[i], &tmp, sizeof(tmp));
+//      }
+    }
+
+//      K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])
+    check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+    check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+    l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+    s = u16str(D_PBLC); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+    for (size_t i = 0; i < p; ++i)
+        check(hal_hash_update(state, (const uint8_t *)&y[i], sizeof(y[i])));
+    check(hal_hash_finalize(state, (uint8_t *)&key->K, sizeof(key->K)));
+
+    return HAL_OK;
+}
+#endif
+
+/* coef() functions for the supported values of w.
+ * This is a bit of premature optimization, because coef() gets called a lot.
+ */
+
+/* w = 1 */
+static uint8_t coef1(const uint8_t * const S, const size_t i)
+{
+    return (S[i/8] >> (7 - (i % 8))) & 0x01;
+}
+
+/* w = 2 */
+static uint8_t coef2(const uint8_t * const S, const size_t i)
+{
+    return (S[i/4] >> (6 - (2 * (i % 4)))) & 0x03;
+}
+
+/* w = 4 */
+static uint8_t coef4(const uint8_t * const S, const size_t i)
+{
+    uint8_t byte = S[i/2];
+    if (i % 2)
+        byte >>= 4;
+    return byte & 0x0f;
+}
+
+/* w = 8 */
+static uint8_t coef8(const uint8_t * const S, const size_t i)
+{
+    return S[i];
+}
+
+/* checksum */
+static uint16_t Cksm(const uint8_t * const S, lmots_parameter_t *lmots)
+{
+    uint16_t sum = 0;
+
+    for (size_t i = 0; i < (lmots->n * 8 / lmots->w); ++i)
+        sum += (lmots->w2 - 1) - lmots->coef(S, i);
+
+    return (sum << lmots->ls);
+}
+
+#if RPC_CLIENT == RPC_CLIENT_LOCAL
+static hal_error_t lmots_sign(lmots_key_t *key,
+                              const uint8_t * const msg, const size_t msg_len,
+                              uint8_t * sig, size_t *sig_len, const size_t sig_max)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMOTS || msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 3: Generating a One Time Signature From a Private Key and a
+//   Message
+
+//     1. set type to the typecode of the algorithm
+//
+//     2. set n, p, and w according to the typecode and Table 1
+
+    size_t n = key->lmots->n;
+    size_t p = key->lmots->p;
+    uint8_t (*coef)() = key->lmots->coef;
+
+    if (sig_max < lmots_signature_len(key->lmots))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//     3. determine x, I and q from the private key
+//
+//     4. set C to a uniformly random n-byte string
+
+    bytestring32 C;
+    check(hal_rpc_get_random(&C, n));
+
+//     5. compute the array y as follows:
+
+    uint8_t statebuf[512];
+    hal_hash_state_t *state = NULL;
+    uint8_t Q[n + 2];           /* hash || 16-bit checksum */
+    uint32_t l;
+    uint16_t s;
+    uint8_t b;
+
+//        Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
+    check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+    check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+    l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+    s = u16str(D_MESG); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+    check(hal_hash_update(state, (const uint8_t *)&C, sizeof(C)));
+    check(hal_hash_update(state, msg, msg_len));
+    check(hal_hash_finalize(state, Q, n));
+
+    /* append checksum */
+    *(uint16_t *)&Q[n] = u16str(Cksm((uint8_t *)Q, key->lmots));
+
+    bytestring32 y[p];
+
+//        for ( i = 0; i < p; i = i + 1 ) {
+    for (size_t i = 0; i < p; ++i) {
+
+//          a = coef(Q || Cksm(Q), i, w)
+        uint8_t a = coef(Q, i);
+
+//          tmp = x[i]
+        bytestring32 tmp;
+        memcpy(&tmp, &key->x[i], sizeof(tmp));
+
+//          for ( j = 0; j < a; j = j + 1 ) {
+        for (size_t j = 0; j < (size_t)a; ++j) {
+
+//             tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
+            check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+            check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+            l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+            s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+            b = u8str(j); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b)));
+            check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp)));
+            check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp)));
+//          }
+        }
+
+//          y[i] = tmp
+        memcpy(&y[i], &tmp, sizeof(tmp));
+    }
+
+//      6. return u32str(type) || C || y[0] || ... || y[p-1]
+    uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_max;
+    check(hal_xdr_encode_int(&sigptr, siglim, key->lmots->type));
+    check(hal_xdr_encode_bytestring32(&sigptr, siglim, &C));
+    for (size_t i = 0; i < p; ++i)
+        check(hal_xdr_encode_bytestring32(&sigptr, siglim, &y[i]));
+
+    if (sig_len != NULL)
+        *sig_len = sigptr - sig;
+
+    return HAL_OK;
+}
+#endif
+
+static hal_error_t lmots_public_key_candidate(const lmots_key_t * const key,
+                                              const uint8_t * const msg, const size_t msg_len,
+                                              const uint8_t * const sig, const size_t sig_len)
+{
+    if (key == NULL || msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    /* Skip the length checks here, because we did a unitary length check
+     * at the start of lms_verify.
+     */
+
+//  1. if the signature is not at least four bytes long, return INVALID
+//
+//  2. parse sigtype, C, and y from the signature as follows:
+//     a. sigtype = strTou32(first 4 bytes of signature)
+
+    const uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_len;
+
+    uint32_t sigtype;
+    check(hal_xdr_decode_int(&sigptr, siglim, &sigtype));
+
+//     b. if sigtype is not equal to pubtype, return INVALID
+
+    if ((lmots_algorithm_t)sigtype != key->lmots->type)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//     c. set n and p according to the pubtype and Table 1;  if the
+//     signature is not exactly 4 + n * (p+1) bytes long, return INVALID
+
+    size_t n = key->lmots->n;
+    size_t p = key->lmots->p;
+    size_t w2 = key->lmots->w2;
+    uint8_t (*coef)() = key->lmots->coef;
+
+//     d. C = next n bytes of signature
+
+    bytestring32 C;
+    check(hal_xdr_decode_bytestring32(&sigptr, siglim, &C));
+
+//     e.  y[0] = next n bytes of signature
+//         y[1] = next n bytes of signature
+//         ...
+//       y[p-1] = next n bytes of signature
+
+    bytestring32 y[p];
+    for (size_t i = 0; i < p; ++i)
+        check(hal_xdr_decode_bytestring32(&sigptr, siglim, &y[i]));
+
+//  3. compute the string Kc as follows
+
+    uint8_t statebuf[512];
+    hal_hash_state_t *state = NULL;
+    uint8_t Q[n + 2];           /* hash || 16-bit checksum */
+    uint32_t l;
+    uint16_t s;
+    uint8_t b;
+
+//     Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
+    check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+    check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+    l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+    s = u16str(D_MESG); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+    check(hal_hash_update(state, (const uint8_t *)&C, sizeof(C)));
+    check(hal_hash_update(state, msg, msg_len));
+    check(hal_hash_finalize(state, Q, n));
+
+    /* append checksum */
+    *(uint16_t *)&Q[n] = u16str(Cksm((uint8_t *)Q, key->lmots));
+
+    bytestring32 z[p];
+
+//     for ( i = 0; i < p; i = i + 1 ) {
+    for (size_t i = 0; i < p; ++i) {
+
+//       a = coef(Q || Cksm(Q), i, w)
+        uint8_t a = coef(Q, i);
+
+//       tmp = y[i]
+        bytestring32 tmp;
+        memcpy(&tmp, &y[i], sizeof(tmp));
+
+//       for ( j = a; j < 2^w - 1; j = j + 1 ) {
+        for (size_t j = (size_t)a; j < w2 - 1; ++j) {
+
+//          tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
+            check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+            check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+            l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+            s = u16str(i); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+            b = u8str(j); check(hal_hash_update(state, (const uint8_t *)&b, sizeof(b)));
+            check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp)));
+            check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp)));
+//       }
+        }
+
+//       z[i] = tmp
+        memcpy(&z[i], &tmp, sizeof(tmp));
+//     }
+    }
+
+//     Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1])
+    check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+    check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+    l = u32str(key->q); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+    s = u16str(D_PBLC); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+    for (size_t i = 0; i < p; ++i)
+        check(hal_hash_update(state, (const uint8_t *)&z[i], sizeof(z[i])));
+    check(hal_hash_finalize(state, (uint8_t *)&key->K, sizeof(key->K)));
+
+//  4. return Kc
+    return HAL_OK;
+}
+
+#if RPC_CLIENT == RPC_CLIENT_LOCAL
+static hal_error_t lmots_private_key_to_der(const lmots_key_t * const key,
+                                            uint8_t *der, size_t *der_len, const size_t der_max)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMOTS)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    // u32str(lmots_type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1]
+    /* we also store K, to speed up restart */
+
+    /*
+     * Calculate data length.
+     */
+
+    size_t len, vlen = 0, hlen;
+
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len;
+    check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0));             vlen += len;
+    check(hal_asn1_encode_size_t(key->q, NULL, &len, 0));                    vlen += len;
+    for (size_t i = 0; i < key->lmots->p; ++i) {
+        check(hal_asn1_encode_bytestring32(&key->x[i], NULL, &len, 0));      vlen += len;
+    }
+    check(hal_asn1_encode_bytestring32(&key->K, NULL, &len, 0));             vlen += len;
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, NULL, &hlen, 0));
+
+    check(hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                               NULL, 0, NULL, hlen + vlen, NULL, der_len, der_max));
+
+    if (der == NULL)
+        return HAL_OK;
+
+    /*
+     * Encode data.
+     */
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max));
+
+    uint8_t *d = der + hlen;
+    memset(d, 0, vlen);
+
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, vlen)); d += len; vlen -= len;
+    check(hal_asn1_encode_bytestring16(&key->I, d, &len, vlen));             d += len; vlen -= len;
+    check(hal_asn1_encode_size_t(key->q, d, &len, vlen));                    d += len; vlen -= len;
+    for (size_t i = 0; i < key->lmots->p; ++i) {
+        check(hal_asn1_encode_bytestring32(&key->x[i], d, &len, vlen));      d += len; vlen -= len;
+    }
+    check(hal_asn1_encode_bytestring32(&key->K, d, &len, vlen));             d += len; vlen -= len;
+
+    return hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                                NULL, 0, der, d - der, der, der_len, der_max);
+}
+
+static size_t lmots_private_key_to_der_len(const lmots_key_t * const key)
+{
+    size_t len = 0;
+    return (lmots_private_key_to_der(key, NULL, &len, 0) == HAL_OK) ? len : 0;
+}
+
+static hal_error_t lmots_private_key_from_der(lmots_key_t *key,
+                                              const uint8_t *der, const size_t der_len)
+{
+    if (key == NULL || der == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    key->type = HAL_KEY_TYPE_HASHSIG_LMOTS;
+
+    size_t hlen, vlen, alg_oid_len, curve_oid_len, privkey_len;
+    const uint8_t     *alg_oid,    *curve_oid,    *privkey;
+
+    check(hal_asn1_decode_pkcs8_privatekeyinfo(&alg_oid, &alg_oid_len,
+                                               &curve_oid, &curve_oid_len,
+                                               &privkey, &privkey_len,
+                                               der, der_len));
+
+    if (alg_oid_len != hal_asn1_oid_mts_hashsig_len ||
+        memcmp(alg_oid, hal_asn1_oid_mts_hashsig, alg_oid_len) != 0 ||
+        curve_oid_len != 0)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    check(hal_asn1_decode_header(ASN1_SEQUENCE, privkey, privkey_len, &hlen, &vlen));
+
+    const uint8_t *d = privkey + hlen;
+    size_t len;
+
+    // u32str(lmots_type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1]
+
+    lmots_algorithm_t lmots_type;
+    check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &len, vlen));  d += len; vlen -= len;
+    key->lmots = lmots_select_parameter_set(lmots_type);
+    check(hal_asn1_decode_bytestring16(&key->I, d, &len, vlen));         d += len; vlen -= len;
+    check(hal_asn1_decode_size_t(&key->q, d, &len, vlen));               d += len; vlen -= len;
+    for (size_t i = 0; i < key->lmots->p; ++i) {
+        check(hal_asn1_decode_bytestring32(&key->x[i], d, &len, vlen));  d += len; vlen -= len;
+    }
+    check(hal_asn1_decode_bytestring32(&key->K, d, &len, vlen));         d += len; vlen -= len;
+
+    if (d != privkey + privkey_len)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    return HAL_OK;
+}
+#endif
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * LMS
+ */
+
+typedef const struct lms_parameter_set {
+    lms_algorithm_t type;
+    size_t                 m,  h,       h2;
+} lms_parameter_t;
+static lms_parameter_t lms_parameters[] = {
+    { lms_sha256_n32_h5,  32,  5,       32 },
+    { lms_sha256_n32_h10, 32, 10,     1024 },
+    { lms_sha256_n32_h15, 32, 15,    32768 },
+    { lms_sha256_n32_h20, 32, 20,  1048576 },
+    { lms_sha256_n32_h25, 32, 25, 33554432 },
+};
+
+typedef struct lms_key {
+    hal_key_type_t type;
+    size_t level;
+    lms_parameter_t *lms;
+    lmots_parameter_t *lmots;
+    bytestring16 I;
+    size_t q;			/* index of next lmots signing key */
+    hal_uuid_t *lmots_keys;	/* private key components */
+    bytestring32 *T;		/* public key components */
+    bytestring32 T1;		/* copy of T[1] */
+    uint8_t *pubkey;            /* in XDR format */
+    size_t pubkey_len;
+    uint8_t *signature;         /* of public key by parent lms key */
+    size_t signature_len;
+} lms_key_t;
+
+static inline lms_parameter_t *lms_select_parameter_set(const lms_algorithm_t lms_type)
+{
+    if (lms_type < lms_sha256_n32_h5 || lms_type > lms_sha256_n32_h25)
+        return NULL;
+    else
+        return &lms_parameters[lms_type - lms_sha256_n32_h5];
+}
+
+static inline size_t lms_public_key_len(lms_parameter_t * const lms)
+{
+    /* u32str(type) || u32str(otstype) || I || T[1] */
+    return 2 * sizeof(uint32_t) + 16 + lms->m;
+}
+
+static inline size_t lms_signature_len(lms_parameter_t * const lms, lmots_parameter_t * const lmots)
+{
+    /* u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1] */
+    return 2 * sizeof(uint32_t) + lmots_signature_len(lmots) + lms->h * lms->m;
+}
+
+#if RPC_CLIENT == RPC_CLIENT_LOCAL
+/* Given a key with most fields filled in, generate the lms private and
+ * public key components.
+ * Let the caller worry about storage.
+ */
+static hal_error_t lms_generate(lms_key_t *key)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS || key->lms == NULL || key->lmots == NULL || key->lmots_keys == NULL || key->T == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    check(hal_uuid_gen((hal_uuid_t *)&key->I));
+    key->q = 0;
+
+    bytestring32 x[key->lmots->p];
+    lmots_key_t lmots_key = {
+        .type = HAL_KEY_TYPE_HASHSIG_LMOTS,
+        .lmots = key->lmots,
+        .x = x
+    };
+    memcpy(&lmots_key.I, &key->I, sizeof(key->I));
+
+    hal_pkey_slot_t slot = {
+        .type  = HAL_KEY_TYPE_HASHSIG_LMOTS,
+        .curve = HAL_CURVE_NONE,
+        .flags = (key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0
+    };
+    hal_ks_t *ks = (key->level == 0) ? hal_ks_token : hal_ks_volatile;
+
+    uint8_t statebuf[512];
+    hal_hash_state_t *state = NULL;
+    uint32_t l;
+    uint16_t s;
+
+    size_t h2 = key->lms->h2;
+
+    /* private key - array of lmots key names */
+    for (size_t q = 0; q < h2; ++q) {
+        /* generate the lmots private and public key components */
+        lmots_key.q = q;
+        check(lmots_generate(&lmots_key));
+
+        /* store the lmots key */
+        uint8_t der[lmots_private_key_to_der_len(&lmots_key)];
+        size_t der_len;
+        check(lmots_private_key_to_der(&lmots_key, der, &der_len, sizeof(der)));
+        check(hal_uuid_gen(&slot.name));
+        hal_error_t err = hal_ks_store(ks, &slot, der, der_len);
+        memset(&x, 0, sizeof(x));
+        memset(der, 0, sizeof(der));
+        if (err != HAL_OK) return err;
+
+        /* record the lmots keystore name */
+        memcpy(&key->lmots_keys[q], &slot.name, sizeof(slot.name));
+
+        /* compute T[r] = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB[r-2^h]) */
+        size_t r = h2 + q;
+        check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+        check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+        l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+        s = u16str(D_LEAF); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+        /* they say "OTS_PUB", but they really just mean K */
+        check(hal_hash_update(state, (const uint8_t *)&lmots_key.K, sizeof(lmots_key.K)));
+        check(hal_hash_finalize(state, (uint8_t *)&key->T[r], sizeof(key->T[r])));
+    }
+
+    /* generate the rest of T[r] = H(I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1]) */
+    for (size_t r = h2 - 1; r > 0; --r) {
+        check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+        check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+        l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+        s = u16str(D_INTR); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+        check(hal_hash_update(state, (const uint8_t *)&key->T[2*r], sizeof(key->T[r])));
+        check(hal_hash_update(state, (const uint8_t *)&key->T[2*r+1], sizeof(key->T[r])));
+        check(hal_hash_finalize(state, (uint8_t *)&key->T[r], sizeof(key->T[r])));
+    }
+
+    memcpy(&key->T1, &key->T[1], sizeof(key->T1));
+
+    /* generate the XDR encoding of the public key, which will be signed
+     * by the previous lms key
+     */
+    uint8_t *pubkey = key->pubkey;
+    const uint8_t * const publim = key->pubkey + key->pubkey_len;
+    // u32str(lms_type) || u32str(lmots_type) || I || T[1]
+    check(hal_xdr_encode_int(&pubkey, publim, key->lms->type));
+    check(hal_xdr_encode_int(&pubkey, publim, key->lmots->type));
+    check(hal_xdr_encode_bytestring16(&pubkey, publim, &key->I));
+    check(hal_xdr_encode_bytestring32(&pubkey, publim, &key->T1));
+
+    return HAL_OK;
+}
+
+static hal_error_t lms_delete(const lms_key_t * const key)
+{
+    hal_pkey_slot_t slot;
+    memset(&slot, 0, sizeof(slot));
+    slot.flags = (key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0;
+
+    hal_ks_t *ks = (key->level == 0) ? hal_ks_token : hal_ks_volatile;
+
+    /* delete the lmots keys */
+    for (size_t i = 0; i < key->lms->h2; ++i) {
+        memcpy(&slot.name, &key->lmots_keys[i], sizeof(slot.name));
+        check(hal_ks_delete(ks, &slot));
+    }
+
+    /* delete the lms key */
+    memcpy(&slot.name, &key->I, sizeof(slot.name));
+    return hal_ks_delete(ks, &slot);
+}
+
+static hal_error_t lms_private_key_to_der(const lms_key_t * const key,
+                                          uint8_t *der, size_t *der_len, const size_t der_max);
+
+static hal_error_t lms_sign(lms_key_t * const key,
+                            const uint8_t * const msg, const size_t msg_len,
+                            uint8_t *sig, size_t *sig_len, const size_t sig_max)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS || msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    if (key->q >= key->lms->h2)
+        return HAL_ERROR_HASHSIG_KEY_EXHAUSTED;
+
+    if (sig_max < lms_signature_len(key->lms, key->lmots))
+        return HAL_ERROR_RESULT_TOO_LONG;
+
+    /* u32str(q) || ots_signature || u32str(lms_type) || path[0] || path[1] || ... || path[h-1] */
+
+    uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_max;
+    check(hal_xdr_encode_int(&sigptr, siglim, key->q));
+
+    /* fetch and decode the lmots signing key from the keystore */
+    hal_pkey_slot_t slot;
+    memset(&slot, 0, sizeof(slot));
+    slot.flags = (key->level == 0) ? HAL_KEY_FLAG_TOKEN : 0;
+    memcpy(&slot.name, &key->lmots_keys[key->q], sizeof(slot.name));
+
+    lmots_key_t lmots_key;
+    memset(&lmots_key, 0, sizeof(lmots_key));
+    bytestring32 x[key->lmots->p];
+    memset(&x, 0, sizeof(x));
+    lmots_key.x = x;
+
+    uint8_t der[HAL_KS_WRAPPED_KEYSIZE];
+    size_t der_len;
+    hal_ks_t *ks = (key->level == 0) ? hal_ks_token : hal_ks_volatile;
+    check(hal_ks_fetch(ks, &slot, der, &der_len, sizeof(der)));
+    check(lmots_private_key_from_der(&lmots_key, der, der_len));
+    memset(&der, 0, sizeof(der));
+
+    //? check lmots_type and I vs. lms key?
+
+    /* generate the lmots signature */
+    size_t lmots_sig_len;
+    check(lmots_sign(&lmots_key, msg, msg_len, sigptr, &lmots_sig_len, sig_max - (sigptr - sig)));
+    memset(&x, 0, sizeof(x));
+    sigptr += lmots_sig_len;
+
+    check(hal_xdr_encode_int(&sigptr, siglim, key->lms->type));
+
+    /* generate the path array */
+    for (size_t r = key->lms->h2 + key->q; r > 1; r /= 2)
+        check(hal_xdr_encode_bytestring32(&sigptr, siglim, ((r & 1) ? &key->T[r-1] : &key->T[r+1])));
+
+    if (sig_len != NULL)
+        *sig_len = sigptr - sig;
+
+    /* update and store q before returning the signature */
+    ++key->q;
+    check(lms_private_key_to_der(key, der, &der_len, sizeof(der)));
+    memcpy(&slot.name, &key->I, sizeof(slot.name));
+    check(hal_ks_rewrite_der(ks, &slot, der, der_len));
+
+    return HAL_OK;
+}
+#endif
+
+static hal_error_t lms_public_key_candidate(const lms_key_t * const key,
+                                            const uint8_t * const msg, const size_t msg_len,
+                                            const uint8_t * const sig, const size_t sig_len,
+                                            bytestring32 * Tc);
+
+static hal_error_t lms_verify(const lms_key_t * const key,
+                              const uint8_t * const msg, const size_t msg_len,
+                              const uint8_t * const sig, const size_t sig_len)
+{
+    if (key == NULL || msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    /* We can do one length check right now, rather than the 3 in
+     * Algorithm 6b and 2 in Algorithm 4b, because the lms and lmots types
+     * in the signature have to match the key.
+     */
+    if (sig_len != lms_signature_len(key->lms, key->lmots))
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//   Algorithm 6: LMS Signature Verification
+
+//     1. if the public key is not at least four bytes long, return
+//        INVALID
+//
+//     2. parse pubtype, I, and T[1] from the public key as follows:
+//
+//        a. pubtype = strTou32(first 4 bytes of public key)
+//
+//        b. set m according to pubtype, based on Table 2
+//
+//        c. if the public key is not exactly 20 + m bytes
+//           long, return INVALID
+
+    /* XXX THIS IS WRONG, should be 24 + m */
+
+    /* XXX missing from draft: pubotstype = strTou32(next 4 bytes of public key) */
+
+//
+//        d. I = next 16 bytes of the public key
+//
+//        e. T[1] = next m bytes of the public key
+//
+//     3. compute the candidate LMS root value Tc from the signature,
+//        message, identifier and pubtype using Algorithm 6b.
+    /* XXX and pubotstype */
+
+    bytestring32 Tc;
+    check(lms_public_key_candidate(key, msg, msg_len, sig, sig_len, &Tc));
+
+//     4. if Tc is equal to T[1], return VALID; otherwise, return INVALID
+
+    return (memcmp(&Tc, &key->T1, sizeof(Tc)) ? HAL_ERROR_INVALID_SIGNATURE : HAL_OK);
+}
+
+static hal_error_t lms_public_key_candidate(const lms_key_t * const key,
+                                            const uint8_t * const msg, const size_t msg_len,
+                                            const uint8_t * const sig, const size_t sig_len,
+                                            bytestring32 * Tc)
+{
+//   Algorithm 6b: Computing an LMS Public Key Candidate from a Signature,
+//   Message, Identifier, and algorithm typecode
+    /* XXX and pubotstype */
+
+//  1. if the signature is not at least eight bytes long, return INVALID
+//
+//  2. parse sigtype, q, ots_signature, and path from the signature as
+//     follows:
+//
+//    a. q = strTou32(first 4 bytes of signature)
+
+    const uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_len;
+
+    uint32_t q;
+    check(hal_xdr_decode_int(&sigptr, siglim, &q));
+
+//    b. otssigtype = strTou32(next 4 bytes of signature)
+
+    uint32_t otssigtype;
+    check(hal_xdr_decode_int_peek(&sigptr, siglim, &otssigtype));
+
+//    c. if otssigtype is not the OTS typecode from the public key, return INVALID
+
+    if ((lmots_algorithm_t)otssigtype != key->lmots->type)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//    d. set n, p according to otssigtype and Table 1; if the
+//    signature is not at least 12 + n * (p + 1) bytes long, return INVALID
+//
+//    e. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature
+
+    /* XXX Technically, this is also wrong - this is the remainder of
+     * ots_signature after otssigtype. The full ots_signature would be
+     * bytes 4 through 8 + n * (p + 1) - 1.
+     */
+
+    const uint8_t * const ots_signature = sigptr;
+    sigptr += lmots_signature_len(key->lmots);
+
+//    f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1))
+
+    uint32_t sigtype;
+    check(hal_xdr_decode_int(&sigptr, siglim, &sigtype));
+
+//    f. if sigtype is not the LM typecode from the public key, return INVALID
+
+    if ((lms_algorithm_t)sigtype != key->lms->type)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//    g. set m, h according to sigtype and Table 2
+
+    size_t m = key->lms->m;
+    size_t h = key->lms->h;
+    size_t h2 = key->lms->h2;
+
+//    h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID
+
+    if (q >= h2)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//    i. set path as follows:
+//          path[0] = next m bytes of signature
+//          path[1] = next m bytes of signature
+//          ...
+//          path[h-1] = next m bytes of signature
+
+    bytestring32 path[h];
+    for (size_t i = 0; i < h; ++i)
+        check(hal_xdr_decode_bytestring32(&sigptr, siglim, &path[i]));
+
+//  3. Kc = candidate public key computed by applying Algorithm 4b
+//     to the signature ots_signature, the message, and the
+//     identifiers I, q
+
+    lmots_key_t lmots_key = {
+        .type =  HAL_KEY_TYPE_HASHSIG_LMOTS,
+        .lmots = key->lmots,
+        .q = q
+    };
+    memcpy(&lmots_key.I, &key->I, sizeof(lmots_key.I));
+    check(lmots_public_key_candidate(&lmots_key, msg, msg_len, ots_signature, lmots_signature_len(key->lmots)));
+
+//  4. compute the candidate LMS root value Tc as follows:
+
+    uint8_t statebuf[512];
+    hal_hash_state_t *state = NULL;
+    uint32_t l;
+    uint16_t s;
+
+//     node_num = 2^h + q
+    size_t r = h2 + q;
+
+//     tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc)
+    bytestring32 tmp;
+    check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+    check(hal_hash_update(state, (const uint8_t *)&lmots_key.I, sizeof(lmots_key.I)));
+    l = u32str(r); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+    s = u16str(D_LEAF); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+    check(hal_hash_update(state, (const uint8_t *)&lmots_key.K, sizeof(lmots_key.K)));
+    check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp)));
+
+//     i = 0
+//     while (node_num > 1) {
+//       if (node_num is odd):
+//         tmp = H(I || u32str(node_num/2) || u16str(D_INTR) || path[i] || tmp)
+//       else:
+//         tmp = H(I || u32str(node_num/2) || u16str(D_INTR) || tmp || path[i])
+//       node_num = node_num/2
+//       i = i + 1
+//     }
+    for (size_t i = 0; r > 1; r /= 2, ++i) {
+        check(hal_hash_initialize(NULL, hal_hash_sha256, &state, statebuf, sizeof(statebuf)));
+        check(hal_hash_update(state, (const uint8_t *)&key->I, sizeof(key->I)));
+        l = u32str(r/2); check(hal_hash_update(state, (const uint8_t *)&l, sizeof(l)));
+        s = u16str(D_INTR); check(hal_hash_update(state, (const uint8_t *)&s, sizeof(s)));
+        if (r & 1) {
+            check(hal_hash_update(state, (const uint8_t *)&path[i], m));
+            check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp)));
+        }
+        else {
+            check(hal_hash_update(state, (const uint8_t *)&tmp, sizeof(tmp)));
+            check(hal_hash_update(state, (const uint8_t *)&path[i], m));
+        }
+        check(hal_hash_finalize(state, (uint8_t *)&tmp, sizeof(tmp)));
+    }
+
+//     Tc = tmp
+    memcpy(Tc, &tmp, sizeof(*Tc));
+
+    return HAL_OK;
+}
+
+#if RPC_CLIENT == RPC_CLIENT_LOCAL
+static hal_error_t lms_private_key_to_der(const lms_key_t * const key,
+                                          uint8_t *der, size_t *der_len, const size_t der_max)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_LMS)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    /*
+     * Calculate data length.
+     */
+
+    // u32str(lms_type) || u32str(lmots_type) || I || q
+
+    size_t len, vlen = 0, hlen;
+
+    check(hal_asn1_encode_lms_algorithm(key->lms->type, NULL, &len, 0));     vlen += len;
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len;
+    check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0));             vlen += len;
+    check(hal_asn1_encode_size_t(key->q, NULL, &len, 0));                    vlen += len;
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, NULL, &hlen, 0));
+
+    check(hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                               NULL, 0, NULL, hlen + vlen, NULL, der_len, der_max));
+
+    if (der == NULL)
+        return HAL_OK;
+
+    /*
+     * Encode data.
+     */
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max));
+
+    uint8_t *d = der + hlen;
+    memset(d, 0, vlen);
+
+    check(hal_asn1_encode_lms_algorithm(key->lms->type, d, &len, vlen));     d += len; vlen -= len;
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, vlen)); d += len; vlen -= len;
+    check(hal_asn1_encode_bytestring16(&key->I, d, &len, vlen));             d += len; vlen -= len;
+    check(hal_asn1_encode_size_t(key->q, d, &len, vlen));                    d += len; vlen -= len;
+
+    return hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                                NULL, 0, der, d - der, der, der_len, der_max);
+}
+
+static size_t lms_private_key_to_der_len(const lms_key_t * const key)
+{
+    size_t len = 0;
+    return lms_private_key_to_der(key, NULL, &len, 0) == HAL_OK ? len : 0;
+}
+#endif
+
+#if 0
+// used in restart - caller will have to allocate and attach storage for lmots_keys[] and T[]
+static hal_error_t lms_private_key_from_der(lms_key_t *key,
+                                            const uint8_t *der, const size_t der_len)
+{
+    if (key == NULL || der == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    key->type = HAL_KEY_TYPE_HASHSIG_LMS;
+
+    size_t hlen, vlen, alg_oid_len, curve_oid_len, privkey_len;
+    const uint8_t     *alg_oid,    *curve_oid,    *privkey;
+
+    check(hal_asn1_decode_pkcs8_privatekeyinfo(&alg_oid, &alg_oid_len,
+                                               &curve_oid, &curve_oid_len,
+                                               &privkey, &privkey_len,
+                                               der, der_len));
+
+    if (alg_oid_len != hal_asn1_oid_mts_hashsig_len ||
+        memcmp(alg_oid, hal_asn1_oid_mts_hashsig, alg_oid_len) != 0 ||
+        curve_oid_len != 0)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    check(hal_asn1_decode_header(ASN1_SEQUENCE, privkey, privkey_len, &hlen, &vlen));
+
+    const uint8_t *d = privkey + hlen;
+    size_t n;
+
+    // u32str(lms_type) || u32str(lmots_type) || I || q
+
+    lms_algorithm_t lms_type;
+    check(hal_asn1_decode_lms_algorithm(&lms_type, d, &n, vlen));     d += n; vlen -= n;
+    key->lms = lms_select_parameter_set(lms_type);
+    lmots_algorithm_t lmots_type;
+    check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &n, vlen)); d += n; vlen -= n;
+    key->lmots = lmots_select_parameter_set(lmots_type);
+    check(hal_asn1_decode_bytestring16(&key->I, d, &n, vlen));        d += n; vlen -= n;
+    check(hal_asn1_decode_size_t(&key->q, d, &n, vlen));              d += n; vlen -= n;
+
+    if (d != privkey + privkey_len)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    return HAL_OK;
+}
+#endif
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * HSS
+ */
+
+/* For purposes of the external API, the key type is "hal_hashsig_key_t".
+ * Internally, we refer to it as "hss_key_t".
+ */
+
+typedef struct hal_hashsig_key hss_key_t;
+
+struct hal_hashsig_key {
+    hal_key_type_t type;
+    hss_key_t *next;
+    size_t L;
+    lms_parameter_t *lms;
+    lmots_parameter_t *lmots;
+    bytestring16 I;
+    bytestring32 T1;
+    lms_key_t *lms_keys;
+};
+
+const size_t hal_hashsig_key_t_size = sizeof(hss_key_t);
+
+static hss_key_t *hss_keys = NULL;
+
+static inline size_t hss_public_key_len(lms_parameter_t * const lms)
+{
+    /* L || pub[0] */
+    return sizeof(uint32_t) + lms_public_key_len(lms);
+}
+
+static inline size_t hss_signature_len(const size_t L, lms_parameter_t * const lms, lmots_parameter_t * const lmots)
+{
+    /* u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk] */
+    return sizeof(uint32_t) + L * lms_signature_len(lms, lmots) + (L - 1) * lms_public_key_len(lms);
+}
+
+size_t hal_hashsig_signature_len(const size_t L,
+                                 const lms_algorithm_t lms_type,
+                                 const lmots_algorithm_t lmots_type)
+{
+    lms_parameter_t * const lms = lms_select_parameter_set(lms_type);
+    if (lms == NULL)
+        return 0;
+
+    lmots_parameter_t * const lmots = lmots_select_parameter_set(lmots_type);
+    if (lmots == NULL)
+        return 0;
+
+    return hss_signature_len(L, lms, lmots);
+}
+
+size_t hal_hashsig_lmots_private_key_len(const lmots_algorithm_t lmots_type)
+{
+    lmots_parameter_t * const lmots = lmots_select_parameter_set(lmots_type);
+    if (lmots == NULL)
+        return 0;
+
+    return lmots_private_key_len(lmots);
+}
+
+#if RPC_CLIENT == RPC_CLIENT_LOCAL
+static inline void *gnaw(uint8_t **mem, size_t *len, const size_t size)
+{
+    if (mem == NULL || *mem == NULL || len == NULL || size > *len)
+        return NULL;
+    void *ret = *mem;
+    *mem += size;
+    *len -= size;
+    return ret;
+}
+
+/* called from pkey_local_generate_hashsig */
+hal_error_t hal_hashsig_key_gen(hal_core_t *core,
+                                hal_hashsig_key_t **key_,
+                                const size_t L,
+                                const lms_algorithm_t lms_type,
+                                const lmots_algorithm_t lmots_type)
+{
+    if (key_ == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    if (L == 0 || L > 8)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    lms_parameter_t *lms = lms_select_parameter_set(lms_type);
+    if (lms == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    lmots_parameter_t *lmots = lmots_select_parameter_set(lmots_type);
+    if (lmots == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    /* w=1 fails on the Alpha, because the key exceeds the keystore block
+     * size. The XDR encoding of the key is going to differ from the DER
+     * encoding, but it's at least in the ballpark to tell us whether the key
+     * will fit.
+     */
+    if (lmots_private_key_len(lmots) > HAL_KS_BLOCK_SIZE)
+        return HAL_ERROR_UNSUPPORTED_KEY;
+
+    /* w=2 fails on the Alpha, as does w=4 with L=2, because the signature
+     * exceeds the meagre 4096-byte RPC packet size.
+     */
+    if (hss_signature_len(L, lms, lmots) > HAL_RPC_MAX_PKT_SIZE)
+        return HAL_ERROR_UNSUPPORTED_KEY;
+
+    /* check flash keystore for space to store the root tree */
+    size_t available;
+    check(hal_ks_available(hal_ks_token, &available));
+    if (available < lms->h2 + 2)
+        return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+    /* check volatile keystore for space to store the lower-level trees */
+    check(hal_ks_available(hal_ks_volatile, &available));
+    if (available < (L - 1) * (lms->h2 + 1))
+        return HAL_ERROR_NO_KEY_INDEX_SLOTS;
+
+    size_t lms_sig_len = lms_signature_len(lms, lmots);
+    size_t lms_pub_len = lms_public_key_len(lms);
+
+    /* allocate lms tree nodes and lmots key names, atomically */
+    size_t len = (sizeof(hss_key_t) +
+                  L * sizeof(lms_key_t) +
+                  L * lms_sig_len +
+                  L * lms_pub_len +
+                  L * lms->h2 * sizeof(hal_uuid_t) +
+                  L * (2 * lms->h2 - 1) * sizeof(bytestring32));
+    uint8_t *mem = hal_allocate_static_memory(len);
+    if (mem == NULL)
+        return HAL_ERROR_ALLOCATION_FAILURE;
+    memset(mem, 0, len);
+
+    /* allocate the key that will stay in working memory */
+    hss_key_t *key = gnaw(&mem, &len, sizeof(hss_key_t));
+    key->type = HAL_KEY_TYPE_HASHSIG_PRIVATE;
+    key->L = L;
+    key->lms = lms;
+    key->lmots = lmots;
+
+    /* add to the list of active keys */
+    key->next = hss_keys;
+    hss_keys = key;
+
+    /* allocate the list of lms trees */
+    key->lms_keys = gnaw(&mem, &len, L * sizeof(lms_key_t));
+
+    /* generate the lms trees */
+    for (size_t i = 0; i < L; ++i) {
+        lms_key_t * lms_key = &key->lms_keys[i];
+        lms_key->type = HAL_KEY_TYPE_HASHSIG_LMS;
+        lms_key->lms = lms;
+        lms_key->lmots = lmots;
+        lms_key->level = i;
+        lms_key->lmots_keys = (hal_uuid_t *)gnaw(&mem, &len, lms->h2 * sizeof(hal_uuid_t));
+        lms_key->T = gnaw(&mem, &len, (2 * lms->h2 - 1) * sizeof(bytestring32));
+        lms_key->signature = gnaw(&mem, &len, lms_sig_len);
+        lms_key->signature_len = lms_sig_len;
+        lms_key->pubkey = gnaw(&mem, &len, lms_pub_len);
+        lms_key->pubkey_len = lms_pub_len;
+
+        check(lms_generate(lms_key));
+
+        if (i > 0)
+            /* sign this tree with the previous */
+            check(lms_sign(&key->lms_keys[i-1],
+                           (const uint8_t * const)lms_key->pubkey, lms_pub_len,
+                           lms_key->signature, NULL, lms_sig_len));
+
+        /* store the lms key */
+        hal_pkey_slot_t slot = {
+            .type  = HAL_KEY_TYPE_HASHSIG_LMS,
+            .curve = HAL_CURVE_NONE,
+            .flags = (i == 0) ? HAL_KEY_FLAG_TOKEN: 0
+        };
+        hal_ks_t *ks = (i == 0) ? hal_ks_token : hal_ks_volatile;
+        uint8_t der[lms_private_key_to_der_len(lms_key)];
+        size_t der_len;
+
+        memcpy(&slot.name, &lms_key->I, sizeof(slot.name));
+        check(lms_private_key_to_der(lms_key, der, &der_len, sizeof(der)));
+        check(hal_ks_store(ks, &slot, der, der_len));
+    }
+
+    memcpy(&key->I, &key->lms_keys[0].I, sizeof(key->I));
+    memcpy(&key->T1, &key->lms_keys[0].T1, sizeof(key->T1));
+
+    *key_ = key;
+
+    /* pkey_local_generate_hashsig stores the key */
+
+    return HAL_OK;
+}
+
+hal_error_t hal_hashsig_key_delete(const hal_hashsig_key_t * const key)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    /* delete the lms trees and their lmots keys */
+    for (size_t level = 0; level < key->L; ++level)
+        check(lms_delete(&key->lms_keys[level]));
+
+    /* XXX free memory, if supported */
+
+    /* remove from global hss_keys linked list */
+    /* XXX or mark it unused, for possible re-use */
+    if (hss_keys == key) {
+        hss_keys = key->next;
+    }
+    else {
+        for (hss_key_t *prev = hss_keys; prev != NULL; prev = prev->next) {
+            if (prev->next == key) {
+                prev->next = key->next;
+                break;
+            }
+        }
+    }
+
+    return HAL_OK;
+}
+
+hal_error_t hal_hashsig_sign(hal_core_t *core,
+                             const hal_hashsig_key_t * const key,
+                             const uint8_t * const msg, const size_t msg_len,
+                             uint8_t *sig, size_t *sig_len, const size_t sig_max)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE || msg == NULL || sig == NULL || sig_len == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    if (sig_max < hss_signature_len(key->L, key->lms, key->lmots))
+        return HAL_ERROR_RESULT_TOO_LONG;
+
+//   To sign a message using the private key prv, the following steps are
+//   performed:
+//
+//      If prv[L-1] is exhausted, then determine the smallest integer d
+//      such that all of the private keys prv[d], prv[d+1], ... , prv[L-1]
+//      are exhausted.  If d is equal to zero, then the HSS key pair is
+//      exhausted, and it MUST NOT generate any more signatures.
+//      Otherwise, the key pairs for levels d through L-1 must be
+//      regenerated during the signature generation process, as follows.
+//      For i from d to L-1, a new LMS public and private key pair with a
+//      new identifier is generated, pub[i] and prv[i] are set to those
+//      values, then the public key pub[i] is signed with prv[i-1], and
+//      sig[i-1] is set to the resulting value.
+
+    if (key->lms_keys[key->L-1].q >= key->lms->h2) {
+        size_t d;
+        for (d = key->L-1; d > 0 && key->lms_keys[d-1].q >= key->lms->h2; --d) {
+        }
+        if (d == 0)
+            return HAL_ERROR_HASHSIG_KEY_EXHAUSTED;
+        for ( ; d < key->L; ++d) {
+            lms_key_t *lms_key = &key->lms_keys[d];
+            /* Delete then regenerate the LMS key. We don't worry about
+             * power-cycling in the middle, because the lower-level trees are
+             * all stored in the volatile keystore, so we'd have to regenerate
+             * them anyway on restart; and this way we don't have to allocate
+             * any additional memory.
+             */
+            check(lms_delete(lms_key));
+            check(lms_generate(lms_key));
+            check(lms_sign(&key->lms_keys[d-1],
+                           (const uint8_t * const)lms_key->pubkey, lms_key->pubkey_len,
+                           lms_key->signature, NULL, lms_key->signature_len));
+
+            hal_pkey_slot_t slot = {
+                .type  = HAL_KEY_TYPE_HASHSIG_LMS,
+                .curve = HAL_CURVE_NONE,
+                .flags = (lms_key->level == 0) ? HAL_KEY_FLAG_TOKEN: 0
+            };
+            hal_ks_t *ks = (lms_key->level == 0) ? hal_ks_token : hal_ks_volatile;
+            uint8_t der[lms_private_key_to_der_len(lms_key)];
+            size_t der_len;
+
+            memcpy(&slot.name, &lms_key->I, sizeof(slot.name));
+            check(lms_private_key_to_der(lms_key, der, &der_len, sizeof(der)));
+            check(hal_ks_store(ks, &slot, der, der_len));
+        }
+    }
+
+//      The message is signed with prv[L-1], and the value sig[L-1] is set
+//      to that result.
+//
+//      The value of the HSS signature is set as follows.  We let
+//      signed_pub_key denote an array of octet strings, where
+//      signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk-
+//      1, inclusive, where Nspk = L-1 denotes the number of signed public
+//      keys.  Then the HSS signature is u32str(Nspk) ||
+//      signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk].
+
+    uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_max;
+    check(hal_xdr_encode_int(&sigptr, siglim, key->L - 1));
+
+    /* copy the lms signed public keys into the signature */
+    for (size_t i = 1; i < key->L; ++i) {
+        lms_key_t *lms_key = &key->lms_keys[i];
+        check(hal_xdr_encode_fixed_opaque(&sigptr, siglim, lms_key->signature, lms_key->signature_len));
+        check(hal_xdr_encode_fixed_opaque(&sigptr, siglim, lms_key->pubkey, lms_key->pubkey_len));
+    }
+
+    /* sign the message with the last lms private key */
+    size_t len;
+    check(lms_sign(&key->lms_keys[key->L-1], msg, msg_len, sigptr, &len, sig_max - (sigptr - sig)));
+    sigptr += len;
+    *sig_len = sigptr - sig;
+
+    return HAL_OK;
+}
+#endif
+
+hal_error_t hal_hashsig_verify(hal_core_t *core,
+                               const hal_hashsig_key_t * const key,
+                               const uint8_t * const msg, const size_t msg_len,
+                               const uint8_t * const sig, const size_t sig_len)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PUBLIC || msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    core = core;
+
+//   To verify a signature sig and message using the public key pub, the
+//   following steps are performed:
+//
+//      The signature S is parsed into its components as follows:
+//
+//      Nspk = strTou32(first four bytes of S)
+//      if Nspk+1 is not equal to the number of levels L in pub:
+//         return INVALID
+
+    const uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_len;
+
+    uint32_t Nspk;
+    check(hal_xdr_decode_int(&sigptr, siglim, &Nspk));
+    if (Nspk + 1 != key->L)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//      key = pub
+//      for (i = 0; i < Nspk; i = i + 1) {
+//         sig = next LMS signature parsed from S
+//         msg = next LMS public key parsed from S
+//         if (lms_verify(msg, key, sig) != VALID):
+//             return INVALID
+//         key = msg
+//      }
+
+    lms_key_t pub = {
+        .type = HAL_KEY_TYPE_HASHSIG_LMS,
+        .lms = key->lms,
+        .lmots = key->lmots
+    };
+    memcpy(&pub.I, &key->I, sizeof(pub.I));
+    memcpy(&pub.T1, &key->T1, sizeof(pub.T1));
+
+    for (size_t i = 0; i < Nspk; ++i) {
+        const uint8_t * const lms_sig = sigptr;
+        /* peek into the signature for the lmots and lms types */
+        /* XXX The structure of the LMS signature makes this a bigger pain
+         * in the ass than necessary.
+         */
+        /* skip over q */
+        sigptr += 4;
+        /* read lmots_type out of the ots_signature */
+        uint32_t lmots_type;
+        check(hal_xdr_decode_int_peek(&sigptr, siglim, &lmots_type));
+        lmots_parameter_t *lmots = lmots_select_parameter_set((lmots_algorithm_t)lmots_type);
+        if (lmots == NULL)
+            return HAL_ERROR_INVALID_SIGNATURE;
+        /* skip over ots_signature */
+        sigptr += lmots_signature_len(lmots);
+        /* read lms_type after ots_signature */
+        uint32_t lms_type;
+        check(hal_xdr_decode_int(&sigptr, siglim, &lms_type));
+        lms_parameter_t *lms = lms_select_parameter_set((lms_algorithm_t)lms_type);
+        if (lms == NULL)
+            return HAL_ERROR_INVALID_SIGNATURE;
+        /* skip over the path elements of the lms signature */
+        sigptr += lms->h * lms->m;
+        /*XXX sigptr = lms_sig + lms_signature_len(lms, lmots); */
+
+        /* verify the signature over the bytestring version of the signed public key */
+        check(lms_verify(&pub, sigptr, lms_public_key_len(lms), lms_sig, sigptr - lms_sig));
+
+        /* parse the signed public key */
+        check(hal_xdr_decode_int(&sigptr, siglim, &lms_type));
+        pub.lms = lms_select_parameter_set((lmots_algorithm_t)lms_type);
+        if (pub.lms == NULL)
+            return HAL_ERROR_INVALID_SIGNATURE;
+        check(hal_xdr_decode_int(&sigptr, siglim, &lmots_type));
+        pub.lmots = lmots_select_parameter_set((lmots_algorithm_t)lmots_type);
+        if (pub.lmots == NULL)
+            return HAL_ERROR_INVALID_SIGNATURE;
+        check(hal_xdr_decode_bytestring16(&sigptr, siglim, &pub.I));
+        check(hal_xdr_decode_bytestring32(&sigptr, siglim, &pub.T1));
+    }
+
+    /* verify the final signature over the message */
+    return lms_verify(&pub, msg, msg_len, sigptr, sig_len - (sigptr - sig));
+}
+
+hal_error_t hal_hashsig_private_key_to_der(const hal_hashsig_key_t * const key,
+                                           uint8_t *der, size_t *der_len, const size_t der_max)
+{
+    if (key == NULL || key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    /*
+     * Calculate data length.
+     */
+
+    size_t len, vlen = 0, hlen;
+
+    check(hal_asn1_encode_size_t(key->L, NULL, &len, 0));                          vlen += len;
+    check(hal_asn1_encode_lms_algorithm(key->lms->type, NULL, &len, 0));           vlen += len;
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0));       vlen += len;
+    check(hal_asn1_encode_uuid((hal_uuid_t *)&key->lms_keys[0].I, NULL, &len, 0)); vlen += len;
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, NULL, &hlen, 0));
+
+    check(hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                               NULL, 0, NULL, hlen + vlen, NULL, der_len, der_max));
+
+    if (der == NULL)
+        return HAL_OK;
+
+    /*
+     * Encode data.
+     */
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max));
+
+    uint8_t *d = der + hlen;
+    memset(d, 0, vlen);
+
+    check(hal_asn1_encode_size_t(key->L, d, &len, vlen));                          d += len; vlen -= len;
+    check(hal_asn1_encode_lms_algorithm(key->lms->type, d, &len, vlen));           d += len; vlen -= len;
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, vlen));       d += len; vlen -= len;
+    check(hal_asn1_encode_uuid((hal_uuid_t *)&key->lms_keys[0].I, d, &len, vlen)); d += len; vlen -= len;
+
+    return hal_asn1_encode_pkcs8_privatekeyinfo(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                                NULL, 0, der, d - der, der, der_len, der_max);
+}
+
+size_t hal_hashsig_private_key_to_der_len(const hal_hashsig_key_t * const key)
+{
+    size_t len = 0;
+    return hal_hashsig_private_key_to_der(key, NULL, &len, 0) == HAL_OK ? len : 0;
+}
+
+hal_error_t hal_hashsig_private_key_from_der(hal_hashsig_key_t **key_,
+                                             void *keybuf, const size_t keybuf_len,
+                                             const uint8_t *der, const size_t der_len)
+{
+    if (key_ == NULL || keybuf == NULL || keybuf_len < sizeof(hal_hashsig_key_t) || der == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    memset(keybuf, 0, keybuf_len);
+
+    hss_key_t *key = keybuf;
+
+    key->type = HAL_KEY_TYPE_HASHSIG_PRIVATE;
+
+    size_t hlen, vlen, alg_oid_len, curve_oid_len, privkey_len;
+    const uint8_t     *alg_oid,    *curve_oid,    *privkey;
+    hal_error_t err;
+
+    if ((err = hal_asn1_decode_pkcs8_privatekeyinfo(&alg_oid, &alg_oid_len,
+                                                    &curve_oid, &curve_oid_len,
+                                                    &privkey, &privkey_len,
+                                                    der, der_len)) != HAL_OK)
+        return err;
+
+    if (alg_oid_len != hal_asn1_oid_mts_hashsig_len ||
+        memcmp(alg_oid, hal_asn1_oid_mts_hashsig, alg_oid_len) != 0 ||
+        curve_oid_len != 0)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    if ((err = hal_asn1_decode_header(ASN1_SEQUENCE, privkey, privkey_len, &hlen, &vlen)) != HAL_OK)
+        return err;
+
+    const uint8_t *d = privkey + hlen;
+    size_t n;
+
+    check(hal_asn1_decode_size_t(&key->L, d, &n, vlen));              d += n; vlen -= n;
+    lms_algorithm_t lms_type;
+    check(hal_asn1_decode_lms_algorithm(&lms_type, d, &n, vlen));     d += n; vlen -= n;
+    key->lms = lms_select_parameter_set(lms_type);
+    lmots_algorithm_t lmots_type;
+    check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &n, vlen)); d += n; vlen -= n;
+    key->lmots = lmots_select_parameter_set(lmots_type);
+    hal_uuid_t I;
+    check(hal_asn1_decode_uuid(&I, d, &n, vlen));                     d += n; vlen -= n;
+
+    if (d != privkey + privkey_len)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    /* Find this key in the list of active hashsig keys, and return a
+     * pointer to that key structure, rather than the caller-provided key
+     * structure. (The caller will wipe his own key structure when done,
+     * and not molest ours.)
+     */
+    for (hss_key_t *hss_key = hss_keys; hss_key != NULL; hss_key = hss_key->next) {
+        if (hal_uuid_cmp(&I, (hal_uuid_t *)&hss_key->lms_keys[0].I) == 0) {
+            *key_ = hss_key;
+            return HAL_OK;
+        }
+    }
+    return HAL_ERROR_KEY_NOT_FOUND;     // or IMPOSSIBLE?
+}
+
+hal_error_t hal_hashsig_public_key_to_der(const hal_hashsig_key_t * const key,
+                                          uint8_t *der, size_t *der_len, const size_t der_max)
+{
+    if (key == NULL || (key->type != HAL_KEY_TYPE_HASHSIG_PRIVATE &&
+                        key->type != HAL_KEY_TYPE_HASHSIG_PUBLIC))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    // L || u32str(lms_type) || u32str(lmots_type) || I || T[1]
+
+    size_t len, vlen = 0, hlen;
+
+    check(hal_asn1_encode_size_t(key->L, NULL, &len, 0));                    vlen += len;
+    check(hal_asn1_encode_lms_algorithm(key->lms->type, NULL, &len, 0));     vlen += len;
+    check(hal_asn1_encode_lmots_algorithm(key->lmots->type, NULL, &len, 0)); vlen += len;
+    check(hal_asn1_encode_bytestring16(&key->I, NULL, &len, 0));             vlen += len;
+    check(hal_asn1_encode_bytestring32(&key->T1, NULL, &len, 0));            vlen += len;
+
+    check(hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max));
+
+    if (der != NULL) {
+        uint8_t *d = der + hlen;
+        size_t dlen = vlen;
+        memset(d, 0, vlen);
+
+        check(hal_asn1_encode_size_t(key->L, d, &len, dlen));                    d += len; dlen -= len;
+        check(hal_asn1_encode_lms_algorithm(key->lms->type, d, &len, dlen));     d += len; dlen -= len;
+        check(hal_asn1_encode_lmots_algorithm(key->lmots->type, d, &len, dlen)); d += len; dlen -= len;
+        check(hal_asn1_encode_bytestring16(&key->I, d, &len, dlen));             d += len; dlen -= len;
+        check(hal_asn1_encode_bytestring32(&key->T1, d, &len, dlen));            d += len; dlen -= len;
+    }
+
+    return hal_asn1_encode_spki(hal_asn1_oid_mts_hashsig, hal_asn1_oid_mts_hashsig_len,
+                                NULL, 0, der, hlen + vlen,
+                                der, der_len, der_max);
+
+}
+
+size_t hal_hashsig_public_key_to_der_len(const hal_hashsig_key_t * const key)
+{
+    size_t len = 0;
+    return hal_hashsig_public_key_to_der(key, NULL, &len, 0) == HAL_OK ? len : 0;
+}
+
+hal_error_t hal_hashsig_public_key_from_der(hal_hashsig_key_t **key_,
+                                            void *keybuf, const size_t keybuf_len,
+                                            const uint8_t * const der, const size_t der_len)
+{
+    if (key_ == NULL || keybuf == NULL || keybuf_len < sizeof(hss_key_t) || der == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    hss_key_t *key = keybuf;
+
+    memset(keybuf, 0, keybuf_len);
+    *key_ = key;
+
+    key->type = HAL_KEY_TYPE_HASHSIG_PUBLIC;
+
+    const uint8_t *alg_oid = NULL, *null = NULL, *pubkey = NULL;
+    size_t         alg_oid_len,     null_len,     pubkey_len;
+
+    check(hal_asn1_decode_spki(&alg_oid, &alg_oid_len, &null, &null_len, &pubkey, &pubkey_len, der, der_len));
+
+    if (null != NULL || null_len != 0 || alg_oid == NULL ||
+        alg_oid_len != hal_asn1_oid_mts_hashsig_len || memcmp(alg_oid, hal_asn1_oid_mts_hashsig, alg_oid_len) != 0)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    size_t len, hlen, vlen;
+
+    check(hal_asn1_decode_header(ASN1_SEQUENCE, pubkey, pubkey_len, &hlen, &vlen));
+
+    const uint8_t * const pubkey_end = pubkey + hlen + vlen;
+    const uint8_t *d = pubkey + hlen;
+
+    // L || u32str(lms_type) || u32str(lmots_type) || I || T[1]
+
+    lms_algorithm_t lms_type;
+    lmots_algorithm_t lmots_type;
+
+    check(hal_asn1_decode_size_t(&key->L, d, &len, pubkey_end - d));              d += len;
+    check(hal_asn1_decode_lms_algorithm(&lms_type, d, &len, pubkey_end - d));     d += len;
+    key->lms = lms_select_parameter_set(lms_type);
+    check(hal_asn1_decode_lmots_algorithm(&lmots_type, d, &len, pubkey_end - d)); d += len;
+    key->lmots = lmots_select_parameter_set(lmots_type);
+    check(hal_asn1_decode_bytestring16(&key->I, d, &len, pubkey_end - d));        d += len;
+    check(hal_asn1_decode_bytestring32(&key->T1, d, &len, pubkey_end - d));       d += len;
+
+    if (d != pubkey_end)
+        return HAL_ERROR_ASN1_PARSE_FAILED;
+
+
+    return HAL_OK;
+}
+
+hal_error_t hal_hashsig_key_load_public(hal_hashsig_key_t **key_,
+                                        void *keybuf, const size_t keybuf_len,
+                                        const size_t L,
+                                        const lms_algorithm_t lms_type,
+                                        const lmots_algorithm_t lmots_type,
+                                        const uint8_t * const I, const size_t I_len,
+                                        const uint8_t * const T1, const size_t T1_len)
+{
+    if (key_ == NULL || keybuf == NULL || keybuf_len < sizeof(hal_hashsig_key_t) ||
+        I == NULL || I_len != sizeof(bytestring16) ||
+        T1 == NULL || T1_len != sizeof(bytestring32))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    memset(keybuf, 0, keybuf_len);
+
+    hal_hashsig_key_t *key = keybuf;
+
+    key->type = HAL_KEY_TYPE_HASHSIG_PUBLIC;
+
+    key->L = L;
+    key->lms = lms_select_parameter_set(lms_type);
+    key->lmots = lmots_select_parameter_set(lmots_type);
+    if (key->lms == NULL || key->lmots == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    memcpy(&key->I, I, I_len);
+    memcpy(&key->T1, T1, T1_len);
+
+    *key_ = key;
+
+    return HAL_OK;
+}
+
+
+hal_error_t hal_hashsig_key_load_public_xdr(hal_hashsig_key_t **key_,
+                                            void *keybuf, const size_t keybuf_len,
+                                            const uint8_t * const xdr, const size_t xdr_len)
+{
+    const uint8_t *xdrptr = xdr;
+    const uint8_t * const xdrlim = xdr + xdr_len;
+
+    /* L || u32str(lms_type) || u32str(lmots_type) || I || T[1] */
+
+    uint32_t L, lms_type, lmots_type;
+    bytestring16 *I;
+    bytestring32 *T1;
+    
+    check(hal_xdr_decode_int(&xdrptr, xdrlim, &L));
+    check(hal_xdr_decode_int(&xdrptr, xdrlim, &lms_type));
+    check(hal_xdr_decode_int(&xdrptr, xdrlim, &lmots_type));
+    check(hal_xdr_decode_bytestring16_ptr(&xdrptr, xdrlim, &I));
+    check(hal_xdr_decode_bytestring32_ptr(&xdrptr, xdrlim, &T1));
+
+    return hal_hashsig_key_load_public(key_, keybuf, keybuf_len, L, lms_type, lmots_type,
+                                       (const uint8_t * const)I, sizeof(bytestring16),
+                                       (const uint8_t * const)T1, sizeof(bytestring32));
+}
diff --git a/hashsig.h b/hashsig.h
new file mode 100644
index 0000000..aeb2828
--- /dev/null
+++ b/hashsig.h
@@ -0,0 +1,115 @@
+/*
+ * hashsig.c
+ * ---------
+ * Implementation of draft-mcgrew-hash-sigs-08.txt
+ *
+ * Copyright (c) 2018, NORDUnet A/S All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * - Redistributions of source code must retain the above copyright notice,
+ *   this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ *
+ * - Neither the name of the NORDUnet nor the names of its contributors may
+ *   be used to endorse or promote products derived from this software
+ *   without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+ * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _HAL_HASHSIG_H_
+#define _HAL_HASHSIG_H_
+
+typedef enum lmots_algorithm_type {
+    lmots_reserved      = 0,
+    lmots_sha256_n32_w1 = 1,
+    lmots_sha256_n32_w2 = 2,
+    lmots_sha256_n32_w4 = 3,
+    lmots_sha256_n32_w8 = 4
+} lmots_algorithm_t;
+
+typedef enum lms_algorithm_type {
+    lms_reserved        = 0,
+    lms_sha256_n32_h5   = 5,
+    lms_sha256_n32_h10  = 6,
+    lms_sha256_n32_h15  = 7,
+    lms_sha256_n32_h20  = 8,
+    lms_sha256_n32_h25  = 9
+} lms_algorithm_t;
+
+typedef struct hal_hashsig_key hal_hashsig_key_t;
+
+extern const size_t hal_hashsig_key_t_size;
+
+extern hal_error_t hal_hashsig_key_gen(hal_core_t *core,
+                                       hal_hashsig_key_t **key_,
+                                       const size_t hss_levels,
+                                       const lms_algorithm_t lms_type,
+                                       const lmots_algorithm_t lmots_type);
+
+extern hal_error_t hal_hashsig_key_delete(const hal_hashsig_key_t * const key);
+
+extern hal_error_t hal_hashsig_private_key_to_der(const hal_hashsig_key_t * const key,
+                                                  uint8_t *der, size_t *der_len, const size_t der_max);
+
+extern size_t hal_hashsig_private_key_to_der_len(const hal_hashsig_key_t * const key);
+
+extern hal_error_t hal_hashsig_private_key_from_der(hal_hashsig_key_t **key_,
+                                                    void *keybuf, const size_t keybuf_len,
+                                                    const uint8_t *der, const size_t der_len);
+
+extern hal_error_t hal_hashsig_public_key_to_der(const hal_hashsig_key_t * const key,
+                                                 uint8_t *der, size_t *der_len, const size_t der_max);
+
+extern size_t hal_hashsig_public_key_to_der_len(const hal_hashsig_key_t * const key);
+
+extern hal_error_t hal_hashsig_public_key_from_der(hal_hashsig_key_t **key,
+                                                   void *keybuf, const size_t keybuf_len,
+                                                   const uint8_t * const der, const size_t der_len);
+
+extern hal_error_t hal_hashsig_sign(hal_core_t *core,
+                                    const hal_hashsig_key_t * const key,
+                                    const uint8_t * const hash, const size_t hash_len,
+                                    uint8_t *signature, size_t *signature_len, const size_t signature_max);
+
+extern hal_error_t hal_hashsig_verify(hal_core_t *core,
+                                      const hal_hashsig_key_t * const key,
+                                      const uint8_t * const hash, const size_t hash_len,
+                                      const uint8_t * const signature, const size_t signature_len);
+
+extern hal_error_t hal_hashsig_key_load_public(hal_hashsig_key_t **key_,
+                                               void *keybuf, const size_t keybuf_len,
+                                               const size_t L,
+                                               const lms_algorithm_t lms_type,
+                                               const lmots_algorithm_t lmots_type,
+                                               const uint8_t * const I, const size_t I_len,
+                                               const uint8_t * const T1, const size_t T1_len);
+
+extern hal_error_t hal_hashsig_key_load_public_xdr(hal_hashsig_key_t **key_,
+                                                   void *keybuf, const size_t keybuf_len,
+                                                   const uint8_t * const xdr, const size_t xdr_len);
+
+extern size_t hal_hashsig_signature_len(const size_t L,
+                                        const lms_algorithm_t lms_type,
+                                        const lmots_algorithm_t lmots_type);
+
+extern size_t hal_hashsig_lmots_private_key_len(const lmots_algorithm_t lmots_type);
+
+//extern hal_error_t hal_hashsig_restart(...);
+
+#endif /* _HAL_HASHSIG_H_ */
diff --git a/ks.c b/ks.c
index f145adc..c848056 100644
--- a/ks.c
+++ b/ks.c
@@ -514,6 +514,10 @@ static inline int acceptable_key_type(const hal_key_type_t type)
   case HAL_KEY_TYPE_EC_PRIVATE:
   case HAL_KEY_TYPE_RSA_PUBLIC:
   case HAL_KEY_TYPE_EC_PUBLIC:
+  case HAL_KEY_TYPE_HASHSIG_PRIVATE:
+  case HAL_KEY_TYPE_HASHSIG_PUBLIC:
+  case HAL_KEY_TYPE_HASHSIG_LMS:
+  case HAL_KEY_TYPE_HASHSIG_LMOTS:
     return 1;
   default:
     return 0;
diff --git a/ks_volatile.c b/ks_volatile.c
index 2d0abd4..75d7fcb 100644
--- a/ks_volatile.c
+++ b/ks_volatile.c
@@ -43,10 +43,6 @@
 #include "hal_internal.h"
 #include "ks.h"
 
-#ifndef STATIC_KS_VOLATILE_SLOTS
-#define STATIC_KS_VOLATILE_SLOTS HAL_STATIC_PKEY_STATE_BLOCKS
-#endif
-
 #ifndef KS_VOLATILE_CACHE_SIZE
 #define KS_VOLATILE_CACHE_SIZE 4
 #endif
@@ -258,8 +254,8 @@ static hal_error_t ks_volatile_init(hal_ks_t *ks, const int alloc)
   hal_error_t err;
 
   if (alloc &&
-      (err = hal_ks_alloc_common(ks, STATIC_KS_VOLATILE_SLOTS, KS_VOLATILE_CACHE_SIZE,
-                                 &mem, sizeof(*db->keys) * STATIC_KS_VOLATILE_SLOTS)) != HAL_OK)
+      (err = hal_ks_alloc_common(ks, HAL_STATIC_KS_VOLATILE_SLOTS, KS_VOLATILE_CACHE_SIZE,
+                                 &mem, sizeof(*db->keys) * HAL_STATIC_KS_VOLATILE_SLOTS)) != HAL_OK)
     return err;
 
   if (alloc)
diff --git a/rpc_api.c b/rpc_api.c
index 1dc8869..b75043a 100644
--- a/rpc_api.c
+++ b/rpc_api.c
@@ -35,6 +35,7 @@
 
 #include "hal.h"
 #include "hal_internal.h"
+#include "hashsig.h"
 
 const hal_hash_handle_t hal_hash_handle_none = {HAL_HANDLE_NONE};
 
@@ -64,6 +65,10 @@ static inline int check_pkey_type(const hal_key_type_t type)
   case HAL_KEY_TYPE_RSA_PUBLIC:
   case HAL_KEY_TYPE_EC_PRIVATE:
   case HAL_KEY_TYPE_EC_PUBLIC:
+  case HAL_KEY_TYPE_HASHSIG_PRIVATE:
+  case HAL_KEY_TYPE_HASHSIG_PUBLIC:
+  case HAL_KEY_TYPE_HASHSIG_LMS:
+  case HAL_KEY_TYPE_HASHSIG_LMOTS:
     return 1;
   default:
     return 0;
@@ -91,6 +96,10 @@ static inline int check_pkey_type_curve_flags(const hal_key_type_t type,
 
   case HAL_KEY_TYPE_RSA_PRIVATE:
   case HAL_KEY_TYPE_RSA_PUBLIC:
+  case HAL_KEY_TYPE_HASHSIG_PRIVATE:
+  case HAL_KEY_TYPE_HASHSIG_PUBLIC:
+  case HAL_KEY_TYPE_HASHSIG_LMS:
+  case HAL_KEY_TYPE_HASHSIG_LMOTS:
     return curve == HAL_CURVE_NONE;
 
   case HAL_KEY_TYPE_EC_PRIVATE:
@@ -264,6 +273,20 @@ hal_error_t hal_rpc_pkey_generate_ec(const hal_client_handle_t client,
   return hal_rpc_pkey_dispatch->generate_ec(client, session, pkey, name, curve, flags);
 }
 
+hal_error_t hal_rpc_pkey_generate_hashsig(const hal_client_handle_t client,
+                                          const hal_session_handle_t session,
+                                          hal_pkey_handle_t *pkey,
+                                          hal_uuid_t *name,
+                                          const size_t hss_levels,
+                                          const lms_algorithm_t lms_type,
+                                          const lmots_algorithm_t lmots_type,
+                                          const hal_key_flags_t flags)
+{
+  if (pkey == NULL || name == NULL || !check_pkey_flags(flags))
+    return HAL_ERROR_BAD_ARGUMENTS;
+  return hal_rpc_pkey_dispatch->generate_hashsig(client, session, pkey, name, hss_levels, lms_type, lmots_type, flags);
+}
+
 hal_error_t hal_rpc_pkey_close(const hal_pkey_handle_t pkey)
 {
   return hal_rpc_pkey_dispatch->close(pkey);
diff --git a/rpc_client.c b/rpc_client.c
index bb63448..2fb8ae6 100644
--- a/rpc_client.c
+++ b/rpc_client.c
@@ -38,6 +38,7 @@
 #include "hal.h"
 #include "hal_internal.h"
 #include "xdr_internal.h"
+#include "hashsig.h"
 
 #ifndef HAL_RPC_CLIENT_DEBUG
 #define HAL_RPC_CLIENT_DEBUG 0
@@ -544,6 +545,44 @@ static hal_error_t pkey_remote_generate_ec(const hal_client_handle_t client,
   return rpc_ret;
 }
 
+static hal_error_t pkey_remote_generate_hashsig(const hal_client_handle_t client,
+                                                const hal_session_handle_t session,
+                                                hal_pkey_handle_t *pkey,
+                                                hal_uuid_t *name,
+                                                const size_t hss_levels,
+                                                const lms_algorithm_t lms_type,
+                                                const lmots_algorithm_t lmots_type,
+                                                const hal_key_flags_t flags)
+{
+  uint8_t outbuf[nargs(7)], *optr = outbuf, *olimit = outbuf + sizeof(outbuf);
+  uint8_t inbuf[nargs(5) + pad(sizeof(name->uuid))];
+  const uint8_t *iptr = inbuf, *ilimit = inbuf + sizeof(inbuf);
+  size_t name_len = sizeof(name->uuid);
+  hal_error_t rpc_ret;
+
+  check(hal_xdr_encode_int(&optr, olimit, RPC_FUNC_PKEY_GENERATE_HASHSIG));
+  check(hal_xdr_encode_int(&optr, olimit, client.handle));
+  check(hal_xdr_encode_int(&optr, olimit, session.handle));
+  check(hal_xdr_encode_int(&optr, olimit, (uint32_t)hss_levels));
+  check(hal_xdr_encode_int(&optr, olimit, (uint32_t)lms_type));
+  check(hal_xdr_encode_int(&optr, olimit, (uint32_t)lmots_type));
+  check(hal_xdr_encode_int(&optr, olimit, flags));
+  check(hal_rpc_send(outbuf, optr - outbuf));
+
+  check(read_matching_packet(RPC_FUNC_PKEY_GENERATE_HASHSIG, inbuf, sizeof(inbuf), &iptr, &ilimit));
+
+  check(hal_xdr_decode_int(&iptr, ilimit, &rpc_ret));
+
+  if (rpc_ret == HAL_OK) {
+    check(hal_xdr_decode_int(&iptr, ilimit, &pkey->handle));
+    check(hal_xdr_decode_variable_opaque(&iptr, ilimit, name->uuid, &name_len));
+    if (name_len != sizeof(name->uuid))
+      return HAL_ERROR_KEY_NAME_TOO_LONG;
+  }
+
+  return rpc_ret;
+}
+
 static hal_error_t pkey_remote_close(const hal_pkey_handle_t pkey)
 {
   uint8_t outbuf[nargs(3)], *optr = outbuf, *olimit = outbuf + sizeof(outbuf);
@@ -1095,6 +1134,7 @@ const hal_rpc_pkey_dispatch_t hal_rpc_remote_pkey_dispatch = {
   .open                         = pkey_remote_open,
   .generate_rsa                 = pkey_remote_generate_rsa,
   .generate_ec                  = pkey_remote_generate_ec,
+  .generate_hashsig             = pkey_remote_generate_hashsig,
   .close                        = pkey_remote_close,
   .delete                       = pkey_remote_delete,
   .get_key_type                 = pkey_remote_get_key_type,
@@ -1117,6 +1157,7 @@ const hal_rpc_pkey_dispatch_t hal_rpc_mixed_pkey_dispatch = {
   .open                         = pkey_remote_open,
   .generate_rsa                 = pkey_remote_generate_rsa,
   .generate_ec                  = pkey_remote_generate_ec,
+  .generate_hashsig             = pkey_remote_generate_hashsig,
   .close                        = pkey_remote_close,
   .delete                       = pkey_remote_delete,
   .get_key_type                 = pkey_remote_get_key_type,
diff --git a/rpc_pkey.c b/rpc_pkey.c
index 294a3e5..1aee050 100644
--- a/rpc_pkey.c
+++ b/rpc_pkey.c
@@ -39,6 +39,7 @@
 #include "hal.h"
 #include "hal_internal.h"
 #include "asn1_internal.h"
+#include "hashsig.h"
 
 #ifndef HAL_STATIC_PKEY_STATE_BLOCKS
 #define HAL_STATIC_PKEY_STATE_BLOCKS 0
@@ -524,6 +525,68 @@ static hal_error_t pkey_local_generate_ec(const hal_client_handle_t client,
 }
 
 /*
+ * Generate a new hash-tree key with supplied name, return a key handle.
+ */
+
+static hal_error_t pkey_local_generate_hashsig(const hal_client_handle_t client,
+                                               const hal_session_handle_t session,
+                                               hal_pkey_handle_t *pkey,
+                                               hal_uuid_t *name,
+                                               const size_t hss_levels,
+                                               const lms_algorithm_t lms_type,
+                                               const lmots_algorithm_t lmots_type,
+                                               const hal_key_flags_t flags)
+{
+  assert(pkey != NULL && name != NULL);
+
+  hal_hashsig_key_t *key = NULL;
+  hal_pkey_slot_t *slot;
+  hal_error_t err;
+
+  if ((err = check_writable(client, flags)) != HAL_OK)
+    return err;
+
+  if ((slot = alloc_slot(flags)) == NULL)
+    return HAL_ERROR_NO_KEY_SLOTS_AVAILABLE;
+
+  if ((err = hal_uuid_gen(&slot->name)) != HAL_OK)
+    return err;
+
+  slot->client  = client;
+  slot->session = session;
+  slot->type    = HAL_KEY_TYPE_HASHSIG_PRIVATE,
+  slot->curve   = HAL_CURVE_NONE;
+  slot->flags   = flags;
+
+  if ((err = hal_hashsig_key_gen(NULL, &key, hss_levels, lms_type, lmots_type)) != HAL_OK) {
+    slot->type = HAL_KEY_TYPE_NONE;
+    return err;
+  }
+
+  uint8_t der[hal_hashsig_private_key_to_der_len(key)];
+  size_t der_len;
+
+  if ((err = hal_hashsig_private_key_to_der(key, der, &der_len, sizeof(der))) == HAL_OK)
+    err = hal_ks_store(ks_from_flags(flags), slot, der, der_len);
+
+  /* There's nothing sensitive in the top-level private key, but we wipe
+   * the der anyway, for symmetry with other key types. The actual key buf
+   * is allocated internally and stays in memory, because everything else
+   * is linked off of it.
+   */
+  memset(der, 0, sizeof(der));
+
+  if (err != HAL_OK) {
+    slot->type = HAL_KEY_TYPE_NONE;
+    return err;
+  }
+
+  *pkey = slot->pkey;
+  *name = slot->name;
+  return HAL_OK;
+}
+
+/*
  * Discard key handle, leaving key intact.
  */
 
@@ -542,6 +605,7 @@ static hal_error_t pkey_local_close(const hal_pkey_handle_t pkey)
 /*
  * Delete a key from the store, given its key handle.
  */
+static hal_error_t pkey_local_get_key_type(const hal_pkey_handle_t pkey, hal_key_type_t *type);
 
 static hal_error_t pkey_local_delete(const hal_pkey_handle_t pkey)
 {
@@ -555,6 +619,21 @@ static hal_error_t pkey_local_delete(const hal_pkey_handle_t pkey)
   if ((err = check_writable(slot->client, slot->flags)) != HAL_OK)
     return err;
 
+  hal_key_type_t key_type;
+  if ((err = pkey_local_get_key_type(pkey, &key_type)) != HAL_OK)
+      return err;
+
+  if (key_type == HAL_KEY_TYPE_HASHSIG_PRIVATE) {
+    hal_hashsig_key_t *key;
+    uint8_t keybuf[hal_hashsig_key_t_size];
+    uint8_t der[HAL_KS_WRAPPED_KEYSIZE];
+    size_t der_len;
+    if ((err = ks_fetch_from_flags(slot, der, &der_len, sizeof(der))) != HAL_OK ||
+        (err = hal_hashsig_private_key_from_der(&key, keybuf, sizeof(keybuf), der, der_len)) != HAL_OK ||
+        (err = hal_hashsig_key_delete(key)) != HAL_OK)
+      return err;
+  }
+
   err = hal_ks_delete(ks_from_flags(slot->flags), slot);
 
   if (err == HAL_OK || err == HAL_ERROR_KEY_NOT_FOUND)
@@ -636,9 +715,15 @@ static size_t pkey_local_get_public_key_len(const hal_pkey_handle_t pkey)
 
   size_t result = 0;
 
-  uint8_t keybuf[hal_rsa_key_t_size > hal_ecdsa_key_t_size ? hal_rsa_key_t_size : hal_ecdsa_key_t_size];
-  hal_rsa_key_t   *rsa_key   = NULL;
-  hal_ecdsa_key_t *ecdsa_key = NULL;
+#ifndef max
+#define max(a, b) ((a) >= (b) ? (a) : (b))
+#endif
+  size_t keybuf_size = max(hal_rsa_key_t_size, hal_ecdsa_key_t_size);
+  keybuf_size = max(keybuf_size, hal_hashsig_key_t_size);
+  uint8_t keybuf[keybuf_size];
+  hal_rsa_key_t     *rsa_key   = NULL;
+  hal_ecdsa_key_t   *ecdsa_key = NULL;
+  hal_hashsig_key_t *hashsig_key = NULL;
   uint8_t der[HAL_KS_WRAPPED_KEYSIZE];
   size_t der_len;
   hal_error_t err;
@@ -648,6 +733,7 @@ static size_t pkey_local_get_public_key_len(const hal_pkey_handle_t pkey)
 
     case HAL_KEY_TYPE_RSA_PUBLIC:
     case HAL_KEY_TYPE_EC_PUBLIC:
+    case HAL_KEY_TYPE_HASHSIG_PUBLIC:
       result = der_len;
       break;
 
@@ -661,6 +747,11 @@ static size_t pkey_local_get_public_key_len(const hal_pkey_handle_t pkey)
         result = hal_ecdsa_public_key_to_der_len(ecdsa_key);
       break;
 
+    case HAL_KEY_TYPE_HASHSIG_PRIVATE:
+      if (hal_hashsig_private_key_from_der(&hashsig_key, keybuf, sizeof(keybuf), der, der_len) == HAL_OK)
+        result = hal_hashsig_public_key_to_der_len(hashsig_key);
+      break;
+
     default:
       break;
     }
@@ -684,10 +775,12 @@ static hal_error_t pkey_local_get_public_key(const hal_pkey_handle_t pkey,
   if (slot == NULL)
     return HAL_ERROR_KEY_NOT_FOUND;
 
-  uint8_t keybuf[hal_rsa_key_t_size > hal_ecdsa_key_t_size
-                 ? hal_rsa_key_t_size : hal_ecdsa_key_t_size];
-  hal_rsa_key_t   *rsa_key   = NULL;
-  hal_ecdsa_key_t *ecdsa_key = NULL;
+  size_t keybuf_size = max(hal_rsa_key_t_size, hal_ecdsa_key_t_size);
+  keybuf_size = max(keybuf_size, hal_hashsig_key_t_size);
+  uint8_t keybuf[keybuf_size];
+  hal_rsa_key_t     *rsa_key   = NULL;
+  hal_ecdsa_key_t   *ecdsa_key = NULL;
+  hal_hashsig_key_t *hashsig_key = NULL;
   uint8_t buf[HAL_KS_WRAPPED_KEYSIZE];
   size_t buf_len;
   hal_error_t err;
@@ -697,6 +790,7 @@ static hal_error_t pkey_local_get_public_key(const hal_pkey_handle_t pkey,
 
     case HAL_KEY_TYPE_RSA_PUBLIC:
     case HAL_KEY_TYPE_EC_PUBLIC:
+    case HAL_KEY_TYPE_HASHSIG_PUBLIC:
       if (der_len != NULL)
         *der_len = buf_len;
       if (der != NULL && der_max < buf_len)
@@ -715,6 +809,11 @@ static hal_error_t pkey_local_get_public_key(const hal_pkey_handle_t pkey,
         err = hal_ecdsa_public_key_to_der(ecdsa_key, der, der_len, der_max);
       break;
 
+    case HAL_KEY_TYPE_HASHSIG_PRIVATE:
+      if ((err = hal_hashsig_private_key_from_der(&hashsig_key, keybuf, sizeof(keybuf), buf, buf_len)) == HAL_OK)
+        err = hal_hashsig_public_key_to_der(hashsig_key, der, der_len, der_max);
+      break;
+
     default:
       err = HAL_ERROR_UNSUPPORTED_KEY;
       break;
@@ -815,6 +914,44 @@ static hal_error_t pkey_local_sign_ecdsa(hal_pkey_slot_t *slot,
   return HAL_OK;
 }
 
+static hal_error_t pkey_local_sign_hashsig(hal_pkey_slot_t *slot,
+                                           uint8_t *keybuf, const size_t keybuf_len,
+                                           const uint8_t * const der, const size_t der_len,
+                                           const hal_hash_handle_t hash,
+                                           const uint8_t * input, size_t input_len,
+                                           uint8_t * signature, size_t *signature_len, const size_t signature_max)
+{
+  hal_hashsig_key_t *key = NULL;
+  hal_error_t err;
+
+  assert(signature != NULL && signature_len != NULL);
+  assert((hash.handle == HAL_HANDLE_NONE) != (input == NULL || input_len == 0));
+
+  if ((err = hal_hashsig_private_key_from_der(&key, keybuf, keybuf_len, der, der_len)) != HAL_OK)
+    return err;
+
+  if (input == NULL || input_len == 0) {
+    hal_digest_algorithm_t alg;
+
+    if ((err = hal_rpc_hash_get_algorithm(hash, &alg))          != HAL_OK ||
+        (err = hal_rpc_hash_get_digest_length(alg, &input_len)) != HAL_OK)
+      return err;
+
+    if (input_len > signature_max)
+      return HAL_ERROR_RESULT_TOO_LONG;
+
+    if ((err = hal_rpc_hash_finalize(hash, signature, input_len)) != HAL_OK)
+      return err;
+
+    input = signature;
+  }
+
+  if ((err = hal_hashsig_sign(NULL, key, input, input_len, signature, signature_len, signature_max)) != HAL_OK)
+    return err;
+
+  return HAL_OK;
+}
+
 static hal_error_t pkey_local_sign(const hal_pkey_handle_t pkey,
                                    const hal_hash_handle_t hash,
                                    const uint8_t * const input,  const size_t input_len,
@@ -831,13 +968,20 @@ static hal_error_t pkey_local_sign(const hal_pkey_handle_t pkey,
                         const hal_hash_handle_t hash,
                         const uint8_t * const input,  const size_t input_len,
                         uint8_t * signature, size_t *signature_len, const size_t signature_max);
+  size_t keybuf_size;
 
   switch (slot->type) {
   case HAL_KEY_TYPE_RSA_PRIVATE:
     signer = pkey_local_sign_rsa;
+    keybuf_size = hal_rsa_key_t_size;
     break;
   case HAL_KEY_TYPE_EC_PRIVATE:
     signer = pkey_local_sign_ecdsa;
+    keybuf_size = hal_ecdsa_key_t_size;
+    break;
+  case HAL_KEY_TYPE_HASHSIG_PRIVATE:
+    signer = pkey_local_sign_hashsig;
+    keybuf_size = hal_hashsig_key_t_size;
     break;
   default:
     return HAL_ERROR_UNSUPPORTED_KEY;
@@ -846,8 +990,7 @@ static hal_error_t pkey_local_sign(const hal_pkey_handle_t pkey,
   if ((slot->flags & HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE) == 0)
     return HAL_ERROR_FORBIDDEN;
 
-  uint8_t keybuf[hal_rsa_key_t_size > hal_ecdsa_key_t_size
-                 ? hal_rsa_key_t_size : hal_ecdsa_key_t_size];
+  uint8_t keybuf[keybuf_size];
   uint8_t der[HAL_KS_WRAPPED_KEYSIZE];
   size_t der_len;
   hal_error_t err;
@@ -960,6 +1103,40 @@ static hal_error_t pkey_local_verify_ecdsa(uint8_t *keybuf, const size_t keybuf_
   return HAL_OK;
 }
 
+static hal_error_t pkey_local_verify_hashsig(uint8_t *keybuf, const size_t keybuf_len, const hal_key_type_t type,
+                                           const uint8_t * const der, const size_t der_len,
+                                           const hal_hash_handle_t hash,
+                                           const uint8_t * input, size_t input_len,
+                                           const uint8_t * const signature, const size_t signature_len)
+{
+  uint8_t digest[signature_len];
+  hal_hashsig_key_t *key = NULL;
+  hal_error_t err;
+
+  assert(signature != NULL && signature_len > 0);
+  assert((hash.handle == HAL_HANDLE_NONE) != (input == NULL || input_len == 0));
+
+  if ((err = hal_hashsig_public_key_from_der(&key, keybuf, keybuf_len, der, der_len)) != HAL_OK)
+    return err;
+
+  if (input == NULL || input_len == 0) {
+    hal_digest_algorithm_t alg;
+
+    // ???
+    if ((err = hal_rpc_hash_get_algorithm(hash, &alg))              != HAL_OK ||
+        (err = hal_rpc_hash_get_digest_length(alg, &input_len))     != HAL_OK ||
+        (err = hal_rpc_hash_finalize(hash, digest, sizeof(digest))) != HAL_OK)
+      return err;
+
+    input = digest;
+  }
+
+  if ((err = hal_hashsig_verify(NULL, key, input, input_len, signature, signature_len)) != HAL_OK)
+    return err;
+
+  return HAL_OK;
+}
+
 static hal_error_t pkey_local_verify(const hal_pkey_handle_t pkey,
                                      const hal_hash_handle_t hash,
                                      const uint8_t * const input, const size_t input_len,
@@ -975,15 +1152,22 @@ static hal_error_t pkey_local_verify(const hal_pkey_handle_t pkey,
                           const hal_hash_handle_t hash,
                           const uint8_t * const input,  const size_t input_len,
                           const uint8_t * const signature, const size_t signature_len);
+  size_t keybuf_size;
 
   switch (slot->type) {
   case HAL_KEY_TYPE_RSA_PRIVATE:
   case HAL_KEY_TYPE_RSA_PUBLIC:
     verifier = pkey_local_verify_rsa;
+    keybuf_size = hal_rsa_key_t_size;
     break;
   case HAL_KEY_TYPE_EC_PRIVATE:
   case HAL_KEY_TYPE_EC_PUBLIC:
     verifier = pkey_local_verify_ecdsa;
+    keybuf_size = hal_ecdsa_key_t_size;
+    break;
+  case HAL_KEY_TYPE_HASHSIG_PUBLIC:
+    verifier = pkey_local_verify_hashsig;
+    keybuf_size = hal_hashsig_key_t_size;
     break;
   default:
     return HAL_ERROR_UNSUPPORTED_KEY;
@@ -992,8 +1176,7 @@ static hal_error_t pkey_local_verify(const hal_pkey_handle_t pkey,
   if ((slot->flags & HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE) == 0)
     return HAL_ERROR_FORBIDDEN;
 
-  uint8_t keybuf[hal_rsa_key_t_size > hal_ecdsa_key_t_size
-                 ? hal_rsa_key_t_size : hal_ecdsa_key_t_size];
+  uint8_t keybuf[keybuf_size];
   uint8_t der[HAL_KS_WRAPPED_KEYSIZE];
   size_t der_len;
   hal_error_t err;
@@ -1317,6 +1500,7 @@ const hal_rpc_pkey_dispatch_t hal_rpc_local_pkey_dispatch = {
   .open                 = pkey_local_open,
   .generate_rsa         = pkey_local_generate_rsa,
   .generate_ec          = pkey_local_generate_ec,
+  .generate_hashsig     = pkey_local_generate_hashsig,
   .close                = pkey_local_close,
   .delete               = pkey_local_delete,
   .get_key_type         = pkey_local_get_key_type,
diff --git a/rpc_server.c b/rpc_server.c
index 3a23f4d..5a06e37 100644
--- a/rpc_server.c
+++ b/rpc_server.c
@@ -35,6 +35,7 @@
 #include "hal.h"
 #include "hal_internal.h"
 #include "xdr_internal.h"
+#include "hashsig.h"
 
 /*
  * RPC calls.
@@ -359,6 +360,36 @@ static hal_error_t pkey_generate_ec(const uint8_t **iptr, const uint8_t * const
     return err;
 }
 
+static hal_error_t pkey_generate_hashsig(const uint8_t **iptr, const uint8_t * const ilimit,
+                                         uint8_t **optr, const uint8_t * const olimit)
+{
+    hal_client_handle_t client;
+    hal_session_handle_t session;
+    hal_pkey_handle_t pkey;
+    hal_uuid_t name;
+    uint32_t hss_levels;
+    uint32_t lms_type;
+    uint32_t lmots_type;
+    hal_key_flags_t flags;
+    uint8_t *optr_orig = *optr;
+    hal_error_t err;
+
+    check(hal_xdr_decode_int(iptr, ilimit, &client.handle));
+    check(hal_xdr_decode_int(iptr, ilimit, &session.handle));
+    check(hal_xdr_decode_int(iptr, ilimit, &hss_levels));
+    check(hal_xdr_decode_int(iptr, ilimit, &lms_type));
+    check(hal_xdr_decode_int(iptr, ilimit, &lmots_type));
+    check(hal_xdr_decode_int(iptr, ilimit, &flags));
+
+    check(hal_rpc_pkey_generate_hashsig(client, session, &pkey, &name, hss_levels, lms_type, lmots_type, flags));
+
+    if ((err = hal_xdr_encode_int(optr, olimit, pkey.handle)) != HAL_OK ||
+        (err = hal_xdr_encode_variable_opaque(optr, olimit, name.uuid, sizeof(name.uuid))) != HAL_OK)
+        *optr = optr_orig;
+
+    return err;
+}
+
 static hal_error_t pkey_close(const uint8_t **iptr, const uint8_t * const ilimit,
                               uint8_t **optr, const uint8_t * const olimit)
 {
@@ -794,6 +825,9 @@ hal_error_t hal_rpc_server_dispatch(const uint8_t * const ibuf, const size_t ile
     case RPC_FUNC_PKEY_GENERATE_EC:
         handler = pkey_generate_ec;
         break;
+    case RPC_FUNC_PKEY_GENERATE_HASHSIG:
+        handler = pkey_generate_hashsig;
+        break;
     case RPC_FUNC_PKEY_CLOSE:
         handler = pkey_close;
         break;
diff --git a/tests/Makefile b/tests/Makefile
index d64728f..d186000 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -45,7 +45,7 @@ CFLAGS		?= -g3 -Wall -fPIC -std=c99 -I${LIBHAL_SRC} -I${LIBTFM_BLD}
 
 CORE_TESTS	= test-aes-key-wrap test-hash test-pbkdf2 test-ecdsa test-bus test-trng test-rsa test-mkmif
 SERVER_TESTS	= test-rpc_server
-CLIENT_TESTS	= test-rpc_hash test-rpc_pkey test-rpc_get_version test-rpc_get_random test-rpc_login test-rpc_bighash test-xdr
+CLIENT_TESTS	= test-rpc_hash test-rpc_pkey test-rpc_get_version test-rpc_get_random test-rpc_login test-rpc_bighash test-xdr test-rpc_hashsig
 
 ALL_TESTS	= ${CORE_TESTS} ${SERVER_TESTS} ${CLIENT_TESTS}
 
@@ -78,3 +78,5 @@ ${BIN}: %: %.o ${LIBS}
 
 %.o: %.c ${LBHAL_SRC}/*.h ${LIBTFM_BLD}/tfm.h
 	${CC} ${CFLAGS} -c -o $@ $<
+
+test-rpc_hashsig.o: test-hashsig.h
diff --git a/tests/test-hashsig.h b/tests/test-hashsig.h
new file mode 100644
index 0000000..b76f9b1
--- /dev/null
+++ b/tests/test-hashsig.h
@@ -0,0 +1,392 @@
+/*
+ * draft-mcgrew Test Case 1
+ */
+
+/* Test Case 1 Public Key */
+
+static uint8_t tc1_key[] = {
+    0x00, 0x00, 0x00, 0x02,
+    0x00, 0x00, 0x00, 0x05,
+    0x00, 0x00, 0x00, 0x04,
+    0x61, 0xa5, 0xd5, 0x7d, 0x37, 0xf5, 0xe4, 0x6b,
+    0xfb, 0x75, 0x20, 0x80, 0x6b, 0x07, 0xa1, 0xb8,
+    0x50, 0x65, 0x0e, 0x3b, 0x31, 0xfe, 0x4a, 0x77,
+    0x3e, 0xa2, 0x9a, 0x07, 0xf0, 0x9c, 0xf2, 0xea,
+    0x30, 0xe5, 0x79, 0xf0, 0xdf, 0x58, 0xef, 0x8e,
+    0x29, 0x8d, 0xa0, 0x43, 0x4c, 0xb2, 0xb8, 0x78,
+};
+
+/* Test Case 1 Message */
+
+static uint8_t tc1_msg[] = {
+    0x54, 0x68, 0x65, 0x20, 0x70, 0x6f, 0x77, 0x65,
+    0x72, 0x73, 0x20, 0x6e, 0x6f, 0x74, 0x20, 0x64,
+    0x65, 0x6c, 0x65, 0x67, 0x61, 0x74, 0x65, 0x64,
+    0x20, 0x74, 0x6f, 0x20, 0x74, 0x68, 0x65, 0x20,
+    0x55, 0x6e, 0x69, 0x74, 0x65, 0x64, 0x20, 0x53,
+    0x74, 0x61, 0x74, 0x65, 0x73, 0x20, 0x62, 0x79,
+    0x20, 0x74, 0x68, 0x65, 0x20, 0x43, 0x6f, 0x6e,
+    0x73, 0x74, 0x69, 0x74, 0x75, 0x74, 0x69, 0x6f,
+    0x6e, 0x2c, 0x20, 0x6e, 0x6f, 0x72, 0x20, 0x70,
+    0x72, 0x6f, 0x68, 0x69, 0x62, 0x69, 0x74, 0x65,
+    0x64, 0x20, 0x62, 0x79, 0x20, 0x69, 0x74, 0x20,
+    0x74, 0x6f, 0x20, 0x74, 0x68, 0x65, 0x20, 0x53,
+    0x74, 0x61, 0x74, 0x65, 0x73, 0x2c, 0x20, 0x61,
+    0x72, 0x65, 0x20, 0x72, 0x65, 0x73, 0x65, 0x72,
+    0x76, 0x65, 0x64, 0x20, 0x74, 0x6f, 0x20, 0x74,
+    0x68, 0x65, 0x20, 0x53, 0x74, 0x61, 0x74, 0x65,
+    0x73, 0x20, 0x72, 0x65, 0x73, 0x70, 0x65, 0x63,
+    0x74, 0x69, 0x76, 0x65, 0x6c, 0x79, 0x2c, 0x20,
+    0x6f, 0x72, 0x20, 0x74, 0x6f, 0x20, 0x74, 0x68,
+    0x65, 0x20, 0x70, 0x65, 0x6f, 0x70, 0x6c, 0x65,
+    0x2e, 0x0a,
+};
+
+/* Test Case 1 Signature */
+
+static uint8_t tc1_sig[] = {
+    0x00, 0x00, 0x00, 0x01,
+    0x00, 0x00, 0x00, 0x05,
+    0x00, 0x00, 0x00, 0x04,
+    0xd3, 0x2b, 0x56, 0x67, 0x1d, 0x7e, 0xb9, 0x88,
+    0x33, 0xc4, 0x9b, 0x43, 0x3c, 0x27, 0x25, 0x86,
+    0xbc, 0x4a, 0x1c, 0x8a, 0x89, 0x70, 0x52, 0x8f,
+    0xfa, 0x04, 0xb9, 0x66, 0xf9, 0x42, 0x6e, 0xb9,
+    0x96, 0x5a, 0x25, 0xbf, 0xd3, 0x7f, 0x19, 0x6b,
+    0x90, 0x73, 0xf3, 0xd4, 0xa2, 0x32, 0xfe, 0xb6,
+    0x91, 0x28, 0xec, 0x45, 0x14, 0x6f, 0x86, 0x29,
+    0x2f, 0x9d, 0xff, 0x96, 0x10, 0xa7, 0xbf, 0x95,
+    0xa6, 0x4c, 0x7f, 0x60, 0xf6, 0x26, 0x1a, 0x62,
+    0x04, 0x3f, 0x86, 0xc7, 0x03, 0x24, 0xb7, 0x70,
+    0x7f, 0x5b, 0x4a, 0x8a, 0x6e, 0x19, 0xc1, 0x14,
+    0xc7, 0xbe, 0x86, 0x6d, 0x48, 0x87, 0x78, 0xa0,
+    0xe0, 0x5f, 0xd5, 0xc6, 0x50, 0x9a, 0x6e, 0x61,
+    0xd5, 0x59, 0xcf, 0x1a, 0x77, 0xa9, 0x70, 0xde,
+    0x92, 0x7d, 0x60, 0xc7, 0x0d, 0x3d, 0xe3, 0x1a,
+    0x7f, 0xa0, 0x10, 0x09, 0x94, 0xe1, 0x62, 0xa2,
+    0x58, 0x2e, 0x8f, 0xf1, 0xb1, 0x0c, 0xd9, 0x9d,
+    0x4e, 0x8e, 0x41, 0x3e, 0xf4, 0x69, 0x55, 0x9f,
+    0x7d, 0x7e, 0xd1, 0x2c, 0x83, 0x83, 0x42, 0xf9,
+    0xb9, 0xc9, 0x6b, 0x83, 0xa4, 0x94, 0x3d, 0x16,
+    0x81, 0xd8, 0x4b, 0x15, 0x35, 0x7f, 0xf4, 0x8c,
+    0xa5, 0x79, 0xf1, 0x9f, 0x5e, 0x71, 0xf1, 0x84,
+    0x66, 0xf2, 0xbb, 0xef, 0x4b, 0xf6, 0x60, 0xc2,
+    0x51, 0x8e, 0xb2, 0x0d, 0xe2, 0xf6, 0x6e, 0x3b,
+    0x14, 0x78, 0x42, 0x69, 0xd7, 0xd8, 0x76, 0xf5,
+    0xd3, 0x5d, 0x3f, 0xbf, 0xc7, 0x03, 0x9a, 0x46,
+    0x2c, 0x71, 0x6b, 0xb9, 0xf6, 0x89, 0x1a, 0x7f,
+    0x41, 0xad, 0x13, 0x3e, 0x9e, 0x1f, 0x6d, 0x95,
+    0x60, 0xb9, 0x60, 0xe7, 0x77, 0x7c, 0x52, 0xf0,
+    0x60, 0x49, 0x2f, 0x2d, 0x7c, 0x66, 0x0e, 0x14,
+    0x71, 0xe0, 0x7e, 0x72, 0x65, 0x55, 0x62, 0x03,
+    0x5a, 0xbc, 0x9a, 0x70, 0x1b, 0x47, 0x3e, 0xcb,
+    0xc3, 0x94, 0x3c, 0x6b, 0x9c, 0x4f, 0x24, 0x05,
+    0xa3, 0xcb, 0x8b, 0xf8, 0xa6, 0x91, 0xca, 0x51,
+    0xd3, 0xf6, 0xad, 0x2f, 0x42, 0x8b, 0xab, 0x6f,
+    0x3a, 0x30, 0xf5, 0x5d, 0xd9, 0x62, 0x55, 0x63,
+    0xf0, 0xa7, 0x5e, 0xe3, 0x90, 0xe3, 0x85, 0xe3,
+    0xae, 0x0b, 0x90, 0x69, 0x61, 0xec, 0xf4, 0x1a,
+    0xe0, 0x73, 0xa0, 0x59, 0x0c, 0x2e, 0xb6, 0x20,
+    0x4f, 0x44, 0x83, 0x1c, 0x26, 0xdd, 0x76, 0x8c,
+    0x35, 0xb1, 0x67, 0xb2, 0x8c, 0xe8, 0xdc, 0x98,
+    0x8a, 0x37, 0x48, 0x25, 0x52, 0x30, 0xce, 0xf9,
+    0x9e, 0xbf, 0x14, 0xe7, 0x30, 0x63, 0x2f, 0x27,
+    0x41, 0x44, 0x89, 0x80, 0x8a, 0xfa, 0xb1, 0xd1,
+    0xe7, 0x83, 0xed, 0x04, 0x51, 0x6d, 0xe0, 0x12,
+    0x49, 0x86, 0x82, 0x21, 0x2b, 0x07, 0x81, 0x05,
+    0x79, 0xb2, 0x50, 0x36, 0x59, 0x41, 0xbc, 0xc9,
+    0x81, 0x42, 0xda, 0x13, 0x60, 0x9e, 0x97, 0x68,
+    0xaa, 0xf6, 0x5d, 0xe7, 0x62, 0x0d, 0xab, 0xec,
+    0x29, 0xeb, 0x82, 0xa1, 0x7f, 0xde, 0x35, 0xaf,
+    0x15, 0xad, 0x23, 0x8c, 0x73, 0xf8, 0x1b, 0xdb,
+    0x8d, 0xec, 0x2f, 0xc0, 0xe7, 0xf9, 0x32, 0x70,
+    0x10, 0x99, 0x76, 0x2b, 0x37, 0xf4, 0x3c, 0x4a,
+    0x3c, 0x20, 0x01, 0x0a, 0x3d, 0x72, 0xe2, 0xf6,
+    0x06, 0xbe, 0x10, 0x8d, 0x31, 0x0e, 0x63, 0x9f,
+    0x09, 0xce, 0x72, 0x86, 0x80, 0x0d, 0x9e, 0xf8,
+    0xa1, 0xa4, 0x02, 0x81, 0xcc, 0x5a, 0x7e, 0xa9,
+    0x8d, 0x2a, 0xdc, 0x7c, 0x74, 0x00, 0xc2, 0xfe,
+    0x5a, 0x10, 0x15, 0x52, 0xdf, 0x4e, 0x3c, 0xcc,
+    0xfd, 0x0c, 0xbf, 0x2d, 0xdf, 0x5d, 0xc6, 0x77,
+    0x9c, 0xbb, 0xc6, 0x8f, 0xee, 0x0c, 0x3e, 0xfe,
+    0x4e, 0xc2, 0x2b, 0x83, 0xa2, 0xca, 0xa3, 0xe4,
+    0x8e, 0x08, 0x09, 0xa0, 0xa7, 0x50, 0xb7, 0x3c,
+    0xcd, 0xcf, 0x3c, 0x79, 0xe6, 0x58, 0x0c, 0x15,
+    0x4f, 0x8a, 0x58, 0xf7, 0xf2, 0x43, 0x35, 0xee,
+    0xc5, 0xc5, 0xeb, 0x5e, 0x0c, 0xf0, 0x1d, 0xcf,
+    0x44, 0x39, 0x42, 0x40, 0x95, 0xfc, 0xeb, 0x07,
+    0x7f, 0x66, 0xde, 0xd5, 0xbe, 0xc7, 0x3b, 0x27,
+    0xc5, 0xb9, 0xf6, 0x4a, 0x2a, 0x9a, 0xf2, 0xf0,
+    0x7c, 0x05, 0xe9, 0x9e, 0x5c, 0xf8, 0x0f, 0x00,
+    0x25, 0x2e, 0x39, 0xdb, 0x32, 0xf6, 0xc1, 0x96,
+    0x74, 0xf1, 0x90, 0xc9, 0xfb, 0xc5, 0x06, 0xd8,
+    0x26, 0x85, 0x77, 0x13, 0xaf, 0xd2, 0xca, 0x6b,
+    0xb8, 0x5c, 0xd8, 0xc1, 0x07, 0x34, 0x75, 0x52,
+    0xf3, 0x05, 0x75, 0xa5, 0x41, 0x78, 0x16, 0xab,
+    0x4d, 0xb3, 0xf6, 0x03, 0xf2, 0xdf, 0x56, 0xfb,
+    0xc4, 0x13, 0xe7, 0xd0, 0xac, 0xd8, 0xbd, 0xd8,
+    0x13, 0x52, 0xb2, 0x47, 0x1f, 0xc1, 0xbc, 0x4f,
+    0x1e, 0xf2, 0x96, 0xfe, 0xa1, 0x22, 0x04, 0x03,
+    0x46, 0x6b, 0x1a, 0xfe, 0x78, 0xb9, 0x4f, 0x7e,
+    0xcf, 0x7c, 0xc6, 0x2f, 0xb9, 0x2b, 0xe1, 0x4f,
+    0x18, 0xc2, 0x19, 0x23, 0x84, 0xeb, 0xce, 0xaf,
+    0x88, 0x01, 0xaf, 0xdf, 0x94, 0x7f, 0x69, 0x8c,
+    0xe9, 0xc6, 0xce, 0xb6, 0x96, 0xed, 0x70, 0xe9,
+    0xe8, 0x7b, 0x01, 0x44, 0x41, 0x7e, 0x8d, 0x7b,
+    0xaf, 0x25, 0xeb, 0x5f, 0x70, 0xf0, 0x9f, 0x01,
+    0x6f, 0xc9, 0x25, 0xb4, 0xdb, 0x04, 0x8a, 0xb8,
+    0xd8, 0xcb, 0x2a, 0x66, 0x1c, 0xe3, 0xb5, 0x7a,
+    0xda, 0x67, 0x57, 0x1f, 0x5d, 0xd5, 0x46, 0xfc,
+    0x22, 0xcb, 0x1f, 0x97, 0xe0, 0xeb, 0xd1, 0xa6,
+    0x59, 0x26, 0xb1, 0x23, 0x4f, 0xd0, 0x4f, 0x17,
+    0x1c, 0xf4, 0x69, 0xc7, 0x6b, 0x88, 0x4c, 0xf3,
+    0x11, 0x5c, 0xce, 0x6f, 0x79, 0x2c, 0xc8, 0x4e,
+    0x36, 0xda, 0x58, 0x96, 0x0c, 0x5f, 0x1d, 0x76,
+    0x0f, 0x32, 0xc1, 0x2f, 0xae, 0xf4, 0x77, 0xe9,
+    0x4c, 0x92, 0xeb, 0x75, 0x62, 0x5b, 0x6a, 0x37,
+    0x1e, 0xfc, 0x72, 0xd6, 0x0c, 0xa5, 0xe9, 0x08,
+    0xb3, 0xa7, 0xdd, 0x69, 0xfe, 0xf0, 0x24, 0x91,
+    0x50, 0xe3, 0xee, 0xbd, 0xfe, 0xd3, 0x9c, 0xbd,
+    0xc3, 0xce, 0x97, 0x04, 0x88, 0x2a, 0x20, 0x72,
+    0xc7, 0x5e, 0x13, 0x52, 0x7b, 0x7a, 0x58, 0x1a,
+    0x55, 0x61, 0x68, 0x78, 0x3d, 0xc1, 0xe9, 0x75,
+    0x45, 0xe3, 0x18, 0x65, 0xdd, 0xc4, 0x6b, 0x3c,
+    0x95, 0x78, 0x35, 0xda, 0x25, 0x2b, 0xb7, 0x32,
+    0x8d, 0x3e, 0xe2, 0x06, 0x24, 0x45, 0xdf, 0xb8,
+    0x5e, 0xf8, 0xc3, 0x5f, 0x8e, 0x1f, 0x33, 0x71,
+    0xaf, 0x34, 0x02, 0x3c, 0xef, 0x62, 0x6e, 0x0a,
+    0xf1, 0xe0, 0xbc, 0x01, 0x73, 0x51, 0xaa, 0xe2,
+    0xab, 0x8f, 0x5c, 0x61, 0x2e, 0xad, 0x0b, 0x72,
+    0x9a, 0x1d, 0x05, 0x9d, 0x02, 0xbf, 0xe1, 0x8e,
+    0xfa, 0x97, 0x1b, 0x73, 0x00, 0xe8, 0x82, 0x36,
+    0x0a, 0x93, 0xb0, 0x25, 0xff, 0x97, 0xe9, 0xe0,
+    0xee, 0xc0, 0xf3, 0xf3, 0xf1, 0x30, 0x39, 0xa1,
+    0x7f, 0x88, 0xb0, 0xcf, 0x80, 0x8f, 0x48, 0x84,
+    0x31, 0x60, 0x6c, 0xb1, 0x3f, 0x92, 0x41, 0xf4,
+    0x0f, 0x44, 0xe5, 0x37, 0xd3, 0x02, 0xc6, 0x4a,
+    0x4f, 0x1f, 0x4a, 0xb9, 0x49, 0xb9, 0xfe, 0xef,
+    0xad, 0xcb, 0x71, 0xab, 0x50, 0xef, 0x27, 0xd6,
+    0xd6, 0xca, 0x85, 0x10, 0xf1, 0x50, 0xc8, 0x5f,
+    0xb5, 0x25, 0xbf, 0x25, 0x70, 0x3d, 0xf7, 0x20,
+    0x9b, 0x60, 0x66, 0xf0, 0x9c, 0x37, 0x28, 0x0d,
+    0x59, 0x12, 0x8d, 0x2f, 0x0f, 0x63, 0x7c, 0x7d,
+    0x7d, 0x7f, 0xad, 0x4e, 0xd1, 0xc1, 0xea, 0x04,
+    0xe6, 0x28, 0xd2, 0x21, 0xe3, 0xd8, 0xdb, 0x77,
+    0xb7, 0xc8, 0x78, 0xc9, 0x41, 0x1c, 0xaf, 0xc5,
+    0x07, 0x1a, 0x34, 0xa0, 0x0f, 0x4c, 0xf0, 0x77,
+    0x38, 0x91, 0x27, 0x53, 0xdf, 0xce, 0x48, 0xf0,
+    0x75, 0x76, 0xf0, 0xd4, 0xf9, 0x4f, 0x42, 0xc6,
+    0xd7, 0x6f, 0x7c, 0xe9, 0x73, 0xe9, 0x36, 0x70,
+    0x95, 0xba, 0x7e, 0x9a, 0x36, 0x49, 0xb7, 0xf4,
+    0x61, 0xd9, 0xf9, 0xac, 0x13, 0x32, 0xa4, 0xd1,
+    0x04, 0x4c, 0x96, 0xae, 0xfe, 0xe6, 0x76, 0x76,
+    0x40, 0x1b, 0x64, 0x45, 0x7c, 0x54, 0xd6, 0x5f,
+    0xef, 0x65, 0x00, 0xc5, 0x9c, 0xdf, 0xb6, 0x9a,
+    0xf7, 0xb6, 0xdd, 0xdf, 0xcb, 0x0f, 0x08, 0x62,
+    0x78, 0xdd, 0x8a, 0xd0, 0x68, 0x60, 0x78, 0xdf,
+    0xb0, 0xf3, 0xf7, 0x9c, 0xd8, 0x93, 0xd3, 0x14,
+    0x16, 0x86, 0x48, 0x49, 0x98, 0x98, 0xfb, 0xc0,
+    0xce, 0xd5, 0xf9, 0x5b, 0x74, 0xe8, 0xff, 0x14,
+    0xd7, 0x35, 0xcd, 0xea, 0x96, 0x8b, 0xee, 0x74,
+    0x00, 0x00, 0x00, 0x05,
+    0xd8, 0xb8, 0x11, 0x2f, 0x92, 0x00, 0xa5, 0xe5,
+    0x0c, 0x4a, 0x26, 0x21, 0x65, 0xbd, 0x34, 0x2c,
+    0xd8, 0x00, 0xb8, 0x49, 0x68, 0x10, 0xbc, 0x71,
+    0x62, 0x77, 0x43, 0x5a, 0xc3, 0x76, 0x72, 0x8d,
+    0x12, 0x9a, 0xc6, 0xed, 0xa8, 0x39, 0xa6, 0xf3,
+    0x57, 0xb5, 0xa0, 0x43, 0x87, 0xc5, 0xce, 0x97,
+    0x38, 0x2a, 0x78, 0xf2, 0xa4, 0x37, 0x29, 0x17,
+    0xee, 0xfc, 0xbf, 0x93, 0xf6, 0x3b, 0xb5, 0x91,
+    0x12, 0xf5, 0xdb, 0xe4, 0x00, 0xbd, 0x49, 0xe4,
+    0x50, 0x1e, 0x85, 0x9f, 0x88, 0x5b, 0xf0, 0x73,
+    0x6e, 0x90, 0xa5, 0x09, 0xb3, 0x0a, 0x26, 0xbf,
+    0xac, 0x8c, 0x17, 0xb5, 0x99, 0x1c, 0x15, 0x7e,
+    0xb5, 0x97, 0x11, 0x15, 0xaa, 0x39, 0xef, 0xd8,
+    0xd5, 0x64, 0xa6, 0xb9, 0x02, 0x82, 0xc3, 0x16,
+    0x8a, 0xf2, 0xd3, 0x0e, 0xf8, 0x9d, 0x51, 0xbf,
+    0x14, 0x65, 0x45, 0x10, 0xa1, 0x2b, 0x8a, 0x14,
+    0x4c, 0xca, 0x18, 0x48, 0xcf, 0x7d, 0xa5, 0x9c,
+    0xc2, 0xb3, 0xd9, 0xd0, 0x69, 0x2d, 0xd2, 0xa2,
+    0x0b, 0xa3, 0x86, 0x34, 0x80, 0xe2, 0x5b, 0x1b,
+    0x85, 0xee, 0x86, 0x0c, 0x62, 0xbf, 0x51, 0x36,
+    0x00, 0x00, 0x00, 0x05,
+    0x00, 0x00, 0x00, 0x04,
+    0xd2, 0xf1, 0x4f, 0xf6, 0x34, 0x6a, 0xf9, 0x64,
+    0x56, 0x9f, 0x7d, 0x6c, 0xb8, 0x80, 0xa1, 0xb6,
+    0x6c, 0x50, 0x04, 0x91, 0x7d, 0xa6, 0xea, 0xfe,
+    0x4d, 0x9e, 0xf6, 0xc6, 0x40, 0x7b, 0x3d, 0xb0,
+    0xe5, 0x48, 0x5b, 0x12, 0x2d, 0x9e, 0xbe, 0x15,
+    0xcd, 0xa9, 0x3c, 0xfe, 0xc5, 0x82, 0xd7, 0xab,
+    0x00, 0x00, 0x00, 0x0a,
+    0x00, 0x00, 0x00, 0x04,
+    0x07, 0x03, 0xc4, 0x91, 0xe7, 0x55, 0x8b, 0x35,
+    0x01, 0x1e, 0xce, 0x35, 0x92, 0xea, 0xa5, 0xda,
+    0x4d, 0x91, 0x87, 0x86, 0x77, 0x12, 0x33, 0xe8,
+    0x35, 0x3b, 0xc4, 0xf6, 0x23, 0x23, 0x18, 0x5c,
+    0x95, 0xca, 0xe0, 0x5b, 0x89, 0x9e, 0x35, 0xdf,
+    0xfd, 0x71, 0x70, 0x54, 0x70, 0x62, 0x09, 0x98,
+    0x8e, 0xbf, 0xdf, 0x6e, 0x37, 0x96, 0x0b, 0xb5,
+    0xc3, 0x8d, 0x76, 0x57, 0xe8, 0xbf, 0xfe, 0xef,
+    0x9b, 0xc0, 0x42, 0xda, 0x4b, 0x45, 0x25, 0x65,
+    0x04, 0x85, 0xc6, 0x6d, 0x0c, 0xe1, 0x9b, 0x31,
+    0x75, 0x87, 0xc6, 0xba, 0x4b, 0xff, 0xcc, 0x42,
+    0x8e, 0x25, 0xd0, 0x89, 0x31, 0xe7, 0x2d, 0xfb,
+    0x6a, 0x12, 0x0c, 0x56, 0x12, 0x34, 0x42, 0x58,
+    0xb8, 0x5e, 0xfd, 0xb7, 0xdb, 0x1d, 0xb9, 0xe1,
+    0x86, 0x5a, 0x73, 0xca, 0xf9, 0x65, 0x57, 0xeb,
+    0x39, 0xed, 0x3e, 0x3f, 0x42, 0x69, 0x33, 0xac,
+    0x9e, 0xed, 0xdb, 0x03, 0xa1, 0xd2, 0x37, 0x4a,
+    0xf7, 0xbf, 0x77, 0x18, 0x55, 0x77, 0x45, 0x62,
+    0x37, 0xf9, 0xde, 0x2d, 0x60, 0x11, 0x3c, 0x23,
+    0xf8, 0x46, 0xdf, 0x26, 0xfa, 0x94, 0x20, 0x08,
+    0xa6, 0x98, 0x99, 0x4c, 0x08, 0x27, 0xd9, 0x0e,
+    0x86, 0xd4, 0x3e, 0x0d, 0xf7, 0xf4, 0xbf, 0xcd,
+    0xb0, 0x9b, 0x86, 0xa3, 0x73, 0xb9, 0x82, 0x88,
+    0xb7, 0x09, 0x4a, 0xd8, 0x1a, 0x01, 0x85, 0xac,
+    0x10, 0x0e, 0x4f, 0x2c, 0x5f, 0xc3, 0x8c, 0x00,
+    0x3c, 0x1a, 0xb6, 0xfe, 0xa4, 0x79, 0xeb, 0x2f,
+    0x5e, 0xbe, 0x48, 0xf5, 0x84, 0xd7, 0x15, 0x9b,
+    0x8a, 0xda, 0x03, 0x58, 0x6e, 0x65, 0xad, 0x9c,
+    0x96, 0x9f, 0x6a, 0xec, 0xbf, 0xe4, 0x4c, 0xf3,
+    0x56, 0x88, 0x8a, 0x7b, 0x15, 0xa3, 0xff, 0x07,
+    0x4f, 0x77, 0x17, 0x60, 0xb2, 0x6f, 0x9c, 0x04,
+    0x88, 0x4e, 0xe1, 0xfa, 0xa3, 0x29, 0xfb, 0xf4,
+    0xe6, 0x1a, 0xf2, 0x3a, 0xee, 0x7f, 0xa5, 0xd4,
+    0xd9, 0xa5, 0xdf, 0xcf, 0x43, 0xc4, 0xc2, 0x6c,
+    0xe8, 0xae, 0xa2, 0xce, 0x8a, 0x29, 0x90, 0xd7,
+    0xba, 0x7b, 0x57, 0x10, 0x8b, 0x47, 0xda, 0xbf,
+    0xbe, 0xad, 0xb2, 0xb2, 0x5b, 0x3c, 0xac, 0xc1,
+    0xac, 0x0c, 0xef, 0x34, 0x6c, 0xbb, 0x90, 0xfb,
+    0x04, 0x4b, 0xee, 0xe4, 0xfa, 0xc2, 0x60, 0x3a,
+    0x44, 0x2b, 0xdf, 0x7e, 0x50, 0x72, 0x43, 0xb7,
+    0x31, 0x9c, 0x99, 0x44, 0xb1, 0x58, 0x6e, 0x89,
+    0x9d, 0x43, 0x1c, 0x7f, 0x91, 0xbc, 0xcc, 0xc8,
+    0x69, 0x0d, 0xbf, 0x59, 0xb2, 0x83, 0x86, 0xb2,
+    0x31, 0x5f, 0x3d, 0x36, 0xef, 0x2e, 0xaa, 0x3c,
+    0xf3, 0x0b, 0x2b, 0x51, 0xf4, 0x8b, 0x71, 0xb0,
+    0x03, 0xdf, 0xb0, 0x82, 0x49, 0x48, 0x42, 0x01,
+    0x04, 0x3f, 0x65, 0xf5, 0xa3, 0xef, 0x6b, 0xbd,
+    0x61, 0xdd, 0xfe, 0xe8, 0x1a, 0xca, 0x9c, 0xe6,
+    0x00, 0x81, 0x26, 0x2a, 0x00, 0x00, 0x04, 0x80,
+    0xdc, 0xbc, 0x9a, 0x3d, 0xa6, 0xfb, 0xef, 0x5c,
+    0x1c, 0x0a, 0x55, 0xe4, 0x8a, 0x0e, 0x72, 0x9f,
+    0x91, 0x84, 0xfc, 0xb1, 0x40, 0x7c, 0x31, 0x52,
+    0x9d, 0xb2, 0x68, 0xf6, 0xfe, 0x50, 0x03, 0x2a,
+    0x36, 0x3c, 0x98, 0x01, 0x30, 0x68, 0x37, 0xfa,
+    0xfa, 0xbd, 0xf9, 0x57, 0xfd, 0x97, 0xea, 0xfc,
+    0x80, 0xdb, 0xd1, 0x65, 0xe4, 0x35, 0xd0, 0xe2,
+    0xdf, 0xd8, 0x36, 0xa2, 0x8b, 0x35, 0x40, 0x23,
+    0x92, 0x4b, 0x6f, 0xb7, 0xe4, 0x8b, 0xc0, 0xb3,
+    0xed, 0x95, 0xee, 0xa6, 0x4c, 0x2d, 0x40, 0x2f,
+    0x4d, 0x73, 0x4c, 0x8d, 0xc2, 0x6f, 0x3a, 0xc5,
+    0x91, 0x82, 0x5d, 0xae, 0xf0, 0x1e, 0xae, 0x3c,
+    0x38, 0xe3, 0x32, 0x8d, 0x00, 0xa7, 0x7d, 0xc6,
+    0x57, 0x03, 0x4f, 0x28, 0x7c, 0xcb, 0x0f, 0x0e,
+    0x1c, 0x9a, 0x7c, 0xbd, 0xc8, 0x28, 0xf6, 0x27,
+    0x20, 0x5e, 0x47, 0x37, 0xb8, 0x4b, 0x58, 0x37,
+    0x65, 0x51, 0xd4, 0x4c, 0x12, 0xc3, 0xc2, 0x15,
+    0xc8, 0x12, 0xa0, 0x97, 0x07, 0x89, 0xc8, 0x3d,
+    0xe5, 0x1d, 0x6a, 0xd7, 0x87, 0x27, 0x19, 0x63,
+    0x32, 0x7f, 0x0a, 0x5f, 0xbb, 0x6b, 0x59, 0x07,
+    0xde, 0xc0, 0x2c, 0x9a, 0x90, 0x93, 0x4a, 0xf5,
+    0xa1, 0xc6, 0x3b, 0x72, 0xc8, 0x26, 0x53, 0x60,
+    0x5d, 0x1d, 0xcc, 0xe5, 0x15, 0x96, 0xb3, 0xc2,
+    0xb4, 0x56, 0x96, 0x68, 0x9f, 0x2e, 0xb3, 0x82,
+    0x00, 0x74, 0x97, 0x55, 0x76, 0x92, 0xca, 0xac,
+    0x4d, 0x57, 0xb5, 0xde, 0x9f, 0x55, 0x69, 0xbc,
+    0x2a, 0xd0, 0x13, 0x7f, 0xd4, 0x7f, 0xb4, 0x7e,
+    0x66, 0x4f, 0xcb, 0x6d, 0xb4, 0x97, 0x1f, 0x5b,
+    0x3e, 0x07, 0xac, 0xed, 0xa9, 0xac, 0x13, 0x0e,
+    0x9f, 0x38, 0x18, 0x2d, 0xe9, 0x94, 0xcf, 0xf1,
+    0x92, 0xec, 0x0e, 0x82, 0xfd, 0x6d, 0x4c, 0xb7,
+    0xf3, 0xfe, 0x00, 0x81, 0x25, 0x89, 0xb7, 0xa7,
+    0xce, 0x51, 0x54, 0x40, 0x45, 0x64, 0x33, 0x01,
+    0x6b, 0x84, 0xa5, 0x9b, 0xec, 0x66, 0x19, 0xa1,
+    0xc6, 0xc0, 0xb3, 0x7d, 0xd1, 0x45, 0x0e, 0xd4,
+    0xf2, 0xd8, 0xb5, 0x84, 0x41, 0x0c, 0xed, 0xa8,
+    0x02, 0x5f, 0x5d, 0x2d, 0x8d, 0xd0, 0xd2, 0x17,
+    0x6f, 0xc1, 0xcf, 0x2c, 0xc0, 0x6f, 0xa8, 0xc8,
+    0x2b, 0xed, 0x4d, 0x94, 0x4e, 0x71, 0x33, 0x9e,
+    0xce, 0x78, 0x0f, 0xd0, 0x25, 0xbd, 0x41, 0xec,
+    0x34, 0xeb, 0xff, 0x9d, 0x42, 0x70, 0xa3, 0x22,
+    0x4e, 0x01, 0x9f, 0xcb, 0x44, 0x44, 0x74, 0xd4,
+    0x82, 0xfd, 0x2d, 0xbe, 0x75, 0xef, 0xb2, 0x03,
+    0x89, 0xcc, 0x10, 0xcd, 0x60, 0x0a, 0xbb, 0x54,
+    0xc4, 0x7e, 0xde, 0x93, 0xe0, 0x8c, 0x11, 0x4e,
+    0xdb, 0x04, 0x11, 0x7d, 0x71, 0x4d, 0xc1, 0xd5,
+    0x25, 0xe1, 0x1b, 0xed, 0x87, 0x56, 0x19, 0x2f,
+    0x92, 0x9d, 0x15, 0x46, 0x2b, 0x93, 0x9f, 0xf3,
+    0xf5, 0x2f, 0x22, 0x52, 0xda, 0x2e, 0xd6, 0x4d,
+    0x8f, 0xae, 0x88, 0x81, 0x8b, 0x1e, 0xfa, 0x2c,
+    0x7b, 0x08, 0xc8, 0x79, 0x4f, 0xb1, 0xb2, 0x14,
+    0xaa, 0x23, 0x3d, 0xb3, 0x16, 0x28, 0x33, 0x14,
+    0x1e, 0xa4, 0x38, 0x3f, 0x1a, 0x6f, 0x12, 0x0b,
+    0xe1, 0xdb, 0x82, 0xce, 0x36, 0x30, 0xb3, 0x42,
+    0x91, 0x14, 0x46, 0x31, 0x57, 0xa6, 0x4e, 0x91,
+    0x23, 0x4d, 0x47, 0x5e, 0x2f, 0x79, 0xcb, 0xf0,
+    0x5e, 0x4d, 0xb6, 0xa9, 0x40, 0x7d, 0x72, 0xc6,
+    0xbf, 0xf7, 0xd1, 0x19, 0x8b, 0x5c, 0x4d, 0x6a,
+    0xad, 0x28, 0x31, 0xdb, 0x61, 0x27, 0x49, 0x93,
+    0x71, 0x5a, 0x01, 0x82, 0xc7, 0xdc, 0x80, 0x89,
+    0xe3, 0x2c, 0x85, 0x31, 0xde, 0xed, 0x4f, 0x74,
+    0x31, 0xc0, 0x7c, 0x02, 0x19, 0x5e, 0xba, 0x2e,
+    0xf9, 0x1e, 0xfb, 0x56, 0x13, 0xc3, 0x7a, 0xf7,
+    0xae, 0x0c, 0x06, 0x6b, 0xab, 0xc6, 0x93, 0x69,
+    0x70, 0x0e, 0x1d, 0xd2, 0x6e, 0xdd, 0xc0, 0xd2,
+    0x16, 0xc7, 0x81, 0xd5, 0x6e, 0x4c, 0xe4, 0x7e,
+    0x33, 0x03, 0xfa, 0x73, 0x00, 0x7f, 0xf7, 0xb9,
+    0x49, 0xef, 0x23, 0xbe, 0x2a, 0xa4, 0xdb, 0xf2,
+    0x52, 0x06, 0xfe, 0x45, 0xc2, 0x0d, 0xd8, 0x88,
+    0x39, 0x5b, 0x25, 0x26, 0x39, 0x1a, 0x72, 0x49,
+    0x96, 0xa4, 0x41, 0x56, 0xbe, 0xac, 0x80, 0x82,
+    0x12, 0x85, 0x87, 0x92, 0xbf, 0x8e, 0x74, 0xcb,
+    0xa4, 0x9d, 0xee, 0x5e, 0x88, 0x12, 0xe0, 0x19,
+    0xda, 0x87, 0x45, 0x4b, 0xff, 0x9e, 0x84, 0x7e,
+    0xd8, 0x3d, 0xb0, 0x7a, 0xf3, 0x13, 0x74, 0x30,
+    0x82, 0xf8, 0x80, 0xa2, 0x78, 0xf6, 0x82, 0xc2,
+    0xbd, 0x0a, 0xd6, 0x88, 0x7c, 0xb5, 0x9f, 0x65,
+    0x2e, 0x15, 0x59, 0x87, 0xd6, 0x1b, 0xbf, 0x6a,
+    0x88, 0xd3, 0x6e, 0xe9, 0x3b, 0x60, 0x72, 0xe6,
+    0x65, 0x6d, 0x9c, 0xcb, 0xaa, 0xe3, 0xd6, 0x55,
+    0x85, 0x2e, 0x38, 0xde, 0xb3, 0xa2, 0xdc, 0xf8,
+    0x05, 0x8d, 0xc9, 0xfb, 0x6f, 0x2a, 0xb3, 0xd3,
+    0xb3, 0x53, 0x9e, 0xb7, 0x7b, 0x24, 0x8a, 0x66,
+    0x10, 0x91, 0xd0, 0x5e, 0xb6, 0xe2, 0xf2, 0x97,
+    0x77, 0x4f, 0xe6, 0x05, 0x35, 0x98, 0x45, 0x7c,
+    0xc6, 0x19, 0x08, 0x31, 0x8d, 0xe4, 0xb8, 0x26,
+    0xf0, 0xfc, 0x86, 0xd4, 0xbb, 0x11, 0x7d, 0x33,
+    0xe8, 0x65, 0xaa, 0x80, 0x50, 0x09, 0xcc, 0x29,
+    0x18, 0xd9, 0xc2, 0xf8, 0x40, 0xc4, 0xda, 0x43,
+    0xa7, 0x03, 0xad, 0x9f, 0x5b, 0x58, 0x06, 0x16,
+    0x3d, 0x71, 0x61, 0x69, 0x6b, 0x5a, 0x0a, 0xdc,
+    0x00, 0x00, 0x00, 0x05,
+    0xd5, 0xc0, 0xd1, 0xbe, 0xbb, 0x06, 0x04, 0x8e,
+    0xd6, 0xfe, 0x2e, 0xf2, 0xc6, 0xce, 0xf3, 0x05,
+    0xb3, 0xed, 0x63, 0x39, 0x41, 0xeb, 0xc8, 0xb3,
+    0xbe, 0xc9, 0x73, 0x87, 0x54, 0xcd, 0xdd, 0x60,
+    0xe1, 0x92, 0x0a, 0xda, 0x52, 0xf4, 0x3d, 0x05,
+    0x5b, 0x50, 0x31, 0xce, 0xe6, 0x19, 0x25, 0x20,
+    0xd6, 0xa5, 0x11, 0x55, 0x14, 0x85, 0x1c, 0xe7,
+    0xfd, 0x44, 0x8d, 0x4a, 0x39, 0xfa, 0xe2, 0xab,
+    0x23, 0x35, 0xb5, 0x25, 0xf4, 0x84, 0xe9, 0xb4,
+    0x0d, 0x6a, 0x4a, 0x96, 0x93, 0x94, 0x84, 0x3b,
+    0xdc, 0xf6, 0xd1, 0x4c, 0x48, 0xe8, 0x01, 0x5e,
+    0x08, 0xab, 0x92, 0x66, 0x2c, 0x05, 0xc6, 0xe9,
+    0xf9, 0x0b, 0x65, 0xa7, 0xa6, 0x20, 0x16, 0x89,
+    0x99, 0x9f, 0x32, 0xbf, 0xd3, 0x68, 0xe5, 0xe3,
+    0xec, 0x9c, 0xb7, 0x0a, 0xc7, 0xb8, 0x39, 0x90,
+    0x03, 0xf1, 0x75, 0xc4, 0x08, 0x85, 0x08, 0x1a,
+    0x09, 0xab, 0x30, 0x34, 0x91, 0x1f, 0xe1, 0x25,
+    0x63, 0x10, 0x51, 0xdf, 0x04, 0x08, 0xb3, 0x94,
+    0x6b, 0x0b, 0xde, 0x79, 0x09, 0x11, 0xe8, 0x97,
+    0x8b, 0xa0, 0x7d, 0xd5, 0x6c, 0x73, 0xe7, 0xee,
+};
+
+typedef struct { const uint8_t *val; size_t len; } hashsig_tc_bn_t;
+typedef struct { hashsig_tc_bn_t key, msg, sig; } hashsig_tc_t;
+
+static const hashsig_tc_t hashsig_tc[] = {
+    { { tc1_key, sizeof(tc1_key) },
+      { tc1_msg, sizeof(tc1_msg) },
+      { tc1_sig, sizeof(tc1_sig) } }
+};
diff --git a/tests/test-rpc_hashsig.c b/tests/test-rpc_hashsig.c
new file mode 100644
index 0000000..d9dd0e7
--- /dev/null
+++ b/tests/test-rpc_hashsig.c
@@ -0,0 +1,528 @@
+/*
+ * test-rpc_hashsig.c
+ * ------------------
+ * Test code for RPC interface to Cryptech public key operations.
+ *
+ * Authors: Rob Austein, Paul Selkirk
+ * Copyright (c) 2015-2018, NORDUnet A/S
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * - Redistributions of source code must retain the above copyright notice,
+ *   this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ *
+ * - Neither the name of the NORDUnet nor the names of its contributors may
+ *   be used to endorse or promote products derived from this software
+ *   without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+ * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/* Parts of this may eventually get folded into test-rpc_pkey.c,
+ * but for now I'd rather do it stand-alone.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <getopt.h>
+#include <assert.h>
+
+#include <hal.h>
+#include <hashsig.h>
+#include "test-hashsig.h"
+
+#include <sys/time.h>
+/* not included in my glibc, sigh... */
+void timersub(struct timeval *a, struct timeval *b, struct timeval *res)
+{
+    res->tv_sec = a->tv_sec - b->tv_sec;
+    res->tv_usec = a->tv_usec - b->tv_usec;
+    if (res->tv_usec < 0) {
+        res->tv_usec += 1000000;
+        --res->tv_sec;
+    }
+    if (res->tv_usec > 1000000) {
+        res->tv_usec -= 1000000;
+        ++res->tv_sec;
+    }
+}
+
+static int debug = 0;
+static int info = 0;
+
+#define lose(...) do { printf(__VA_ARGS__); goto fail; } while (0)
+
+static int test_hashsig_testvec_local(const hashsig_tc_t * const tc, hal_key_flags_t flags)
+{
+    hal_error_t err;
+
+    assert(tc != NULL);
+
+    printf("Starting local hashsig test vector test\n");
+
+    uint8_t tc_keybuf[hal_hashsig_key_t_size];
+    hal_hashsig_key_t *tc_key = NULL;
+
+    if ((err = hal_hashsig_key_load_public_xdr(&tc_key,
+                                               tc_keybuf, sizeof(tc_keybuf),
+                                               tc->key.val, tc->key.len)) != HAL_OK)
+        lose("Could not load public key from test vector: %s\n", hal_error_string(err));
+
+    if ((err = hal_hashsig_verify(NULL, tc_key, tc->msg.val, tc->msg.len, tc->sig.val, tc->sig.len)) != HAL_OK)
+        lose("Verify failed: %s\n", hal_error_string(err));
+
+    printf("OK\n");
+    return 1;
+
+fail:
+    return 0;
+}
+
+static int test_hashsig_testvec_remote(const hashsig_tc_t * const tc, hal_key_flags_t flags)
+{
+    const hal_client_handle_t client = {HAL_HANDLE_NONE};
+    const hal_session_handle_t session = {HAL_HANDLE_NONE};
+    hal_pkey_handle_t public_key = {HAL_HANDLE_NONE};
+    hal_error_t err;
+    size_t len;
+
+    assert(tc != NULL);
+
+    {
+        flags |= HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE;
+
+        printf("Starting remote hashsig test vector test, flags 0x%lx\n", (unsigned long) flags);
+
+        uint8_t tc_keybuf[hal_hashsig_key_t_size];
+        hal_hashsig_key_t *tc_key = NULL;
+
+        if ((err = hal_hashsig_key_load_public_xdr(&tc_key,
+                                                   tc_keybuf, sizeof(tc_keybuf),
+                                                   tc->key.val, tc->key.len)) != HAL_OK)
+            lose("Could not load public key from test vector: %s\n", hal_error_string(err));
+
+        hal_uuid_t public_name;
+
+        uint8_t public_der[hal_hashsig_public_key_to_der_len(tc_key)];
+
+        if ((err = hal_hashsig_public_key_to_der(tc_key, public_der, &len, sizeof(public_der))) != HAL_OK)
+            lose("Could not DER encode public key from test vector: %s\n", hal_error_string(err));
+
+        assert(len == sizeof(public_der));
+
+        if ((err = hal_rpc_pkey_load(client, session, &public_key, &public_name,
+                                     public_der, sizeof(public_der), flags)) != HAL_OK)
+            lose("Could not load public key into RPC: %s\n", hal_error_string(err));
+
+        if ((err = hal_rpc_pkey_verify(public_key, hal_hash_handle_none,
+                                       tc->msg.val, tc->msg.len, tc->sig.val, tc->sig.len)) != HAL_OK)
+            lose("Could not verify: %s\n", hal_error_string(err));
+
+        if ((err = hal_rpc_pkey_delete(public_key)) != HAL_OK)
+            lose("Could not delete public key: %s\n", hal_error_string(err));
+
+        printf("OK\n");
+        return 1;
+    }
+
+fail:
+    if (public_key.handle != HAL_HANDLE_NONE &&
+        (err = hal_rpc_pkey_delete(public_key)) != HAL_OK)
+        printf("Warning: could not delete public key: %s\n", hal_error_string(err));
+
+    return 0;
+}
+
+static void hexdump(const char * const label, const uint8_t * const buf, const size_t len)
+{
+    printf("%-15s ", label);
+
+    for (size_t i = 0; i < len; ++i) {
+        printf("%02x", buf[i]);
+        if ((i & 0x0f) == 0x0f) {
+            printf("\n");
+            if (i < len - 1)
+                printf("                ");
+        }
+    }
+    if ((len & 0x0f) != 0)
+        printf("\n");
+}
+
+static inline size_t lms_type_to_h(const lms_algorithm_t lms_type)
+{
+    switch (lms_type) {
+    case lms_sha256_n32_h5:  return  5;
+    case lms_sha256_n32_h10: return 10;
+    case lms_sha256_n32_h15: return 15;
+    case lms_sha256_n32_h20: return 20;
+    case lms_sha256_n32_h25: return 25;
+    default: return 0;
+    }
+}
+
+static inline size_t two_to_the(const size_t n)
+{
+    if (n % 5 != 0)
+        return 0;
+
+    size_t result, i;
+    for (result = 1, i = 0; i < n; i += 5)
+        result *= 32;
+
+    return result;
+}
+
+static inline size_t lms_type_to_h2(const lms_algorithm_t lms_type)
+{
+    switch (lms_type) {
+    case lms_sha256_n32_h5:  return two_to_the(5);
+    case lms_sha256_n32_h10: return two_to_the(10);
+    case lms_sha256_n32_h15: return two_to_the(15);
+    case lms_sha256_n32_h20: return two_to_the(20);
+    case lms_sha256_n32_h25: return two_to_the(25);
+    default:                 return 0;
+    }
+}
+
+static inline size_t lmots_type_to_w(const lmots_algorithm_t lmots_type)
+{
+    switch (lmots_type) {
+    case lmots_sha256_n32_w1: return 1;
+    case lmots_sha256_n32_w2: return 2;
+    case lmots_sha256_n32_w4: return 4;
+    case lmots_sha256_n32_w8: return 8;
+    default: return 0;
+    }
+}
+
+static inline size_t lmots_type_to_p(const lmots_algorithm_t lmots_type)
+{
+    switch (lmots_type) {
+    case lmots_sha256_n32_w1: return 265;
+    case lmots_sha256_n32_w2: return 133;
+    case lmots_sha256_n32_w4: return  67;
+    case lmots_sha256_n32_w8: return  34;
+    default: return 0;
+    }
+}
+
+#include <xdr_internal.h>
+
+static hal_error_t dump_hss_signature(const uint8_t * const sig, const size_t len)
+{
+    const uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + len;
+    hal_error_t err;
+
+    hexdump("Nspk", sigptr, 4);
+    uint32_t Nspk;
+    if ((err = hal_xdr_decode_int(&sigptr, siglim, &Nspk)) != HAL_OK) return err;
+
+    for (size_t i = 0; i < Nspk + 1; ++i) {
+        printf("--------------------------------------------\nsig[%lu]\n", i);
+        hexdump("q", sigptr, 4); sigptr += 4;
+
+        {
+            hexdump("lmots type", sigptr, 4);
+            uint32_t lmots_type;
+            if ((err = hal_xdr_decode_int(&sigptr, siglim, &lmots_type)) != HAL_OK) return err;
+            hexdump("C", sigptr, 32); sigptr += 32;
+            size_t p = lmots_type_to_p((const lmots_algorithm_t)lmots_type);
+            for (size_t j = 0; j < p; ++j) {
+                char label[16];
+                sprintf(label, "y[%lu]", j);
+                hexdump(label, sigptr, 32); sigptr += 32;
+            }
+        }
+
+        hexdump("lms type", sigptr, 4);
+        uint32_t lms_type;
+        if ((err = hal_xdr_decode_int(&sigptr, siglim, &lms_type)) != HAL_OK) return err;
+        size_t h = lms_type_to_h((const lms_algorithm_t)lms_type);
+        for (size_t j = 0; j < h; ++j) {
+            char label[16];
+            sprintf(label, "path[%lu]", j);
+            hexdump(label, sigptr, 32); sigptr += 32;
+        }
+
+        if (i == Nspk)
+            break;
+
+        printf("--------------------------------------------\npubkey[%lu]\n", i + 1);
+        hexdump("lms type", sigptr, 4); sigptr += 4;
+        hexdump("lmots type", sigptr, 4); sigptr += 4;
+        hexdump("I", sigptr, 16); sigptr += 16;
+        hexdump("T[1]", sigptr, 32); sigptr += 32;
+    }
+
+    if (sigptr < siglim) {
+        printf("--------------------------------------------\nextra\n");
+        hexdump("", sigptr, siglim - sigptr);
+    }
+
+    return HAL_OK;
+}
+
+static int test_hashsig_sign(const size_t L,
+                             const lms_algorithm_t lms_type,
+                             const lmots_algorithm_t lmots_type,
+                             size_t iterations)
+{
+    const hal_client_handle_t client = {HAL_HANDLE_NONE};
+    const hal_session_handle_t session = {HAL_HANDLE_NONE};
+    hal_pkey_handle_t private_key = {HAL_HANDLE_NONE};
+    hal_pkey_handle_t public_key = {HAL_HANDLE_NONE};
+    hal_error_t err;
+    size_t len;
+
+    {
+        hal_key_flags_t flags = HAL_KEY_FLAG_USAGE_DIGITALSIGNATURE;
+
+        printf("Starting hashsig key test: L %lu, lms type %u (h=%lu), lmots type %u (w=%lu)\n",
+               L, lms_type, lms_type_to_h(lms_type), lmots_type, lmots_type_to_w(lmots_type));
+
+        if (info)
+            printf("Info: signature length %lu, lmots private key length %lu\n",
+                   hal_hashsig_signature_len(L, lms_type, lmots_type),
+                   hal_hashsig_lmots_private_key_len(lmots_type));
+
+        hal_uuid_t private_name, public_name;
+        struct timeval tv_start, tv_end, tv_diff;
+
+        size_t Lh2 = two_to_the(L * lms_type_to_h(lms_type));
+        size_t h2 = lms_type_to_h2(lms_type);
+
+        if (info)
+            gettimeofday(&tv_start, NULL);
+        if ((err = hal_rpc_pkey_generate_hashsig(client, session, &private_key, &private_name,
+                                                 L, lms_type, lmots_type, flags)) != HAL_OK)
+            lose("Could not generate hashsig private key: %s\n", hal_error_string(err));
+        if (info) {
+            gettimeofday(&tv_end, NULL);
+            timersub(&tv_end, &tv_start, &tv_diff);
+            long per_key = (tv_diff.tv_sec * 1000000 + tv_diff.tv_usec) / (L * h2);
+            printf("Info: %ldm%ld.%03lds to generate key (%ld.%03lds per lmots key)\n",
+                   tv_diff.tv_sec / 60, tv_diff.tv_sec % 60, tv_diff.tv_usec / 1000,
+                   per_key / 1000000, (per_key % 1000000) / 1000);
+        }
+
+        uint8_t public_der[hal_rpc_pkey_get_public_key_len(private_key)];
+
+        if ((err = hal_rpc_pkey_get_public_key(private_key, public_der, &len, sizeof(public_der))) != HAL_OK)
+            lose("Could not DER encode RPC hashsig public key from RPC hashsig private key: %s\n", hal_error_string(err));
+
+        assert(len == sizeof(public_der));
+
+        if ((err = hal_rpc_pkey_load(client, session, &public_key, &public_name,
+                                     public_der, sizeof(public_der), flags)) != HAL_OK)
+            lose("Could not load public key into RPC: %s\n", hal_error_string(err));
+
+        if (iterations > 0) {
+            uint8_t sig[hal_hashsig_signature_len(L, lms_type, lmots_type)];
+
+            if (info)
+                gettimeofday(&tv_start, NULL);
+            int i;
+            for (i = 0; i < iterations; ++i) {
+                if ((err = hal_rpc_pkey_sign(private_key, hal_hash_handle_none,
+                                             tc1_msg, sizeof(tc1_msg), sig, &len, sizeof(sig))) == HAL_OK) {
+                    assert(len == sizeof(sig));
+                    if (debug) {
+                        printf("Debug: received signature:\n");
+                        dump_hss_signature(sig, len);
+                    }
+                }
+                else {
+                    if (i == Lh2 && err == HAL_ERROR_HASHSIG_KEY_EXHAUSTED)
+                        break;
+                    else
+                        lose("Could not sign (%d): %s\n", i, hal_error_string(err));
+                }
+            }
+            if (info) {
+                gettimeofday(&tv_end, NULL);
+                timersub(&tv_end, &tv_start, &tv_diff);
+                long per_sig = (tv_diff.tv_sec * 1000000 + tv_diff.tv_usec) / i;
+                printf("Info: %ldm%ld.%03lds to generate %d signatures (%ld.%03lds per signature)\n",
+                       tv_diff.tv_sec / 60, tv_diff.tv_sec % 60, tv_diff.tv_usec / 1000, i,
+                       per_sig / 1000000, (per_sig % 1000000) / 1000);
+            }
+
+            if (info)
+                gettimeofday(&tv_start, NULL);
+            if ((err = hal_rpc_pkey_verify(public_key, hal_hash_handle_none,
+                                           tc1_msg, sizeof(tc1_msg), sig, len)) != HAL_OK)
+                lose("Could not verify: %s\n", hal_error_string(err));
+            if (info) {
+                gettimeofday(&tv_end, NULL);
+                timersub(&tv_end, &tv_start, &tv_diff);
+                printf("Info: %ldm%ld.%03lds to verify 1 signature\n",
+                       tv_diff.tv_sec / 60, tv_diff.tv_sec % 60, tv_diff.tv_usec / 1000);
+            }
+        }
+
+        if ((err = hal_rpc_pkey_delete(private_key)) != HAL_OK)
+            lose("Could not delete private key: %s\n", hal_error_string(err));
+
+        if ((err = hal_rpc_pkey_delete(public_key)) != HAL_OK)
+            lose("Could not delete public key: %s\n", hal_error_string(err));
+
+        printf("OK\n");
+        return 1;
+    }
+
+fail:
+    if (private_key.handle != HAL_HANDLE_NONE &&
+        (err = hal_rpc_pkey_delete(private_key)) != HAL_OK)
+        printf("Warning: could not delete private key: %s\n", hal_error_string(err));
+
+    if (public_key.handle != HAL_HANDLE_NONE &&
+        (err = hal_rpc_pkey_delete(public_key)) != HAL_OK)
+        printf("Warning: could not delete public key: %s\n", hal_error_string(err));
+
+    return 0;
+}
+
+int main(int argc, char *argv[])
+{
+    const hal_client_handle_t client = {HAL_HANDLE_NONE};
+    char *pin = "fnord";
+    int do_default = 1;
+    int do_testvec = 0;
+    size_t iterations = 1;
+    size_t L_lo = 0, L_hi = 0;
+    size_t lms_lo = 5, lms_hi = 0;
+    size_t lmots_lo = 3, lmots_hi = 0;
+    char *p;
+    hal_error_t err;
+    int ok = 1;
+
+char usage[] = "\
+Usage: %s [-d] [-i] [-p pin] [-t] [-L n] [-l n] [-o n] [-n n]\n\
+       -d: enable debugging - hexdump signatures\n\
+       -i: enable informational messages - runtimes and signature lengths\n\
+       -p: user PIN\n\
+       -t: verify test vectors\n\
+       -L: number of levels in the HSS scheme (1..8)\n\
+       -l: LMS type (5..9)\n\
+       -o: LM-OTS type (1..4)\n\
+       -n: number of signatures to generate (0..'max')\n\
+Numeric arguments can be a single number or a range, e.g. '1..4'\n";
+
+    int opt;
+    while ((opt = getopt(argc, argv, "ditp:L:l:o:n:h?")) != -1) {
+        switch (opt) {
+        case 'd':
+            debug = 1;
+            break;
+        case 'i':
+            info = 1;
+            break;
+        case 't':
+            do_testvec = 1;
+            do_default = 0;
+            break;
+        case 'p':
+            pin = optarg;
+            break;
+        case 'n':
+            if (strcmp(optarg, "max") == 0)
+                iterations = (size_t)-1;
+            else
+                iterations = (size_t)atoi(optarg);
+            do_default = 0;
+            break;
+        case 'L':
+            if ((p = strtok(optarg, ".")) != NULL)
+                L_lo = (size_t)atoi(p);
+            if ((p = strtok(NULL, ".")) != NULL)
+                L_hi = (size_t)atoi(p);
+            do_default = 0;
+            break;
+        case 'l':
+            if ((p = strtok(optarg, ".")) != NULL)
+                lms_lo = (size_t)atoi(p);
+            if ((p = strtok(NULL, ".")) != NULL)
+                lms_hi = (size_t)atoi(p);
+            do_default = 0;
+            break;
+        case 'o':
+            if ((p = strtok(optarg, ".")) != NULL)
+                lmots_lo = (size_t)atoi(p);
+            if ((p = strtok(NULL, ".")) != NULL)
+                lmots_hi = (size_t)atoi(p);
+            do_default = 0;
+            break;
+        case 'h':
+        case '?':
+            fprintf(stdout, usage, argv[0]);
+            exit(EXIT_SUCCESS);
+        default:
+            fprintf(stderr, usage, argv[0]);
+            exit(EXIT_FAILURE);
+        }
+    }
+
+    if (do_default) {
+        do_testvec = 1;
+        L_lo = 1;
+    }
+
+    if (L_hi < L_lo) L_hi = L_lo;
+    if (lms_hi < lms_lo) lms_hi = lms_lo;
+    if (lmots_hi < lmots_lo) lmots_hi = lmots_lo;
+
+    if ((err = hal_rpc_client_init()) != HAL_OK)
+        printf("Warning: Trouble initializing RPC client: %s\n", hal_error_string(err));
+
+    if ((err = hal_rpc_login(client, HAL_USER_NORMAL, pin, strlen(pin))) != HAL_OK)
+        printf("Warning: Trouble logging into HSM: %s\n", hal_error_string(err));
+
+    if (do_testvec) {
+        for (int i = 0; i < (sizeof(hashsig_tc)/sizeof(*hashsig_tc)); i++)
+            ok &= test_hashsig_testvec_local(&hashsig_tc[i], 0);
+
+        for (int i = 0; i < (sizeof(hashsig_tc)/sizeof(*hashsig_tc)); i++)
+            for (int j = 0; j < 2; j++)
+                ok &= test_hashsig_testvec_remote(&hashsig_tc[i], j * HAL_KEY_FLAG_TOKEN);
+    }
+
+    /* signing/performance tests: run with -i */
+    /* A single test would be of the form '-L 2 -l 5 -o 3 -n 1' */
+    /* A range test of just keygen would be of the form '-o 1..4 -n 0' */
+    /* A test to key exhaustion would be of the form '-n max' */
+    if (L_lo > 0) {
+        for (size_t L = L_lo; L <= L_hi; ++L) {
+            for (lms_algorithm_t lms_type = lms_lo; lms_type <= lms_hi; ++lms_type) {
+                for (lmots_algorithm_t lmots_type = lmots_lo; lmots_type <= lmots_hi; ++lmots_type) {
+                    ok &= test_hashsig_sign(L, lms_type, lmots_type, iterations);
+                }
+            }
+        }
+    }
+
+    if ((err = hal_rpc_logout(client)) != HAL_OK)
+        printf("Warning: Trouble logging out of HSM: %s\n", hal_error_string(err));
+
+    if ((err = hal_rpc_client_close()) != HAL_OK)
+        printf("Warning: Trouble shutting down RPC client: %s\n", hal_error_string(err));
+
+    return !ok;
+}