upstream: Add experimental support for PQC XMSS keys (Extended

Hash-Based Signatures) The code is not compiled in by default (see WITH_XMSS
in Makefile.inc) Joint work with stefan-lukas_gazdag at genua.eu See
https://tools.ietf.org/html/draft-irtf-cfrg-xmss-hash-based-signatures-12 ok
djm@

OpenBSD-Commit-ID: ef3eccb96762a5d6f135d7daeef608df7776a7ac

33 files changed, 3657 insertions, 73 deletions

diff --git a/Makefile.in b/Makefile.in
index 2d26e83a..25d45eaf 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -62,6 +62,15 @@ MKDIR_P=@MKDIR_P@
 
 TARGETS=ssh$(EXEEXT) sshd$(EXEEXT) ssh-add$(EXEEXT) ssh-keygen$(EXEEXT) ssh-keyscan${EXEEXT} ssh-keysign${EXEEXT} ssh-pkcs11-helper$(EXEEXT) ssh-agent$(EXEEXT) scp$(EXEEXT) sftp-server$(EXEEXT) sftp$(EXEEXT)
 
+XMSS_OBJS=\
+	ssh-xmss.c \
+	sshkey-xmss.c \
+	xmss_commons.c \
+	xmss_fast.c \
+	xmss_hash.c \
+	xmss_hash_address.c \
+	xmss_wots.c
+
 LIBOPENSSH_OBJS=\
 	ssh_api.o \
 	ssherr.o \
@@ -71,7 +80,8 @@ LIBOPENSSH_OBJS=\
 	sshbuf-misc.o \
 	sshbuf-getput-crypto.o \
 	krl.o \
-	bitmap.o
+	bitmap.o \
+	${XMSS_OBJS}
 
 LIBSSH_OBJS=${LIBOPENSSH_OBJS} \
 	authfd.o authfile.o bufaux.o bufbn.o bufec.o buffer.o \
diff --git a/authfd.c b/authfd.c
index 148bc9bf..1eff7ba9 100644
--- a/authfd.c
+++ b/authfd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: authfd.c,v 1.107 2018/02/10 09:25:34 djm Exp $ */
+/* $OpenBSD: authfd.c,v 1.108 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -129,7 +129,7 @@ ssh_request_reply(int sock, struct sshbuf *request, struct sshbuf *reply)
 
 	/* Get the length of the message, and format it in the buffer. */
 	len = sshbuf_len(request);
-	put_u32(buf, len);
+	POKE_U32(buf, len);
 
 	/* Send the length and then the packet to the agent. */
 	if (atomicio(vwrite, sock, buf, 4) != 4 ||
@@ -144,7 +144,7 @@ ssh_request_reply(int sock, struct sshbuf *request, struct sshbuf *reply)
 	    return SSH_ERR_AGENT_COMMUNICATION;
 
 	/* Extract the length, and check it for sanity. */
-	len = get_u32(buf);
+	len = PEEK_U32(buf);
 	if (len > MAX_AGENT_REPLY_LEN)
 		return SSH_ERR_INVALID_FORMAT;
 
@@ -391,19 +391,7 @@ ssh_agent_sign(int sock, const struct sshkey *key,
 
 
 static int
-ssh_encode_identity_ssh2(struct sshbuf *b, const struct sshkey *key,
-    const char *comment)
-{
-	int r;
-
-	if ((r = sshkey_private_serialize(key, b)) != 0 ||
-	    (r = sshbuf_put_cstring(b, comment)) != 0)
-		return r;
-	return 0;
-}
-
-static int
-encode_constraints(struct sshbuf *m, u_int life, u_int confirm)
+encode_constraints(struct sshbuf *m, u_int life, u_int confirm, u_int maxsign)
 {
 	int r;
 
@@ -416,6 +404,11 @@ encode_constraints(struct sshbuf *m, u_int life, u_int confirm)
 		if ((r = sshbuf_put_u8(m, SSH_AGENT_CONSTRAIN_CONFIRM)) != 0)
 			goto out;
 	}
+	if (maxsign != 0) {
+		if ((r = sshbuf_put_u8(m, SSH_AGENT_CONSTRAIN_MAXSIGN)) != 0 ||
+		    (r = sshbuf_put_u32(m, maxsign)) != 0)
+			goto out;
+	}
 	r = 0;
  out:
 	return r;
@@ -427,10 +420,10 @@ encode_constraints(struct sshbuf *m, u_int life, u_int confirm)
  */
 int
 ssh_add_identity_constrained(int sock, const struct sshkey *key,
-    const char *comment, u_int life, u_int confirm)
+    const char *comment, u_int life, u_int confirm, u_int maxsign)
 {
 	struct sshbuf *msg;
-	int r, constrained = (life || confirm);
+	int r, constrained = (life || confirm || maxsign);
 	u_char type;
 
 	if ((msg = sshbuf_new()) == NULL)
@@ -447,11 +440,15 @@ ssh_add_identity_constrained(int sock, const struct sshkey *key,
 #endif
 	case KEY_ED25519:
 	case KEY_ED25519_CERT:
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
 		type = constrained ?
 		    SSH2_AGENTC_ADD_ID_CONSTRAINED :
 		    SSH2_AGENTC_ADD_IDENTITY;
 		if ((r = sshbuf_put_u8(msg, type)) != 0 ||
-		    (r = ssh_encode_identity_ssh2(msg, key, comment)) != 0)
+		    (r = sshkey_private_serialize_maxsign(key, msg, maxsign,
+		    NULL)) != 0 ||
+		    (r = sshbuf_put_cstring(msg, comment)) != 0)
 			goto out;
 		break;
 	default:
@@ -459,7 +456,7 @@ ssh_add_identity_constrained(int sock, const struct sshkey *key,
 		goto out;
 	}
 	if (constrained &&
-	    (r = encode_constraints(msg, life, confirm)) != 0)
+	    (r = encode_constraints(msg, life, confirm, maxsign)) != 0)
 		goto out;
 	if ((r = ssh_request_reply(sock, msg, msg)) != 0)
 		goto out;
@@ -537,7 +534,7 @@ ssh_update_card(int sock, int add, const char *reader_id, const char *pin,
 	    (r = sshbuf_put_cstring(msg, pin)) != 0)
 		goto out;
 	if (constrained &&
-	    (r = encode_constraints(msg, life, confirm)) != 0)
+	    (r = encode_constraints(msg, life, confirm, 0)) != 0)
 		goto out;
 	if ((r = ssh_request_reply(sock, msg, msg)) != 0)
 		goto out;
diff --git a/authfd.h b/authfd.h
index 41997ce6..ab954ffc 100644
--- a/authfd.h
+++ b/authfd.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: authfd.h,v 1.42 2018/02/10 09:25:34 djm Exp $ */
+/* $OpenBSD: authfd.h,v 1.43 2018/02/23 15:58:37 markus Exp $ */
 
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
@@ -30,7 +30,7 @@ int	ssh_lock_agent(int sock, int lock, const char *password);
 int	ssh_fetch_identitylist(int sock, struct ssh_identitylist **idlp);
 void	ssh_free_identitylist(struct ssh_identitylist *idl);
 int	ssh_add_identity_constrained(int sock, const struct sshkey *key,
-	    const char *comment, u_int life, u_int confirm);
+	    const char *comment, u_int life, u_int confirm, u_int maxsign);
 int	ssh_remove_identity(int sock, struct sshkey *key);
 int	ssh_update_card(int sock, int add, const char *reader_id,
 	    const char *pin, u_int life, u_int confirm);
@@ -77,6 +77,7 @@ int	ssh_agent_sign(int sock, const struct sshkey *key,
 
 #define	SSH_AGENT_CONSTRAIN_LIFETIME		1
 #define	SSH_AGENT_CONSTRAIN_CONFIRM		2
+#define	SSH_AGENT_CONSTRAIN_MAXSIGN		3
 
 /* extended failure messages */
 #define SSH2_AGENT_FAILURE			30
diff --git a/authfile.c b/authfile.c
index d09b700d..57dcd808 100644
--- a/authfile.c
+++ b/authfile.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: authfile.c,v 1.127 2017/07/01 13:50:45 djm Exp $ */
+/* $OpenBSD: authfile.c,v 1.128 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Copyright (c) 2000, 2013 Markus Friedl.  All rights reserved.
  *
@@ -191,6 +191,8 @@ sshkey_load_private_type(int type, const char *filename, const char *passphrase,
 		*perm_ok = 1;
 
 	r = sshkey_load_private_type_fd(fd, type, passphrase, keyp, commentp);
+	if (r == 0 && keyp && *keyp)
+		r = sshkey_set_filename(*keyp, filename);
  out:
 	close(fd);
 	return r;
@@ -249,6 +251,9 @@ sshkey_load_private(const char *filename, const char *passphrase,
 	    (r = sshkey_parse_private_fileblob(buffer, passphrase, keyp,
 	    commentp)) != 0)
 		goto out;
+	if (keyp && *keyp &&
+	    (r = sshkey_set_filename(*keyp, filename)) != 0)
+		goto out;
 	r = 0;
  out:
 	close(fd);
@@ -397,6 +402,7 @@ sshkey_load_private_cert(int type, const char *filename, const char *passphrase,
 	case KEY_ECDSA:
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519:
+	case KEY_XMSS:
 	case KEY_UNSPEC:
 		break;
 	default:
diff --git a/cipher.c b/cipher.c
index 9f454675..57876361 100644
--- a/cipher.c
+++ b/cipher.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: cipher.c,v 1.110 2018/02/13 03:36:56 djm Exp $ */
+/* $OpenBSD: cipher.c,v 1.111 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -401,7 +401,7 @@ cipher_get_length(struct sshcipher_ctx *cc, u_int *plenp, u_int seqnr,
 		    cp, len);
 	if (len < 4)
 		return SSH_ERR_MESSAGE_INCOMPLETE;
-	*plenp = get_u32(cp);
+	*plenp = PEEK_U32(cp);
 	return 0;
 }
 
diff --git a/dns.c b/dns.c
index 6e1abb53..ff1a2c41 100644
--- a/dns.c
+++ b/dns.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: dns.c,v 1.37 2017/09/14 04:32:21 djm Exp $ */
+/* $OpenBSD: dns.c,v 1.38 2018/02/23 15:58:37 markus Exp $ */
 
 /*
  * Copyright (c) 2003 Wesley Griffin. All rights reserved.
@@ -105,6 +105,11 @@ dns_read_key(u_int8_t *algorithm, u_int8_t *digest_type,
 		if (!*digest_type)
 			*digest_type = SSHFP_HASH_SHA256;
 		break;
+	case KEY_XMSS:
+		*algorithm = SSHFP_KEY_XMSS;
+		if (!*digest_type)
+			*digest_type = SSHFP_HASH_SHA256;
+		break;
 	default:
 		*algorithm = SSHFP_KEY_RESERVED; /* 0 */
 		*digest_type = SSHFP_HASH_RESERVED; /* 0 */
diff --git a/dns.h b/dns.h
index 68443f7c..91f3c632 100644
--- a/dns.h
+++ b/dns.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: dns.h,v 1.17 2017/09/14 04:32:21 djm Exp $ */
+/* $OpenBSD: dns.h,v 1.18 2018/02/23 15:58:37 markus Exp $ */
 
 /*
  * Copyright (c) 2003 Wesley Griffin. All rights reserved.
@@ -33,7 +33,8 @@ enum sshfp_types {
 	SSHFP_KEY_RSA = 1,
 	SSHFP_KEY_DSA = 2,
 	SSHFP_KEY_ECDSA = 3,
-	SSHFP_KEY_ED25519 = 4
+	SSHFP_KEY_ED25519 = 4,
+	SSHFP_KEY_XMSS = 5
 };
 
 enum sshfp_hashes {
diff --git a/pathnames.h b/pathnames.h
index 1c221b01..cb44caa4 100644
--- a/pathnames.h
+++ b/pathnames.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: pathnames.h,v 1.27 2017/05/05 10:42:49 naddy Exp $ */
+/* $OpenBSD: pathnames.h,v 1.28 2018/02/23 15:58:37 markus Exp $ */
 
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
@@ -39,6 +39,7 @@
 #define _PATH_HOST_DSA_KEY_FILE		SSHDIR "/ssh_host_dsa_key"
 #define _PATH_HOST_ECDSA_KEY_FILE	SSHDIR "/ssh_host_ecdsa_key"
 #define _PATH_HOST_ED25519_KEY_FILE	SSHDIR "/ssh_host_ed25519_key"
+#define _PATH_HOST_XMSS_KEY_FILE	SSHDIR "/ssh_host_xmss_key"
 #define _PATH_HOST_RSA_KEY_FILE		SSHDIR "/ssh_host_rsa_key"
 #define _PATH_DH_MODULI			SSHDIR "/moduli"
 
@@ -75,6 +76,7 @@
 #define _PATH_SSH_CLIENT_ID_ECDSA	_PATH_SSH_USER_DIR "/id_ecdsa"
 #define _PATH_SSH_CLIENT_ID_RSA		_PATH_SSH_USER_DIR "/id_rsa"
 #define _PATH_SSH_CLIENT_ID_ED25519	_PATH_SSH_USER_DIR "/id_ed25519"
+#define _PATH_SSH_CLIENT_ID_XMSS	_PATH_SSH_USER_DIR "/id_xmss"
 
 /*
  * Configuration file in user's home directory.  This file need not be
diff --git a/readconf.c b/readconf.c
index 56bff850..88051db5 100644
--- a/readconf.c
+++ b/readconf.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: readconf.c,v 1.282 2018/02/23 02:34:33 djm Exp $ */
+/* $OpenBSD: readconf.c,v 1.283 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -1943,6 +1943,7 @@ fill_default_options(Options * options)
 #endif
 		add_identity_file(options, "~/",
 		    _PATH_SSH_CLIENT_ID_ED25519, 0);
+		add_identity_file(options, "~/", _PATH_SSH_CLIENT_ID_XMSS, 0);
 	}
 	if (options->escape_char == -1)
 		options->escape_char = '~';
diff --git a/servconf.c b/servconf.c
index bf8ad671..c87a9a2b 100644
--- a/servconf.c
+++ b/servconf.c
@@ -1,5 +1,5 @@
 
-/* $OpenBSD: servconf.c,v 1.324 2018/02/16 02:32:40 djm Exp $ */
+/* $OpenBSD: servconf.c,v 1.325 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
  *                    All rights reserved
@@ -253,6 +253,8 @@ fill_default_server_options(ServerOptions *options)
 #endif
 		servconf_add_hostkey("[default]", 0, options,
 		    _PATH_HOST_ED25519_KEY_FILE);
+		servconf_add_hostkey("[default]", 0, options,
+		    _PATH_HOST_XMSS_KEY_FILE);
 	}
 	/* No certificates by default */
 	if (options->num_ports == 0)
diff --git a/ssh-add.c b/ssh-add.c
index 2afd4833..adcc4599 100644
--- a/ssh-add.c
+++ b/ssh-add.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-add.c,v 1.134 2017/08/29 09:42:29 dlg Exp $ */
+/* $OpenBSD: ssh-add.c,v 1.135 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -78,6 +78,7 @@ static char *default_files[] = {
 #endif
 #endif /* WITH_OPENSSL */
 	_PATH_SSH_CLIENT_ID_ED25519,
+	_PATH_SSH_CLIENT_ID_XMSS,
 	NULL
 };
 
@@ -89,6 +90,10 @@ static int lifetime = 0;
 /* User has to confirm key use */
 static int confirm = 0;
 
+/* Maximum number of signatures (XMSS) */
+static u_int maxsign = 0;
+static u_int minleft = 0;
+
 /* we keep a cache of one passphrase */
 static char *pass = NULL;
 static void
@@ -190,7 +195,10 @@ add_file(int agent_fd, const char *filename, int key_only, int qflag)
 	char *comment = NULL;
 	char msg[1024], *certpath = NULL;
 	int r, fd, ret = -1;
+	size_t i;
+	u_int32_t left;
 	struct sshbuf *keyblob;
+	struct ssh_identitylist *idlist;
 
 	if (strcmp(filename, "-") == 0) {
 		fd = STDIN_FILENO;
@@ -268,8 +276,40 @@ add_file(int agent_fd, const char *filename, int key_only, int qflag)
 		comment = xstrdup(filename);
 	sshbuf_free(keyblob);
 
+	/* For XMSS */
+	if ((r = sshkey_set_filename(private, filename)) != 0) {
+		fprintf(stderr, "Could not add filename to private key: %s (%s)\n",
+		    filename, comment);
+		goto out;
+	}
+	if (maxsign && minleft &&
+	    (r = ssh_fetch_identitylist(agent_fd, &idlist)) == 0) {
+		for (i = 0; i < idlist->nkeys; i++) {
+			if (!sshkey_equal_public(idlist->keys[i], private))
+				continue;
+			left = sshkey_signatures_left(idlist->keys[i]);
+			if (left < minleft) {
+				fprintf(stderr,
+				    "Only %d signatures left.\n", left);
+				break;
+			}
+			fprintf(stderr, "Skipping update: ");
+			if (left == minleft) {
+				fprintf(stderr,
+				   "required signatures left (%d).\n", left);
+			} else {
+				fprintf(stderr,
+				   "more signatures left (%d) than"
+				    " required (%d).\n", left, minleft);
+			}
+			ssh_free_identitylist(idlist);
+			goto out;
+		}
+		ssh_free_identitylist(idlist);
+	}
+
 	if ((r = ssh_add_identity_constrained(agent_fd, private, comment,
-	    lifetime, confirm)) == 0) {
+	    lifetime, confirm, maxsign)) == 0) {
 		fprintf(stderr, "Identity added: %s (%s)\n", filename, comment);
 		ret = 0;
 		if (lifetime != 0)
@@ -317,7 +357,7 @@ add_file(int agent_fd, const char *filename, int key_only, int qflag)
 	sshkey_free(cert);
 
 	if ((r = ssh_add_identity_constrained(agent_fd, private, comment,
-	    lifetime, confirm)) != 0) {
+	    lifetime, confirm, maxsign)) != 0) {
 		error("Certificate %s (%s) add failed: %s", certpath,
 		    private->cert->key_id, ssh_err(r));
 		goto out;
@@ -368,6 +408,7 @@ list_identities(int agent_fd, int do_fp)
 	char *fp;
 	int r;
 	struct ssh_identitylist *idlist;
+	u_int32_t left;
 	size_t i;
 
 	if ((r = ssh_fetch_identitylist(agent_fd, &idlist)) != 0) {
@@ -392,7 +433,12 @@ list_identities(int agent_fd, int do_fp)
 				    ssh_err(r));
 				continue;
 			}
-			fprintf(stdout, " %s\n", idlist->comments[i]);
+			fprintf(stdout, " %s", idlist->comments[i]);
+			left = sshkey_signatures_left(idlist->keys[i]);
+			if (left > 0)
+				fprintf(stdout,
+				    " [signatures left %d]", left);
+			fprintf(stdout, "\n");
 		}
 	}
 	ssh_free_identitylist(idlist);
@@ -454,6 +500,8 @@ usage(void)
 	fprintf(stderr, "  -L          List public key parameters of all identities.\n");
 	fprintf(stderr, "  -k          Load only keys and not certificates.\n");
 	fprintf(stderr, "  -c          Require confirmation to sign using identities\n");
+	fprintf(stderr, "  -m minleft  Maxsign is only changed if less than minleft are left (for XMSS)\n");
+	fprintf(stderr, "  -M maxsign  Maximum number of signatures allowed (for XMSS)\n");
 	fprintf(stderr, "  -t life     Set lifetime (in seconds) when adding identities.\n");
 	fprintf(stderr, "  -d          Delete identity.\n");
 	fprintf(stderr, "  -D          Delete all identities.\n");
@@ -500,7 +548,7 @@ main(int argc, char **argv)
 		exit(2);
 	}
 
