Naive implementation of draft-mcgrew-hash-sigs-10.txt

3 files changed, 2005 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..c07470a
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,16 @@
+LIBHAL = ../../../sw/libhal
+CFLAGS = -Wall -Wextra -g -I$(LIBHAL)
+
+all: hashsig
+
+hashsig: hashsig_naive.o xdr.o errorstrings.o
+	$(CC) -o $@ $^ -lcrypto
+
+xdr.o: $(LIBHAL)/xdr.c
+	$(CC) -c $(CFLAGS) -o $@ $^
+
+errorstrings.o: $(LIBHAL)/errorstrings.c
+	$(CC) -c $(CFLAGS) -o $@ $^
+
+clean:
+	rm -f hashsig hashsig_naive.o xdr.o errorstrings.o
diff --git a/README b/README
new file mode 100644
index 0000000..bec81a5
--- /dev/null
+++ b/README
@@ -0,0 +1,12 @@
+Reference implementation of of the LMS Hash Based Signature Scheme from
+draft-mcgrew-hash-sigs-10.
+
+This is a naive implementation, which hews as closely as possible to the
+text of the draft, without any regard for performance (or security - keys
+are stored unencrypted in the local file system). It is intended to show
+that the draft can be implemented as written (except I found a few
+omissions in the text), and can interoperate with the official reference
+implementation at http://github.com/cisco/hash-sigs.
+
+The user interface is modeled on demo.c from the Cisco implementation,
+although all code was written independently.
diff --git a/hashsig_naive.c b/hashsig_naive.c
new file mode 100644
index 0000000..aa590bf
--- /dev/null
+++ b/hashsig_naive.c
@@ -0,0 +1,1977 @@
+/*
+ * hashsig.c
+ * ---------
+ * Naive implementation of draft-mcgrew-hash-sigs-10.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.
+ */
+
+/*
+ * This is a naive implementation of McGrew et al's Hash-Based Signature
+ * scheme, which hews as closely as possible to the text of the draft,
+ * without any regard for performance (or security - keys are stored
+ * unencrypted in the local file system).
+ *
+ * For simplicity, this implemention restricts all LMS keys in the HSS scheme
+ * to use the same LMS type and LM-OTS type.
+ */
+
+#include <arpa/inet.h>		/* htonl and friends */
+
+#include <openssl/sha.h>
+#include <openssl/rand.h>
+
+#include "hal.h"
+#include "hashsig.h"
+#include "xdr_internal.h"
+
+typedef struct { uint8_t bytes[32]; } bytestring32;
+typedef struct { uint8_t bytes[16]; } bytestring16;
+
+#define check(op) do { hal_error_t _err = (op); if (_err != HAL_OK) return _err; } while (0)
+#define checkssl(op) do { if ((op) == 0) { return HAL_ERROR_IMPOSSIBLE; } } while (0)
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * XDR extensions
+ */
+
+static inline hal_error_t hal_xdr_encode_bytestring32(uint8_t **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(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring32 *value)
+{
+    return hal_xdr_decode_fixed_opaque(inbuf, limit, (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_encode_bytestring16(uint8_t **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(const uint8_t ** const inbuf, const uint8_t * const limit, bytestring16 *value)
+{
+    return hal_xdr_decode_fixed_opaque(inbuf, limit, (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));
+}
+
+/* ---------------------------------------------------------------- */
+
+// 3.1.  Data Types
+
+#define u32str(X) htonl(X)
+#define u16str(X) htons(X)
+#define u8str(X) (X & 0xff)
+
+// 3.1.3.  Strings of w-bit elements
+
+static uint8_t coef(const uint8_t * const S, const size_t i, size_t w)
+{
+    switch (w) {
+    case 1:
+        return (S[i/8] >> (7 - (i % 8))) & 0x01;
+    case 2:
+        return (S[i/4] >> (6 - (2 * (i % 4)))) & 0x03;
+    case 4:
+        return (S[i/2] >> (4 - (4 * (i % 2)))) & 0x0f;
+    case 8:
+        return S[i];
+    default:
+        return 0;
+    }
+}
+
+// 3.2.  Security string
+
+#define D_PBLC 0x8080
+#define D_MESG 0x8181
+#define D_LEAF 0x8282
+#define D_INTR 0x8383
+
+/* ---------------------------------------------------------------- */
+
+// 4.  LM-OTS One-Time Signatures
+
+// 4.2.  Parameter Sets
+
+static inline size_t lmots_type_to_n(const lmots_algorithm_t lmots_type)
+{
+    switch (lmots_type) {
+    case lmots_sha256_n32_w1:
+    case lmots_sha256_n32_w2:
+    case lmots_sha256_n32_w4:
+    case lmots_sha256_n32_w8: return 32;
+    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;
+    }
+}
+
+static inline size_t lmots_type_to_ls(const lmots_algorithm_t lmots_type)
+{
+    switch (lmots_type) {
+    case lmots_sha256_n32_w1: return 7;
+    case lmots_sha256_n32_w2: return 6;
+    case lmots_sha256_n32_w4: return 4;
+    case lmots_sha256_n32_w8: return 0;
+    default: return 0;
+    }
+}
+
+// 4.3.  Private Key
+
+static inline size_t lmots_private_key_len(const lmots_algorithm_t lmots_type)
+{
+    /* u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */
+    return 2 * sizeof(uint32_t) + sizeof(bytestring16) + lmots_type_to_p(lmots_type) * lmots_type_to_n(lmots_type);
+}
+
+static hal_error_t lmots_generate_private_key(const lmots_algorithm_t lmots_type,
+                                              const bytestring16 * const I, const size_t q,
+                                              uint8_t *key, size_t *key_len, const size_t key_max)
+{
+    if (I == NULL || key == NULL|| key_max < lmots_private_key_len(lmots_type))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 0: Generating a Private Key
+
+//  1. retrieve the value p from the type, and the value I the 16 byte
+//     identifier of the LMS public/private keypair that this LM-OTS private
+//     key will be used with
+
+//  2. set type to the typecode of the algorithm
+
+//  3. set n and p according to the typecode and Table 1
+
+    size_t n = lmots_type_to_n(lmots_type);
+    size_t p = lmots_type_to_p(lmots_type);
+
+//  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
+//     }
+
+    bytestring32 x[p];
+    for (size_t i = 0; i < p; ++i)
+        checkssl(RAND_bytes((unsigned char *)&x[i], n));
+
+//  5. return u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1]
+
+    uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_max;
+    check(hal_xdr_encode_int(&keyptr, keylim, lmots_type));
+    check(hal_xdr_encode_bytestring16(&keyptr, keylim, I));
+    check(hal_xdr_encode_int(&keyptr, keylim, q));
+    for (size_t i = 0; i < p; ++i)
+        check(hal_xdr_encode_bytestring32(&keyptr, keylim, &x[i]));
+
+    if (key_len != NULL)
+        *key_len = keyptr - key;
+
+    return HAL_OK;
+}
+
+// 4.4.  Public Key
+
+static inline size_t lmots_public_key_len(const lmots_algorithm_t lmots_type)
+{
+    /* u32str(type) || I || u32str(q) || K */
+    return ((2 * sizeof(uint32_t)) + sizeof(bytestring16) + lmots_type_to_n(lmots_type));
+}
+
+static hal_error_t lmots_generate_public_key(const uint8_t * const key, const size_t key_len,
+                                             uint8_t *pub, size_t *pub_len, const size_t pub_max)
+{
+    if (key == NULL || pub == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 1: Generating a One Time Signature Public Key From a
+//   Private Key
+//
+//   1. set type to the typecode of the algorithm
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    lmots_algorithm_t lmots_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type));
+
+    /* private key format
+     * u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1]
+     */
+
+//   2. set the integers n, p, and w according to the typecode and Table 1
+
+    /* XXX n is not used here */
+    size_t p = lmots_type_to_p(lmots_type);
+    size_t w = lmots_type_to_w(lmots_type);
+
+//   3. determine x, I and q from the private key
+
+    bytestring16 I;
+    check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I));
+
+    uint32_t q;
+    check(hal_xdr_decode_int(&keyptr, keylim, &q));
+
+    bytestring32 x[p];
+    for (size_t i = 0; i < p; ++i)
+        check(hal_xdr_decode_bytestring32(&keyptr, keylim, &x[i]));
+
+//   4. compute the string K as follows:
+//      for ( i = 0; i < p; i = i + 1 ) {
+//        tmp = x[i]
+//        for ( j = 0; j < 2^w - 1; j = j + 1 ) {
+//           tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
+//        }
+//        y[i] = tmp
+//      }
+//      K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])
+
+    SHA256_CTX ctx;
+    bytestring32 y[p];
+    for (size_t i = 0; i < p; ++i) {
+        bytestring32 tmp;
+        memcpy(&tmp, &x[i], sizeof(tmp));
+        for (size_t j = 0; j < (1U << w) - 1; ++j) {
+            checkssl(SHA256_Init(&ctx));
+            checkssl(SHA256_Update(&ctx, &I, sizeof(I)));
+            uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+            uint16_t s = u16str(i); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+            uint8_t b = u8str(j); checkssl(SHA256_Update(&ctx, &b, sizeof(b)));
+            checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp)));
+            checkssl(SHA256_Final((unsigned char *)&tmp, &ctx));
+        }
+        memcpy(&y[i], &tmp, sizeof(tmp));
+    }
+    bytestring32 K;
+    checkssl(SHA256_Init(&ctx));
+    checkssl(SHA256_Update(&ctx, &I, sizeof(I)));
+    uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+    uint16_t s = u16str(D_PBLC); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+    for (size_t i = 0; i < p; ++i)
+        checkssl(SHA256_Update(&ctx, (uint8_t *)&y[i], sizeof(y[i])));
+    checkssl(SHA256_Final((unsigned char *)&K, &ctx));
+
+//   5. return u32str(type) || I || u32str(q) || K
+
+    uint8_t *pubptr = pub;
+    const uint8_t * const publim = pub + pub_max;
+    check(hal_xdr_encode_int(&pubptr, publim, lmots_type));
+    check(hal_xdr_encode_bytestring16(&pubptr, publim, &I));
+    check(hal_xdr_encode_int(&pubptr, publim, q));
+    check(hal_xdr_encode_bytestring32(&pubptr, publim, &K));
+
+    if (pub_len != NULL)
+        *pub_len = pubptr - pub;
+
+    return HAL_OK;
+}
+
+// 4.5.  Checksum
+
+static uint16_t Cksm(const uint8_t * const S, const lmots_algorithm_t lmots_type)
+{
+//   Algorithm 2: Checksum Calculation
+//     sum = 0
+//     for ( i = 0; i < (n*8/w); i = i + 1 ) {
+//       sum = sum + (2^w - 1) - coef(S, i, w)
+//     }
+//     return (sum << ls)
+
+    size_t n = lmots_type_to_n(lmots_type);
+    size_t w = lmots_type_to_w(lmots_type);
+    size_t ls = lmots_type_to_ls(lmots_type);
+
+    uint16_t sum = 0;
+    for (size_t i = 0; i < (n * 8 / w); ++i)
+        sum += ((1 << w) - 1) - coef(S, i, w);
+    return (sum << ls);
+}
+
+// 4.6.  Signature Generation
+
+static inline size_t lmots_signature_len(const lmots_algorithm_t lmots_type)
+{
+    /* u32str(type) || C || y[0] || ... || y[p-1] */
+    return (sizeof(uint32_t) + ((lmots_type_to_p(lmots_type) + 1) * lmots_type_to_n(lmots_type)));
+}
+
+static hal_error_t lmots_sign(const uint8_t * const key, const size_t key_len,
+                              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 ||  msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 3: Generating a One Time Signature From a Private Key and a
+//   Message
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    /* private key format
+     * u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1]
+     */
+
+//     1. set type to the typecode of the algorithm
+
+    lmots_algorithm_t lmots_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type));
+
+//     2. set n, p, and w according to the typecode and Table 1
+
+    size_t n = lmots_type_to_n(lmots_type);
+    size_t p = lmots_type_to_p(lmots_type);
+    size_t w = lmots_type_to_w(lmots_type);
+
+//     3. determine x, I and q from the private key
+
+    bytestring16 I;
+    check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I));
+
+    uint32_t q;
+    check(hal_xdr_decode_int(&keyptr, keylim, &q));
+
+    bytestring32 x[p];
+    for (size_t i = 0; i < p; ++i)
+        check(hal_xdr_decode_bytestring32(&keyptr, keylim, &x[i]));
+
+//     4. set C to a uniformly random n-byte string
+
+    bytestring32 C;
+    checkssl(RAND_bytes((unsigned char *)&C, n));
+
+//     5. compute the array y as follows:
+//        Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
+//        for ( i = 0; i < p; i = i + 1 ) {
+//          a = coef(Q || Cksm(Q), i, w)
+//          tmp = x[i]
+//          for ( j = 0; j < a; j = j + 1 ) {
+//             tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
+//          }
+//          y[i] = tmp
+//        }
+
+    SHA256_CTX ctx;
+    uint8_t Q[n + 2];           /* hash || 16-bit checksum */
+
+    checkssl(SHA256_Init(&ctx));
+    checkssl(SHA256_Update(&ctx, &I, sizeof(I)));
+    uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+    uint16_t s = u16str(D_MESG); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+    checkssl(SHA256_Update(&ctx, &C, sizeof(C)));
+    checkssl(SHA256_Update(&ctx, msg, msg_len));
+    checkssl(SHA256_Final((unsigned char *)Q, &ctx));
+
+    /* append checksum */
+    *(uint16_t *)&Q[n] = u16str(Cksm((uint8_t *)Q, lmots_type));
+
+    bytestring32 y[p];
+    for (size_t i = 0; i < p; ++i) {
+        size_t a = coef(Q, i, w);
+        bytestring32 tmp;
+        memcpy(&tmp, &x[i], sizeof(tmp));
+        for (size_t j = 0; j < a; ++j) {
+            checkssl(SHA256_Init(&ctx));
+            checkssl(SHA256_Update(&ctx, &I, sizeof(I)));
+            uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+            uint16_t s = u16str(i); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+            uint8_t b = u8str(j); checkssl(SHA256_Update(&ctx, &b, sizeof(b)));
+            checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp)));
+            checkssl(SHA256_Final((unsigned char *)&tmp, &ctx));
+        }
+        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, 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;
+}
+
+// 4.7.  Signature Verification
+
+static hal_error_t lmots_public_key_candidate(const lmots_algorithm_t pubtype,
+                                              const bytestring16 * const I, const size_t q,
+                                              const uint8_t * const msg, const size_t msg_len,
+                                              const uint8_t * const sig, const size_t sig_len,
+                                              bytestring32 * Kc);
+
+#if 0 /* unused */
+static hal_error_t lmots_verify(const uint8_t * const key, const size_t key_len,
+                                const uint8_t * const msg, const size_t msg_len,
+                                const uint8_t * const sig, const size_t sig_len)
+{
+    if (key == NULL || key_len < lmots_private_key_len(lmots_type) ||
+        msg == NULL || sig == NULL || sig_len < lmots_signature_len(lmots_type))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 4a: Verifying a Signature and Message Using a Public Key
+//
+//    1. if the public key is not at least four bytes long, return INVALID
+
+    if (key_len < 4)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//    2. parse pubtype, I, q, and K from the public key as follows:
+//       a. pubtype = strTou32(first 4 bytes of public key)
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    lmots_algorithm_t lmots_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type));
+
+    /* XXX missing from draft */
+    size_t n = lmots_type_to_n(lmots_type);
+
+//       b. if the public key is not exactly 24 + n bytes long,
+//          return INVALID
+
+    if (key_len != 24 + n)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//       c. I = next 16 bytes of public key
+
+    bytestring16 I;
+    check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I));
+
+//       d. q = strTou32(next 4 bytes of public key)
+
+    uint32_t q;
+    check(hal_xdr_decode_int(&keyptr, keylim, &q));
+
+//       e. K = next n bytes of public key
+
+    bytestring32 K;
+    check(hal_xdr_decode_bytestring32(&keyptr, keylim, &K));
+
+//    3. compute the public key candidate Kc from the signature,
+//       message, and the identifiers I and q obtained from the
+//       public key, using Algorithm 4b.  If Algorithm 4b returns
+//       INVALID, then return INVALID.
+
+    bytestring32 Kc;
+    check(lmots_public_key_candidate(lmots_type, &I, q, msg, msg_len, sig, sig_len, &Kc));
+
+//    4. if Kc is equal to K, return VALID; otherwise, return INVALID
+
+    return (memcmp(&Kc, &K, sizeof(Kc)) ? HAL_ERROR_INVALID_SIGNATURE : HAL_OK);
+}
+#endif
+
+static hal_error_t lmots_public_key_candidate(const lmots_algorithm_t lmots_type,
+                                              const bytestring16 * const I, const size_t q,
+                                              const uint8_t * const msg, const size_t msg_len,
+                                              const uint8_t * const sig, const size_t sig_len,
+                                              bytestring32 * const Kc)
+{
+    if (I == NULL || msg == NULL || sig == NULL || Kc == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 4b: Computing a Public Key Candidate Kc from a Signature,
+//   Message, Signature Typecode Type, and identifiers I, q
+//
+//  1. if the signature is not at least four bytes long, return INVALID
+
+    if (sig_len < 4)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//  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;
+
+    lmots_algorithm_t sigtype;
+    check(hal_xdr_decode_int(&sigptr, siglim, &sigtype));
+
+//     b. if sigtype is not equal to pubtype, return INVALID
+
+    if (sigtype != 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 = lmots_type_to_n(lmots_type);
+    size_t p = lmots_type_to_p(lmots_type);
+
+    if (sig_len != 4 + n * (p + 1))
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//     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
+//     Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
+//     for ( i = 0; i < p; i = i + 1 ) {
+//       a = coef(Q || Cksm(Q), i, w)
+//       tmp = y[i]
+//       for ( j = a; j < 2^w - 1; j = j + 1 ) {
+//          tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
+//       }
+//       z[i] = tmp
+//     }
+//     Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1])
+
+    SHA256_CTX ctx;
+    uint8_t Q[n + 2];           /* hash || 16-bit checksum */
+
+    checkssl(SHA256_Init(&ctx));
+    checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+    uint32_t l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+    uint16_t s = u16str(D_MESG); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+    checkssl(SHA256_Update(&ctx, &C, sizeof(C)));
+    checkssl(SHA256_Update(&ctx, msg, msg_len));
+    checkssl(SHA256_Final((unsigned char *)Q, &ctx));
+
+    /* append checksum */
+    *(uint16_t *)&Q[n] = u16str(Cksm((uint8_t *)Q, lmots_type));
+
+    size_t w = lmots_type_to_w(lmots_type);
+    bytestring32 z[p];
+
+    for (size_t i = 0; i < p; ++i) {
+        uint8_t a = coef(Q, i, w);
+        bytestring32 tmp;
+        memcpy(&tmp, &y[i], sizeof(tmp));
+        for (size_t j = (size_t)a; j < (1U << w) - 1; ++j) {
+            checkssl(SHA256_Init(&ctx));
+            checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+            l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+            s = u16str(i); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+            uint8_t b = u8str(j); checkssl(SHA256_Update(&ctx, &b, sizeof(b)));
+            checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp)));
+            checkssl(SHA256_Final((unsigned char *)&tmp, &ctx));
+        }
+        memcpy(&z[i], &tmp, sizeof(tmp));
+    }
+
+    checkssl(SHA256_Init(&ctx));
+    checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+    l = u32str(q); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+    s = u16str(D_PBLC); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+    for (size_t i = 0; i < p; ++i)
+        checkssl(SHA256_Update(&ctx, &z[i], sizeof(z[i])));
+    checkssl(SHA256_Final((unsigned char *)Kc, &ctx));
+
+//  4. return Kc
+
+    return HAL_OK;
+}
+
+/* ---------------------------------------------------------------- */
+
+// 5.  Leighton Micali Signatures
+
+// 5.1.  Parameters
+
+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 lms_type_to_m(const lms_algorithm_t lms_type)
+{
+    switch (lms_type) {
+    case lms_sha256_n32_h5:
+    case lms_sha256_n32_h10:
+    case lms_sha256_n32_h15:
+    case lms_sha256_n32_h20:
+    case lms_sha256_n32_h25: return 32;
+    default: return 0;
+    }
+}
+
+// 5.2.  LMS Private Key
+
+static inline size_t lms_private_key_len(const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type)
+{
+    /* u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1] */
+    return ((2 * sizeof(uint32_t)) + ((1 << lms_type_to_h(lms_type)) * lmots_private_key_len(lmots_type)));
+}
+
+static hal_error_t lms_generate_private_key(const lms_algorithm_t lms_type,
+                                            const lmots_algorithm_t lmots_type,
+                                            uint8_t * const key, size_t * const key_len, const size_t key_max)
+{
+    if (key == NULL || key_max < lms_private_key_len(lms_type, lmots_type))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   Algorithm 5: Computing an LMS Private Key.
+
+//      1. determine h and m from the typecode and Table 2.
+
+    size_t h = lms_type_to_h(lms_type);
+    /* XXX m is not used here */
+
+    /* XXX missing from draft: generate I for this keypair */
+    bytestring16 I;
+    checkssl(RAND_bytes((unsigned char *)&I, sizeof(I)));
+
+//      2. compute the array OTS_PRIV[] as follows:
+//         for ( q = 0; q < 2^h; q = q + 1) {
+//            OTS_PRIV[q] = LM-OTS private key with identifiers I, q
+//         }
+
+    /* initialize the key buffer with type and q=0, so we can generate the
+     * lmots private keys directly in the key buffer
+     */
+    uint8_t *keyptr = key;
+    uint8_t *keylim = key + key_max;
+    check(hal_xdr_encode_int(&keyptr, keylim, lms_type));
+    check(hal_xdr_encode_int(&keyptr, keylim, 0));
+
+    for (size_t q = 0; q < (1U << h); ++q) {
+        size_t ots_len;
+        check(lmots_generate_private_key(lmots_type, &I, q, keyptr, &ots_len, keylim - keyptr));
+        keyptr += ots_len;
+    }
+
+//      3. q = 0
+
+    /* XXX missing from draft: return the key in output format */
+    /* 4. return u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1] */
+
+    if (key_len != NULL)
+        *key_len = keyptr - key;
+
+    return HAL_OK;
+}
+
+// 5.3.  LMS Public Key
+
+static inline size_t lms_public_key_len(const lms_algorithm_t lms_type)
+{
+    /* u32str(type) || u32str(otstype) || I || T[1] */
+    return ((2 * sizeof(uint32_t)) + 16 + lms_type_to_m(lms_type));
+}
+
+static hal_error_t lms_generate_T(const lms_algorithm_t lms_type,
+                                  const lmots_algorithm_t lmots_type,
+                                  const bytestring16 * const I,
+                                  const uint8_t * const key,
+                                  bytestring32 * const T)
+{
+    size_t h = lms_type_to_h(lms_type);
+    size_t lmots_prv_len = lmots_private_key_len(lmots_type);
+    size_t lmots_pub_len = lmots_public_key_len(lmots_type);
+    const uint8_t *keyptr = key;
+    SHA256_CTX ctx;
+
+//  T[r]=/ H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h])   if r >= 2^h,
+//       \ H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1]) otherwise.
+
+    /* first generate the leaf-node T values */
+    for (size_t q = 0; q < (1U << h); ++q) {
+        /* generate OTS_PUB_HASH[q] */
+        size_t r = (1 << h) + q;
+        uint8_t pub[lmots_pub_len];
+        check(lmots_generate_public_key(keyptr, lmots_prv_len, pub, NULL, lmots_pub_len));
+        keyptr += lmots_prv_len;
+
+        checkssl(SHA256_Init(&ctx));
+        checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+        uint32_t l = u32str(r); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+        uint16_t s = u16str(D_LEAF); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+        checkssl(SHA256_Update(&ctx, &pub[24], sizeof(bytestring32)));
+        checkssl(SHA256_Final((unsigned char *)&T[r], &ctx));
+    }
+
+    /* then generate the rest of T[], from bottom to top */
+    for (size_t r = (1 << h) - 1; r > 0; --r) {
+        checkssl(SHA256_Init(&ctx));
+        checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+        uint32_t l = u32str(r); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+        uint16_t s = u16str(D_INTR); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+        checkssl(SHA256_Update(&ctx, &T[2*r], sizeof(T[r])));
+        checkssl(SHA256_Update(&ctx, &T[2*r+1], sizeof(T[r])));
+        checkssl(SHA256_Final((unsigned char *)&T[r], &ctx));
+    }
+
+    return HAL_OK;
+}
+
+static hal_error_t lms_generate_public_key(const uint8_t * const key, const size_t key_len,
+                                           uint8_t *pub, size_t *pub_len, const size_t pub_max)
+{
+    if (key == NULL ||  pub == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    /* private key format
+     * u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1]
+     */
+
+    lms_algorithm_t lms_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lms_type));
+    size_t h = lms_type_to_h(lms_type);
+
+    /* skip over q, which will be 0 */
+    keyptr += 4;
+
+    /* peek into the first lmots private key for type and I */
+    /* u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1] */
+    const uint8_t *lookahead = keyptr;
+    lmots_algorithm_t lmots_type;
+    bytestring16 I;
+    check(hal_xdr_decode_int(&lookahead, keylim, &lmots_type));
+    check(hal_xdr_decode_bytestring16(&lookahead, keylim, &I));
+
+//   The LMS public key is the string u32str(type) || u32str(otstype) || I || T[1].
+
+    uint8_t *pubptr = pub;
+    const uint8_t * const publim = pub + pub_max;
+    check(hal_xdr_encode_int(&pubptr, publim, lms_type));
+    check(hal_xdr_encode_int(&pubptr, publim, lmots_type));
+    check(hal_xdr_encode_bytestring16(&pubptr, publim, &I));
+    bytestring32 T[1 << (h + 1)];
+    check(lms_generate_T(lms_type, lmots_type, &I, keyptr, T));
+    check(hal_xdr_encode_bytestring32(&pubptr, publim, &T[1]));
+
+    if (pub_len != NULL)
+        *pub_len = pubptr - pub;
+
+    return HAL_OK;
+}
+
+// 5.4.  LMS Signature
+
+static inline size_t lms_signature_len(const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type)
+{
+    /* u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1] */
+    return ((2 * sizeof(uint32_t)) + lmots_signature_len(lmots_type) + (lms_type_to_h(lms_type) * lms_type_to_m(lms_type)));
+}
+
+static hal_error_t lms_sign(const uint8_t * const key, const size_t key_len,
+                            const uint8_t * const msg, const size_t msg_len,
+                            uint8_t *sig, size_t *sig_len, const size_t sig_max)
+{
+//   An LMS signature consists of
+//
+//      the number q of the leaf associated with the LM-OTS signature, as
+//      a four-byte unsigned integer in network byte order,
+//
+//      an LM-OTS signature, and
+//
+//      a typecode indicating the particular LMS algorithm,
+//
+//      an array of h m-byte values that is associated with the path
+//      through the tree from the leaf associated with the LM-OTS
+//      signature to the root.
+//
+//   Symbolically, the signature can be represented as u32str(q) ||
+//   ots_signature || u32str(type) || path[0] || path[1] || ... ||
+//   path[h-1].
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    /* private key format
+     * u32str(type) || u32str(q) || OTS_PRIV[0] || OTS_PRIV[1] || ... || OTS_PRIV[2^h - 1]
+     */
+
+    lms_algorithm_t lms_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lms_type));
+    size_t h = lms_type_to_h(lms_type);
+
+    uint32_t q;
+    check(hal_xdr_decode_int(&keyptr, keylim, &q));
+    if (q >= (1U << h))
+        return HAL_ERROR_HASHSIG_KEY_EXHAUSTED;
+
+    /* peek into the first lmots private key for lmots_type and I */
+    const uint8_t *lookahead = keyptr;
+    lmots_algorithm_t lmots_type;
+    check(hal_xdr_decode_int(&lookahead, keylim, &lmots_type));
+    bytestring16 I;
+    check(hal_xdr_decode_bytestring16(&lookahead, keylim, &I));
+
+    if (sig_max < lms_signature_len(lms_type, lmots_type))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_max;
+    check(hal_xdr_encode_int(&sigptr, siglim, q));
+
+    /* locate the lmots signing key OTS_PRIV[q] */
+    const size_t lmots_key_len = lmots_private_key_len(lmots_type);
+    const uint8_t * const lmots_key = keyptr + q * lmots_key_len;
+
+    /* generate the lmots signature */
+    size_t lmots_sig_len;
+    check(lmots_sign(lmots_key, lmots_key_len, msg, msg_len, sigptr, &lmots_sig_len, siglim - sigptr));
+    sigptr += lmots_sig_len;
+
+    check(hal_xdr_encode_int(&sigptr, siglim, lms_type));
+
+    /* generate the path array */
+    bytestring32 T[1 << (h + 1)];
+    check(lms_generate_T(lms_type, lmots_type, &I, keyptr, T));
+    for (size_t r = (1 << h) + q; r > 1; r /= 2)
+        check(hal_xdr_encode_bytestring32(&sigptr, siglim, ((r & 1) ? &T[r-1] : &T[r+1])));
+
+    if (sig_len != NULL)
+        *sig_len = sigptr - sig;
+
+    /* update q before returning the signature */
+    keyptr = key + 4;
+    check(hal_xdr_encode_int((uint8_t ** const)&keyptr, keylim, ++q));
+
+    return HAL_OK;
+}
+
+// 5.5.  LMS Signature Verification
+
+static hal_error_t lms_public_key_candidate(const lms_algorithm_t pubtype,
+                                            const lmots_algorithm_t pubotstype,
+                                            const bytestring16 * const I,
+                                            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 uint8_t * const key, const size_t key_len,
+                              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;
+
+//   Algorithm 6: LMS Signature Verification
+
+//     1. if the public key is not at least eight bytes long, return
+//        INVALID
+
+    if (key_len < 8)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//     2. parse pubtype, I, and T[1] from the public key as follows:
+//
+//        a. pubtype = strTou32(first 4 bytes of public key)
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    lms_algorithm_t pubtype;
+    check(hal_xdr_decode_int(&keyptr, keylim, &pubtype));
+
+//       b. ots_typecode = strTou32(next 4 bytes of public key)
+
+    lmots_algorithm_t pubotstype;
+    check(hal_xdr_decode_int(&keyptr, keylim, &pubotstype));
+
+//        c. set m according to pubtype, based on Table 2
+
+    size_t m = lms_type_to_m(pubtype);
+
+//        d. if the public key is not exactly 24 + m bytes
+//           long, return INVALID
+
+    if (key_len != 24 + m)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//        e. I = next 16 bytes of the public key
+
+    bytestring16 I;
+    check(hal_xdr_decode_bytestring16(&keyptr, keylim, &I));
+
+//        f. T[1] = next m bytes of the public key
+
+    bytestring32 T1;
+    check(hal_xdr_decode_bytestring32(&keyptr, keylim, &T1));
+
+//     3. compute the candidate LMS root value Tc from the signature,
+//        message, identifier and pubtype using Algorithm 6b.
+
+    bytestring32 Tc;
+    check(lms_public_key_candidate(pubtype, pubotstype, &I, msg, msg_len, sig, sig_len, &Tc));
+
+//     4. if Tc is equal to T[1], return VALID; otherwise, return INVALID
+
+    return (memcmp(&Tc, &T1, sizeof(Tc)) ? HAL_ERROR_INVALID_SIGNATURE : HAL_OK);
+}
+
+static hal_error_t lms_public_key_candidate(const lms_algorithm_t pubtype,
+                                            const lmots_algorithm_t pubotstype, // XXX missing from draft
+                                            const bytestring16 * const I,
+                                            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
+
+//  1. if the signature is not at least eight bytes long, return INVALID
+
+    if (sig_len < 8)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//  2. parse sigtype, q, ots_signature, and path from the signature as
+//     follows:
+    const uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_len;
+
+//    a. q = strTou32(first 4 bytes of signature)
+
+    uint32_t q;
+    check(hal_xdr_decode_int(&sigptr, siglim, &q));
+
+//    b. otssigtype = strTou32(next 4 bytes of signature)
+
+    lmots_algorithm_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 (otssigtype != pubotstype)
+        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
+
+    size_t n = lmots_type_to_n(otssigtype);
+    size_t p = lmots_type_to_p(otssigtype);
+    if (sig_len < 12 + n * (p + 1))
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//    e. ots_signature = bytes 8 through 8 + n * (p + 1) - 1 of signature
+
+    /* XXX 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(otssigtype);
+
+//    f. sigtype = strTou32(4 bytes of signature at location 8 + n * (p + 1))
+
+    lms_algorithm_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 (sigtype != pubtype)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//    g. set m, h according to sigtype and Table 2
+
+    size_t m = lms_type_to_m(sigtype);
+    size_t h = lms_type_to_h(sigtype);
+
+//    h. if q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID
+
+    if (q >= (1U << h) || sig_len != 12 + n * (p + 1) + m * h)
+        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
+
+    bytestring32 Kc;
+    check(lmots_public_key_candidate(pubotstype, I, q, msg, msg_len, ots_signature, lmots_signature_len(otssigtype), &Kc));
+
+//  4. compute the candidate LMS root value Tc as follows:
+//     node_num = 2^h + q
+    size_t r = (1 << h) + q;
+
+//     tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc)
+    bytestring32 tmp;
+    SHA256_CTX ctx;
+    checkssl(SHA256_Init(&ctx));
+    checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+    uint32_t l = u32str(r); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+    uint16_t s = u16str(D_LEAF); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+    checkssl(SHA256_Update(&ctx, &Kc, sizeof(Kc)));
+    checkssl(SHA256_Final((unsigned char *)&tmp, &ctx));
+
+//     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) {
+        checkssl(SHA256_Init(&ctx));
+        checkssl(SHA256_Update(&ctx, I, sizeof(*I)));
+        uint32_t l = u32str(r/2); checkssl(SHA256_Update(&ctx, &l, sizeof(l)));
+        uint16_t s = u16str(D_INTR); checkssl(SHA256_Update(&ctx, &s, sizeof(s)));
+        if (r & 1) {
+            checkssl(SHA256_Update(&ctx, &path[i], m));
+            checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp)));
+        }
+        else {
+            checkssl(SHA256_Update(&ctx, &tmp, sizeof(tmp)));
+            checkssl(SHA256_Update(&ctx, &path[i], m));
+        }
+        checkssl(SHA256_Final((unsigned char *)&tmp, &ctx));
+    }
+
+//     Tc = tmp
+    memcpy(Tc, &tmp, sizeof(*Tc));
+
+    return HAL_OK;
+}
+
+/* ---------------------------------------------------------------- */
+
+//6.  Hierarchical signatures
+
+// 6.1.  Key Generation
+
+static inline size_t hss_private_key_len(const size_t L, const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type)
+{
+    /* u32str(L) || lms_priv[0] || lms_priv[1] || ... || lms_priv[L-1] || sig[0] || pub[1] || ... || sig[L-2] || pub[L-1] */
+    return (4 + (L * lms_private_key_len(lms_type, lmots_type)) +
+            ((L - 1) * (lms_signature_len(lms_type, lmots_type) + lms_public_key_len(lms_type))));
+}
+
+static hal_error_t hss_generate_private_key(const size_t L,
+                                            const lms_algorithm_t lms_type,
+                                            const lmots_algorithm_t lmots_type,
+                                            uint8_t * const key, size_t * const key_len, const size_t key_max)
+{
+    if (L == 0 || L > 8 ||
+        lms_type < lms_sha256_n32_h5 || lms_type > lms_sha256_n32_h25 ||
+        lmots_type < lmots_sha256_n32_w1 || lmots_type > lmots_sha256_n32_w8 ||
+        key == NULL || key_max < hss_private_key_len(L, lms_type, lmots_type))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_max;
+
+//   The HSS private key consists of prv[0], ... , prv[L-1].
+    /* XXX This omits L */
+
+    check(hal_xdr_encode_int(&keyptr, keylim, L));
+
+    size_t lms_prv_len = lms_private_key_len(lms_type, lmots_type);
+    size_t lms_pub_len = lms_public_key_len(lms_type);
+    size_t lms_sig_len = lms_signature_len(lms_type, lmots_type);
+
+    for (size_t i = 0; i < L; ++i, keyptr += lms_prv_len) {
+        check(lms_generate_private_key(lms_type, lmots_type, keyptr, NULL, lms_prv_len));
+        if (i > 0) {
+            /* Generate the public key, and sign it with the previous private
+             * key. Stash the signed public keys at the end of the private
+             * key file, so we can copy them wholesale into the signature.
+             */
+            uint8_t *sigptr = key + 4 + (L * lms_prv_len) + ((i - 1) * (lms_sig_len + lms_pub_len));
+            uint8_t *pubptr = sigptr + lms_sig_len;
+            check(lms_generate_public_key(keyptr, lms_prv_len, pubptr, NULL, lms_pub_len));
+            check(lms_sign(keyptr - lms_prv_len, lms_prv_len, pubptr, lms_pub_len, sigptr, NULL, lms_sig_len));
+        }
+    }
+    keyptr += (L - 1) * (lms_sig_len + lms_pub_len);
+
+    if (key_len != NULL)
+        *key_len = keyptr - key;
+
+    return HAL_OK;
+}
+
+static inline size_t hss_public_key_len(const lms_algorithm_t lms_type)
+{
+    /* L || pub[0] */
+    return (sizeof(uint32_t) + lms_public_key_len(lms_type));
+}
+
+static hal_error_t hss_generate_public_key(const size_t L,
+                                           const lms_algorithm_t lms_type,
+                                           const lmots_algorithm_t lmots_type,
+                                           const uint8_t * const key, const size_t key_len,
+                                           uint8_t *pub, size_t *pub_len, const size_t pub_max)
+{
+    if (key == NULL || key_len < hss_private_key_len(L, lms_type, lmots_type) ||
+        pub == NULL || pub_max < hss_public_key_len(lms_type))
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+    uint8_t *pubptr = pub;
+    const uint8_t * const publim = pub + pub_max;
+
+//   The public key of the HSS scheme consists of the number of levels L,
+//   followed by pub[0], the public key of the top level.
+
+    uint32_t L_key;
+    check(hal_xdr_decode_int(&keyptr, keylim, &L_key));
+    if ((size_t)L_key != L)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    check(hal_xdr_encode_int(&pubptr, publim, L));
+
+    /* generate the lms public key from the first lms private key */
+    size_t len;
+    check(lms_generate_public_key(keyptr, lms_private_key_len(lms_type, lmots_type), pubptr, &len, publim - pubptr));
+    pubptr += len;
+
+    if (pub_len != NULL)
+        *pub_len = pubptr - pub;
+
+    return HAL_OK;
+}
+
+//6.2.  Signature Generation
+
+static inline size_t hss_signature_len(const size_t L, const lms_algorithm_t lms_type, const lmots_algorithm_t lmots_type)
+{
+    /* u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk] */
+    return (sizeof(uint32_t) +
+            (L * lms_signature_len(lms_type, lmots_type)) +
+            ((L - 1) * lms_public_key_len(lms_type)));
+}
+
+static hal_error_t hss_sign(const uint8_t * const key, const size_t key_len,
+                            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 || msg == NULL || sig == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+
+    /* private key format:
+     * u32str(L) || lms_priv[0] || lms_priv[1] || ... || lms_priv[L-1]
+     */
+
+    uint32_t L;
+    check(hal_xdr_decode_int(&keyptr, keylim, &L));
+
+    /* peek into the first lms private key for lms and lmots types */
+    lms_algorithm_t lms_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lms_type));
+    keyptr += 4;	/* skip over q */
+    lmots_algorithm_t lmots_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type));
+
+    size_t h = lms_type_to_h(lms_type);
+    size_t lms_prv_len = lms_private_key_len(lms_type, lmots_type);
+    size_t lms_pub_len = lms_public_key_len(lms_type);
+    size_t lms_sig_len = lms_signature_len(lms_type, lmots_type);
+
+//   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.
+
+    uint32_t q;
+    keyptr = key + 4 + ((L - 1) * lms_prv_len) + 4;
+    check(hal_xdr_decode_int_peek(&keyptr, keylim, &q));
+    if (q >= (1U << h)) {
+        size_t d;
+        for (d = L - 1; d > 0; --d) {
+            keyptr = key + 4 + ((d -1) * lms_prv_len) + 4;
+            check(hal_xdr_decode_int_peek(&keyptr, keylim, &q));
+            if (q < (1U << h))
+                break;
+        }
+        if (d == 0)
+            return HAL_ERROR_HASHSIG_KEY_EXHAUSTED;
+        for ( ; d < L; ++d) {
+            keyptr = key + 4 + (d * lms_prv_len);
+            /* generate the new private key */
+            check(lms_generate_private_key(lms_type, lmots_type, (uint8_t * const)keyptr, NULL, lms_prv_len));
+            /* generate the new signed public key, after all the private keys */
+            uint8_t *sigptr = (uint8_t *)key + 4 + (L * lms_prv_len) + ((d - 1) * (lms_sig_len + lms_pub_len));
+            uint8_t *pubptr = sigptr + lms_pub_len;
+            check(lms_generate_public_key(keyptr, lms_prv_len, pubptr, NULL, lms_pub_len));
+            check(lms_sign(keyptr - lms_prv_len, lms_prv_len, pubptr, lms_pub_len, sigptr, NULL, lms_sig_len));
+        }
+    }
+
+    uint8_t *sigptr = sig;
+    const uint8_t * const siglim = sig + sig_max;
+    check(hal_xdr_encode_int(&sigptr, siglim, L - 1));
+
+//      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].
+
+    /* copy the precomputed signed public keys from the end of the private key */
+    keyptr = key + 4 + (L * lms_prv_len);
+    check(hal_xdr_encode_fixed_opaque(&sigptr, siglim, keyptr, (L - 1) * (lms_sig_len + lms_pub_len)));
+
+    /* sign the message with the last lms private key */
+    keyptr -= lms_prv_len;
+    check(lms_sign(keyptr, lms_prv_len, msg, msg_len, sigptr, NULL, lms_sig_len));
+    sigptr += lms_sig_len;
+
+    if (sig_len != NULL)
+        *sig_len = sigptr - sig;
+
+    return HAL_OK;
+}
+
+//6.3.  Signature Verification
+
+static hal_error_t hss_verify(const uint8_t * const pub, const size_t pub_len,
+                              const uint8_t * const message, const size_t message_len,
+                              const uint8_t * const signature, const size_t signature_len)
+{
+    if (pub == NULL || message == NULL || signature == NULL)
+        return HAL_ERROR_BAD_ARGUMENTS;
+
+//   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)
+
+    const uint8_t * sigptr = signature;
+    const uint8_t * const siglim = signature + signature_len;
+    uint32_t Nspk;
+    check(hal_xdr_decode_int(&sigptr, siglim, &Nspk));
+
+//      if Nspk+1 is not equal to the number of levels L in pub:
+//         return INVALID
+
+    const uint8_t * pubptr = pub;
+    const uint8_t * const publim = pub + pub_len;
+    uint32_t L;
+    check(hal_xdr_decode_int(&pubptr, publim, &L));
+    if (Nspk + 1 != L)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//      key = pub
+    const uint8_t *key = pubptr; size_t key_len = pub_len - sizeof(uint32_t);
+    const uint8_t *sig; size_t sig_len;
+    const uint8_t *msg; size_t msg_len;
+
+//      for (i = 0; i < Nspk; i = i + 1) {
+    for (size_t i = 0; i < Nspk; ++i) {
+
+        /* peek into the lms public key for lms and lmots types */
+        const uint8_t *keyptr = key;
+        const uint8_t * const keylim = key + key_len;
+        lms_algorithm_t lms_type;
+        check(hal_xdr_decode_int(&keyptr, keylim, &lms_type));
+        lmots_algorithm_t lmots_type;
+        check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type));
+
+//         sig = next LMS signature parsed from S
+//         msg = next LMS public key parsed from S
+        sig = sigptr; sig_len = lms_signature_len(lms_type, lmots_type); sigptr += sig_len;
+        msg = sigptr; msg_len = lms_public_key_len(lms_type); sigptr += msg_len;
+
+        if (sigptr > siglim)
+            return HAL_ERROR_INVALID_SIGNATURE;
+
+//         if (lms_verify(msg, key, sig) != VALID):
+//             return INVALID
+        check(lms_verify(key, key_len, msg, msg_len, sig, sig_len));
+
+//         key = msg
+        key = msg; key_len = msg_len;
+//      }
+    }
+
+    /* peek into the lms public key for lms and lmots types */
+    const uint8_t *keyptr = key;
+    const uint8_t * const keylim = key + key_len;
+    lms_algorithm_t lms_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lms_type));
+    lmots_algorithm_t lmots_type;
+    check(hal_xdr_decode_int(&keyptr, keylim, &lmots_type));
+
+//      sig = next LMS signature parsed from S
+    sig = sigptr; sig_len = lms_signature_len(lms_type, lmots_type); sigptr += sig_len;
+
+    if (sigptr != siglim)
+        return HAL_ERROR_INVALID_SIGNATURE;
+
+//      return lms_verify(message, key, sig)
+    check(lms_verify(key, key_len, message, message_len, sig, sig_len));
+
+    return HAL_OK;
+}
+
+/* ---------------------------------------------------------------- */
+
+/*
+ * driver code, roughly like hash-sigs-c/demo.c
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <fcntl.h>
+
+static void hexdump(const char * const label, const void * const buf, const size_t len)
+{
+    printf("%-11s ", label);
+
+    const uint8_t *b = buf;
+    for (size_t i = 0; i < len; ++i, ++b) {
+        printf("%02x", *b);
+        if ((i & 0x0f) == 0x0f) {
+            printf("\n");
+            if (i < len - 1)
+                printf("            ");
+        }
+    }
+    if ((len & 0x0f) != 0)
+        printf("\n");
+}
+
+static hal_error_t dump_lmots_prv(const uint8_t * const buf, size_t * const len, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("lmots type", bufptr, 4);
+    uint32_t lmots_type;
+    check(hal_xdr_decode_int(&bufptr, buflim, &lmots_type));
+    hexdump("I", bufptr, 16);
+    bufptr += 16;
+    hexdump("q", bufptr, 4);
+    bufptr += 4;
+    size_t p = lmots_type_to_p(lmots_type);
+    for (size_t i = 0; i < p && bufptr < buflim; ++i) {
+        char label[16];
+        sprintf(label, "x[%lu]", i);
+        hexdump(label, bufptr, 32);
+        bufptr += 32;
+    }
+
+    if (len != NULL)
+        *len = bufptr - buf;
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_lmots_sig(const uint8_t * const buf, size_t * const len, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("lmots type", bufptr, 4);
+    uint32_t lmots_type;
+    check(hal_xdr_decode_int(&bufptr, buflim, &lmots_type));
+    hexdump("C", bufptr, 32);
+    bufptr += 32;
+    size_t p = lmots_type_to_p(lmots_type);
+    for (size_t i = 0; i < p && bufptr < buflim; ++i) {
+        char label[16];
+        sprintf(label, "y[%lu]", i);
+        hexdump(label, bufptr, 32);
+        bufptr += 32;
+    }
+
+    if (len != NULL)
+        *len = bufptr - buf;
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_lms_prv(const uint8_t * const buf, size_t * const len, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("lms type", bufptr, 4);
+    uint32_t lms_type;
+    check(hal_xdr_decode_int(&bufptr, buflim, &lms_type));
+    hexdump("q", bufptr, 4);
+    uint32_t q;
+    check(hal_xdr_decode_int(&bufptr, buflim, &q));
+    size_t h = lms_type_to_h(lms_type);
+    for (size_t i = 0; i < (1U << h) && bufptr < buflim; ++i) {
+        printf("--------------------------------------------\notsprv[%lu]\n", i);
+        size_t lmots_len;
+        check(dump_lmots_prv(bufptr, &lmots_len, buflim - bufptr));
+        bufptr += lmots_len;
+    }
+
+    if (len != NULL)
+        *len = bufptr - buf;
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_lms_pub(const uint8_t * const buf, size_t * const len, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("lms type", bufptr, 4);
+    uint32_t lms_type;
+    check(hal_xdr_decode_int(&bufptr, buflim, &lms_type));
+    hexdump("lmots type", bufptr, 4);
+    bufptr += 4;
+    hexdump("I", bufptr, 16);
+    bufptr += 16;
+    hexdump("T[1]", bufptr, 32);
+    bufptr += 32;
+
+    if (len != NULL)
+        *len = bufptr - buf;
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_lms_sig(const uint8_t * const buf, size_t * const len, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("q", bufptr, 4);
+    bufptr += 4;
+    size_t lmots_len;
+    check(dump_lmots_sig(bufptr, &lmots_len, buflim - bufptr));
+    bufptr += lmots_len;
+    hexdump("lms type", bufptr, 4);
+    uint32_t lms_type;
+    check(hal_xdr_decode_int(&bufptr, buflim, &lms_type));
+    size_t h = lms_type_to_h(lms_type);
+    for (size_t i = 0; i < h && bufptr < buflim; ++i) {
+        char label[16];
+        sprintf(label, "path[%lu]", i);
+        hexdump(label, bufptr, 32);
+        bufptr += 32;
+    }
+
+    if (len != NULL)
+        *len = bufptr - buf;
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_hss_prv(const uint8_t * const buf, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+    size_t len;
+
+    hexdump("L", bufptr, 4);
+    uint32_t L;
+    check(hal_xdr_decode_int(&bufptr, buflim, &L));
+
+    for (size_t i = 0; i < L && bufptr < buflim; ++i) {
+        printf("--------------------------------------------\nlmsprv[%lu]\n", i);
+        check(dump_lms_prv(bufptr, &len, buflim - bufptr));
+        bufptr += len;
+    }
+
+    printf("--------------------------------------------\n");
+    for (size_t i = 0; i < L - 1 && bufptr < buflim; ++i) {
+        printf("--------------------------------------------\nsig[%lu]\n", i);
+        check(dump_lms_sig(bufptr, &len, buflim - bufptr));
+        bufptr += len;
+        printf("--------------------------------------------\npub[%lu]\n", i + 1);
+        check(dump_lms_pub(bufptr, &len, buflim - bufptr));
+        bufptr += len;
+    }
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_hss_pub(const uint8_t * const buf, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("L", bufptr, 4);
+    uint32_t L;
+    check(hal_xdr_decode_int(&bufptr, buflim, &L));
+
+    printf("--------------------------------------------\npubkey[0]\n");
+    size_t lms_len;
+    check(dump_lms_pub(bufptr, &lms_len, buflim - bufptr));
+    bufptr += lms_len;
+
+    return HAL_OK;
+}
+
+static hal_error_t dump_hss_sig(const uint8_t * const buf, const size_t max)
+{
+    const uint8_t *bufptr = buf;
+    const uint8_t * const buflim = buf + max;
+
+    hexdump("Nspk", bufptr, 4);
+    uint32_t Nspk;
+    check(hal_xdr_decode_int(&bufptr, buflim, &Nspk));
+
+    for (size_t i = 0; i <= Nspk && bufptr < buflim; ++i) {
+        printf("--------------------------------------------\nsig[%lu]\n", i);
+        size_t lms_len;
+        check(dump_lms_sig(bufptr, &lms_len, buflim - bufptr));
+        bufptr += lms_len;
+        if (bufptr < buflim) {
+            printf("--------------------------------------------\npubkey[%lu]\n", i + 1);
+            check(dump_lms_pub(bufptr, &lms_len, buflim - bufptr));
+            bufptr += lms_len;
+        }
+    }
+
+    return HAL_OK;
+}
+
+int main(int argc, char *argv[])
+{
+    char usage[] = "\
+Usage: %s genkey <keyname> [parameters]\n\
+       %s sign <keyname> <files to sign>\n\
+       %s verify <keyname> <files to sign>\n";
+
+    int fd;
+    struct stat statbuf;
+    size_t len;
+    hal_error_t err;
+
+    if (argc < 3) {
+        fprintf(stderr, usage, argv[0], argv[0], argv[0]);
+        return 1;
+    }
+
+    if (strcmp(argv[1], "genkey") == 0) {
+        /* default parameter set */
+        size_t L = 2;
+        lms_algorithm_t lms_type = lms_sha256_n32_h5;
+        lmots_algorithm_t lmots_type = lmots_sha256_n32_w8;
+        if (argc > 3) {
+            int val[3];
+            for (int i = 0; i < 3; ++i) {
+                char *str = strtok(i == 0 ? argv[3] : NULL, "/");
+                if (str == NULL) {
+                    fprintf(stderr, "genkey parameters are of the form \"L/h/w\", e.g. \"3/10/4\"\n");
+                    return 1;
+                }
+                val[i] = atoi(str);
+            }
+            L = (size_t)val[0];
+            if (L < 1 || L > 8) {
+                fprintf(stderr, "unsupported value of L (%d), must be 1-8\n", val[0]);
+                return 1;
+            }
+            switch (val[1]) {
+            case 5: lms_type = lms_sha256_n32_h5; break;
+            case 10: lms_type = lms_sha256_n32_h10; break;
+            case 15: lms_type = lms_sha256_n32_h15; break;
+            case 20: lms_type = lms_sha256_n32_h20; break;
+            case 25: lms_type = lms_sha256_n32_h25; break;
+            default:
+                fprintf(stderr, "unsupported value of h (%d), must be 5,10,15,20,25\n", val[1]);
+                return 1;
+            }
+            switch (val[2]) {
+            case 1: lmots_type = lmots_sha256_n32_w1; break;
+            case 2: lmots_type = lmots_sha256_n32_w2; break;
+            case 4: lmots_type = lmots_sha256_n32_w4; break;
+            case 8: lmots_type = lmots_sha256_n32_w8; break;
+            default:
+                fprintf(stderr, "unsupported value of w (%d), must be 1,2,4,8\n", val[2]);
+                return 1;
+            }
+        }
+        uint8_t prv[hss_private_key_len(L, lms_type, lmots_type)];
+        size_t prv_len;
+        if ((err = hss_generate_private_key(L, lms_type, lmots_type, prv, &prv_len, sizeof(prv))) != HAL_OK) {
+            fprintf(stderr, "hss_generate_private_key: %s\n", hal_error_string(err));
+            return 1;
+        }
+        if (prv_len != sizeof(prv)) {
+            fprintf(stderr, "hss_generate_private_key returned length %lu, expected %lu\n", prv_len, sizeof(prv));
+            return 1;
+        }
+        char fn[strlen(argv[2]) + 5];
+        strcpy(fn, argv[2]);
+        strcat(fn, ".prv");
+        if ((fd = creat(fn, S_IRUSR|S_IWUSR)) == -1) {
+            perror("creat prv");
+            return 1;
+        }
+        if ((len = write(fd, prv, sizeof(prv))) != sizeof(prv)) {
+            fprintf(stderr, "write prv returned %lu, expected %lu\n", len, sizeof(prv));
+            return 1;
+        }
+        if (close(fd) != 0) {
+            perror("close prv");
+            return 1;
+        }
+        uint8_t pub[hss_public_key_len(lms_type)];
+        if ((err = hss_generate_public_key(L, lms_type, lmots_type, prv, sizeof(prv), pub, &len, sizeof(pub))) != HAL_OK) {
+            fprintf(stderr, "hss_generate_public_key: %s\n", hal_error_string(err));
+            return 1;
+        }
+        if (len != sizeof(pub)) {
+            fprintf(stderr, "hss_generate_public_key returned length %lu, expected %lu\n", len, sizeof(pub));
+            return 1;
+        }
+        strcpy(fn, argv[2]);
+        strcat(fn, ".pub");
+        if ((fd = creat(fn, S_IRUSR|S_IWUSR)) == -1) {
+            perror("creat pub");
+            return 1;
+        }
+        if ((len = write(fd, pub, sizeof(pub))) != sizeof(pub)) {
+            fprintf(stderr, "write pub returned %lu, expected %lu\n", len, sizeof(pub));
+            return 1;
+        }
+        if (close(fd) != 0) {
+            perror("close pub");
+            return 1;
+        }
+        return 0;
+    }
+
+    else if (strcmp(argv[1], "sign") == 0) {
+        if (argc < 4) {
+            fprintf(stderr, usage, argv[0], argv[0], argv[0]);
+            return 1;
+        }
+        char fn[strlen(argv[2]) + 5];
+        strcpy(fn, argv[2]);
+        strcat(fn, ".prv");
+        if (stat(fn, &statbuf) != 0) {
+            perror("stat prv");
+            return 1;
+        }
+        if ((fd = open(fn, O_RDONLY)) == -1) {
+            perror("open prv");
+            return 1;
+        }
+        uint8_t prv[statbuf.st_size];
+        if ((len = read(fd, prv, sizeof(prv))) != sizeof(prv)) {
+            fprintf(stderr, "read prv returned %lu, expected %lu\n", len, sizeof(prv));
+            return 1;
+        }
+        if (close(fd) != 0) {
+            perror("close prv");
+            return 1;
+        }
+        strcpy(fn, argv[2]);
+        strcat(fn, ".pub");
+        if (stat(fn, &statbuf) != 0) {
+            perror("stat pub");
+            return 1;
+        }
+        if ((fd = open(fn, O_RDONLY)) == -1) {
+            perror("open pub");
+            return 1;
+        }
+        uint8_t pub[statbuf.st_size];
+        if ((len = read(fd, pub, sizeof(pub))) != sizeof(pub)) {
+            fprintf(stderr, "read pub returned %lu, expected %lu\n", len, sizeof(pub));
+            return 1;
+        }
+        if (close(fd) != 0) {
+            perror("close pub");
+            return 1;
+        }
+        for (int i = 3; i < argc; ++i) {
+            char *fn = argv[i];
+            printf("signing %s\n", fn);
+            if (stat(fn, &statbuf) != 0) {
+                perror("stat msg");
+                return 1;
+            }
+            if ((fd = open(fn, O_RDONLY)) == -1) {
+                perror("open msg");
+                return 1;
+            }
+            uint8_t msg[statbuf.st_size];
+            if ((len = read(fd, msg, sizeof(msg))) != sizeof(msg)) {
+                fprintf(stderr, "read msg returned %lu, expected %lu\n", len, sizeof(msg));
+                return 1;
+            }
+            if (close(fd) != 0) {
+                perror("close msg");
+                return 1;
+            }
+            const uint8_t * pubptr = pub;
+            const uint8_t * const publim = pub + sizeof(pub);
+            uint32_t L;
+            check(hal_xdr_decode_int(&pubptr, publim, &L));
+            lms_algorithm_t lms_type;
+            check(hal_xdr_decode_int(&pubptr, publim, &lms_type));
+            lmots_algorithm_t lmots_type;
+            check(hal_xdr_decode_int(&pubptr, publim, &lmots_type));
+            uint8_t sig[hss_signature_len(L, lms_type, lmots_type)];
+            if ((err = hss_sign(prv, sizeof(prv), msg, sizeof(msg), sig, &len, sizeof(sig))) != HAL_OK) {
+                fprintf(stderr, "hss_sign: %s\n", hal_error_string(err));
+                return 1;
+            }
+            if (len != sizeof(sig)) {
+                fprintf(stderr, "hss_sign returned length %lu, expected %lu\n", len, sizeof(sig));
+                return 1;
+            }
+            char sn[strlen(fn) + 5];
+            strcpy(sn, fn);
+            strcat(sn, ".sig");
+            if ((fd = creat(sn, S_IRUSR|S_IWUSR)) == -1) {
+                perror("creat sig");
+                return 1;
+            }
+            if ((len = write(fd, sig, sizeof(sig))) != sizeof(sig)) {
+                fprintf(stderr, "write sig returned %lu, expected %lu\n", len, sizeof(sig));
+                return 1;
+            }
+            if (close(fd) != 0) {
+                perror("close sig");
+                return 1;
+            }
+        }
+        strcpy(fn, argv[2]);
+        strcat(fn, ".prv");
+        if ((fd = creat(fn, S_IRUSR|S_IWUSR)) == -1) {
+            perror("creat prv");
+            return 1;
+        }
+        if ((len = write(fd, prv, sizeof(prv))) != sizeof(prv)) {
+            fprintf(stderr, "write prv returned %lu, expected %lu\n", len, sizeof(prv));
+            return 1;
+        }
+        if (close(fd) != 0) {
+            perror("close prv");
+            return 1;
+        }
+        return 0;
+    }
+
+    else if (strcmp(argv[1], "verify") == 0) {
+        if (argc < 4) {
+            fprintf(stderr, usage, argv[0], argv[0], argv[0]);
+            return 1;
+        }
+        char fn[strlen(argv[2]) + 5];
+        strcpy(fn, argv[2]);
+        strcat(fn, ".pub");
+        if (stat(fn, &statbuf) != 0) {
+            perror("stat pub");
+            return 1;
+        }
+        if ((fd = open(fn, O_RDONLY)) == -1) {
+            perror("open pub");
+            return 1;
+        }
+        uint8_t pub[statbuf.st_size];
+        if ((len = read(fd, pub, sizeof(pub))) != sizeof(pub)) {
+            fprintf(stderr, "read pub returned %lu, expected %lu\n", len, sizeof(pub));
+            return 1;
+        }
+        if (close(fd) != 0) {
+            perror("close pub");
+            return 1;
+        }
+        int ret = 0;
+        for (int i = 3; i < argc; ++i) {
+            char *fn = argv[i];
+            printf("verifying %s\n", fn);
+            if (stat(fn, &statbuf) != 0) {
+                perror("stat msg");
+                return 1;
+            }
+            if ((fd = open(fn, O_RDONLY)) == -1) {
+                perror("open msg");
+                return 1;
+            }
+            uint8_t msg[statbuf.st_size];
+            if ((len = read(fd, msg, sizeof(msg))) != sizeof(msg)) {
+                fprintf(stderr, "read msg returned %lu, expected %lu\n", len, sizeof(msg));
+                return 1;
+            }
+            if (close(fd) != 0) {
+                perror("close msg");
+                return 1;
+            }
+            char sn[strlen(fn) + 5];
+            strcpy(sn, fn);
+            strcat(sn, ".sig");
+            if (stat(sn, &statbuf) != 0) {
+                perror("stat sig");
+                return 1;
+            }
+            uint8_t sig[statbuf.st_size];
+            if ((fd = open(sn, O_RDONLY)) == -1) {
+                perror("open sig");
+                return 1;
+            }
+            if ((len = read(fd, sig, sizeof(sig))) != sizeof(sig)) {
+                fprintf(stderr, "write sig returned %lu, expected %lu\n", len, sizeof(sig));
+                return 1;
+            }
+            if (close(fd) != 0) {
+                perror("close sig");
+                return 1;
+            }
+            if ((err = hss_verify(pub, sizeof(pub), msg, sizeof(msg), sig, sizeof(sig))) != HAL_OK) {
+                fprintf(stderr, "hss_verify: %s\n", hal_error_string(err));
+                ret++;
+            }
+            else
+                printf("signature verified\n");
+        }
+        return ret;
+    }
+
+    else if (strcmp(argv[1], "read") == 0) {
+        if (argc < 3) {
+            fprintf(stderr, usage, argv[0], argv[0], argv[0]);
+            return 1;
+        }
+        for (int i = 2; i < argc; ++i) {
+            char *fn = argv[i];
+            printf("reading %s\n", fn);
+            if (stat(fn, &statbuf) != 0) {
+                perror("stat");
+                return 1;
+            }
+            if ((fd = open(fn, O_RDONLY)) == -1) {
+                perror("open");
+                return 1;
+            }
+            uint8_t buf[statbuf.st_size];
+            if ((len = read(fd, buf, sizeof(buf))) != sizeof(buf)) {
+                fprintf(stderr, "read returned %lu, expected %lu\n", len, sizeof(buf));
+                return 1;
+            }
+            if (close(fd) != 0) {
+                perror("close");
+                return 1;
+            }
+            char *ext = strrchr(fn, '.');
+            if (strcmp(ext, ".prv") == 0) {
+                if (dump_hss_prv(buf, sizeof(buf)) != HAL_OK)
+                    return 1;
+            }
+            else if (strcmp(ext, ".pub") == 0) {
+                if (dump_hss_pub(buf, sizeof(buf)) != HAL_OK)
+                    return 1;
+            }
+            else if (strcmp(ext, ".sig") == 0) {
+                if (dump_hss_sig(buf, sizeof(buf)) != HAL_OK)
+                    return 1;
+            }
+            else {
+                fprintf(stderr, "unknown file type\n");
+                return 1;
+            }
+        }
+        return 0;
+    }
+
+    fprintf(stderr, usage, argv[0], argv[0], argv[0]);
+    return 1;
+}