-	while ((ch = getopt(argc, argv, "klLcdDxXE:e:qs:t:")) != -1) {
+	while ((ch = getopt(argc, argv, "klLcdDxXE:e:M:m:qs:t:")) != -1) {
 		switch (ch) {
 		case 'E':
 			fingerprint_hash = ssh_digest_alg_by_name(optarg);
@@ -525,6 +573,22 @@ main(int argc, char **argv)
 		case 'c':
 			confirm = 1;
 			break;
+		case 'm':
+			minleft = (int)strtonum(optarg, 1, UINT_MAX, NULL);
+			if (minleft == 0) {
+				usage();
+				ret = 1;
+				goto done;
+			}
+			break;
+		case 'M':
+			maxsign = (int)strtonum(optarg, 1, UINT_MAX, NULL);
+			if (maxsign == 0) {
+				usage();
+				ret = 1;
+				goto done;
+			}
+			break;
 		case 'd':
 			deleting = 1;
 			break;
diff --git a/ssh-agent.c b/ssh-agent.c
index 39888a72..2a4578b0 100644
--- a/ssh-agent.c
+++ b/ssh-agent.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-agent.c,v 1.227 2018/01/23 05:27:21 djm Exp $ */
+/* $OpenBSD: ssh-agent.c,v 1.228 2018/02/23 15:58:37 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -245,7 +245,8 @@ process_request_identities(SocketEntry *e)
 	    (r = sshbuf_put_u32(msg, idtab->nentries)) != 0)
 		fatal("%s: buffer error: %s", __func__, ssh_err(r));
 	TAILQ_FOREACH(id, &idtab->idlist, next) {
-		if ((r = sshkey_puts(id->key, msg)) != 0 ||
+		if ((r = sshkey_puts_opts(id->key, msg, SSHKEY_SERIALIZE_INFO))
+		     != 0 ||
 		    (r = sshbuf_put_cstring(msg, id->comment)) != 0) {
 			error("%s: put key/comment: %s", __func__,
 			    ssh_err(r));
@@ -402,7 +403,7 @@ process_add_identity(SocketEntry *e)
 {
 	Identity *id;
 	int success = 0, confirm = 0;
-	u_int seconds;
+	u_int seconds, maxsign;
 	char *comment = NULL;
 	time_t death = 0;
 	struct sshkey *k = NULL;
@@ -433,6 +434,18 @@ process_add_identity(SocketEntry *e)
 		case SSH_AGENT_CONSTRAIN_CONFIRM:
 			confirm = 1;
 			break;
+		case SSH_AGENT_CONSTRAIN_MAXSIGN:
+			if ((r = sshbuf_get_u32(e->request, &maxsign)) != 0) {
+				error("%s: bad maxsign constraint: %s",
+				    __func__, ssh_err(r));
+				goto err;
+			}
+			if ((r = sshkey_enable_maxsign(k, maxsign)) != 0) {
+				error("%s: cannot enable maxsign: %s",
+				    __func__, ssh_err(r));
+				goto err;
+			}
+			break;
 		default:
 			error("%s: Unknown constraint %d", __func__, ctype);
  err:
@@ -448,14 +461,15 @@ process_add_identity(SocketEntry *e)
 		death = monotime() + lifetime;
 	if ((id = lookup_identity(k)) == NULL) {
 		id = xcalloc(1, sizeof(Identity));
-		id->key = k;
 		TAILQ_INSERT_TAIL(&idtab->idlist, id, next);
 		/* Increment the number of identities. */
 		idtab->nentries++;
 	} else {
-		sshkey_free(k);
+		/* key state might have been updated */
+		sshkey_free(id->key);
 		free(id->comment);
 	}
+	id->key = k;
 	id->comment = comment;
 	id->death = death;
 	id->confirm = confirm;
diff --git a/ssh-keygen.c b/ssh-keygen.c
index 9812c0d2..d80930ee 100644
--- a/ssh-keygen.c
+++ b/ssh-keygen.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-keygen.c,v 1.312 2018/02/10 05:48:46 djm Exp $ */
+/* $OpenBSD: ssh-keygen.c,v 1.313 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1994 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -275,6 +275,10 @@ ask_filename(struct passwd *pw, const char *prompt)
 		case KEY_ED25519_CERT:
 			name = _PATH_SSH_CLIENT_ID_ED25519;
 			break;
+		case KEY_XMSS:
+		case KEY_XMSS_CERT:
+			name = _PATH_SSH_CLIENT_ID_XMSS;
+			break;
 		default:
 			fatal("bad key type");
 		}
@@ -969,6 +973,9 @@ do_gen_all_hostkeys(struct passwd *pw)
 #endif /* OPENSSL_HAS_ECC */
 #endif /* WITH_OPENSSL */
 		{ "ed25519", "ED25519",_PATH_HOST_ED25519_KEY_FILE },
+#ifdef WITH_XMSS
+		{ "xmss", "XMSS",_PATH_HOST_XMSS_KEY_FILE },
+#endif /* WITH_XMSS */
 		{ NULL, NULL, NULL }
 	};
 
@@ -1455,7 +1462,8 @@ do_change_comment(struct passwd *pw)
 		}
 	}
 
-	if (private->type != KEY_ED25519 && !use_new_format) {
+	if (private->type != KEY_ED25519 && private->type != KEY_XMSS &&
+	    !use_new_format) {
 		error("Comments are only supported for keys stored in "
 		    "the new format (-o).");
 		explicit_bzero(passphrase, strlen(passphrase));
@@ -1705,7 +1713,8 @@ do_ca_sign(struct passwd *pw, int argc, char **argv)
 			fatal("%s: unable to open \"%s\": %s",
 			    __func__, tmp, ssh_err(r));
 		if (public->type != KEY_RSA && public->type != KEY_DSA &&
-		    public->type != KEY_ECDSA && public->type != KEY_ED25519)
+		    public->type != KEY_ECDSA && public->type != KEY_ED25519 &&
+		    public->type != KEY_XMSS)
 			fatal("%s: key \"%s\" type %s cannot be certified",
 			    __func__, tmp, sshkey_type(public));
 
@@ -2405,7 +2414,7 @@ main(int argc, char **argv)
 			gen_all_hostkeys = 1;
 			break;
 		case 'b':
-			bits = (u_int32_t)strtonum(optarg, 256, 32768, &errstr);
+			bits = (u_int32_t)strtonum(optarg, 10, 32768, &errstr);
 			if (errstr)
 				fatal("Bits has bad value %s (%s)",
 					optarg, errstr);
@@ -2683,6 +2692,8 @@ main(int argc, char **argv)
 			    _PATH_HOST_ECDSA_KEY_FILE, rr_hostname);
 			n += do_print_resource_record(pw,
 			    _PATH_HOST_ED25519_KEY_FILE, rr_hostname);
+			n += do_print_resource_record(pw,
+			    _PATH_HOST_XMSS_KEY_FILE, rr_hostname);
 			if (n == 0)
 				fatal("no keys found.");
 			exit(0);
diff --git a/ssh-keyscan.c b/ssh-keyscan.c
index 15059f6f..53536860 100644
--- a/ssh-keyscan.c
+++ b/ssh-keyscan.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-keyscan.c,v 1.117 2018/02/23 05:14:05 djm Exp $ */
+/* $OpenBSD: ssh-keyscan.c,v 1.118 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Copyright 1995, 1996 by David Mazieres <dm@lcs.mit.edu>.
  *
@@ -58,9 +58,10 @@ int ssh_port = SSH_DEFAULT_PORT;
 #define KT_RSA		(1<<1)
 #define KT_ECDSA	(1<<2)
 #define KT_ED25519	(1<<3)
+#define KT_XMSS		(1<<4)
 
 #define KT_MIN		KT_DSA
-#define KT_MAX		KT_ED25519
+#define KT_MAX		KT_XMSS
 
 int get_cert = 0;
 int get_keytypes = KT_RSA|KT_ECDSA|KT_ED25519;
@@ -238,6 +239,10 @@ keygrab_ssh2(con *c)
 		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] = get_cert ?
 		    "ssh-ed25519-cert-v01@openssh.com" : "ssh-ed25519";
 		break;
+	case KT_XMSS:
+		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] = get_cert ?
+		    "ssh-xmss-cert-v01@openssh.com" : "ssh-xmss@openssh.com";
+		break;
 	case KT_ECDSA:
 		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] = get_cert ?
 		    "ecdsa-sha2-nistp256-cert-v01@openssh.com,"
@@ -718,6 +723,9 @@ main(int argc, char **argv)
 				case KEY_ED25519:
 					get_keytypes |= KT_ED25519;
 					break;
+				case KEY_XMSS:
+					get_keytypes |= KT_XMSS;
+					break;
 				case KEY_UNSPEC:
 				default:
 					fatal("Unknown key type \"%s\"", tname);
diff --git a/ssh-keysign.c b/ssh-keysign.c
index 17e87a28..78bb66b0 100644
--- a/ssh-keysign.c
+++ b/ssh-keysign.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-keysign.c,v 1.53 2018/02/07 22:52:45 dtucker Exp $ */
+/* $OpenBSD: ssh-keysign.c,v 1.54 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Copyright (c) 2002 Markus Friedl.  All rights reserved.
  *
@@ -171,7 +171,7 @@ main(int argc, char **argv)
 {
 	struct sshbuf *b;
 	Options options;
-#define NUM_KEYTYPES 4
+#define NUM_KEYTYPES 5
 	struct sshkey *keys[NUM_KEYTYPES], *key = NULL;
 	struct passwd *pw;
 	int r, key_fd[NUM_KEYTYPES], i, found, version = 2, fd;
@@ -198,6 +198,7 @@ main(int argc, char **argv)
 	key_fd[i++] = open(_PATH_HOST_DSA_KEY_FILE, O_RDONLY);
 	key_fd[i++] = open(_PATH_HOST_ECDSA_KEY_FILE, O_RDONLY);
 	key_fd[i++] = open(_PATH_HOST_ED25519_KEY_FILE, O_RDONLY);
+	key_fd[i++] = open(_PATH_HOST_XMSS_KEY_FILE, O_RDONLY);
 	key_fd[i++] = open(_PATH_HOST_RSA_KEY_FILE, O_RDONLY);
 
 	original_real_uid = getuid();	/* XXX readconf.c needs this */
diff --git a/ssh-xmss.c b/ssh-xmss.c
new file mode 100644
index 00000000..d9dafd76
--- /dev/null
+++ b/ssh-xmss.c
@@ -0,0 +1,188 @@
+/* $OpenBSD: ssh-xmss.c,v 1.1 2018/02/23 15:58:38 markus Exp $*/
+/*
+ * Copyright (c) 2017 Stefan-Lukas Gazdag.
+ * Copyright (c) 2017 Markus Friedl.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#define SSHKEY_INTERNAL
+#include <sys/types.h>
+#include <limits.h>
+
+#include <string.h>
+#include <stdarg.h>
+#include <unistd.h>
+
+#include "log.h"
+#include "sshbuf.h"
+#include "sshkey.h"
+#include "sshkey-xmss.h"
+#include "ssherr.h"
+#include "ssh.h"
+
+#include "xmss_fast.h"
+
+int
+ssh_xmss_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
+    const u_char *data, size_t datalen, u_int compat)
+{
+	u_char *sig = NULL;
+	size_t slen = 0, len = 0, required_siglen;
+	unsigned long long smlen;
+	int r, ret;
+	struct sshbuf *b = NULL;
+
+	if (lenp != NULL)
+		*lenp = 0;
+	if (sigp != NULL)
+		*sigp = NULL;
+
+	if (key == NULL ||
+	    sshkey_type_plain(key->type) != KEY_XMSS ||
+	    key->xmss_sk == NULL ||
+	    sshkey_xmss_params(key) == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshkey_xmss_siglen(key, &required_siglen)) != 0)
+		return r;
+	if (datalen >= INT_MAX - required_siglen)
+		return SSH_ERR_INVALID_ARGUMENT;
+	smlen = slen = datalen + required_siglen;
+	if ((sig = malloc(slen)) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	if ((r = sshkey_xmss_get_state(key, error)) != 0)
+		goto out;
+	if ((ret = xmss_sign(key->xmss_sk, sshkey_xmss_bds_state(key), sig, &smlen,
+	    data, datalen, sshkey_xmss_params(key))) != 0 || smlen <= datalen) {
+		r = SSH_ERR_INVALID_ARGUMENT; /* XXX better error? */
+		goto out;
+	}
+	/* encode signature */
+	if ((b = sshbuf_new()) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+	if ((r = sshbuf_put_cstring(b, "ssh-xmss@openssh.com")) != 0 ||
+	    (r = sshbuf_put_string(b, sig, smlen - datalen)) != 0)
+		goto out;
+	len = sshbuf_len(b);
+	if (sigp != NULL) {
+		if ((*sigp = malloc(len)) == NULL) {
+			r = SSH_ERR_ALLOC_FAIL;
+			goto out;
+		}
+		memcpy(*sigp, sshbuf_ptr(b), len);
+	}
+	if (lenp != NULL)
+		*lenp = len;
+	/* success */
+	r = 0;
+ out:
+	if ((ret = sshkey_xmss_update_state(key, error)) != 0) {
+		/* discard signature since we cannot update the state */
+		if (r == 0 && sigp != NULL && *sigp != NULL) {
+			explicit_bzero(*sigp, len);
+			free(*sigp);
+		}
+		if (sigp != NULL)
+			*sigp = NULL;
+		if (lenp != NULL)
+			*lenp = 0;
+		r = ret;
+	}
+	sshbuf_free(b);
+	if (sig != NULL) {
+		explicit_bzero(sig, slen);
+		free(sig);
+	}
+
+	return r;
+}
+
+int
+ssh_xmss_verify(const struct sshkey *key,
+    const u_char *signature, size_t signaturelen,
+    const u_char *data, size_t datalen, u_int compat)
+{
+	struct sshbuf *b = NULL;
+	char *ktype = NULL;
+	const u_char *sigblob;
+	u_char *sm = NULL, *m = NULL;
+	size_t len, required_siglen;
+	unsigned long long smlen = 0, mlen = 0;
+	int r, ret;
+
+	if (key == NULL ||
+	    sshkey_type_plain(key->type) != KEY_XMSS ||
+	    key->xmss_pk == NULL ||
+	    sshkey_xmss_params(key) == NULL ||
+	    signature == NULL || signaturelen == 0)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshkey_xmss_siglen(key, &required_siglen)) != 0)
+		return r;
+	if (datalen >= INT_MAX - required_siglen)
+		return SSH_ERR_INVALID_ARGUMENT;
+
+	if ((b = sshbuf_from(signature, signaturelen)) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	if ((r = sshbuf_get_cstring(b, &ktype, NULL)) != 0 ||
+	    (r = sshbuf_get_string_direct(b, &sigblob, &len)) != 0)
+		goto out;
+	if (strcmp("ssh-xmss@openssh.com", ktype) != 0) {
+		r = SSH_ERR_KEY_TYPE_MISMATCH;
+		goto out;
+	}
+	if (sshbuf_len(b) != 0) {
+		r = SSH_ERR_UNEXPECTED_TRAILING_DATA;
+		goto out;
+	}
+	if (len != required_siglen) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+	if (datalen >= SIZE_MAX - len) {
+		r = SSH_ERR_INVALID_ARGUMENT;
+		goto out;
+	}
+	smlen = len + datalen;
+	mlen = smlen;
+	if ((sm = malloc(smlen)) == NULL || (m = malloc(mlen)) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+	memcpy(sm, sigblob, len);
+	memcpy(sm+len, data, datalen);
+	if ((ret = xmss_sign_open(m, &mlen, sm, smlen,
+	    key->xmss_pk, sshkey_xmss_params(key))) != 0) {
+		debug2("%s: crypto_sign_xmss_open failed: %d",
+		    __func__, ret);
+	}
+	if (ret != 0 || mlen != datalen) {
+		r = SSH_ERR_SIGNATURE_INVALID;
+		goto out;
+	}
+	/* XXX compare 'm' and 'data' ? */
+	/* success */
+	r = 0;
+ out:
+	if (sm != NULL) {
+		explicit_bzero(sm, smlen);
+		free(sm);
+	}
+	if (m != NULL) {
+		explicit_bzero(m, smlen); /* NB mlen may be invalid if r != 0 */
+		free(m);
+	}
+	sshbuf_free(b);
+	free(ktype);
+	return r;
+}
diff --git a/ssh.c b/ssh.c
index fa57290b..d3619fe2 100644
--- a/ssh.c
+++ b/ssh.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh.c,v 1.474 2018/02/23 02:34:33 djm Exp $ */
+/* $OpenBSD: ssh.c,v 1.475 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -1384,7 +1384,7 @@ main(int ac, char **av)
 	sensitive_data.keys = NULL;
 	sensitive_data.external_keysign = 0;
 	if (options.hostbased_authentication) {
-		sensitive_data.nkeys = 9;
+		sensitive_data.nkeys = 11;
 		sensitive_data.keys = xcalloc(sensitive_data.nkeys,
 		    sizeof(struct sshkey));	/* XXX */
 		for (i = 0; i < sensitive_data.nkeys; i++)
@@ -1411,6 +1411,10 @@ main(int ac, char **av)
 		    _PATH_HOST_RSA_KEY_FILE, "", NULL, NULL);
 		sensitive_data.keys[8] = key_load_private_type(KEY_DSA,
 		    _PATH_HOST_DSA_KEY_FILE, "", NULL, NULL);
+		sensitive_data.keys[9] = key_load_private_cert(KEY_XMSS,
+		    _PATH_HOST_XMSS_KEY_FILE, "", NULL);
+		sensitive_data.keys[10] = key_load_private_type(KEY_XMSS,
+		    _PATH_HOST_XMSS_KEY_FILE, "", NULL, NULL);
 		PRIV_END;
 
 		if (options.hostbased_authentication == 1 &&
@@ -1418,7 +1422,8 @@ main(int ac, char **av)
 		    sensitive_data.keys[5] == NULL &&
 		    sensitive_data.keys[6] == NULL &&
 		    sensitive_data.keys[7] == NULL &&
-		    sensitive_data.keys[8] == NULL) {
+		    sensitive_data.keys[8] == NULL &&
+		    sensitive_data.keys[9] == NULL) {
 #ifdef OPENSSL_HAS_ECC
 			sensitive_data.keys[1] = key_load_cert(
 			    _PATH_HOST_ECDSA_KEY_FILE);
@@ -1439,6 +1444,10 @@ main(int ac, char **av)
 			    _PATH_HOST_RSA_KEY_FILE, NULL);
 			sensitive_data.keys[8] = key_load_public(
 			    _PATH_HOST_DSA_KEY_FILE, NULL);
+			sensitive_data.keys[9] = key_load_cert(
+			    _PATH_HOST_XMSS_KEY_FILE);
+			sensitive_data.keys[10] = key_load_public(
+			    _PATH_HOST_XMSS_KEY_FILE, NULL);
 			sensitive_data.external_keysign = 1;
 		}
 	}
diff --git a/sshconnect.c b/sshconnect.c
index 07eae09f..3805d35d 100644
--- a/sshconnect.c
+++ b/sshconnect.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect.c,v 1.296 2018/02/23 04:18:46 dtucker Exp $ */
+/* $OpenBSD: sshconnect.c,v 1.297 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -1475,6 +1475,7 @@ show_other_keys(struct hostkeys *hostkeys, struct sshkey *key)
 		KEY_DSA,
 		KEY_ECDSA,
 		KEY_ED25519,
+		KEY_XMSS,
 		-1
 	};
 	int i, ret = 0;
@@ -1592,7 +1593,7 @@ maybe_add_key_to_agent(char *authfile, const struct sshkey *private,
 	}
 
 	if ((r = ssh_add_identity_constrained(auth_sock, private, comment, 0,
-	    (options.add_keys_to_agent == 3))) == 0)
+	    (options.add_keys_to_agent == 3), 0)) == 0)
 		debug("identity added to agent: %s", authfile);
 	else
 		debug("could not add identity to agent: %s (%d)", authfile, r);
diff --git a/sshd.c b/sshd.c
index 7466d5a4..0b9a7ec4 100644
--- a/sshd.c
+++ b/sshd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshd.c,v 1.504 2018/02/11 21:16:56 dtucker Exp $ */
+/* $OpenBSD: sshd.c,v 1.505 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -705,6 +705,7 @@ list_hostkey_types(void)
 		case KEY_DSA:
 		case KEY_ECDSA:
 		case KEY_ED25519:
+		case KEY_XMSS:
 			if (buffer_len(&b) > 0)
 				buffer_append(&b, ",", 1);
 			p = key_ssh_name(key);
@@ -726,6 +727,7 @@ list_hostkey_types(void)
 		case KEY_DSA_CERT:
 		case KEY_ECDSA_CERT:
 		case KEY_ED25519_CERT:
+		case KEY_XMSS_CERT:
 			if (buffer_len(&b) > 0)
 				buffer_append(&b, ",", 1);
 			p = key_ssh_name(key);
@@ -752,6 +754,7 @@ get_hostkey_by_type(int type, int nid, int need_private, struct ssh *ssh)
 		case KEY_DSA_CERT:
 		case KEY_ECDSA_CERT:
 		case KEY_ED25519_CERT:
+		case KEY_XMSS_CERT:
 			key = sensitive_data.host_certificates[i];
 			break;
 		default:
@@ -1734,6 +1737,7 @@ main(int ac, char **av)
 		case KEY_DSA:
 		case KEY_ECDSA:
 		case KEY_ED25519:
+		case KEY_XMSS:
 			if (have_agent || key != NULL)
 				sensitive_data.have_ssh2_key = 1;
 			break;
diff --git a/sshkey-xmss.c b/sshkey-xmss.c
new file mode 100644
index 00000000..41cc1bad
--- /dev/null
+++ b/sshkey-xmss.c
@@ -0,0 +1,1048 @@
+/* $OpenBSD: sshkey-xmss.c,v 1.1 2018/02/23 15:58:38 markus Exp $ */
+/*
+ * Copyright (c) 2017 Markus Friedl.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 <sys/types.h>
+#include <sys/uio.h>
+
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <errno.h>
+
+#include "ssh2.h"
+#include "ssherr.h"
+#include "sshbuf.h"
+#include "cipher.h"
+#include "sshkey.h"
+#include "sshkey-xmss.h"
+#include "atomicio.h"
+
+#include "xmss_fast.h"
+
+/* opaque internal XMSS state */
+#define XMSS_MAGIC		"xmss-state-v1"
+#define XMSS_CIPHERNAME		"aes256-gcm@openssh.com"
+struct ssh_xmss_state {
+	xmss_params	params;
+	u_int32_t	n, w, h, k;
+
+	bds_state	bds;
+	u_char		*stack;
+	u_int32_t	stackoffset;
+	u_char		*stacklevels;
+	u_char		*auth;
+	u_char		*keep;
+	u_char		*th_nodes;
+	u_char		*retain;
+	treehash_inst	*treehash;
+
+	u_int32_t	idx;		/* state read from file */
+	u_int32_t	maxidx;		/* resticted # of signatures */
+	int		have_state;	/* .state file exists */
+	int		lockfd;		/* locked in sshkey_xmss_get_state() */
+	int		allow_update;	/* allow sshkey_xmss_update_state() */
+	char		*enc_ciphername;/* encrypt state with cipher */
+	u_char		*enc_keyiv;	/* encrypt state with key */
+	u_int32_t	enc_keyiv_len;	/* length of enc_keyiv */
+};
+
+int	 sshkey_xmss_init_bds_state(struct sshkey *);
+int	 sshkey_xmss_init_enc_key(struct sshkey *, const char *);
+void	 sshkey_xmss_free_bds(struct sshkey *);
+int	 sshkey_xmss_get_state_from_file(struct sshkey *, const char *,
+	    int *, sshkey_printfn *);
+int	 sshkey_xmss_encrypt_state(const struct sshkey *, struct sshbuf *,
+	    struct sshbuf **);
+int	 sshkey_xmss_decrypt_state(const struct sshkey *, struct sshbuf *,
+	    struct sshbuf **);
+int	 sshkey_xmss_serialize_enc_key(const struct sshkey *, struct sshbuf *);
+int	 sshkey_xmss_deserialize_enc_key(struct sshkey *, struct sshbuf *);
+
+#define PRINT(s...) do { if (pr) pr(s); } while (0)
+
+int
+sshkey_xmss_init(struct sshkey *key, const char *name)
+{
+	struct ssh_xmss_state *state;
+
+	if (key->xmss_state != NULL)
+		return SSH_ERR_INVALID_FORMAT;
+	if (name == NULL)
+		return SSH_ERR_INVALID_FORMAT;
+	state = calloc(sizeof(struct ssh_xmss_state), 1);
+	if (state == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	if (strcmp(name, XMSS_SHA2_256_W16_H10_NAME) == 0) {
+		state->n = 32;
+		state->w = 16;
+		state->h = 10;
+	} else if (strcmp(name, XMSS_SHA2_256_W16_H16_NAME) == 0) {
+		state->n = 32;
+		state->w = 16;
+		state->h = 16;
+	} else if (strcmp(name, XMSS_SHA2_256_W16_H20_NAME) == 0) {
+		state->n = 32;
+		state->w = 16;
+		state->h = 20;
+	} else {
+		free(state);
+		return SSH_ERR_KEY_TYPE_UNKNOWN;
+	}
+	if ((key->xmss_name = strdup(name)) == NULL) {
+		free(state);
+		return SSH_ERR_ALLOC_FAIL;
+	}
+	state->k = 2;	/* XXX hardcoded */
+	state->lockfd = -1;
+	if (xmss_set_params(&state->params, state->n, state->h, state->w,
+	    state->k) != 0) {
+		free(state);
+		return SSH_ERR_INVALID_FORMAT;
+	}
+	key->xmss_state = state;
+	return 0;
+}
+
+void
+sshkey_xmss_free_state(struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	sshkey_xmss_free_bds(key);
+	if (state) {
+		if (state->enc_keyiv) {
+			explicit_bzero(state->enc_keyiv, state->enc_keyiv_len);
+			free(state->enc_keyiv);
+		}
+		free(state->enc_ciphername);
+		free(state);
+	}
+	key->xmss_state = NULL;
+}
+
+#define SSH_XMSS_K2_MAGIC	"k=2"
+#define num_stack(x)		((x->h+1)*(x->n))
+#define num_stacklevels(x)	(x->h+1)
+#define num_auth(x)		((x->h)*(x->n))
+#define num_keep(x)		((x->h >> 1)*(x->n))
+#define num_th_nodes(x)		((x->h - x->k)*(x->n))
+#define num_retain(x)		(((1ULL << x->k) - x->k - 1) * (x->n))
+#define num_treehash(x)		((x->h) - (x->k))
+
+int
+sshkey_xmss_init_bds_state(struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+	u_int32_t i;
+
+	state->stackoffset = 0;
+	if ((state->stack = calloc(num_stack(state), 1)) == NULL ||
+	    (state->stacklevels = calloc(num_stacklevels(state), 1))== NULL ||
+	    (state->auth = calloc(num_auth(state), 1)) == NULL ||
+	    (state->keep = calloc(num_keep(state), 1)) == NULL ||
+	    (state->th_nodes = calloc(num_th_nodes(state), 1)) == NULL ||
+	    (state->retain = calloc(num_retain(state), 1)) == NULL ||
+	    (state->treehash = calloc(num_treehash(state),
+	    sizeof(treehash_inst))) == NULL) {
+		sshkey_xmss_free_bds(key);
+		return SSH_ERR_ALLOC_FAIL;
+	}
+	for (i = 0; i < state->h - state->k; i++)
+		state->treehash[i].node = &state->th_nodes[state->n*i];
+	xmss_set_bds_state(&state->bds, state->stack, state->stackoffset,
+	    state->stacklevels, state->auth, state->keep, state->treehash,
+	    state->retain, 0);
+	return 0;
+}
+
+void
+sshkey_xmss_free_bds(struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	if (state == NULL)
+		return;
+	free(state->stack);
+	free(state->stacklevels);
+	free(state->auth);
+	free(state->keep);
+	free(state->th_nodes);
+	free(state->retain);
+	free(state->treehash);
+	state->stack = NULL;
+	state->stacklevels = NULL;
+	state->auth = NULL;
+	state->keep = NULL;
+	state->th_nodes = NULL;
+	state->retain = NULL;
+	state->treehash = NULL;
+}
+
+void *
+sshkey_xmss_params(const struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	if (state == NULL)
+		return NULL;
+	return &state->params;
+}
+
+void *
+sshkey_xmss_bds_state(const struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	if (state == NULL)
+		return NULL;
+	return &state->bds;
+}
+
+int
+sshkey_xmss_siglen(const struct sshkey *key, size_t *lenp)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	if (lenp == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (state == NULL)
+		return SSH_ERR_INVALID_FORMAT;
+	*lenp = 4 + state->n +
+	    state->params.wots_par.keysize +
+	    state->h * state->n;
+	return 0;
+}
+
+size_t
+sshkey_xmss_pklen(const struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	if (state == NULL)
+		return 0;
+	return state->n * 2;
+}
+
+size_t
+sshkey_xmss_sklen(const struct sshkey *key)
+{
+	struct ssh_xmss_state *state = key->xmss_state;
+
+	if (state == NULL)
+		return 0;
+	return state->n * 4 + 4;
+}
+
+int
+sshkey_xmss_init_enc_key(struct sshkey *k, const char *ciphername)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	const struct sshcipher *cipher;
+	size_t keylen = 0, ivlen = 0;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((cipher = cipher_by_name(ciphername)) == NULL)
+		return SSH_ERR_INTERNAL_ERROR;
+	if ((state->enc_ciphername = strdup(ciphername)) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	keylen = cipher_keylen(cipher);
+	ivlen = cipher_ivlen(cipher);
+	state->enc_keyiv_len = keylen + ivlen;
+	if ((state->enc_keyiv = calloc(state->enc_keyiv_len, 1)) == NULL) {
+		free(state->enc_ciphername);
+		state->enc_ciphername = NULL;
+		return SSH_ERR_ALLOC_FAIL;
+	}
+	arc4random_buf(state->enc_keyiv, state->enc_keyiv_len);
+	return 0;
+}
+
+int
+sshkey_xmss_serialize_enc_key(const struct sshkey *k, struct sshbuf *b)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	int r;
+
+	if (state == NULL || state->enc_keyiv == NULL ||
+	    state->enc_ciphername == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshbuf_put_cstring(b, state->enc_ciphername)) != 0 ||
+	    (r = sshbuf_put_string(b, state->enc_keyiv,
+	    state->enc_keyiv_len)) != 0)
+		return r;
+	return 0;
+}
+
+int
+sshkey_xmss_deserialize_enc_key(struct sshkey *k, struct sshbuf *b)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	size_t len;
+	int r;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshbuf_get_cstring(b, &state->enc_ciphername, NULL)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->enc_keyiv, &len)) != 0)
+		return r;
+	state->enc_keyiv_len = len;
+	return 0;
+}
+
+int
+sshkey_xmss_serialize_pk_info(const struct sshkey *k, struct sshbuf *b,
+    enum sshkey_serialize_rep opts)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	u_char have_info = 1;
+	u_int32_t idx;
+	int r;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (opts != SSHKEY_SERIALIZE_INFO)
+		return 0;
+	idx = k->xmss_sk ? PEEK_U32(k->xmss_sk) : state->idx;
+	if ((r = sshbuf_put_u8(b, have_info)) != 0 ||
+	    (r = sshbuf_put_u32(b, idx)) != 0 ||
+	    (r = sshbuf_put_u32(b, state->maxidx)) != 0)
+		return r;
+	return 0;
+}
+
+int
+sshkey_xmss_deserialize_pk_info(struct sshkey *k, struct sshbuf *b)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	u_char have_info;
+	int r;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	/* optional */
+	if (sshbuf_len(b) == 0)
+		return 0;
+	if ((r = sshbuf_get_u8(b, &have_info)) != 0)
+		return r;
+	if (have_info != 1)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshbuf_get_u32(b, &state->idx)) != 0 ||
+	    (r = sshbuf_get_u32(b, &state->maxidx)) != 0)
+		return r;
+	return 0;
+}
+
+int
+sshkey_xmss_generate_private_key(struct sshkey *k, u_int bits)
+{
+	int r;
+	const char *name;
+
+	if (bits == 10) {
+		name = XMSS_SHA2_256_W16_H10_NAME;
+	} else if (bits == 16) {
+		name = XMSS_SHA2_256_W16_H16_NAME;
+	} else if (bits == 20) {
+		name = XMSS_SHA2_256_W16_H20_NAME;
+	} else {
+		name = XMSS_DEFAULT_NAME;
+	}
+	if ((r = sshkey_xmss_init(k, name)) != 0 ||
+	    (r = sshkey_xmss_init_bds_state(k)) != 0 ||
+	    (r = sshkey_xmss_init_enc_key(k, XMSS_CIPHERNAME)) != 0)
+		return r;
+	if ((k->xmss_pk = malloc(sshkey_xmss_pklen(k))) == NULL ||
+	    (k->xmss_sk = malloc(sshkey_xmss_sklen(k))) == NULL) {
+		return SSH_ERR_ALLOC_FAIL;
+	}
+	xmss_keypair(k->xmss_pk, k->xmss_sk, sshkey_xmss_bds_state(k),
+	    sshkey_xmss_params(k));
+	return 0;
+}
+
+int
+sshkey_xmss_get_state_from_file(struct sshkey *k, const char *filename,
+    int *have_file, sshkey_printfn *pr)
+{
+	struct sshbuf *b = NULL, *enc = NULL;
+	int ret = SSH_ERR_SYSTEM_ERROR, r, fd = -1;
+	u_int32_t len;
+	unsigned char buf[4], *data = NULL;
+
+	*have_file = 0;
+	if ((fd = open(filename, O_RDONLY)) >= 0) {
+		*have_file = 1;
+		if (atomicio(read, fd, buf, sizeof(buf)) != sizeof(buf)) {
+			PRINT("%s: corrupt state file: %s", __func__, filename);
+			goto done;
+		}
+		len = PEEK_U32(buf);
+		if ((data = calloc(len, 1)) == NULL) {
+			ret = SSH_ERR_ALLOC_FAIL;
+			goto done;
+		}
+		if (atomicio(read, fd, data, len) != len) {
+			PRINT("%s: cannot read blob: %s", __func__, filename);
+			goto done;
+		}
+		if ((enc = sshbuf_from(data, len)) == NULL) {
+			ret = SSH_ERR_ALLOC_FAIL;
+			goto done;
+		}
+		sshkey_xmss_free_bds(k);
+		if ((r = sshkey_xmss_decrypt_state(k, enc, &b)) != 0) {
+			ret = r;
+			goto done;
+		}
+		if ((r = sshkey_xmss_deserialize_state(k, b)) != 0) {
+			ret = r;
+			goto done;
+		}
+		ret = 0;
+	}
+done:
+	if (fd != -1)
+		close(fd);
+	free(data);
+	sshbuf_free(enc);
+	sshbuf_free(b);
+	return ret;
+}
+
+int
+sshkey_xmss_get_state(const struct sshkey *k, sshkey_printfn *pr)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	u_int32_t idx = 0;
+	char *filename = NULL;
+	char *statefile = NULL, *ostatefile = NULL, *lockfile = NULL;
+	int lockfd = -1, have_state = 0, have_ostate, tries = 0;
+	int ret = SSH_ERR_INVALID_ARGUMENT, r;
+
+	if (state == NULL)
+		goto done;
+	/*
+	 * If maxidx is set, then we are allowed a limited number
+	 * of signatures, but don't need to access the disk.
+	 * Otherwise we need to deal with the on-disk state.
+	 */
+	if (state->maxidx) {
+		/* xmss_sk always contains the current state */
+		idx = PEEK_U32(k->xmss_sk);
+		if (idx < state->maxidx) {
+			state->allow_update = 1;
+			return 0;
+		}
+		return SSH_ERR_INVALID_ARGUMENT;
+	}
+	if ((filename = k->xmss_filename) == NULL)
+		goto done;
+	if (asprintf(&lockfile, "%s.lock", filename) < 0 ||
+	    asprintf(&statefile, "%s.state", filename) < 0 ||
+	    asprintf(&ostatefile, "%s.ostate", filename) < 0) {
+		ret = SSH_ERR_ALLOC_FAIL;
+		goto done;
+	}
+	if ((lockfd = open(lockfile, O_CREAT|O_RDONLY, 0600)) < 0) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: cannot open/create: %s", __func__, lockfile);
+		goto done;
+	}
+	while (flock(lockfd, LOCK_EX|LOCK_NB) < 0) {
+		if (errno != EWOULDBLOCK) {
+			ret = SSH_ERR_SYSTEM_ERROR;
+			PRINT("%s: cannot lock: %s", __func__, lockfile);
+			goto done;
+		}
+		if (++tries > 10) {
+			ret = SSH_ERR_SYSTEM_ERROR;
+			PRINT("%s: giving up on: %s", __func__, lockfile);
+			goto done;
+		}
+		usleep(1000*100*tries);
+	}
+	/* XXX no longer const */
+	if ((r = sshkey_xmss_get_state_from_file((struct sshkey *)k,
+	    statefile, &have_state, pr)) != 0) {
+		if ((r = sshkey_xmss_get_state_from_file((struct sshkey *)k,
+		    ostatefile, &have_ostate, pr)) == 0) {
+			state->allow_update = 1;
+			r = sshkey_xmss_forward_state(k, 1);
+			state->idx = PEEK_U32(k->xmss_sk);
+			state->allow_update = 0;
+		}
+	}
+	if (!have_state && !have_ostate) {
+		/* check that bds state is initialized */
+		if (state->bds.auth == NULL)
+			goto done;
+		PRINT("%s: start from scratch idx 0: %u", __func__, state->idx);
+	} else if (r != 0) {
+		ret = r;
+		goto done;
+	}
+	if (state->idx + 1 < state->idx) {
+		PRINT("%s: state wrap: %u", __func__, state->idx);
+		goto done;
+	}
+	state->have_state = have_state;
+	state->lockfd = lockfd;
+	state->allow_update = 1;
+	lockfd = -1;
+	ret = 0;
+done:
+	if (lockfd != -1)
+		close(lockfd);
+	free(lockfile);
+	free(statefile);
+	free(ostatefile);
+	return ret;
+}
+
+int
+sshkey_xmss_forward_state(const struct sshkey *k, u_int32_t reserve)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	u_char *sig = NULL;
+	size_t required_siglen;
+	unsigned long long smlen;
+	u_char data;
+	int ret, r;
+
+	if (state == NULL || !state->allow_update)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (reserve == 0)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (state->idx + reserve <= state->idx)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshkey_xmss_siglen(k, &required_siglen)) != 0)
+		return r;
+	if ((sig = malloc(required_siglen)) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	while (reserve-- > 0) {
+		state->idx = PEEK_U32(k->xmss_sk);
+		smlen = required_siglen;
+		if ((ret = xmss_sign(k->xmss_sk, sshkey_xmss_bds_state(k),
+		    sig, &smlen, &data, 0, sshkey_xmss_params(k))) != 0) {
+			r = SSH_ERR_INVALID_ARGUMENT;
+			break;
+		}
+	}
+	free(sig);
+	return r;
+}
+
+int
+sshkey_xmss_update_state(const struct sshkey *k, sshkey_printfn *pr)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	struct sshbuf *b = NULL, *enc = NULL;
+	u_int32_t idx = 0;
+	unsigned char buf[4];
+	char *filename = NULL;
+	char *statefile = NULL, *ostatefile = NULL, *nstatefile = NULL;
+	int fd = -1;
+	int ret = SSH_ERR_INVALID_ARGUMENT;
+
+	if (state == NULL || !state->allow_update)
+		return ret;
+	if (state->maxidx) {
+		/* no update since the number of signatures is limited */
+		ret = 0;
+		goto done;
+	}
+	idx = PEEK_U32(k->xmss_sk);
+	if (idx == state->idx) {
+		/* no signature happend, no need to update */
+		ret = 0;
+		goto done;
+	} else if (idx != state->idx + 1) {
+		PRINT("%s: more than one signature happened: idx %u state %u",
+		     __func__, idx, state->idx);
+		goto done;
+	}
+	state->idx = idx;
+	if ((filename = k->xmss_filename) == NULL)
+		goto done;
+	if (asprintf(&statefile, "%s.state", filename) < 0 ||
+	    asprintf(&ostatefile, "%s.ostate", filename) < 0 ||
+	    asprintf(&nstatefile, "%s.nstate", filename) < 0) {
+		ret = SSH_ERR_ALLOC_FAIL;
+		goto done;
+	}
+	unlink(nstatefile);
+	if ((b = sshbuf_new()) == NULL) {
+		ret = SSH_ERR_ALLOC_FAIL;
+		goto done;
+	}
+	if ((ret = sshkey_xmss_serialize_state(k, b)) != 0) {
+		PRINT("%s: SERLIALIZE FAILED: %d", __func__, ret);
+		goto done;
+	}
+	if ((ret = sshkey_xmss_encrypt_state(k, b, &enc)) != 0) {
+		PRINT("%s: ENCRYPT FAILED: %d", __func__, ret);
+		goto done;
+	}
+	if ((fd = open(nstatefile, O_CREAT|O_WRONLY|O_EXCL, 0600)) < 0) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: open new state file: %s", __func__, nstatefile);
+		goto done;
+	}
+	POKE_U32(buf, sshbuf_len(enc));
+	if (atomicio(vwrite, fd, buf, sizeof(buf)) != sizeof(buf)) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: write new state file hdr: %s", __func__, nstatefile);
+		close(fd);
+		goto done;
+	}
+	if (atomicio(vwrite, fd, (void *)sshbuf_ptr(enc), sshbuf_len(enc)) !=
+	    sshbuf_len(enc)) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: write new state file data: %s", __func__, nstatefile);
+		close(fd);
+		goto done;
+	}
+	if (fsync(fd) < 0) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: sync new state file: %s", __func__, nstatefile);
+		close(fd);
+		goto done;
+	}
+	if (close(fd) < 0) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: close new state file: %s", __func__, nstatefile);
+		goto done;
+	}
+	if (state->have_state) {
+		unlink(ostatefile);
+		if (link(statefile, ostatefile)) {
+			ret = SSH_ERR_SYSTEM_ERROR;
+			PRINT("%s: backup state %s to %s", __func__, statefile,
+			    ostatefile);
+			goto done;
+		}
+	}
+	if (rename(nstatefile, statefile) < 0) {
+		ret = SSH_ERR_SYSTEM_ERROR;
+		PRINT("%s: rename %s to %s", __func__, nstatefile, statefile);
+		goto done;
+	}
+	ret = 0;
+done:
+	if (state->lockfd != -1) {
+		close(state->lockfd);
+		state->lockfd = -1;
+	}
+	if (nstatefile)
+		unlink(nstatefile);
+	free(statefile);
+	free(ostatefile);
+	free(nstatefile);
+	sshbuf_free(b);
+	sshbuf_free(enc);
+	return ret;
+}
+
+int
+sshkey_xmss_serialize_state(const struct sshkey *k, struct sshbuf *b)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	treehash_inst *th;
+	u_int32_t i, node;
+	int r;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (state->stack == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	state->stackoffset = state->bds.stackoffset;	/* copy back */
+	if ((r = sshbuf_put_cstring(b, SSH_XMSS_K2_MAGIC)) != 0 ||
+	    (r = sshbuf_put_u32(b, state->idx)) != 0 ||
+	    (r = sshbuf_put_string(b, state->stack, num_stack(state))) != 0 ||
+	    (r = sshbuf_put_u32(b, state->stackoffset)) != 0 ||
+	    (r = sshbuf_put_string(b, state->stacklevels, num_stacklevels(state))) != 0 ||
+	    (r = sshbuf_put_string(b, state->auth, num_auth(state))) != 0 ||
+	    (r = sshbuf_put_string(b, state->keep, num_keep(state))) != 0 ||
+	    (r = sshbuf_put_string(b, state->th_nodes, num_th_nodes(state))) != 0 ||
+	    (r = sshbuf_put_string(b, state->retain, num_retain(state))) != 0 ||
+	    (r = sshbuf_put_u32(b, num_treehash(state))) != 0)
+		return r;
+	for (i = 0; i < num_treehash(state); i++) {
+		th = &state->treehash[i];
+		node = th->node - state->th_nodes;
+		if ((r = sshbuf_put_u32(b, th->h)) != 0 ||
+		    (r = sshbuf_put_u32(b, th->next_idx)) != 0 ||
+		    (r = sshbuf_put_u32(b, th->stackusage)) != 0 ||
+		    (r = sshbuf_put_u8(b, th->completed)) != 0 ||
+		    (r = sshbuf_put_u32(b, node)) != 0)
+			return r;
+	}
+	return 0;
+}
+
+int
+sshkey_xmss_serialize_state_opt(const struct sshkey *k, struct sshbuf *b,
+    enum sshkey_serialize_rep opts)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	int r = SSH_ERR_INVALID_ARGUMENT;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((r = sshbuf_put_u8(b, opts)) != 0)
+		return r;
+	switch (opts) {
+	case SSHKEY_SERIALIZE_STATE:
+		r = sshkey_xmss_serialize_state(k, b);
+		break;
+	case SSHKEY_SERIALIZE_FULL:
+		if ((r = sshkey_xmss_serialize_enc_key(k, b)) != 0)
+			break;
+		r = sshkey_xmss_serialize_state(k, b);
+		break;
+	case SSHKEY_SERIALIZE_DEFAULT:
+		r = 0;
+		break;
+	default:
+		r = SSH_ERR_INVALID_ARGUMENT;
+		break;
+	}
+	return r;
+}
+
+int
+sshkey_xmss_deserialize_state(struct sshkey *k, struct sshbuf *b)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	treehash_inst *th;
+	u_int32_t i, lh, node;
+	size_t ls, lsl, la, lk, ln, lr;
+	char *magic;
+	int r;
+
+	if (state == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (k->xmss_sk == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((state->treehash = calloc(num_treehash(state),
+	    sizeof(treehash_inst))) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	if ((r = sshbuf_get_cstring(b, &magic, NULL)) != 0 ||
+	    (r = sshbuf_get_u32(b, &state->idx)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->stack, &ls)) != 0 ||
+	    (r = sshbuf_get_u32(b, &state->stackoffset)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->stacklevels, &lsl)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->auth, &la)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->keep, &lk)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->th_nodes, &ln)) != 0 ||
+	    (r = sshbuf_get_string(b, &state->retain, &lr)) != 0 ||
+	    (r = sshbuf_get_u32(b, &lh)) != 0)
+		return r;
+	if (strcmp(magic, SSH_XMSS_K2_MAGIC) != 0)
+		return SSH_ERR_INVALID_ARGUMENT;
+	/* XXX check stackoffset */
+	if (ls != num_stack(state) ||
+	    lsl != num_stacklevels(state) ||
+	    la != num_auth(state) ||
+	    lk != num_keep(state) ||
+	    ln != num_th_nodes(state) ||
+	    lr != num_retain(state) ||
+	    lh != num_treehash(state))
+		return SSH_ERR_INVALID_ARGUMENT;
+	for (i = 0; i < num_treehash(state); i++) {
+		th = &state->treehash[i];
+		if ((r = sshbuf_get_u32(b, &th->h)) != 0 ||
+		    (r = sshbuf_get_u32(b, &th->next_idx)) != 0 ||
+		    (r = sshbuf_get_u32(b, &th->stackusage)) != 0 ||
+		    (r = sshbuf_get_u8(b, &th->completed)) != 0 ||
+		    (r = sshbuf_get_u32(b, &node)) != 0)
+			return r;
+		if (node < num_th_nodes(state))
+			th->node = &state->th_nodes[node];
+	}
+	POKE_U32(k->xmss_sk, state->idx);
+	xmss_set_bds_state(&state->bds, state->stack, state->stackoffset,
+	    state->stacklevels, state->auth, state->keep, state->treehash,
+	    state->retain, 0);
+	return 0;
+}
+
+int
+sshkey_xmss_deserialize_state_opt(struct sshkey *k, struct sshbuf *b)
+{
+	enum sshkey_serialize_rep opts;
+	u_char have_state;
+	int r;
+
+	if ((r = sshbuf_get_u8(b, &have_state)) != 0)
+		return r;
+
+	opts = have_state;
+	switch (opts) {
+	case SSHKEY_SERIALIZE_DEFAULT:
+		r = 0;
+		break;
+	case SSHKEY_SERIALIZE_STATE:
+		if ((r = sshkey_xmss_deserialize_state(k, b)) != 0)
+			return r;
+		break;
+	case SSHKEY_SERIALIZE_FULL:
+		if ((r = sshkey_xmss_deserialize_enc_key(k, b)) != 0 ||
+		    (r = sshkey_xmss_deserialize_state(k, b)) != 0)
+			return r;
+		break;
+	default:
+		r = SSH_ERR_INVALID_FORMAT;
+		break;
+	}
+	return r;
+}
+
+int
+sshkey_xmss_encrypt_state(const struct sshkey *k, struct sshbuf *b,
+   struct sshbuf **retp)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	struct sshbuf *encrypted = NULL, *encoded = NULL, *padded = NULL;
+	struct sshcipher_ctx *ciphercontext = NULL;
+	const struct sshcipher *cipher;
+	u_char *cp, *key, *iv = NULL;
+	size_t i, keylen, ivlen, blocksize, authlen, encrypted_len, aadlen;
+	int r = SSH_ERR_INTERNAL_ERROR;
+
+	if (retp != NULL)
+		*retp = NULL;
+	if (state == NULL ||
+	    state->enc_keyiv == NULL ||
+	    state->enc_ciphername == NULL)
+		return SSH_ERR_INTERNAL_ERROR;
+	if ((cipher = cipher_by_name(state->enc_ciphername)) == NULL) {
+		r = SSH_ERR_INTERNAL_ERROR;
+		goto out;
+	}
+	blocksize = cipher_blocksize(cipher);
+	keylen = cipher_keylen(cipher);
+	ivlen = cipher_ivlen(cipher);
+	authlen = cipher_authlen(cipher);
+	if (state->enc_keyiv_len != keylen + ivlen) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+	key = state->enc_keyiv;
+	if ((encrypted = sshbuf_new()) == NULL ||
+	    (encoded = sshbuf_new()) == NULL ||
+	    (padded = sshbuf_new()) == NULL ||
+	    (iv = malloc(ivlen)) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+
+	/* replace first 4 bytes of IV with index to ensure uniqueness */
+	memcpy(iv, key + keylen, ivlen);
+	POKE_U32(iv, state->idx);
+
+	if ((r = sshbuf_put(encoded, XMSS_MAGIC, sizeof(XMSS_MAGIC))) != 0 ||
+	    (r = sshbuf_put_u32(encoded, state->idx)) != 0)
+		goto out;
+
+	/* padded state will be encrypted */
+	if ((r = sshbuf_putb(padded, b)) != 0)
+		goto out;
+	i = 0;
+	while (sshbuf_len(padded) % blocksize) {
+		if ((r = sshbuf_put_u8(padded, ++i & 0xff)) != 0)
+			goto out;
+	}
+	encrypted_len = sshbuf_len(padded);
+
+	/* header including the length of state is used as AAD */
+	if ((r = sshbuf_put_u32(encoded, encrypted_len)) != 0)
+		goto out;
+	aadlen = sshbuf_len(encoded);
+
+	/* concat header and state */
+	if ((r = sshbuf_putb(encoded, padded)) != 0)
+		goto out;
+
+	/* reserve space for encryption of encoded data plus auth tag */
+	/* encrypt at offset addlen */
+	if ((r = sshbuf_reserve(encrypted,
+	    encrypted_len + aadlen + authlen, &cp)) != 0 ||
+	    (r = cipher_init(&ciphercontext, cipher, key, keylen,
+	    iv, ivlen, 1)) != 0 ||
+	    (r = cipher_crypt(ciphercontext, 0, cp, sshbuf_ptr(encoded),
+	    encrypted_len, aadlen, authlen)) != 0)
+		goto out;
+
+	/* success */
+	r = 0;
+ out:
+	if (retp != NULL) {
+		*retp = encrypted;
+		encrypted = NULL;
+	}
+	sshbuf_free(padded);
+	sshbuf_free(encoded);
+	sshbuf_free(encrypted);
+	cipher_free(ciphercontext);
+	free(iv);
+	return r;
+}
+
+int
+sshkey_xmss_decrypt_state(const struct sshkey *k, struct sshbuf *encoded,
+   struct sshbuf **retp)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	struct sshbuf *copy = NULL, *decrypted = NULL;
+	struct sshcipher_ctx *ciphercontext = NULL;
+	const struct sshcipher *cipher = NULL;
+	u_char *key, *iv = NULL, *dp;
+	size_t keylen, ivlen, authlen, aadlen;
+	u_int blocksize, encrypted_len, index;
+	int r = SSH_ERR_INTERNAL_ERROR;
+
+	if (retp != NULL)
+		*retp = NULL;
+	if (state == NULL ||
+	    state->enc_keyiv == NULL ||
+	    state->enc_ciphername == NULL)
+		return SSH_ERR_INTERNAL_ERROR;
+	if ((cipher = cipher_by_name(state->enc_ciphername)) == NULL) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+	blocksize = cipher_blocksize(cipher);
+	keylen = cipher_keylen(cipher);
+	ivlen = cipher_ivlen(cipher);
+	authlen = cipher_authlen(cipher);
+	if (state->enc_keyiv_len != keylen + ivlen) {
+		r = SSH_ERR_INTERNAL_ERROR;
+		goto out;
+	}
+	key = state->enc_keyiv;
+
+	if ((copy = sshbuf_fromb(encoded)) == NULL ||
+	    (decrypted = sshbuf_new()) == NULL ||
+	    (iv = malloc(ivlen)) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+
+	/* check magic */
+	if (sshbuf_len(encoded) < sizeof(XMSS_MAGIC) ||
+	    memcmp(sshbuf_ptr(encoded), XMSS_MAGIC, sizeof(XMSS_MAGIC))) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+	/* parse public portion */
+	if ((r = sshbuf_consume(encoded, sizeof(XMSS_MAGIC))) != 0 ||
+	    (r = sshbuf_get_u32(encoded, &index)) != 0 ||
+	    (r = sshbuf_get_u32(encoded, &encrypted_len)) != 0)
+		goto out;
+
+	/* check size of encrypted key blob */
+	if (encrypted_len < blocksize || (encrypted_len % blocksize) != 0) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+	/* check that an appropriate amount of auth data is present */
+	if (sshbuf_len(encoded) < encrypted_len + authlen) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+
+	aadlen = sshbuf_len(copy) - sshbuf_len(encoded);
+
+	/* replace first 4 bytes of IV with index to ensure uniqueness */
+	memcpy(iv, key + keylen, ivlen);
+	POKE_U32(iv, index);
+
+	/* decrypt private state of key */
+	if ((r = sshbuf_reserve(decrypted, aadlen + encrypted_len, &dp)) != 0 ||
+	    (r = cipher_init(&ciphercontext, cipher, key, keylen,
+	    iv, ivlen, 0)) != 0 ||
+	    (r = cipher_crypt(ciphercontext, 0, dp, sshbuf_ptr(copy),
+	    encrypted_len, aadlen, authlen)) != 0)
+		goto out;
+
+	/* there should be no trailing data */
+	if ((r = sshbuf_consume(encoded, encrypted_len + authlen)) != 0)
+		goto out;
+	if (sshbuf_len(encoded) != 0) {
+		r = SSH_ERR_INVALID_FORMAT;
+		goto out;
+	}
+
+	/* remove AAD */
+	if ((r = sshbuf_consume(decrypted, aadlen)) != 0)
+		goto out;
+	/* XXX encrypted includes unchecked padding */
+
+	/* success */
+	r = 0;
+	if (retp != NULL) {
+		*retp = decrypted;
+		decrypted = NULL;
+	}
+ out:
+	cipher_free(ciphercontext);
+	sshbuf_free(copy);
+	sshbuf_free(decrypted);
+	free(iv);
+	return r;
+}
+
+u_int32_t
+sshkey_xmss_signatures_left(const struct sshkey *k)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+	u_int32_t idx;
+
+	if (sshkey_type_plain(k->type) == KEY_XMSS && state &&
+	    state->maxidx) {
+		idx = k->xmss_sk ? PEEK_U32(k->xmss_sk) : state->idx;
+		if (idx < state->maxidx)
+			return state->maxidx - idx;
+	}
+	return 0;
+}
+
+int
+sshkey_xmss_enable_maxsign(struct sshkey *k, u_int32_t maxsign)
+{
+	struct ssh_xmss_state *state = k->xmss_state;
+
+	if (sshkey_type_plain(k->type) != KEY_XMSS)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (maxsign == 0)
+		return 0;
+	if (state->idx + maxsign < state->idx)
+		return SSH_ERR_INVALID_ARGUMENT;
+	state->maxidx = state->idx + maxsign;
+	return 0;
+}
diff --git a/sshkey-xmss.h b/sshkey-xmss.h
new file mode 100644
index 00000000..b9f8ead1
--- /dev/null
+++ b/sshkey-xmss.h
@@ -0,0 +1,56 @@
+/* $OpenBSD: sshkey-xmss.h,v 1.1 2018/02/23 15:58:38 markus Exp $ */
+/*
+ * Copyright (c) 2017 Markus Friedl.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 SSHKEY_XMSS_H
+#define SSHKEY_XMSS_H
+
+#define XMSS_SHA2_256_W16_H10_NAME "XMSS_SHA2-256_W16_H10"
+#define XMSS_SHA2_256_W16_H16_NAME "XMSS_SHA2-256_W16_H16"
+#define XMSS_SHA2_256_W16_H20_NAME "XMSS_SHA2-256_W16_H20"
+#define XMSS_DEFAULT_NAME	   XMSS_SHA2_256_W16_H10_NAME
+
+size_t	 sshkey_xmss_pklen(const struct sshkey *);
+size_t	 sshkey_xmss_sklen(const struct sshkey *);
+int	 sshkey_xmss_init(struct sshkey *, const char *);
+void	 sshkey_xmss_free_state(struct sshkey *);
+int	 sshkey_xmss_generate_private_key(struct sshkey *, u_int);
+int	 sshkey_xmss_serialize_state(const struct sshkey *, struct sshbuf *);
+int	 sshkey_xmss_serialize_state_opt(const struct sshkey *, struct sshbuf *,
+            enum sshkey_serialize_rep);
+int	 sshkey_xmss_serialize_pk_info(const struct sshkey *, struct sshbuf *,
+	    enum sshkey_serialize_rep);
+int	 sshkey_xmss_deserialize_state(struct sshkey *, struct sshbuf *);
+int	 sshkey_xmss_deserialize_state_opt(struct sshkey *, struct sshbuf *);
+int	 sshkey_xmss_deserialize_pk_info(struct sshkey *, struct sshbuf *);
+
+int	 sshkey_xmss_siglen(const struct sshkey *, size_t *);
+void	*sshkey_xmss_params(const struct sshkey *);
+void	*sshkey_xmss_bds_state(const struct sshkey *);
+int	 sshkey_xmss_get_state(const struct sshkey *, sshkey_printfn *);
+int	 sshkey_xmss_enable_maxsign(struct sshkey *, u_int32_t);
+int	 sshkey_xmss_forward_state(const struct sshkey *, u_int32_t);
+int	 sshkey_xmss_update_state(const struct sshkey *, sshkey_printfn *);
+u_int32_t sshkey_xmss_signatures_left(const struct sshkey *);
+
+#endif /* SSHKEY_XMSS_H */
diff --git a/sshkey.c b/sshkey.c
index 0e146d4d..d8ee70ca 100644
--- a/sshkey.c
+++ b/sshkey.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshkey.c,v 1.61 2018/02/14 16:03:32 jsing Exp $ */
+/* $OpenBSD: sshkey.c,v 1.62 2018/02/23 15:58:38 markus Exp $ */
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
  * Copyright (c) 2008 Alexander von Gernler.  All rights reserved.
@@ -55,8 +55,11 @@
 #include "digest.h"
 #define SSHKEY_INTERNAL
 #include "sshkey.h"
+#include "sshkey-xmss.h"
 #include "match.h"
 
+#include "xmss_fast.h"
+
 /* openssh private key file format */
 #define MARK_BEGIN		"-----BEGIN OPENSSH PRIVATE KEY-----\n"
 #define MARK_END		"-----END OPENSSH PRIVATE KEY-----\n"
@@ -71,6 +74,8 @@
 /* Version identification string for SSH v1 identity files. */
 #define LEGACY_BEGIN		"SSH PRIVATE KEY FILE FORMAT 1.1\n"
 
+int	sshkey_private_serialize_opt(const struct sshkey *key,
+    struct sshbuf *buf, enum sshkey_serialize_rep);
 static int sshkey_from_blob_internal(struct sshbuf *buf,
     struct sshkey **keyp, int allow_cert);
 
@@ -87,6 +92,11 @@ static const struct keytype keytypes[] = {
 	{ "ssh-ed25519", "ED25519", KEY_ED25519, 0, 0, 0 },
 	{ "ssh-ed25519-cert-v01@openssh.com", "ED25519-CERT",
 	    KEY_ED25519_CERT, 0, 1, 0 },
+#ifdef WITH_XMSS
+	{ "ssh-xmss@openssh.com", "XMSS", KEY_XMSS, 0, 0, 0 },
+	{ "ssh-xmss-cert-v01@openssh.com", "XMSS-CERT",
+	    KEY_XMSS_CERT, 0, 1, 0 },
+#endif /* WITH_XMSS */
 #ifdef WITH_OPENSSL
 	{ "ssh-rsa", "RSA", KEY_RSA, 0, 0, 0 },
 	{ "rsa-sha2-256", "RSA", KEY_RSA, 0, 0, 1 },
@@ -274,6 +284,8 @@ sshkey_size(const struct sshkey *k)
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519:
 	case KEY_ED25519_CERT:
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
 		return 256;	/* XXX */
 	}
 	return 0;
@@ -287,6 +299,7 @@ sshkey_type_is_valid_ca(int type)
 	case KEY_DSA:
 	case KEY_ECDSA:
 	case KEY_ED25519:
+	case KEY_XMSS:
 		return 1;
 	default:
 		return 0;
@@ -314,6 +327,8 @@ sshkey_type_plain(int type)
 		return KEY_ECDSA;
 	case KEY_ED25519_CERT:
 		return KEY_ED25519;
+	case KEY_XMSS_CERT:
+		return KEY_XMSS;
 	default:
 		return type;
 	}
@@ -461,6 +476,8 @@ sshkey_new(int type)
 	k->cert = NULL;
 	k->ed25519_sk = NULL;
 	k->ed25519_pk = NULL;
+	k->xmss_sk = NULL;
+	k->xmss_pk = NULL;
 	switch (k->type) {
 #ifdef WITH_OPENSSL
 	case KEY_RSA:
@@ -494,6 +511,8 @@ sshkey_new(int type)
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519:
 	case KEY_ED25519_CERT:
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
 		/* no need to prealloc */
 		break;
 	case KEY_UNSPEC:
@@ -542,6 +561,8 @@ sshkey_add_private(struct sshkey *k)
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519:
 	case KEY_ED25519_CERT:
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
 		/* no need to prealloc */
 		break;
 	case KEY_UNSPEC:
@@ -598,6 +619,20 @@ sshkey_free(struct sshkey *k)
 		freezero(k->ed25519_sk, ED25519_SK_SZ);
 		k->ed25519_sk = NULL;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
+		freezero(k->xmss_pk, sshkey_xmss_pklen(k));
+		k->xmss_pk = NULL;
+		freezero(k->xmss_sk, sshkey_xmss_sklen(k));
+		k->xmss_sk = NULL;
+		sshkey_xmss_free_state(k);
+		free(k->xmss_name);
+		k->xmss_name = NULL;
+		free(k->xmss_filename);
+		k->xmss_filename = NULL;
+		break;
+#endif /* WITH_XMSS */
 	case KEY_UNSPEC:
 		break;
 	default:
@@ -677,6 +712,13 @@ sshkey_equal_public(const struct sshkey *a, const struct sshkey *b)
 	case KEY_ED25519_CERT:
 		return a->ed25519_pk != NULL && b->ed25519_pk != NULL &&
 		    memcmp(a->ed25519_pk, b->ed25519_pk, ED25519_PK_SZ) == 0;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
+		return a->xmss_pk != NULL && b->xmss_pk != NULL &&
+		    sshkey_xmss_pklen(a) == sshkey_xmss_pklen(b) &&
+		    memcmp(a->xmss_pk, b->xmss_pk, sshkey_xmss_pklen(a)) == 0;
+#endif /* WITH_XMSS */
 	default:
 		return 0;
 	}
@@ -696,7 +738,8 @@ sshkey_equal(const struct sshkey *a, const struct sshkey *b)
 }
 
 static int
-to_blob_buf(const struct sshkey *key, struct sshbuf *b, int force_plain)
+to_blob_buf(const struct sshkey *key, struct sshbuf *b, int force_plain,
+  enum sshkey_serialize_rep opts)
 {
 	int type, ret = SSH_ERR_INTERNAL_ERROR;
 	const char *typename;
@@ -720,6 +763,9 @@ to_blob_buf(const struct sshkey *key, struct sshbuf *b, int force_plain)
 	case KEY_RSA_CERT:
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519_CERT:
+#ifdef WITH_XMSS
+	case KEY_XMSS_CERT:
+#endif /* WITH_XMSS */
 		/* Use the existing blob */
 		/* XXX modified flag? */
 		if ((ret = sshbuf_putb(b, key->cert->certblob)) != 0)
@@ -764,6 +810,19 @@ to_blob_buf(const struct sshkey *key, struct sshbuf *b, int force_plain)
 		    key->ed25519_pk, ED25519_PK_SZ)) != 0)
 			return ret;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+		if (key->xmss_name == NULL || key->xmss_pk == NULL ||
+		    sshkey_xmss_pklen(key) == 0)
+			return SSH_ERR_INVALID_ARGUMENT;
+		if ((ret = sshbuf_put_cstring(b, typename)) != 0 ||
+		    (ret = sshbuf_put_cstring(b, key->xmss_name)) != 0 ||
+		    (ret = sshbuf_put_string(b,
+		    key->xmss_pk, sshkey_xmss_pklen(key))) != 0 ||
+		    (ret = sshkey_xmss_serialize_pk_info(key, b, opts)) != 0)
+			return ret;
+		break;
+#endif /* WITH_XMSS */
 	default:
 		return SSH_ERR_KEY_TYPE_UNKNOWN;
 	}
@@ -773,18 +832,19 @@ to_blob_buf(const struct sshkey *key, struct sshbuf *b, int force_plain)
 int
 sshkey_putb(const struct sshkey *key, struct sshbuf *b)
 {
-	return to_blob_buf(key, b, 0);
+	return to_blob_buf(key, b, 0, SSHKEY_SERIALIZE_DEFAULT);
 }
 
 int
-sshkey_puts(const struct sshkey *key, struct sshbuf *b)
+sshkey_puts_opts(const struct sshkey *key, struct sshbuf *b,
+    enum sshkey_serialize_rep opts)
 {
 	struct sshbuf *tmp;
 	int r;
 
 	if ((tmp = sshbuf_new()) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
-	r = to_blob_buf(key, tmp, 0);
+	r = to_blob_buf(key, tmp, 0, opts);
 	if (r == 0)
 		r = sshbuf_put_stringb(b, tmp);
 	sshbuf_free(tmp);
@@ -792,13 +852,20 @@ sshkey_puts(const struct sshkey *key, struct sshbuf *b)
 }
 
 int
+sshkey_puts(const struct sshkey *key, struct sshbuf *b)
+{
+	return sshkey_puts_opts(key, b, SSHKEY_SERIALIZE_DEFAULT);
+}
+
+int
 sshkey_putb_plain(const struct sshkey *key, struct sshbuf *b)
 {
-	return to_blob_buf(key, b, 1);
+	return to_blob_buf(key, b, 1, SSHKEY_SERIALIZE_DEFAULT);
 }
 
 static int
-to_blob(const struct sshkey *key, u_char **blobp, size_t *lenp, int force_plain)
+to_blob(const struct sshkey *key, u_char **blobp, size_t *lenp, int force_plain,
+    enum sshkey_serialize_rep opts)
 {
 	int ret = SSH_ERR_INTERNAL_ERROR;
 	size_t len;
@@ -810,7 +877,7 @@ to_blob(const struct sshkey *key, u_char **blobp, size_t *lenp, int force_plain)
 		*blobp = NULL;
 	if ((b = sshbuf_new()) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
-	if ((ret = to_blob_buf(key, b, force_plain)) != 0)
+	if ((ret = to_blob_buf(key, b, force_plain, opts)) != 0)
 		goto out;
 	len = sshbuf_len(b);
 	if (lenp != NULL)
@@ -831,13 +898,13 @@ to_blob(const struct sshkey *key, u_char **blobp, size_t *lenp, int force_plain)
 int
 sshkey_to_blob(const struct sshkey *key, u_char **blobp, size_t *lenp)
 {
-	return to_blob(key, blobp, lenp, 0);
+	return to_blob(key, blobp, lenp, 0, SSHKEY_SERIALIZE_DEFAULT);
 }
 
 int
 sshkey_plain_to_blob(const struct sshkey *key, u_char **blobp, size_t *lenp)
 {
-	return to_blob(key, blobp, lenp, 1);
+	return to_blob(key, blobp, lenp, 1, SSHKEY_SERIALIZE_DEFAULT);
 }
 
 int
@@ -856,7 +923,8 @@ sshkey_fingerprint_raw(const struct sshkey *k, int dgst_alg,
 		r = SSH_ERR_INVALID_ARGUMENT;
 		goto out;
 	}
-	if ((r = to_blob(k, &blob, &blob_len, 1)) != 0)
+	if ((r = to_blob(k, &blob, &blob_len, 1, SSHKEY_SERIALIZE_DEFAULT))
+	    != 0)
 		goto out;
 	if ((ret = calloc(1, SSH_DIGEST_MAX_LENGTH)) == NULL) {
 		r = SSH_ERR_ALLOC_FAIL;
@@ -1173,6 +1241,10 @@ sshkey_read(struct sshkey *ret, char **cpp)
 	case KEY_ECDSA_CERT:
 	case KEY_RSA_CERT:
 	case KEY_ED25519_CERT:
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
+#endif /* WITH_XMSS */
 		space = strchr(cp, ' ');
 		if (space == NULL)
 			return SSH_ERR_INVALID_FORMAT;
@@ -1270,6 +1342,25 @@ sshkey_read(struct sshkey *ret, char **cpp)
 			/* XXX */
 #endif
 			break;
+#ifdef WITH_XMSS
+		case KEY_XMSS:
+			free(ret->xmss_pk);
+			ret->xmss_pk = k->xmss_pk;
+			k->xmss_pk = NULL;
+			free(ret->xmss_state);
+			ret->xmss_state = k->xmss_state;
+			k->xmss_state = NULL;
+			free(ret->xmss_name);
+			ret->xmss_name = k->xmss_name;
+			k->xmss_name = NULL;
+			free(ret->xmss_filename);
+			ret->xmss_filename = k->xmss_filename;
+			k->xmss_filename = NULL;
+#ifdef DEBUG_PK
+			/* XXX */
+#endif
+			break;
+#endif /* WITH_XMSS */
 		}
 		*cpp = ep;
 		retval = 0;
@@ -1528,6 +1619,11 @@ sshkey_generate(int type, u_int bits, struct sshkey **keyp)
 		crypto_sign_ed25519_keypair(k->ed25519_pk, k->ed25519_sk);
 		ret = 0;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+		ret = sshkey_xmss_generate_private_key(k, bits);
+		break;
+#endif /* WITH_XMSS */
 #ifdef WITH_OPENSSL
 	case KEY_DSA:
 		ret = dsa_generate_private_key(bits, &k->dsa);
@@ -1671,6 +1767,29 @@ sshkey_from_private(const struct sshkey *k, struct sshkey **pkp)
 			memcpy(n->ed25519_pk, k->ed25519_pk, ED25519_PK_SZ);
 		}
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
+		if ((n = sshkey_new(k->type)) == NULL)
+			return SSH_ERR_ALLOC_FAIL;
+		if ((ret = sshkey_xmss_init(n, k->xmss_name)) != 0) {
+			sshkey_free(n);
+			return ret;
+		}
+		if (k->xmss_pk != NULL) {
+			size_t pklen = sshkey_xmss_pklen(k);
+			if (pklen == 0 || sshkey_xmss_pklen(n) != pklen) {
+				sshkey_free(n);
+				return SSH_ERR_INTERNAL_ERROR;
+			}
+			if ((n->xmss_pk = malloc(pklen)) == NULL) {
+				sshkey_free(n);
+				return SSH_ERR_ALLOC_FAIL;
+			}
+			memcpy(n->xmss_pk, k->xmss_pk, pklen);
+		}
+		break;
+#endif /* WITH_XMSS */
 	default:
 		return SSH_ERR_KEY_TYPE_UNKNOWN;
 	}
@@ -1812,7 +1931,7 @@ sshkey_from_blob_internal(struct sshbuf *b, struct sshkey **keyp,
     int allow_cert)
 {
 	int type, ret = SSH_ERR_INTERNAL_ERROR;
-	char *ktype = NULL, *curve = NULL;
+	char *ktype = NULL, *curve = NULL, *xmss_name = NULL;
 	struct sshkey *key = NULL;
 	size_t len;
 	u_char *pk = NULL;
@@ -1963,6 +2082,36 @@ sshkey_from_blob_internal(struct sshbuf *b, struct sshkey **keyp,
 		key->ed25519_pk = pk;
 		pk = NULL;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS_CERT:
+		/* Skip nonce */
+		if (sshbuf_get_string_direct(b, NULL, NULL) != 0) {
+			ret = SSH_ERR_INVALID_FORMAT;
+			goto out;
+		}
+		/* FALLTHROUGH */
+	case KEY_XMSS:
+		if ((ret = sshbuf_get_cstring(b, &xmss_name, NULL)) != 0)
+			goto out;
+		if ((key = sshkey_new(type)) == NULL) {
+			ret = SSH_ERR_ALLOC_FAIL;
+			goto out;
+		}
+		if ((ret = sshkey_xmss_init(key, xmss_name)) != 0)
+			goto out;
+		if ((ret = sshbuf_get_string(b, &pk, &len)) != 0)
+			goto out;
+		if (len == 0 || len != sshkey_xmss_pklen(key)) {
+			ret = SSH_ERR_INVALID_FORMAT;
+			goto out;
+		}
+		key->xmss_pk = pk;
+		pk = NULL;
+		if (type != KEY_XMSS_CERT &&
+		    (ret = sshkey_xmss_deserialize_pk_info(key, b)) != 0)
+			goto out;
+		break;
+#endif /* WITH_XMSS */
 	case KEY_UNSPEC:
 	default:
 		ret = SSH_ERR_KEY_TYPE_UNKNOWN;
@@ -1985,6 +2134,7 @@ sshkey_from_blob_internal(struct sshbuf *b, struct sshkey **keyp,
  out:
 	sshbuf_free(copy);
 	sshkey_free(key);
+	free(xmss_name);
 	free(ktype);
 	free(curve);
 	free(pk);
@@ -2079,6 +2229,11 @@ sshkey_sign(const struct sshkey *key,
 	case KEY_ED25519:
 	case KEY_ED25519_CERT:
 		return ssh_ed25519_sign(key, sigp, lenp, data, datalen, compat);
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
+		return ssh_xmss_sign(key, sigp, lenp, data, datalen, compat);
+#endif /* WITH_XMSS */
 	default:
 		return SSH_ERR_KEY_TYPE_UNKNOWN;
 	}
@@ -2112,6 +2267,11 @@ sshkey_verify(const struct sshkey *key,
 	case KEY_ED25519:
 	case KEY_ED25519_CERT:
 		return ssh_ed25519_verify(key, sig, siglen, data, dlen, compat);
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+	case KEY_XMSS_CERT:
+		return ssh_xmss_verify(key, sig, siglen, data, dlen, compat);
+#endif /* WITH_XMSS */
 	default:
 		return SSH_ERR_KEY_TYPE_UNKNOWN;
 	}
@@ -2135,6 +2295,8 @@ sshkey_demote(const struct sshkey *k, struct sshkey **dkp)
 	pk->rsa = NULL;
 	pk->ed25519_pk = NULL;
 	pk->ed25519_sk = NULL;
+	pk->xmss_pk = NULL;
+	pk->xmss_sk = NULL;
 
 	switch (k->type) {
 #ifdef WITH_OPENSSL
@@ -2196,6 +2358,29 @@ sshkey_demote(const struct sshkey *k, struct sshkey **dkp)
 			memcpy(pk->ed25519_pk, k->ed25519_pk, ED25519_PK_SZ);
 		}
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS_CERT:
+		if ((ret = sshkey_cert_copy(k, pk)) != 0)
+			goto fail;
+		/* FALLTHROUGH */
+	case KEY_XMSS:
+		if ((ret = sshkey_xmss_init(pk, k->xmss_name)) != 0)
+			goto fail;
+		if (k->xmss_pk != NULL) {
+			size_t pklen = sshkey_xmss_pklen(k);
+
+			if (pklen == 0 || sshkey_xmss_pklen(pk) != pklen) {
+				ret = SSH_ERR_INTERNAL_ERROR;
+				goto fail;
+			}
+			if ((pk->xmss_pk = malloc(pklen)) == NULL) {
+				ret = SSH_ERR_ALLOC_FAIL;
+				goto fail;
+			}
+			memcpy(pk->xmss_pk, k->xmss_pk, pklen);
+		}
+		break;
+#endif /* WITH_XMSS */
 	default:
 		ret = SSH_ERR_KEY_TYPE_UNKNOWN;
  fail:
@@ -2227,6 +2412,11 @@ sshkey_to_certified(struct sshkey *k)
 	case KEY_ED25519:
 		newtype = KEY_ED25519_CERT;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+		newtype = KEY_XMSS_CERT;
+		break;
+#endif /* WITH_XMSS */
 	default:
 		return SSH_ERR_INVALID_ARGUMENT;
 	}
@@ -2311,6 +2501,18 @@ sshkey_certify_custom(struct sshkey *k, struct sshkey *ca, const char *alg,
 		    k->ed25519_pk, ED25519_PK_SZ)) != 0)
 			goto out;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS_CERT:
+		if (k->xmss_name == NULL) {
+			ret = SSH_ERR_INVALID_ARGUMENT;
+			goto out;
+		}
+		if ((ret = sshbuf_put_cstring(cert, k->xmss_name)) ||
+		    (ret = sshbuf_put_string(cert,
+		    k->xmss_pk, sshkey_xmss_pklen(k))) != 0)
+			goto out;
+		break;
+#endif /* WITH_XMSS */
 	default:
 		ret = SSH_ERR_INVALID_ARGUMENT;
 		goto out;
@@ -2468,7 +2670,8 @@ sshkey_format_cert_validity(const struct sshkey_cert *cert, char *s, size_t l)
 }
 
 int
-sshkey_private_serialize(const struct sshkey *key, struct sshbuf *b)
+sshkey_private_serialize_opt(const struct sshkey *key, struct sshbuf *b,
+    enum sshkey_serialize_rep opts)
 {
 	int r = SSH_ERR_INTERNAL_ERROR;
 
@@ -2554,6 +2757,36 @@ sshkey_private_serialize(const struct sshkey *key, struct sshbuf *b)
 		    ED25519_SK_SZ)) != 0)
 			goto out;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+		if (key->xmss_name == NULL) {
+			r = SSH_ERR_INVALID_ARGUMENT;
+			goto out;
+		}
+		if ((r = sshbuf_put_cstring(b, key->xmss_name)) != 0 ||
+		    (r = sshbuf_put_string(b, key->xmss_pk,
+		    sshkey_xmss_pklen(key))) != 0 ||
+		    (r = sshbuf_put_string(b, key->xmss_sk,
+		    sshkey_xmss_sklen(key))) != 0 ||
+		    (r = sshkey_xmss_serialize_state_opt(key, b, opts)) != 0)
+			goto out;
+		break;
+	case KEY_XMSS_CERT:
+		if (key->cert == NULL || sshbuf_len(key->cert->certblob) == 0 ||
+		    key->xmss_name == NULL) {
+			r = SSH_ERR_INVALID_ARGUMENT;
+			goto out;
+		}
+		if ((r = sshbuf_put_stringb(b, key->cert->certblob)) != 0 ||
+		    (r = sshbuf_put_cstring(b, key->xmss_name)) != 0 ||
+		    (r = sshbuf_put_string(b, key->xmss_pk,
+		    sshkey_xmss_pklen(key))) != 0 ||
+		    (r = sshbuf_put_string(b, key->xmss_sk,
+		    sshkey_xmss_sklen(key))) != 0 ||
+		    (r = sshkey_xmss_serialize_state_opt(key, b, opts)) != 0)
+			goto out;
+		break;
+#endif /* WITH_XMSS */
 	default:
 		r = SSH_ERR_INVALID_ARGUMENT;
 		goto out;
@@ -2565,13 +2798,21 @@ sshkey_private_serialize(const struct sshkey *key, struct sshbuf *b)
 }
 
 int
+sshkey_private_serialize(const struct sshkey *key, struct sshbuf *b)
+{
+	return sshkey_private_serialize_opt(key, b,
+	    SSHKEY_SERIALIZE_DEFAULT);
+}
+
+int
 sshkey_private_deserialize(struct sshbuf *buf, struct sshkey **kp)
 {
-	char *tname = NULL, *curve = NULL;
+	char *tname = NULL, *curve = NULL, *xmss_name = NULL;
 	struct sshkey *k = NULL;
 	size_t pklen = 0, sklen = 0;
 	int type, r = SSH_ERR_INTERNAL_ERROR;
 	u_char *ed25519_pk = NULL, *ed25519_sk = NULL;
+	u_char *xmss_pk = NULL, *xmss_sk = NULL;
 #ifdef WITH_OPENSSL
 	BIGNUM *exponent = NULL;
 #endif /* WITH_OPENSSL */
@@ -2716,6 +2957,48 @@ sshkey_private_deserialize(struct sshbuf *buf, struct sshkey **kp)
 		k->ed25519_sk = ed25519_sk;
 		ed25519_pk = ed25519_sk = NULL;
 		break;
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+		if ((k = sshkey_new_private(type)) == NULL) {
+			r = SSH_ERR_ALLOC_FAIL;
+			goto out;
+		}
+		if ((r = sshbuf_get_cstring(buf, &xmss_name, NULL)) != 0 ||
+		    (r = sshkey_xmss_init(k, xmss_name)) != 0 ||
+		    (r = sshbuf_get_string(buf, &xmss_pk, &pklen)) != 0 ||
+		    (r = sshbuf_get_string(buf, &xmss_sk, &sklen)) != 0)
+			goto out;
+		if (pklen != sshkey_xmss_pklen(k) ||
+		    sklen != sshkey_xmss_sklen(k)) {
+			r = SSH_ERR_INVALID_FORMAT;
+			goto out;
+		}
+		k->xmss_pk = xmss_pk;
+		k->xmss_sk = xmss_sk;
+		xmss_pk = xmss_sk = NULL;
+		/* optional internal state */
+		if ((r = sshkey_xmss_deserialize_state_opt(k, buf)) != 0)
+			goto out;
+		break;
+	case KEY_XMSS_CERT:
+		if ((r = sshkey_froms(buf, &k)) != 0 ||
+		    (r = sshkey_add_private(k)) != 0 ||
+		    (r = sshbuf_get_string(buf, &xmss_pk, &pklen)) != 0 ||
+		    (r = sshbuf_get_string(buf, &xmss_sk, &sklen)) != 0)
+			goto out;
+		if (pklen != sshkey_xmss_pklen(k) ||
+		    sklen != sshkey_xmss_sklen(k)) {
+			r = SSH_ERR_INVALID_FORMAT;
+			goto out;
+		}
+		k->xmss_pk = xmss_pk;
+		k->xmss_sk = xmss_sk;
+		xmss_pk = xmss_sk = NULL;
+		/* optional internal state */
+		if ((r = sshkey_xmss_deserialize_state_opt(k, buf)) != 0)
+			goto out;
+		break;
+#endif /* WITH_XMSS */
 	default:
 		r = SSH_ERR_KEY_TYPE_UNKNOWN;
 		goto out;
@@ -2747,6 +3030,9 @@ sshkey_private_deserialize(struct sshbuf *buf, struct sshkey **kp)
 	sshkey_free(k);
 	freezero(ed25519_pk, pklen);
 	freezero(ed25519_sk, sklen);
+	free(xmss_name);
+	freezero(xmss_pk, pklen);
+	freezero(xmss_sk, sklen);
 	return r;
 }
 
@@ -3001,7 +3287,8 @@ sshkey_private_to_blob2(const struct sshkey *prv, struct sshbuf *blob,
 		goto out;
 
 	/* append private key and comment*/
-	if ((r = sshkey_private_serialize(prv, encrypted)) != 0 ||
+	if ((r = sshkey_private_serialize_opt(prv, encrypted,
+	     SSHKEY_SERIALIZE_FULL)) != 0 ||
 	    (r = sshbuf_put_cstring(encrypted, comment)) != 0)
 		goto out;
 
@@ -3362,6 +3649,9 @@ sshkey_private_to_fileblob(struct sshkey *key, struct sshbuf *blob,
 		    passphrase, comment);
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519:
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+#endif /* WITH_XMSS */
 		return sshkey_private_to_blob2(key, blob, passphrase,
 		    comment, new_format_cipher, new_format_rounds);
 	default:
@@ -3545,6 +3835,9 @@ sshkey_parse_private_fileblob_type(struct sshbuf *blob, int type,
 		    passphrase, keyp);
 #endif /* WITH_OPENSSL */
 	case KEY_ED25519:
+#ifdef WITH_XMSS
+	case KEY_XMSS:
+#endif /* WITH_XMSS */
 		return sshkey_parse_private2(blob, type, passphrase,
 		    keyp, commentp);
 	case KEY_UNSPEC:
@@ -3576,3 +3869,90 @@ sshkey_parse_private_fileblob(struct sshbuf *buffer, const char *passphrase,
 	return sshkey_parse_private_fileblob_type(buffer, KEY_UNSPEC,
 	    passphrase, keyp, commentp);
 }
+
+#ifdef WITH_XMSS
+/*
+ * serialize the key with the current state and forward the state
+ * maxsign times.
+ */
+int
+sshkey_private_serialize_maxsign(const struct sshkey *k, struct sshbuf *b,
+    u_int32_t maxsign, sshkey_printfn *pr)
+{
+	int r, rupdate;
+
+	if (maxsign == 0 ||
+	    sshkey_type_plain(k->type) != KEY_XMSS)
+		return sshkey_private_serialize_opt(k, b,
+		    SSHKEY_SERIALIZE_DEFAULT);
+	if ((r = sshkey_xmss_get_state(k, pr)) != 0 ||
+	    (r = sshkey_private_serialize_opt(k, b,
+	    SSHKEY_SERIALIZE_STATE)) != 0 ||
+	    (r = sshkey_xmss_forward_state(k, maxsign)) != 0)
+		goto out;
+	r = 0;
+out:
+	if ((rupdate = sshkey_xmss_update_state(k, pr)) != 0) {
+		if (r == 0)
+			r = rupdate;
+	}
+	return r;
+}
+
+u_int32_t
+sshkey_signatures_left(const struct sshkey *k)
+{
+	if (sshkey_type_plain(k->type) == KEY_XMSS)
+		return sshkey_xmss_signatures_left(k);
+	return 0;
+}
+
+int
+sshkey_enable_maxsign(struct sshkey *k, u_int32_t maxsign)
+{
+	if (sshkey_type_plain(k->type) != KEY_XMSS)
+		return SSH_ERR_INVALID_ARGUMENT;
+	return sshkey_xmss_enable_maxsign(k, maxsign);
+}
+
+int
+sshkey_set_filename(struct sshkey *k, const char *filename)
+{
+	if (k == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if (sshkey_type_plain(k->type) != KEY_XMSS)
+		return 0;
+	if (filename == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	if ((k->xmss_filename = strdup(filename)) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	return 0;
+}
+#else
+int
+sshkey_private_serialize_maxsign(const struct sshkey *k, struct sshbuf *b,
+    u_int32_t maxsign, sshkey_printfn *pr)
+{
+	return sshkey_private_serialize_opt(k, b, SSHKEY_SERIALIZE_DEFAULT);
+}
+
+u_int32_t
+sshkey_signatures_left(const struct sshkey *k)
+{
+	return 0;
+}
+
+int
+sshkey_enable_maxsign(struct sshkey *k, u_int32_t maxsign)
+{
+	return SSH_ERR_INVALID_ARGUMENT;
+}
+
+int
+sshkey_set_filename(struct sshkey *k, const char *filename)
+{
+	if (k == NULL)
+		return SSH_ERR_INVALID_ARGUMENT;
+	return 0;
+}
+#endif /* WITH_XMSS */
diff --git a/sshkey.h b/sshkey.h
index 7efa16ff..c795815f 100644
--- a/sshkey.h
+++ b/sshkey.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshkey.h,v 1.23 2017/12/18 02:25:15 djm Exp $ */
+/* $OpenBSD: sshkey.h,v 1.24 2018/02/23 15:58:38 markus Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -61,6 +61,8 @@ enum sshkey_types {
 	KEY_DSA_CERT,
 	KEY_ECDSA_CERT,
 	KEY_ED25519_CERT,
+	KEY_XMSS,
+	KEY_XMSS_CERT,
 	KEY_UNSPEC
 };
 
@@ -76,6 +78,14 @@ enum sshkey_fp_rep {
 	SSH_FP_RANDOMART
 };
 
+/* Private key serialisation formats, used on the wire */
+enum sshkey_serialize_rep {
+	SSHKEY_SERIALIZE_DEFAULT = 0,
+	SSHKEY_SERIALIZE_STATE = 1,
+	SSHKEY_SERIALIZE_FULL = 2,
+	SSHKEY_SERIALIZE_INFO = 254,
+};
+
 /* key is stored in external hardware */
 #define SSHKEY_FLAG_EXT		0x0001
 
@@ -104,6 +114,11 @@ struct sshkey {
 	EC_KEY	*ecdsa;
 	u_char	*ed25519_sk;
 	u_char	*ed25519_pk;
+	char	*xmss_name;
+	char	*xmss_filename;	/* for state file updates */
+	void	*xmss_state;	/* depends on xmss_name, opaque */
+	u_char	*xmss_sk;
+	u_char	*xmss_pk;
 	struct sshkey_cert *cert;
 };
 
@@ -171,6 +186,8 @@ int	 sshkey_to_blob(const struct sshkey *, u_char **, size_t *);
 int	 sshkey_to_base64(const struct sshkey *, char **);
 int	 sshkey_putb(const struct sshkey *, struct sshbuf *);
 int	 sshkey_puts(const struct sshkey *, struct sshbuf *);
+int	 sshkey_puts_opts(const struct sshkey *, struct sshbuf *,
+    enum sshkey_serialize_rep);
 int	 sshkey_plain_to_blob(const struct sshkey *, u_char **, size_t *);
 int	 sshkey_putb_plain(const struct sshkey *, struct sshbuf *);
 
@@ -186,6 +203,8 @@ void	sshkey_dump_ec_key(const EC_KEY *);
 
 /* private key parsing and serialisation */
 int	sshkey_private_serialize(const struct sshkey *key, struct sshbuf *buf);
+int	sshkey_private_serialize_opt(const struct sshkey *key, struct sshbuf *buf,
+    enum sshkey_serialize_rep);
 int	sshkey_private_deserialize(struct sshbuf *buf,  struct sshkey **keyp);
 
 /* private key file format parsing and serialisation */
@@ -200,6 +219,15 @@ int	sshkey_parse_private_fileblob_type(struct sshbuf *blob, int type,
 /* XXX should be internal, but used by ssh-keygen */
 int ssh_rsa_generate_additional_parameters(struct sshkey *);
 
+/* stateful keys (e.g. XMSS) */
+typedef void sshkey_printfn(const char *, ...) __attribute__((format(printf, 1, 2)));
+int	 sshkey_set_filename(struct sshkey *, const char *);
+int	 sshkey_enable_maxsign(struct sshkey *, u_int32_t);
+u_int32_t sshkey_signatures_left(const struct sshkey *);
+int	 sshkey_forward_state(const struct sshkey *, u_int32_t, sshkey_printfn *);
+int	 sshkey_private_serialize_maxsign(const struct sshkey *key, struct sshbuf *buf,
+    u_int32_t maxsign, sshkey_printfn *pr);
+
 #ifdef SSHKEY_INTERNAL
 int ssh_rsa_sign(const struct sshkey *key,
     u_char **sigp, size_t *lenp, const u_char *data, size_t datalen,
@@ -222,6 +250,11 @@ int ssh_ed25519_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
 int ssh_ed25519_verify(const struct sshkey *key,
     const u_char *signature, size_t signaturelen,
     const u_char *data, size_t datalen, u_int compat);
+int ssh_xmss_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
+    const u_char *data, size_t datalen, u_int compat);
+int ssh_xmss_verify(const struct sshkey *key,
+    const u_char *signature, size_t signaturelen,
+    const u_char *data, size_t datalen, u_int compat);
 #endif
 
 #if !defined(WITH_OPENSSL)
diff --git a/xmss_commons.c b/xmss_commons.c
new file mode 100644
index 00000000..51171af9
--- /dev/null
+++ b/xmss_commons.c
@@ -0,0 +1,27 @@
+/*
+xmss_commons.c 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#include "xmss_commons.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+
+void to_byte(unsigned char *out, unsigned long long in, uint32_t bytes)
+{
+  int32_t i;
+  for (i = bytes-1; i >= 0; i--) {
+    out[i] = in & 0xff;
+    in = in >> 8;
+  }
+}
+
+void hexdump(const unsigned char *a, size_t len)
+{
+  size_t i;
+  for (i = 0; i < len; i++)
+    printf("%02x", a[i]);
+}
\ No newline at end of file
diff --git a/xmss_commons.h b/xmss_commons.h
new file mode 100644
index 00000000..32fd4e2d
--- /dev/null
+++ b/xmss_commons.h
@@ -0,0 +1,15 @@
+/*
+xmss_commons.h 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+#ifndef XMSS_COMMONS_H
+#define XMSS_COMMONS_H
+
+#include <stdlib.h>
+#include <stdint.h>
+
+void to_byte(unsigned char *output, unsigned long long in, uint32_t bytes);
+void hexdump(const unsigned char *a, size_t len);
+#endif
\ No newline at end of file
diff --git a/xmss_fast.c b/xmss_fast.c
new file mode 100644
index 00000000..7ddc92f8
--- /dev/null
+++ b/xmss_fast.c
@@ -0,0 +1,1099 @@
+/*
+xmss_fast.c version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#include "xmss_fast.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+#include "crypto_api.h"
+#include "xmss_wots.h"
+#include "xmss_hash.h"
+
+#include "xmss_commons.h"
+#include "xmss_hash_address.h"
+// For testing
+#include "stdio.h"
+
+
+
+/**
+ * Used for pseudorandom keygeneration,
+ * generates the seed for the WOTS keypair at address addr
+ *
+ * takes n byte sk_seed and returns n byte seed using 32 byte address addr.
+ */
+static void get_seed(unsigned char *seed, const unsigned char *sk_seed, int n, uint32_t addr[8])
+{
+  unsigned char bytes[32];
+  // Make sure that chain addr, hash addr, and key bit are 0!
+  setChainADRS(addr,0);
+  setHashADRS(addr,0);
+  setKeyAndMask(addr,0);
+  // Generate pseudorandom value
+  addr_to_byte(bytes, addr);
+  prf(seed, bytes, sk_seed, n);
+}
+
+/**
+ * Initialize xmss params struct
+ * parameter names are the same as in the draft
+ * parameter k is K as used in the BDS algorithm
+ */
+int xmss_set_params(xmss_params *params, int n, int h, int w, int k)
+{
+  if (k >= h || k < 2 || (h - k) % 2) {
+    fprintf(stderr, "For BDS traversal, H - K must be even, with H > K >= 2!\n");
+    return 1;
+  }
+  params->h = h;
+  params->n = n;
+  params->k = k;
+  wots_params wots_par;
+  wots_set_params(&wots_par, n, w);
+  params->wots_par = wots_par;
+  return 0;
+}
+
+/**
+ * Initialize BDS state struct
+ * parameter names are the same as used in the description of the BDS traversal
+ */
+void xmss_set_bds_state(bds_state *state, unsigned char *stack, int stackoffset, unsigned char *stacklevels, unsigned char *auth, unsigned char *keep, treehash_inst *treehash, unsigned char *retain, int next_leaf)
+{
+  state->stack = stack;
+  state->stackoffset = stackoffset;
+  state->stacklevels = stacklevels;
+  state->auth = auth;
+  state->keep = keep;
+  state->treehash = treehash;
+  state->retain = retain;
+  state->next_leaf = next_leaf;
+}
+
+/**
+ * Initialize xmssmt_params struct
+ * parameter names are the same as in the draft
+ *
+ * Especially h is the total tree height, i.e. the XMSS trees have height h/d
+ */
+int xmssmt_set_params(xmssmt_params *params, int n, int h, int d, int w, int k)
+{
+  if (h % d) {
+    fprintf(stderr, "d must divide h without remainder!\n");
+    return 1;
+  }
+  params->h = h;
+  params->d = d;
+  params->n = n;
+  params->index_len = (h + 7) / 8;
+  xmss_params xmss_par;
+  if (xmss_set_params(&xmss_par, n, (h/d), w, k)) {
+    return 1;
+  }
+  params->xmss_par = xmss_par;
+  return 0;
+}
+
+/**
+ * Computes a leaf from a WOTS public key using an L-tree.
+ */
+static void l_tree(unsigned char *leaf, unsigned char *wots_pk, const xmss_params *params, const unsigned char *pub_seed, uint32_t addr[8])
+{
+  unsigned int l = params->wots_par.len;
+  unsigned int n = params->n;
+  uint32_t i = 0;
+  uint32_t height = 0;
+  uint32_t bound;
+
+  //ADRS.setTreeHeight(0);
+  setTreeHeight(addr, height);
+  
+  while (l > 1) {
+     bound = l >> 1; //floor(l / 2);
+     for (i = 0; i < bound; i++) {
+       //ADRS.setTreeIndex(i);
+       setTreeIndex(addr, i);
+       //wots_pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS);
+       hash_h(wots_pk+i*n, wots_pk+i*2*n, pub_seed, addr, n);
+     }
+     //if ( l % 2 == 1 ) {
+     if (l & 1) {
+       //pk[floor(l / 2) + 1] = pk[l];
+       memcpy(wots_pk+(l>>1)*n, wots_pk+(l-1)*n, n);
+       //l = ceil(l / 2);
+       l=(l>>1)+1;
+     }
+     else {
+       //l = ceil(l / 2);
+       l=(l>>1);
+     }
+     //ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
+     height++;
+     setTreeHeight(addr, height);
+   }
+   //return pk[0];
+   memcpy(leaf, wots_pk, n);
+}
+
+/**
+ * Computes the leaf at a given address. First generates the WOTS key pair, then computes leaf using l_tree. As this happens position independent, we only require that addr encodes the right ltree-address.
+ */
+static void gen_leaf_wots(unsigned char *leaf, const unsigned char *sk_seed, const xmss_params *params, const unsigned char *pub_seed, uint32_t ltree_addr[8], uint32_t ots_addr[8])
+{
+  unsigned char seed[params->n];
+  unsigned char pk[params->wots_par.keysize];
+
+  get_seed(seed, sk_seed, params->n, ots_addr);
+  wots_pkgen(pk, seed, &(params->wots_par), pub_seed, ots_addr);
+
+  l_tree(leaf, pk, params, pub_seed, ltree_addr);
+}
+
+static int treehash_minheight_on_stack(bds_state* state, const xmss_params *params, const treehash_inst *treehash) {
+  unsigned int r = params->h, i;
+  for (i = 0; i < treehash->stackusage; i++) {
+    if (state->stacklevels[state->stackoffset - i - 1] < r) {
+      r = state->stacklevels[state->stackoffset - i - 1];
+    }
+  }
+  return r;
+}
+
+/**
+ * Merkle's TreeHash algorithm. The address only needs to initialize the first 78 bits of addr. Everything else will be set by treehash.
+ * Currently only used for key generation.
+ *
+ */
+static void treehash_setup(unsigned char *node, int height, int index, bds_state *state, const unsigned char *sk_seed, const xmss_params *params, const unsigned char *pub_seed, const uint32_t addr[8])
+{
+  unsigned int idx = index;
+  unsigned int n = params->n;
+  unsigned int h = params->h;
+  unsigned int k = params->k;
+  // use three different addresses because at this point we use all three formats in parallel
+  uint32_t ots_addr[8];
+  uint32_t ltree_addr[8];
+  uint32_t  node_addr[8];
+  // only copy layer and tree address parts
+  memcpy(ots_addr, addr, 12);
+  // type = ots
+  setType(ots_addr, 0);
+  memcpy(ltree_addr, addr, 12);
+  setType(ltree_addr, 1);
+  memcpy(node_addr, addr, 12);
+  setType(node_addr, 2);
+
+  uint32_t lastnode, i;
+  unsigned char stack[(height+1)*n];
+  unsigned int stacklevels[height+1];
+  unsigned int stackoffset=0;
+  unsigned int nodeh;
+
+  lastnode = idx+(1<<height);
+
+  for (i = 0; i < h-k; i++) {
+    state->treehash[i].h = i;
+    state->treehash[i].completed = 1;
+    state->treehash[i].stackusage = 0;
+  }
+
+  i = 0;
+  for (; idx < lastnode; idx++) {
+    setLtreeADRS(ltree_addr, idx);
+    setOTSADRS(ots_addr, idx);
+    gen_leaf_wots(stack+stackoffset*n, sk_seed, params, pub_seed, ltree_addr, ots_addr);
+    stacklevels[stackoffset] = 0;
+    stackoffset++;
+    if (h - k > 0 && i == 3) {
+      memcpy(state->treehash[0].node, stack+stackoffset*n, n);
+    }
+    while (stackoffset>1 && stacklevels[stackoffset-1] == stacklevels[stackoffset-2])
+    {
+      nodeh = stacklevels[stackoffset-1];
+      if (i >> nodeh == 1) {
+        memcpy(state->auth + nodeh*n, stack+(stackoffset-1)*n, n);
+      }
+      else {
+        if (nodeh < h - k && i >> nodeh == 3) {
+          memcpy(state->treehash[nodeh].node, stack+(stackoffset-1)*n, n);
+        }
+        else if (nodeh >= h - k) {
+          memcpy(state->retain + ((1 << (h - 1 - nodeh)) + nodeh - h + (((i >> nodeh) - 3) >> 1)) * n, stack+(stackoffset-1)*n, n);
+        }
+      }
+      setTreeHeight(node_addr, stacklevels[stackoffset-1]);
+      setTreeIndex(node_addr, (idx >> (stacklevels[stackoffset-1]+1)));
+      hash_h(stack+(stackoffset-2)*n, stack+(stackoffset-2)*n, pub_seed,
+          node_addr, n);
+      stacklevels[stackoffset-2]++;
+      stackoffset--;
+    }
+    i++;
+  }
+
+  for (i = 0; i < n; i++)
+    node[i] = stack[i];
+}
+
+static void treehash_update(treehash_inst *treehash, bds_state *state, const unsigned char *sk_seed, const xmss_params *params, const unsigned char *pub_seed, const uint32_t addr[8]) {
+  int n = params->n;
+
+  uint32_t ots_addr[8];
+  uint32_t ltree_addr[8];
+  uint32_t  node_addr[8];
+  // only copy layer and tree address parts
+  memcpy(ots_addr, addr, 12);
+  // type = ots
+  setType(ots_addr, 0);
+  memcpy(ltree_addr, addr, 12);
+  setType(ltree_addr, 1);
+  memcpy(node_addr, addr, 12);
+  setType(node_addr, 2);
+
+  setLtreeADRS(ltree_addr, treehash->next_idx);
+  setOTSADRS(ots_addr, treehash->next_idx);
+
+  unsigned char nodebuffer[2 * n];
+  unsigned int nodeheight = 0;
+  gen_leaf_wots(nodebuffer, sk_seed, params, pub_seed, ltree_addr, ots_addr);
+  while (treehash->stackusage > 0 && state->stacklevels[state->stackoffset-1] == nodeheight) {
+    memcpy(nodebuffer + n, nodebuffer, n);
+    memcpy(nodebuffer, state->stack + (state->stackoffset-1)*n, n);
+    setTreeHeight(node_addr, nodeheight);
+    setTreeIndex(node_addr, (treehash->next_idx >> (nodeheight+1)));
+    hash_h(nodebuffer, nodebuffer, pub_seed, node_addr, n);
+    nodeheight++;
+    treehash->stackusage--;
+    state->stackoffset--;
+  }
+  if (nodeheight == treehash->h) { // this also implies stackusage == 0
+    memcpy(treehash->node, nodebuffer, n);
+    treehash->completed = 1;
+  }
+  else {
+    memcpy(state->stack + state->stackoffset*n, nodebuffer, n);
+    treehash->stackusage++;
+    state->stacklevels[state->stackoffset] = nodeheight;
+    state->stackoffset++;
+    treehash->next_idx++;
+  }
+}
+
+/**
+ * Computes a root node given a leaf and an authapth
+ */
+static void validate_authpath(unsigned char *root, const unsigned char *leaf, unsigned long leafidx, const unsigned char *authpath, const xmss_params *params, const unsigned char *pub_seed, uint32_t addr[8])
+{
+  unsigned int n = params->n;
+
+  uint32_t i, j;
+  unsigned char buffer[2*n];
+
+  // If leafidx is odd (last bit = 1), current path element is a right child and authpath has to go to the left.
+  // Otherwise, it is the other way around
+  if (leafidx & 1) {
+    for (j = 0; j < n; j++)
+      buffer[n+j] = leaf[j];
+    for (j = 0; j < n; j++)
+      buffer[j] = authpath[j];
+  }
+  else {
+    for (j = 0; j < n; j++)
+      buffer[j] = leaf[j];
+    for (j = 0; j < n; j++)
+      buffer[n+j] = authpath[j];
+  }
+  authpath += n;
+
+  for (i=0; i < params->h-1; i++) {
+    setTreeHeight(addr, i);
+    leafidx >>= 1;
+    setTreeIndex(addr, leafidx);
+    if (leafidx&1) {
+      hash_h(buffer+n, buffer, pub_seed, addr, n);
+      for (j = 0; j < n; j++)
+        buffer[j] = authpath[j];
+    }
+    else {
+      hash_h(buffer, buffer, pub_seed, addr, n);
+      for (j = 0; j < n; j++)
+        buffer[j+n] = authpath[j];
+    }
+    authpath += n;
+  }
+  setTreeHeight(addr, (params->h-1));
+  leafidx >>= 1;
+  setTreeIndex(addr, leafidx);
+  hash_h(root, buffer, pub_seed, addr, n);
+}
+
+/**
+ * Performs one treehash update on the instance that needs it the most.
+ * Returns 1 if such an instance was not found
+ **/
+static char bds_treehash_update(bds_state *state, unsigned int updates, const unsigned char *sk_seed, const xmss_params *params, unsigned char *pub_seed, const uint32_t addr[8]) {
+  uint32_t i, j;
+  unsigned int level, l_min, low;
+  unsigned int h = params->h;
+  unsigned int k = params->k;
+  unsigned int used = 0;
+
+  for (j = 0; j < updates; j++) {
+    l_min = h;
+    level = h - k;
+    for (i = 0; i < h - k; i++) {
+      if (state->treehash[i].completed) {
+        low = h;
+      }
+      else if (state->treehash[i].stackusage == 0) {
+        low = i;
+      }
+      else {
+        low = treehash_minheight_on_stack(state, params, &(state->treehash[i]));
+      }
+      if (low < l_min) {
+        level = i;
+        l_min = low;
+      }
+    }
+    if (level == h - k) {
+      break;
+    }
+    treehash_update(&(state->treehash[level]), state, sk_seed, params, pub_seed, addr);
+    used++;
+  }
+  return updates - used;
+}
+
+/**
+ * Updates the state (typically NEXT_i) by adding a leaf and updating the stack
+ * Returns 1 if all leaf nodes have already been processed
+ **/
+static char bds_state_update(bds_state *state, const unsigned char *sk_seed, const xmss_params *params, unsigned char *pub_seed, const uint32_t addr[8]) {
+  uint32_t ltree_addr[8];
+  uint32_t node_addr[8];
+  uint32_t ots_addr[8];
+
+  int n = params->n;
+  int h = params->h;
+  int k = params->k;
+
+  int nodeh;
+  int idx = state->next_leaf;
+  if (idx == 1 << h) {
+    return 1;
+  }
+
+  // only copy layer and tree address parts
+  memcpy(ots_addr, addr, 12);
+  // type = ots
+  setType(ots_addr, 0);
+  memcpy(ltree_addr, addr, 12);
+  setType(ltree_addr, 1);
+  memcpy(node_addr, addr, 12);
+  setType(node_addr, 2);
+  
+  setOTSADRS(ots_addr, idx);
+  setLtreeADRS(ltree_addr, idx);
+
+  gen_leaf_wots(state->stack+state->stackoffset*n, sk_seed, params, pub_seed, ltree_addr, ots_addr);
+
+  state->stacklevels[state->stackoffset] = 0;
+  state->stackoffset++;
+  if (h - k > 0 && idx == 3) {
+    memcpy(state->treehash[0].node, state->stack+state->stackoffset*n, n);
+  }
+  while (state->stackoffset>1 && state->stacklevels[state->stackoffset-1] == state->stacklevels[state->stackoffset-2]) {
+    nodeh = state->stacklevels[state->stackoffset-1];
+    if (idx >> nodeh == 1) {
+      memcpy(state->auth + nodeh*n, state->stack+(state->stackoffset-1)*n, n);
+    }
+    else {
+      if (nodeh < h - k && idx >> nodeh == 3) {
+        memcpy(state->treehash[nodeh].node, state->stack+(state->stackoffset-1)*n, n);
+      }
+      else if (nodeh >= h - k) {
+        memcpy(state->retain + ((1 << (h - 1 - nodeh)) + nodeh - h + (((idx >> nodeh) - 3) >> 1)) * n, state->stack+(state->stackoffset-1)*n, n);
+      }
+    }
+    setTreeHeight(node_addr, state->stacklevels[state->stackoffset-1]);
+    setTreeIndex(node_addr, (idx >> (state->stacklevels[state->stackoffset-1]+1)));
+    hash_h(state->stack+(state->stackoffset-2)*n, state->stack+(state->stackoffset-2)*n, pub_seed, node_addr, n);
+
+    state->stacklevels[state->stackoffset-2]++;
+    state->stackoffset--;
+  }
+  state->next_leaf++;
+  return 0;
+}
+
+/**
+ * Returns the auth path for node leaf_idx and computes the auth path for the
+ * next leaf node, using the algorithm described by Buchmann, Dahmen and Szydlo
+ * in "Post Quantum Cryptography", Springer 2009.
+ */
+static void bds_round(bds_state *state, const unsigned long leaf_idx, const unsigned char *sk_seed, const xmss_params *params, unsigned char *pub_seed, uint32_t addr[8])
+{
+  unsigned int i;
+  unsigned int n = params->n;
+  unsigned int h = params->h;
+  unsigned int k = params->k;
+
+  unsigned int tau = h;
+  unsigned int startidx;
+  unsigned int offset, rowidx;
+  unsigned char buf[2 * n];
+
+  uint32_t ots_addr[8];
+  uint32_t ltree_addr[8];
+  uint32_t  node_addr[8];
+  // only copy layer and tree address parts
+  memcpy(ots_addr, addr, 12);
+  // type = ots
+  setType(ots_addr, 0);
+  memcpy(ltree_addr, addr, 12);
+  setType(ltree_addr, 1);
+  memcpy(node_addr, addr, 12);
+  setType(node_addr, 2);
+
+  for (i = 0; i < h; i++) {
+    if (! ((leaf_idx >> i) & 1)) {
+      tau = i;
+      break;
+    }
+  }
+
+  if (tau > 0) {
+    memcpy(buf,     state->auth + (tau-1) * n, n);
+    // we need to do this before refreshing state->keep to prevent overwriting
+    memcpy(buf + n, state->keep + ((tau-1) >> 1) * n, n);
+  }
+  if (!((leaf_idx >> (tau + 1)) & 1) && (tau < h - 1)) {
+    memcpy(state->keep + (tau >> 1)*n, state->auth + tau*n, n);
+  }
+  if (tau == 0) {
+    setLtreeADRS(ltree_addr, leaf_idx);
+    setOTSADRS(ots_addr, leaf_idx);
+    gen_leaf_wots(state->auth, sk_seed, params, pub_seed, ltree_addr, ots_addr);
+  }
+  else {
+    setTreeHeight(node_addr, (tau-1));
+    setTreeIndex(node_addr, leaf_idx >> tau);
+    hash_h(state->auth + tau * n, buf, pub_seed, node_addr, n);
+    for (i = 0; i < tau; i++) {
+      if (i < h - k) {
+        memcpy(state->auth + i * n, state->treehash[i].node, n);
+      }
+      else {
+        offset = (1 << (h - 1 - i)) + i - h;
+        rowidx = ((leaf_idx >> i) - 1) >> 1;
+        memcpy(state->auth + i * n, state->retain + (offset + rowidx) * n, n);
+      }
+    }
+
+    for (i = 0; i < ((tau < h - k) ? tau : (h - k)); i++) {
+      startidx = leaf_idx + 1 + 3 * (1 << i);
+      if (startidx < 1U << h) {
+        state->treehash[i].h = i;
+        state->treehash[i].next_idx = startidx;
+        state->treehash[i].completed = 0;
+        state->treehash[i].stackusage = 0;
+      }
+    }
+  }
+}
+
+/*
+ * Generates a XMSS key pair for a given parameter set.
+ * Format sk: [(32bit) idx || SK_SEED || SK_PRF || PUB_SEED || root]
+ * Format pk: [root || PUB_SEED] omitting algo oid.
+ */
+int xmss_keypair(unsigned char *pk, unsigned char *sk, bds_state *state, xmss_params *params)
+{
+  unsigned int n = params->n;
+  // Set idx = 0
+  sk[0] = 0;
+  sk[1] = 0;
+  sk[2] = 0;
+  sk[3] = 0;
+  // Init SK_SEED (n byte), SK_PRF (n byte), and PUB_SEED (n byte)
+  randombytes(sk+4, 3*n);
+  // Copy PUB_SEED to public key
+  memcpy(pk+n, sk+4+2*n, n);
+
+  uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+
+  // Compute root
+  treehash_setup(pk, params->h, 0, state, sk+4, params, sk+4+2*n, addr);
+  // copy root to sk
+  memcpy(sk+4+3*n, pk, n);
+  return 0;
+}
+
+/**
+ * Signs a message.
+ * Returns
+ * 1. an array containing the signature followed by the message AND
+ * 2. an updated secret key!
+ *
+ */
+int xmss_sign(unsigned char *sk, bds_state *state, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg, unsigned long long msglen, const xmss_params *params)
+{
+  unsigned int h = params->h;
+  unsigned int n = params->n;
+  unsigned int k = params->k;
+  uint16_t i = 0;
+
+  // Extract SK
+  unsigned long idx = ((unsigned long)sk[0] << 24) | ((unsigned long)sk[1] << 16) | ((unsigned long)sk[2] << 8) | sk[3];
+  unsigned char sk_seed[n];
+  memcpy(sk_seed, sk+4, n);
+  unsigned char sk_prf[n];
+  memcpy(sk_prf, sk+4+n, n);
+  unsigned char pub_seed[n];
+  memcpy(pub_seed, sk+4+2*n, n);
+  
+  // index as 32 bytes string
+  unsigned char idx_bytes_32[32];
+  to_byte(idx_bytes_32, idx, 32);
+  
+  unsigned char hash_key[3*n]; 
+  
+  // Update SK
+  sk[0] = ((idx + 1) >> 24) & 255;
+  sk[1] = ((idx + 1) >> 16) & 255;
+  sk[2] = ((idx + 1) >> 8) & 255;
+  sk[3] = (idx + 1) & 255;
+  // -- Secret key for this non-forward-secure version is now updated.
+  // -- A productive implementation should use a file handle instead and write the updated secret key at this point!
+
+  // Init working params
+  unsigned char R[n];
+  unsigned char msg_h[n];
+  unsigned char ots_seed[n];
+  uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+
+  // ---------------------------------
+  // Message Hashing
+  // ---------------------------------
+
+  // Message Hash:
+  // First compute pseudorandom value
+  prf(R, idx_bytes_32, sk_prf, n);
+  // Generate hash key (R || root || idx)
+  memcpy(hash_key, R, n);
+  memcpy(hash_key+n, sk+4+3*n, n);
+  to_byte(hash_key+2*n, idx, n);
+  // Then use it for message digest
+  h_msg(msg_h, msg, msglen, hash_key, 3*n, n);
+
+  // Start collecting signature
+  *sig_msg_len = 0;
+
+  // Copy index to signature
+  sig_msg[0] = (idx >> 24) & 255;
+  sig_msg[1] = (idx >> 16) & 255;
+  sig_msg[2] = (idx >> 8) & 255;
+  sig_msg[3] = idx & 255;
+
+  sig_msg += 4;
+  *sig_msg_len += 4;
+
+  // Copy R to signature
+  for (i = 0; i < n; i++)
+    sig_msg[i] = R[i];
+
+  sig_msg += n;
+  *sig_msg_len += n;
+
+  // ----------------------------------
+  // Now we start to "really sign"
+  // ----------------------------------
+
+  // Prepare Address
+  setType(ots_addr, 0);
+  setOTSADRS(ots_addr, idx);
+
+  // Compute seed for OTS key pair
+  get_seed(ots_seed, sk_seed, n, ots_addr);
+
+  // Compute WOTS signature
+  wots_sign(sig_msg, msg_h, ots_seed, &(params->wots_par), pub_seed, ots_addr);
+
+  sig_msg += params->wots_par.keysize;
+  *sig_msg_len += params->wots_par.keysize;
+
+  // the auth path was already computed during the previous round
+  memcpy(sig_msg, state->auth, h*n);
+
+  if (idx < (1U << h) - 1) {
+    bds_round(state, idx, sk_seed, params, pub_seed, ots_addr);
+    bds_treehash_update(state, (h - k) >> 1, sk_seed, params, pub_seed, ots_addr);
+  }
+
+/* TODO: save key/bds state here! */
+
+  sig_msg += params->h*n;
+  *sig_msg_len += params->h*n;
+
+  //Whipe secret elements?
+  //zerobytes(tsk, CRYPTO_SECRETKEYBYTES);
+
+
+  memcpy(sig_msg, msg, msglen);
+  *sig_msg_len += msglen;
+
+  return 0;
+}
+
+/**
+ * Verifies a given message signature pair under a given public key.
+ */
+int xmss_sign_open(unsigned char *msg, unsigned long long *msglen, const unsigned char *sig_msg, unsigned long long sig_msg_len, const unsigned char *pk, const xmss_params *params)
+{
+  unsigned int n = params->n;
+
+  unsigned long long i, m_len;
+  unsigned long idx=0;
+  unsigned char wots_pk[params->wots_par.keysize];
+  unsigned char pkhash[n];
+  unsigned char root[n];
+  unsigned char msg_h[n];
+  unsigned char hash_key[3*n];
+
+  unsigned char pub_seed[n];
+  memcpy(pub_seed, pk+n, n);
+
+  // Init addresses
+  uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  uint32_t ltree_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  uint32_t node_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+
+  setType(ots_addr, 0);
+  setType(ltree_addr, 1);
+  setType(node_addr, 2);
+
+  // Extract index
+  idx = ((unsigned long)sig_msg[0] << 24) | ((unsigned long)sig_msg[1] << 16) | ((unsigned long)sig_msg[2] << 8) | sig_msg[3];
+  printf("verify:: idx = %lu\n", idx);
+  
+  // Generate hash key (R || root || idx)
+  memcpy(hash_key, sig_msg+4,n);
+  memcpy(hash_key+n, pk, n);
+  to_byte(hash_key+2*n, idx, n);
+  
+  sig_msg += (n+4);
+  sig_msg_len -= (n+4);
+
+  // hash message 
+  unsigned long long tmp_sig_len = params->wots_par.keysize+params->h*n;
+  m_len = sig_msg_len - tmp_sig_len;
+  h_msg(msg_h, sig_msg + tmp_sig_len, m_len, hash_key, 3*n, n);
+
+  //-----------------------
+  // Verify signature
+  //-----------------------
+
+  // Prepare Address
+  setOTSADRS(ots_addr, idx);
+  // Check WOTS signature
+  wots_pkFromSig(wots_pk, sig_msg, msg_h, &(params->wots_par), pub_seed, ots_addr);
+
+  sig_msg += params->wots_par.keysize;
+  sig_msg_len -= params->wots_par.keysize;
+
+  // Compute Ltree
+  setLtreeADRS(ltree_addr, idx);
+  l_tree(pkhash, wots_pk, params, pub_seed, ltree_addr);
+
+  // Compute root
+  validate_authpath(root, pkhash, idx, sig_msg, params, pub_seed, node_addr);
+
+  sig_msg += params->h*n;
+  sig_msg_len -= params->h*n;
+
+  for (i = 0; i < n; i++)
+    if (root[i] != pk[i])
+      goto fail;
+
+  *msglen = sig_msg_len;
+  for (i = 0; i < *msglen; i++)
+    msg[i] = sig_msg[i];
+
+  return 0;
+
+
+fail:
+  *msglen = sig_msg_len;
+  for (i = 0; i < *msglen; i++)
+    msg[i] = 0;
+  *msglen = -1;
+  return -1;
+}
+
+/*
+ * Generates a XMSSMT key pair for a given parameter set.
+ * Format sk: [(ceil(h/8) bit) idx || SK_SEED || SK_PRF || PUB_SEED || root]
+ * Format pk: [root || PUB_SEED] omitting algo oid.
+ */
+int xmssmt_keypair(unsigned char *pk, unsigned char *sk, bds_state *states, unsigned char *wots_sigs, xmssmt_params *params)
+{
+  unsigned int n = params->n;
+  unsigned int i;
+  unsigned char ots_seed[params->n];
+  // Set idx = 0
+  for (i = 0; i < params->index_len; i++) {
+    sk[i] = 0;
+  }
+  // Init SK_SEED (n byte), SK_PRF (n byte), and PUB_SEED (n byte)
+  randombytes(sk+params->index_len, 3*n);
+  // Copy PUB_SEED to public key
+  memcpy(pk+n, sk+params->index_len+2*n, n);
+
+  // Set address to point on the single tree on layer d-1
+  uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  setLayerADRS(addr, (params->d-1));
+  // Set up state and compute wots signatures for all but topmost tree root
+  for (i = 0; i < params->d - 1; i++) {
+    // Compute seed for OTS key pair
+    treehash_setup(pk, params->xmss_par.h, 0, states + i, sk+params->index_len, &(params->xmss_par), pk+n, addr);
+    setLayerADRS(addr, (i+1));
+    get_seed(ots_seed, sk+params->index_len, n, addr);
+    wots_sign(wots_sigs + i*params->xmss_par.wots_par.keysize, pk, ots_seed, &(params->xmss_par.wots_par), pk+n, addr);
+  }
+  treehash_setup(pk, params->xmss_par.h, 0, states + i, sk+params->index_len, &(params->xmss_par), pk+n, addr);
+  memcpy(sk+params->index_len+3*n, pk, n);
+  return 0;
+}
+
+/**
+ * Signs a message.
+ * Returns
+ * 1. an array containing the signature followed by the message AND
+ * 2. an updated secret key!
+ *
+ */
+int xmssmt_sign(unsigned char *sk, bds_state *states, unsigned char *wots_sigs, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg, unsigned long long msglen, const xmssmt_params *params)
+{
+  unsigned int n = params->n;
+  
+  unsigned int tree_h = params->xmss_par.h;
+  unsigned int h = params->h;
+  unsigned int k = params->xmss_par.k;
+  unsigned int idx_len = params->index_len;
+  uint64_t idx_tree;
+  uint32_t idx_leaf;
+  uint64_t i, j;
+  int needswap_upto = -1;
+  unsigned int updates;
+
+  unsigned char sk_seed[n];
+  unsigned char sk_prf[n];
+  unsigned char pub_seed[n];
+  // Init working params
+  unsigned char R[n];
+  unsigned char msg_h[n];
+  unsigned char hash_key[3*n];
+  unsigned char ots_seed[n];
+  uint32_t addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  unsigned char idx_bytes_32[32];
+  bds_state tmp;
+
+  // Extract SK 
+  unsigned long long idx = 0;
+  for (i = 0; i < idx_len; i++) {
+    idx |= ((unsigned long long)sk[i]) << 8*(idx_len - 1 - i);
+  }
+
+  memcpy(sk_seed, sk+idx_len, n);
+  memcpy(sk_prf, sk+idx_len+n, n);
+  memcpy(pub_seed, sk+idx_len+2*n, n);
+
+  // Update SK
+  for (i = 0; i < idx_len; i++) {
+    sk[i] = ((idx + 1) >> 8*(idx_len - 1 - i)) & 255;
+  }
+  // -- Secret key for this non-forward-secure version is now updated.
+  // -- A productive implementation should use a file handle instead and write the updated secret key at this point!
+
+
+  // ---------------------------------
+  // Message Hashing
+  // ---------------------------------
+
+  // Message Hash:
+  // First compute pseudorandom value
+  to_byte(idx_bytes_32, idx, 32);
+  prf(R, idx_bytes_32, sk_prf, n);
+  // Generate hash key (R || root || idx)
+  memcpy(hash_key, R, n);
+  memcpy(hash_key+n, sk+idx_len+3*n, n);
+  to_byte(hash_key+2*n, idx, n);
+  
+  // Then use it for message digest
+  h_msg(msg_h, msg, msglen, hash_key, 3*n, n);
+
+  // Start collecting signature
+  *sig_msg_len = 0;
+
+  // Copy index to signature
+  for (i = 0; i < idx_len; i++) {
+    sig_msg[i] = (idx >> 8*(idx_len - 1 - i)) & 255;
+  }
+
+  sig_msg += idx_len;
+  *sig_msg_len += idx_len;
+
+  // Copy R to signature
+  for (i = 0; i < n; i++)
+    sig_msg[i] = R[i];
+
+  sig_msg += n;
+  *sig_msg_len += n;
+
+  // ----------------------------------
+  // Now we start to "really sign"
+  // ----------------------------------
+
+  // Handle lowest layer separately as it is slightly different...
+
+  // Prepare Address
+  setType(ots_addr, 0);
+  idx_tree = idx >> tree_h;
+  idx_leaf = (idx & ((1 << tree_h)-1));
+  setLayerADRS(ots_addr, 0);
+  setTreeADRS(ots_addr, idx_tree);
+  setOTSADRS(ots_addr, idx_leaf);
+
+  // Compute seed for OTS key pair
+  get_seed(ots_seed, sk_seed, n, ots_addr);
+
+  // Compute WOTS signature
+  wots_sign(sig_msg, msg_h, ots_seed, &(params->xmss_par.wots_par), pub_seed, ots_addr);
+
+  sig_msg += params->xmss_par.wots_par.keysize;
+  *sig_msg_len += params->xmss_par.wots_par.keysize;
+
+  memcpy(sig_msg, states[0].auth, tree_h*n);
+  sig_msg += tree_h*n;
+  *sig_msg_len += tree_h*n;
+
+  // prepare signature of remaining layers
+  for (i = 1; i < params->d; i++) {
+    // put WOTS signature in place
+    memcpy(sig_msg, wots_sigs + (i-1)*params->xmss_par.wots_par.keysize, params->xmss_par.wots_par.keysize);
+
+    sig_msg += params->xmss_par.wots_par.keysize;
+    *sig_msg_len += params->xmss_par.wots_par.keysize;
+
+    // put AUTH nodes in place
+    memcpy(sig_msg, states[i].auth, tree_h*n);
+    sig_msg += tree_h*n;
+    *sig_msg_len += tree_h*n;
+  }
+
+  updates = (tree_h - k) >> 1;
+
+  setTreeADRS(addr, (idx_tree + 1));
+  // mandatory update for NEXT_0 (does not count towards h-k/2) if NEXT_0 exists
+  if ((1 + idx_tree) * (1 << tree_h) + idx_leaf < (1ULL << h)) {
+    bds_state_update(&states[params->d], sk_seed, &(params->xmss_par), pub_seed, addr);
+  }
+
+  for (i = 0; i < params->d; i++) {
+    // check if we're not at the end of a tree
+    if (! (((idx + 1) & ((1ULL << ((i+1)*tree_h)) - 1)) == 0)) {
+      idx_leaf = (idx >> (tree_h * i)) & ((1 << tree_h)-1);
+      idx_tree = (idx >> (tree_h * (i+1)));
+      setLayerADRS(addr, i);
+      setTreeADRS(addr, idx_tree);
+      if (i == (unsigned int) (needswap_upto + 1)) {
+        bds_round(&states[i], idx_leaf, sk_seed, &(params->xmss_par), pub_seed, addr);
+      }
+      updates = bds_treehash_update(&states[i], updates, sk_seed, &(params->xmss_par), pub_seed, addr);
+      setTreeADRS(addr, (idx_tree + 1));
+      // if a NEXT-tree exists for this level;
+      if ((1 + idx_tree) * (1 << tree_h) + idx_leaf < (1ULL << (h - tree_h * i))) {
+        if (i > 0 && updates > 0 && states[params->d + i].next_leaf < (1ULL << h)) {
+          bds_state_update(&states[params->d + i], sk_seed, &(params->xmss_par), pub_seed, addr);
+          updates--;
+        }
+      }
+    }
+    else if (idx < (1ULL << h) - 1) {
+      memcpy(&tmp, states+params->d + i, sizeof(bds_state));
+      memcpy(states+params->d + i, states + i, sizeof(bds_state));
+      memcpy(states + i, &tmp, sizeof(bds_state));
+
+      setLayerADRS(ots_addr, (i+1));
+      setTreeADRS(ots_addr, ((idx + 1) >> ((i+2) * tree_h)));
+      setOTSADRS(ots_addr, (((idx >> ((i+1) * tree_h)) + 1) & ((1 << tree_h)-1)));
+
+      get_seed(ots_seed, sk+params->index_len, n, ots_addr);
+      wots_sign(wots_sigs + i*params->xmss_par.wots_par.keysize, states[i].stack, ots_seed, &(params->xmss_par.wots_par), pub_seed, ots_addr);
+
+      states[params->d + i].stackoffset = 0;
+      states[params->d + i].next_leaf = 0;
+
+      updates--; // WOTS-signing counts as one update
+      needswap_upto = i;
+      for (j = 0; j < tree_h-k; j++) {
+        states[i].treehash[j].completed = 1;
+      }
+    }
+  }
+
+  //Whipe secret elements?
+  //zerobytes(tsk, CRYPTO_SECRETKEYBYTES);
+
+  memcpy(sig_msg, msg, msglen);
+  *sig_msg_len += msglen;
+
+  return 0;
+}
+
+/**
+ * Verifies a given message signature pair under a given public key.
+ */
+int xmssmt_sign_open(unsigned char *msg, unsigned long long *msglen, const unsigned char *sig_msg, unsigned long long sig_msg_len, const unsigned char *pk, const xmssmt_params *params)
+{
+  unsigned int n = params->n;
+
+  unsigned int tree_h = params->xmss_par.h;
+  unsigned int idx_len = params->index_len;
+  uint64_t idx_tree;
+  uint32_t idx_leaf;
+
+  unsigned long long i, m_len;
+  unsigned long long idx=0;
+  unsigned char wots_pk[params->xmss_par.wots_par.keysize];
+  unsigned char pkhash[n];
+  unsigned char root[n];
+  unsigned char msg_h[n];
+  unsigned char hash_key[3*n];
+
+  unsigned char pub_seed[n];
+  memcpy(pub_seed, pk+n, n);
+
+  // Init addresses
+  uint32_t ots_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  uint32_t ltree_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+  uint32_t node_addr[8] = {0, 0, 0, 0, 0, 0, 0, 0};
+
+  // Extract index
+  for (i = 0; i < idx_len; i++) {
+    idx |= ((unsigned long long)sig_msg[i]) << (8*(idx_len - 1 - i));
+  }
+  printf("verify:: idx = %llu\n", idx);
+  sig_msg += idx_len;
+  sig_msg_len -= idx_len;
+  
+  // Generate hash key (R || root || idx)
+  memcpy(hash_key, sig_msg,n);
+  memcpy(hash_key+n, pk, n);
+  to_byte(hash_key+2*n, idx, n);
+
+  sig_msg += n;
+  sig_msg_len -= n;
+  
+
+  // hash message (recall, R is now on pole position at sig_msg
+  unsigned long long tmp_sig_len = (params->d * params->xmss_par.wots_par.keysize) + (params->h * n);
+  m_len = sig_msg_len - tmp_sig_len;
+  h_msg(msg_h, sig_msg + tmp_sig_len, m_len, hash_key, 3*n, n);
+
+  
+  //-----------------------
+  // Verify signature
+  //-----------------------
+
+  // Prepare Address
+  idx_tree = idx >> tree_h;
+  idx_leaf = (idx & ((1 << tree_h)-1));
+  setLayerADRS(ots_addr, 0);
+  setTreeADRS(ots_addr, idx_tree);
+  setType(ots_addr, 0);
+
+  memcpy(ltree_addr, ots_addr, 12);
+  setType(ltree_addr, 1);
+
+  memcpy(node_addr, ltree_addr, 12);
+  setType(node_addr, 2);
+  
+  setOTSADRS(ots_addr, idx_leaf);
+
+  // Check WOTS signature
+  wots_pkFromSig(wots_pk, sig_msg, msg_h, &(params->xmss_par.wots_par), pub_seed, ots_addr);
+
+  sig_msg += params->xmss_par.wots_par.keysize;
+  sig_msg_len -= params->xmss_par.wots_par.keysize;
+
+  // Compute Ltree
+  setLtreeADRS(ltree_addr, idx_leaf);
+  l_tree(pkhash, wots_pk, &(params->xmss_par), pub_seed, ltree_addr);
+
+  // Compute root
+  validate_authpath(root, pkhash, idx_leaf, sig_msg, &(params->xmss_par), pub_seed, node_addr);
+
+  sig_msg += tree_h*n;
+  sig_msg_len -= tree_h*n;
+
+  for (i = 1; i < params->d; i++) {
+    // Prepare Address
+    idx_leaf = (idx_tree & ((1 << tree_h)-1));
+    idx_tree = idx_tree >> tree_h;
+
+    setLayerADRS(ots_addr, i);
+    setTreeADRS(ots_addr, idx_tree);
+    setType(ots_addr, 0);
+
+    memcpy(ltree_addr, ots_addr, 12);
+    setType(ltree_addr, 1);
+
+    memcpy(node_addr, ltree_addr, 12);
+    setType(node_addr, 2);
+
+    setOTSADRS(ots_addr, idx_leaf);
+
+    // Check WOTS signature
+    wots_pkFromSig(wots_pk, sig_msg, root, &(params->xmss_par.wots_par), pub_seed, ots_addr);
+
+    sig_msg += params->xmss_par.wots_par.keysize;
+    sig_msg_len -= params->xmss_par.wots_par.keysize;
+
+    // Compute Ltree
+    setLtreeADRS(ltree_addr, idx_leaf);
+    l_tree(pkhash, wots_pk, &(params->xmss_par), pub_seed, ltree_addr);
+
+    // Compute root
+    validate_authpath(root, pkhash, idx_leaf, sig_msg, &(params->xmss_par), pub_seed, node_addr);
+
+    sig_msg += tree_h*n;
+    sig_msg_len -= tree_h*n;
+
+  }
+
+  for (i = 0; i < n; i++)
+    if (root[i] != pk[i])
+      goto fail;
+
+  *msglen = sig_msg_len;
+  for (i = 0; i < *msglen; i++)
+    msg[i] = sig_msg[i];
+
+  return 0;
+
+
+fail:
+  *msglen = sig_msg_len;
+  for (i = 0; i < *msglen; i++)
+    msg[i] = 0;
+  *msglen = -1;
+  return -1;
+}
diff --git a/xmss_fast.h b/xmss_fast.h
new file mode 100644
index 00000000..657cd27f
--- /dev/null
+++ b/xmss_fast.h
@@ -0,0 +1,109 @@
+/*
+xmss_fast.h version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#include "xmss_wots.h"
+
+#ifndef XMSS_H
+#define XMSS_H
+typedef struct{
+  unsigned int level;
+  unsigned long long subtree;
+  unsigned int subleaf;
+} leafaddr;
+
+typedef struct{
+  wots_params wots_par;
+  unsigned int n;
+  unsigned int h;
+  unsigned int k;
+} xmss_params;
+
+typedef struct{
+  xmss_params xmss_par;
+  unsigned int n;
+  unsigned int h;
+  unsigned int d;
+  unsigned int index_len;
+} xmssmt_params;
+
+typedef struct{
+  unsigned int h;
+  unsigned int next_idx;
+  unsigned int stackusage;
+  unsigned char completed;
+  unsigned char *node;
+} treehash_inst;
+
+typedef struct {
+  unsigned char *stack;
+  unsigned int stackoffset;
+  unsigned char *stacklevels;
+  unsigned char *auth;
+  unsigned char *keep;
+  treehash_inst *treehash;
+  unsigned char *retain;
+  unsigned int next_leaf;
+} bds_state;
+
+/**
+ * Initialize BDS state struct
+ * parameter names are the same as used in the description of the BDS traversal
+ */
+void xmss_set_bds_state(bds_state *state, unsigned char *stack, int stackoffset, unsigned char *stacklevels, unsigned char *auth, unsigned char *keep, treehash_inst *treehash, unsigned char *retain, int next_leaf);
+/**
+ * Initializes parameter set.
+ * Needed, for any of the other methods.
+ */
+int xmss_set_params(xmss_params *params, int n, int h, int w, int k);
+/**
+ * Initialize xmssmt_params struct
+ * parameter names are the same as in the draft
+ * 
+ * Especially h is the total tree height, i.e. the XMSS trees have height h/d
+ */
+int xmssmt_set_params(xmssmt_params *params, int n, int h, int d, int w, int k);
+/**
+ * Generates a XMSS key pair for a given parameter set.
+ * Format sk: [(32bit) idx || SK_SEED || SK_PRF || PUB_SEED || root]
+ * Format pk: [root || PUB_SEED] omitting algo oid.
+ */
+int xmss_keypair(unsigned char *pk, unsigned char *sk, bds_state *state, xmss_params *params);
+/**
+ * Signs a message.
+ * Returns 
+ * 1. an array containing the signature followed by the message AND
+ * 2. an updated secret key!
+ * 
+ */
+int xmss_sign(unsigned char *sk, bds_state *state, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg,unsigned long long msglen, const xmss_params *params);
+/**
+ * Verifies a given message signature pair under a given public key.
+ * 
+ * Note: msg and msglen are pure outputs which carry the message in case verification succeeds. The (input) message is assumed to be within sig_msg which has the form (sig||msg). 
+ */
+int xmss_sign_open(unsigned char *msg,unsigned long long *msglen, const unsigned char *sig_msg,unsigned long long sig_msg_len, const unsigned char *pk, const xmss_params *params);
+
+/*
+ * Generates a XMSSMT key pair for a given parameter set.
+ * Format sk: [(ceil(h/8) bit) idx || SK_SEED || SK_PRF || PUB_SEED || root]
+ * Format pk: [root || PUB_SEED] omitting algo oid.
+ */
+int xmssmt_keypair(unsigned char *pk, unsigned char *sk, bds_state *states, unsigned char *wots_sigs, xmssmt_params *params);
+/**
+ * Signs a message.
+ * Returns 
+ * 1. an array containing the signature followed by the message AND
+ * 2. an updated secret key!
+ * 
+ */
+int xmssmt_sign(unsigned char *sk, bds_state *state, unsigned char *wots_sigs, unsigned char *sig_msg, unsigned long long *sig_msg_len, const unsigned char *msg, unsigned long long msglen, const xmssmt_params *params);
+/**
+ * Verifies a given message signature pair under a given public key.
+ */
+int xmssmt_sign_open(unsigned char *msg, unsigned long long *msglen, const unsigned char *sig_msg, unsigned long long sig_msg_len, const unsigned char *pk, const xmssmt_params *params);
+#endif
+
diff --git a/xmss_hash.c b/xmss_hash.c
new file mode 100644
index 00000000..963b584b
--- /dev/null
+++ b/xmss_hash.c
@@ -0,0 +1,133 @@
+/*
+hash.c version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#include "xmss_hash_address.h"
+#include "xmss_commons.h"
+#include "xmss_hash.h"
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <openssl/sha.h>
+#include <openssl/hmac.h>
+#include <openssl/evp.h>
+
+int core_hash_SHA2(unsigned char *, const unsigned int, const unsigned char *,
+    unsigned int, const unsigned char *, unsigned long long, unsigned int);
+
+unsigned char* addr_to_byte(unsigned char *bytes, const uint32_t addr[8]){
+#if IS_LITTLE_ENDIAN==1 
+  int i = 0;
+  for(i=0;i<8;i++)
+    to_byte(bytes+i*4, addr[i],4);
+  return bytes;  
+#else
+  memcpy(bytes, addr, 32);
+  return bytes; 
+#endif   
+}
+
+int core_hash_SHA2(unsigned char *out, const unsigned int type, const unsigned char *key, unsigned int keylen, const unsigned char *in, unsigned long long inlen, unsigned int n){  
+  unsigned long long i = 0;
+  unsigned char buf[inlen + n + keylen];
+  
+  // Input is (toByte(X, 32) || KEY || M) 
+  
+  // set toByte
+  to_byte(buf, type, n);
+  
+  for (i=0; i < keylen; i++) {
+    buf[i+n] = key[i];
+  }
+  
+  for (i=0; i < inlen; i++) {
+    buf[keylen + n + i] = in[i];
+  }
+
+  if (n == 32) {
+    SHA256(buf, inlen + keylen + n, out);
+    return 0;
+  }
+  else {
+    if (n == 64) {
+      SHA512(buf, inlen + keylen + n, out);
+      return 0;
+    }
+  }
+  return 1;
+}
+
+/**
+ * Implements PRF
+ */
+int prf(unsigned char *out, const unsigned char *in, const unsigned char *key, unsigned int keylen)
+{ 
+  return core_hash_SHA2(out, 3, key, keylen, in, 32, keylen);
+}
+
+/*
+ * Implemts H_msg
+ */
+int h_msg(unsigned char *out, const unsigned char *in, unsigned long long inlen, const unsigned char *key, const unsigned int keylen, const unsigned int n)
+{
+  if (keylen != 3*n){
+    // H_msg takes 3n-bit keys, but n does not match the keylength of keylen
+    return -1;
+  }  
+  return core_hash_SHA2(out, 2, key, keylen, in, inlen, n);
+}
+
+/**
+ * We assume the left half is in in[0]...in[n-1]
+ */
+int hash_h(unsigned char *out, const unsigned char *in, const unsigned char *pub_seed, uint32_t addr[8], const unsigned int n)
+{
+
+  unsigned char buf[2*n];
+  unsigned char key[n];
+  unsigned char bitmask[2*n];
+  unsigned char byte_addr[32];
+  unsigned int i;
+
+  setKeyAndMask(addr, 0);
+  addr_to_byte(byte_addr, addr);
+  prf(key, byte_addr, pub_seed, n);
+  // Use MSB order
+  setKeyAndMask(addr, 1);
+  addr_to_byte(byte_addr, addr);
+  prf(bitmask, byte_addr, pub_seed, n);
+  setKeyAndMask(addr, 2);
+  addr_to_byte(byte_addr, addr);
+  prf(bitmask+n, byte_addr, pub_seed, n);
+  for (i = 0; i < 2*n; i++) {
+    buf[i] = in[i] ^ bitmask[i];
+  }
+  return core_hash_SHA2(out, 1, key, n, buf, 2*n, n);
+}
+
+int hash_f(unsigned char *out, const unsigned char *in, const unsigned char *pub_seed, uint32_t addr[8], const unsigned int n)
+{
+  unsigned char buf[n];
+  unsigned char key[n];
+  unsigned char bitmask[n];
+  unsigned char byte_addr[32];
+  unsigned int i;
+
+  setKeyAndMask(addr, 0);  
+  addr_to_byte(byte_addr, addr);  
+  prf(key, byte_addr, pub_seed, n);
+  
+  setKeyAndMask(addr, 1);
+  addr_to_byte(byte_addr, addr);
+  prf(bitmask, byte_addr, pub_seed, n);
+  
+  for (i = 0; i < n; i++) {
+    buf[i] = in[i] ^ bitmask[i];
+  }
+  return core_hash_SHA2(out, 0, key, n, buf, n, n);
+}
diff --git a/xmss_hash.h b/xmss_hash.h
new file mode 100644
index 00000000..2fed7300
--- /dev/null
+++ b/xmss_hash.h
@@ -0,0 +1,19 @@
+/*
+hash.h version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#ifndef HASH_H
+#define HASH_H
+
+#define IS_LITTLE_ENDIAN 1
+
+unsigned char* addr_to_byte(unsigned char *bytes, const uint32_t addr[8]);
+int prf(unsigned char *out, const unsigned char *in, const unsigned char *key, unsigned int keylen);
+int h_msg(unsigned char *out,const unsigned char *in,unsigned long long inlen, const unsigned char *key, const unsigned int keylen, const unsigned int n);
+int hash_h(unsigned char *out, const unsigned char *in, const unsigned char *pub_seed, uint32_t addr[8], const unsigned int n);
+int hash_f(unsigned char *out, const unsigned char *in, const unsigned char *pub_seed, uint32_t addr[8], const unsigned int n);
+
+#endif
diff --git a/xmss_hash_address.c b/xmss_hash_address.c
new file mode 100644
index 00000000..223c6f8a
--- /dev/null
+++ b/xmss_hash_address.c
@@ -0,0 +1,59 @@
+/*
+hash_address.c version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+#include <stdint.h>
+#include "xmss_hash_address.h"	/* prototypes */
+
+void setLayerADRS(uint32_t adrs[8], uint32_t layer){
+  adrs[0] = layer;
+}
+
+void setTreeADRS(uint32_t adrs[8], uint64_t tree){
+  adrs[1] = (uint32_t) (tree >> 32);
+  adrs[2] = (uint32_t) tree;
+}
+
+void setType(uint32_t adrs[8], uint32_t type){
+  adrs[3] = type;
+  int i;
+  for(i = 4; i < 8; i++){
+    adrs[i] = 0;
+  }
+}
+
+void setKeyAndMask(uint32_t adrs[8], uint32_t keyAndMask){
+  adrs[7] = keyAndMask;
+}
+
+// OTS
+
+void setOTSADRS(uint32_t adrs[8], uint32_t ots){
+  adrs[4] = ots;
+}
+
+void setChainADRS(uint32_t adrs[8], uint32_t chain){
+  adrs[5] = chain;
+}
+
+void setHashADRS(uint32_t adrs[8], uint32_t hash){
+  adrs[6] = hash;
+}
+
+// L-tree
+
+void setLtreeADRS(uint32_t adrs[8], uint32_t ltree){
+  adrs[4] = ltree;
+}
+
+// Hash Tree & L-tree
+
+void setTreeHeight(uint32_t adrs[8], uint32_t treeHeight){
+  adrs[5] = treeHeight;
+}
+
+void setTreeIndex(uint32_t adrs[8], uint32_t treeIndex){
+  adrs[6] = treeIndex;
+}
diff --git a/xmss_hash_address.h b/xmss_hash_address.h
new file mode 100644
index 00000000..73cbfd61
--- /dev/null
+++ b/xmss_hash_address.h
@@ -0,0 +1,37 @@
+/*
+hash_address.h version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#include <stdint.h>
+
+void setLayerADRS(uint32_t adrs[8], uint32_t layer);
+
+void setTreeADRS(uint32_t adrs[8], uint64_t tree);
+
+void setType(uint32_t adrs[8], uint32_t type);
+
+void setKeyAndMask(uint32_t adrs[8], uint32_t keyAndMask);
+
+// OTS
+
+void setOTSADRS(uint32_t adrs[8], uint32_t ots);
+
+void setChainADRS(uint32_t adrs[8], uint32_t chain);
+
+void setHashADRS(uint32_t adrs[8], uint32_t hash);
+
+// L-tree
+
+void setLtreeADRS(uint32_t adrs[8], uint32_t ltree);
+
+// Hash Tree & L-tree
+
+void setTreeHeight(uint32_t adrs[8], uint32_t treeHeight);
+
+void setTreeIndex(uint32_t adrs[8], uint32_t treeIndex);
+
+
+
diff --git a/xmss_wots.c b/xmss_wots.c
new file mode 100644
index 00000000..fcd03340
--- /dev/null
+++ b/xmss_wots.c
@@ -0,0 +1,185 @@
+/*
+wots.c version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <limits.h>
+#include "xmss_commons.h"
+#include "xmss_hash.h"
+#include "xmss_wots.h"
+#include "xmss_hash_address.h"
+
+
+/* libm-free version of log2() for wots */
+static inline int
+wots_log2(uint32_t v)
+{
+  int      b;
+
+  for (b = sizeof (v) * CHAR_BIT - 1; b >= 0; b--) {
+    if ((1U << b) & v) {
+      return b;
+    }
+  }
+  return 0;
+}
+
+void
+wots_set_params(wots_params *params, int n, int w)
+{
+  params->n = n;
+  params->w = w;
+  params->log_w = wots_log2(params->w);
+  params->len_1 = (CHAR_BIT * n) / params->log_w;
+  params->len_2 = (wots_log2(params->len_1 * (w - 1)) / params->log_w) + 1;
+  params->len = params->len_1 + params->len_2;
+  params->keysize = params->len * params->n;
+}
+
+/**
+ * Helper method for pseudorandom key generation
+ * Expands an n-byte array into a len*n byte array
+ * this is done using PRF
+ */
+static void expand_seed(unsigned char *outseeds, const unsigned char *inseed, const wots_params *params)
+{
+  uint32_t i = 0;
+  unsigned char ctr[32];
+  for(i = 0; i < params->len; i++){
+    to_byte(ctr, i, 32);
+    prf((outseeds + (i*params->n)), ctr, inseed, params->n);
+  }
+}
+
+/**
+ * Computes the chaining function.
+ * out and in have to be n-byte arrays
+ *
+ * interpretes in as start-th value of the chain
+ * addr has to contain the address of the chain
+ */
+static void gen_chain(unsigned char *out, const unsigned char *in, unsigned int start, unsigned int steps, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
+{
+  uint32_t i, j;
+  for (j = 0; j < params->n; j++)
+    out[j] = in[j];
+
+  for (i = start; i < (start+steps) && i < params->w; i++) {
+    setHashADRS(addr, i);
+    hash_f(out, out, pub_seed, addr, params->n);
+  }
+}
+
+/**
+ * base_w algorithm as described in draft.
+ *
+ *
+ */
+static void base_w(int *output, const int out_len, const unsigned char *input, const wots_params *params)
+{
+  int in = 0;
+  int out = 0;
+  uint32_t total = 0;
+  int bits = 0;
+  int consumed = 0;
+
+  for (consumed = 0; consumed < out_len; consumed++) {
+    if (bits == 0) {
+      total = input[in];
+      in++;
+      bits += 8;
+    }
+    bits -= params->log_w;
+    output[out] = (total >> bits) & (params->w - 1);
+    out++;
+  }
+}
+
+void wots_pkgen(unsigned char *pk, const unsigned char *sk, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
+{
+  uint32_t i;
+  expand_seed(pk, sk, params);
+  for (i=0; i < params->len; i++) {
+    setChainADRS(addr, i);
+    gen_chain(pk+i*params->n, pk+i*params->n, 0, params->w-1, params, pub_seed, addr);
+  }
+}
+
+
+int wots_sign(unsigned char *sig, const unsigned char *msg, const unsigned char *sk, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
+{
+  //int basew[params->len];
+  int csum = 0;
+  uint32_t i = 0;
+  int *basew = calloc(params->len, sizeof(int));
+  if (basew == NULL)
+    return -1;
+
+  base_w(basew, params->len_1, msg, params);
+
+  for (i=0; i < params->len_1; i++) {
+    csum += params->w - 1 - basew[i];
+  }
+
+  csum = csum << (8 - ((params->len_2 * params->log_w) % 8));
+
+  int len_2_bytes = ((params->len_2 * params->log_w) + 7) / 8;
+
+  unsigned char csum_bytes[len_2_bytes];
+  to_byte(csum_bytes, csum, len_2_bytes);
+
+  int csum_basew[params->len_2];
+  base_w(csum_basew, params->len_2, csum_bytes, params);
+
+  for (i = 0; i < params->len_2; i++) {
+    basew[params->len_1 + i] = csum_basew[i];
+  }
+
+  expand_seed(sig, sk, params);
+
+  for (i = 0; i < params->len; i++) {
+    setChainADRS(addr, i);
+    gen_chain(sig+i*params->n, sig+i*params->n, 0, basew[i], params, pub_seed, addr);
+  }
+  free(basew);
+  return 0;
+}
+
+int wots_pkFromSig(unsigned char *pk, const unsigned char *sig, const unsigned char *msg, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8])
+{
+  int csum = 0;
+  uint32_t i = 0;
+  int *basew = calloc(params->len, sizeof(int));
+  if (basew == NULL)
+    return -1;
+
+  base_w(basew, params->len_1, msg, params);
+
+  for (i=0; i < params->len_1; i++) {
+    csum += params->w - 1 - basew[i];
+  }
+
+  csum = csum << (8 - ((params->len_2 * params->log_w) % 8));
+
+  int len_2_bytes = ((params->len_2 * params->log_w) + 7) / 8;
+
+  unsigned char csum_bytes[len_2_bytes];
+  to_byte(csum_bytes, csum, len_2_bytes);
+
+  int csum_basew[params->len_2];
+  base_w(csum_basew, params->len_2, csum_bytes, params);
+
+  for (i = 0; i < params->len_2; i++) {
+    basew[params->len_1 + i] = csum_basew[i];
+  }
+  for (i=0; i < params->len; i++) {
+    setChainADRS(addr, i);
+    gen_chain(pk+i*params->n, sig+i*params->n, basew[i], params->w-1-basew[i], params, pub_seed, addr);
+  }
+  free(basew);
+  return 0;
+}
diff --git a/xmss_wots.h b/xmss_wots.h
new file mode 100644
index 00000000..49543108
--- /dev/null
+++ b/xmss_wots.h
@@ -0,0 +1,59 @@
+/*
+wots.h version 20160722
+Andreas Hülsing
+Joost Rijneveld
+Public domain.
+*/
+
+#ifndef WOTS_H
+#define WOTS_H
+
+#include "stdint.h"
+
+/**
+ * WOTS parameter set
+ * 
+ * Meaning as defined in draft-irtf-cfrg-xmss-hash-based-signatures-02
+ */
+typedef struct {
+  uint32_t len_1;
+  uint32_t len_2;
+  uint32_t len;
+  uint32_t n;
+  uint32_t w;
+  uint32_t log_w;
+  uint32_t keysize;
+} wots_params;
+
+/**
+ * Set the WOTS parameters, 
+ * only m, n, w are required as inputs,
+ * len, len_1, and len_2 are computed from those.
+ *
+ * Assumes w is a power of 2
+ */
+void wots_set_params(wots_params *params, int n, int w);
+
+/**
+ * WOTS key generation. Takes a 32byte seed for the secret key, expands it to a full WOTS secret key and computes the corresponding public key. 
+ * For this it takes the seed pub_seed which is used to generate bitmasks and hash keys and the address of this WOTS key pair addr
+ * 
+ * params, must have been initialized before using wots_set params for params ! This is not done in this function
+ * 
+ * Places the computed public key at address pk.
+ */
+void wots_pkgen(unsigned char *pk, const unsigned char *sk, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8]);
+
+/**
+ * Takes a m-byte message and the 32-byte seed for the secret key to compute a signature that is placed at "sig".
+ *  
+ */
+int wots_sign(unsigned char *sig, const unsigned char *msg, const unsigned char *sk, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8]);
+
+/**
+ * Takes a WOTS signature, a m-byte message and computes a WOTS public key that it places at pk.
+ * 
+ */
+int wots_pkFromSig(unsigned char *pk, const unsigned char *sig, const unsigned char *msg, const wots_params *params, const unsigned char *pub_seed, uint32_t addr[8]);
+
+#endif