From a6be8e7c63a6251fb97b03b4d58d70655939876a Mon Sep 17 00:00:00 2001 From: markus Date: Fri, 23 Feb 2018 15:58:37 +0000 Subject: [PATCH] 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@ --- usr.bin/ssh/Makefile.inc | 14 +- usr.bin/ssh/authfd.c | 39 +- usr.bin/ssh/authfd.h | 5 +- usr.bin/ssh/authfile.c | 8 +- usr.bin/ssh/cipher.c | 4 +- usr.bin/ssh/dns.c | 7 +- usr.bin/ssh/dns.h | 5 +- usr.bin/ssh/pathnames.h | 4 +- usr.bin/ssh/readconf.c | 3 +- usr.bin/ssh/servconf.c | 4 +- usr.bin/ssh/ssh-add.c | 74 ++- usr.bin/ssh/ssh-agent.c | 24 +- usr.bin/ssh/ssh-keygen.c | 19 +- usr.bin/ssh/ssh-keyscan.c | 12 +- usr.bin/ssh/ssh-keysign.c | 5 +- usr.bin/ssh/ssh-xmss.c | 188 ++++++ usr.bin/ssh/ssh.c | 15 +- usr.bin/ssh/sshconnect.c | 5 +- usr.bin/ssh/sshd.c | 6 +- usr.bin/ssh/sshkey-xmss.c | 1048 +++++++++++++++++++++++++++++ usr.bin/ssh/sshkey-xmss.h | 56 ++ usr.bin/ssh/sshkey.c | 410 +++++++++++- usr.bin/ssh/sshkey.h | 35 +- usr.bin/ssh/xmss_commons.c | 27 + usr.bin/ssh/xmss_commons.h | 15 + usr.bin/ssh/xmss_fast.c | 1099 +++++++++++++++++++++++++++++++ usr.bin/ssh/xmss_fast.h | 109 +++ usr.bin/ssh/xmss_hash.c | 133 ++++ usr.bin/ssh/xmss_hash.h | 19 + usr.bin/ssh/xmss_hash_address.c | 59 ++ usr.bin/ssh/xmss_hash_address.h | 37 ++ usr.bin/ssh/xmss_wots.c | 185 ++++++ usr.bin/ssh/xmss_wots.h | 59 ++ 33 files changed, 3659 insertions(+), 73 deletions(-) create mode 100644 usr.bin/ssh/ssh-xmss.c create mode 100644 usr.bin/ssh/sshkey-xmss.c create mode 100644 usr.bin/ssh/sshkey-xmss.h create mode 100644 usr.bin/ssh/xmss_commons.c create mode 100644 usr.bin/ssh/xmss_commons.h create mode 100644 usr.bin/ssh/xmss_fast.c create mode 100644 usr.bin/ssh/xmss_fast.h create mode 100644 usr.bin/ssh/xmss_hash.c create mode 100644 usr.bin/ssh/xmss_hash.h create mode 100644 usr.bin/ssh/xmss_hash_address.c create mode 100644 usr.bin/ssh/xmss_hash_address.h create mode 100644 usr.bin/ssh/xmss_wots.c create mode 100644 usr.bin/ssh/xmss_wots.h diff --git a/usr.bin/ssh/Makefile.inc b/usr.bin/ssh/Makefile.inc index 13dd9a04fc4..3d72e8f328c 100644 --- a/usr.bin/ssh/Makefile.inc +++ b/usr.bin/ssh/Makefile.inc @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile.inc,v 1.57 2018/01/08 15:37:21 markus Exp $ +# $OpenBSD: Makefile.inc,v 1.58 2018/02/23 15:58:37 markus Exp $ .include @@ -122,4 +122,16 @@ SRCS_PKCS11+= ssh-pkcs11.c SRCS_PKCS11+= .endif +WITH_XMSS?= no +.if (${WITH_XMSS:L} == "yes") +CFLAGS+= -DWITH_XMSS +SRCS_KEY+= ssh-xmss.c +SRCS_KEY+= sshkey-xmss.c +SRCS_KEY+= xmss_commons.c +SRCS_KEY+= xmss_fast.c +SRCS_KEY+= xmss_hash.c +SRCS_KEY+= xmss_hash_address.c +SRCS_KEY+= xmss_wots.c +.endif + .include diff --git a/usr.bin/ssh/authfd.c b/usr.bin/ssh/authfd.c index e4d186d01d4..358c977438b 100644 --- a/usr.bin/ssh/authfd.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -127,7 +127,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 || @@ -142,7 +142,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; @@ -389,19 +389,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; @@ -414,6 +402,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; @@ -425,10 +418,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) @@ -445,11 +438,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: @@ -457,7 +454,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; @@ -535,7 +532,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/usr.bin/ssh/authfd.h b/usr.bin/ssh/authfd.h index 41997ce6d29..ab954ffc0a3 100644 --- a/usr.bin/ssh/authfd.h +++ b/usr.bin/ssh/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 @@ -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/usr.bin/ssh/authfile.c b/usr.bin/ssh/authfile.c index 06a4f92effa..4f23fbce3d1 100644 --- a/usr.bin/ssh/authfile.c +++ b/usr.bin/ssh/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. * @@ -186,6 +186,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; @@ -244,6 +246,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); @@ -392,6 +397,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/usr.bin/ssh/cipher.c b/usr.bin/ssh/cipher.c index d1db1b5c691..b3587b55ff3 100644 --- a/usr.bin/ssh/cipher.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -395,7 +395,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/usr.bin/ssh/dns.c b/usr.bin/ssh/dns.c index 33d93a237b5..c56e35e0f37 100644 --- a/usr.bin/ssh/dns.c +++ b/usr.bin/ssh/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. @@ -102,6 +102,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/usr.bin/ssh/dns.h b/usr.bin/ssh/dns.h index 68443f7cbbb..91f3c632dd1 100644 --- a/usr.bin/ssh/dns.h +++ b/usr.bin/ssh/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/usr.bin/ssh/pathnames.h b/usr.bin/ssh/pathnames.h index b1bd7b82e5b..512cb99591a 100644 --- a/usr.bin/ssh/pathnames.h +++ b/usr.bin/ssh/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 @@ -34,6 +34,7 @@ #define _PATH_HOST_ECDSA_KEY_FILE SSHDIR "/ssh_host_ecdsa_key" #define _PATH_HOST_RSA_KEY_FILE SSHDIR "/ssh_host_rsa_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_DH_MODULI ETCDIR "/moduli" #define _PATH_SSH_PROGRAM "/usr/bin/ssh" @@ -67,6 +68,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/usr.bin/ssh/readconf.c b/usr.bin/ssh/readconf.c index db4632dba9e..5d17b725600 100644 --- a/usr.bin/ssh/readconf.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -1926,6 +1926,7 @@ fill_default_options(Options * options) add_identity_file(options, "~/", _PATH_SSH_CLIENT_ID_ECDSA, 0); 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/usr.bin/ssh/servconf.c b/usr.bin/ssh/servconf.c index 93a1e54d7d7..c17c949a36a 100644 --- a/usr.bin/ssh/servconf.c +++ b/usr.bin/ssh/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 , Espoo, Finland * All rights reserved @@ -232,6 +232,8 @@ fill_default_server_options(ServerOptions *options) _PATH_HOST_ECDSA_KEY_FILE); 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/usr.bin/ssh/ssh-add.c b/usr.bin/ssh/ssh-add.c index f017ec71fb8..f5c5b24a3bd 100644 --- a/usr.bin/ssh/ssh-add.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -70,6 +70,7 @@ static char *default_files[] = { _PATH_SSH_CLIENT_ID_DSA, _PATH_SSH_CLIENT_ID_ECDSA, _PATH_SSH_CLIENT_ID_ED25519, + _PATH_SSH_CLIENT_ID_XMSS, NULL }; @@ -81,6 +82,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 @@ -182,7 +187,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; @@ -260,8 +268,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) @@ -309,7 +349,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; @@ -360,6 +400,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) { @@ -384,7 +425,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); @@ -446,6 +492,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"); @@ -487,7 +535,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); @@ -512,6 +560,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/usr.bin/ssh/ssh-agent.c b/usr.bin/ssh/ssh-agent.c index 267f126b2e6..58d31bff481 100644 --- a/usr.bin/ssh/ssh-agent.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -230,7 +230,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)); @@ -387,7 +388,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; @@ -418,6 +419,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: @@ -433,14 +446,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/usr.bin/ssh/ssh-keygen.c b/usr.bin/ssh/ssh-keygen.c index 4e45d7d70aa..d57ef78d49a 100644 --- a/usr.bin/ssh/ssh-keygen.c +++ b/usr.bin/ssh/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 * Copyright (c) 1994 Tatu Ylonen , Espoo, Finland @@ -267,6 +267,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"); } @@ -953,6 +957,9 @@ do_gen_all_hostkeys(struct passwd *pw) { "ecdsa", "ECDSA",_PATH_HOST_ECDSA_KEY_FILE }, #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 } }; @@ -1439,7 +1446,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)); @@ -1689,7 +1697,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)); @@ -2385,7 +2394,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); @@ -2665,6 +2674,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/usr.bin/ssh/ssh-keyscan.c b/usr.bin/ssh/ssh-keyscan.c index b5c9539d2d5..c52a518651a 100644 --- a/usr.bin/ssh/ssh-keyscan.c +++ b/usr.bin/ssh/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 . * @@ -52,9 +52,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; @@ -220,6 +221,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," @@ -696,6 +701,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/usr.bin/ssh/ssh-keysign.c b/usr.bin/ssh/ssh-keysign.c index dc2c5eec457..38cb080b7a8 100644 --- a/usr.bin/ssh/ssh-keysign.c +++ b/usr.bin/ssh/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. * @@ -161,7 +161,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; @@ -185,6 +185,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/usr.bin/ssh/ssh-xmss.c b/usr.bin/ssh/ssh-xmss.c new file mode 100644 index 00000000000..d9dafd762a6 --- /dev/null +++ b/usr.bin/ssh/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 +#include + +#include +#include +#include + +#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/usr.bin/ssh/ssh.c b/usr.bin/ssh/ssh.c index 55cafe2bcb5..4f2ffd03dd1 100644 --- a/usr.bin/ssh/ssh.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -1350,7 +1350,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 */ @@ -1371,6 +1371,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 && @@ -1378,7 +1382,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) { sensitive_data.keys[1] = key_load_cert( _PATH_HOST_ECDSA_KEY_FILE); sensitive_data.keys[2] = key_load_cert( @@ -1395,6 +1400,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/usr.bin/ssh/sshconnect.c b/usr.bin/ssh/sshconnect.c index ba66b755461..29400574863 100644 --- a/usr.bin/ssh/sshconnect.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -1435,6 +1435,7 @@ show_other_keys(struct hostkeys *hostkeys, struct sshkey *key) KEY_DSA, KEY_ECDSA, KEY_ED25519, + KEY_XMSS, -1 }; int i, ret = 0; @@ -1552,7 +1553,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/usr.bin/ssh/sshd.c b/usr.bin/ssh/sshd.c index be1bafa9395..42104451236 100644 --- a/usr.bin/ssh/sshd.c +++ b/usr.bin/ssh/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 * Copyright (c) 1995 Tatu Ylonen , Espoo, Finland @@ -663,6 +663,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); @@ -684,6 +685,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); @@ -710,6 +712,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: @@ -1603,6 +1606,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/usr.bin/ssh/sshkey-xmss.c b/usr.bin/ssh/sshkey-xmss.c new file mode 100644 index 00000000000..41cc1bade17 --- /dev/null +++ b/usr.bin/ssh/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 +#include + +#include +#include +#include +#include +#include + +#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/usr.bin/ssh/sshkey-xmss.h b/usr.bin/ssh/sshkey-xmss.h new file mode 100644 index 00000000000..b9f8ead1047 --- /dev/null +++ b/usr.bin/ssh/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/usr.bin/ssh/sshkey.c b/usr.bin/ssh/sshkey.c index 2e9cdaaa82e..80a7875ff31 100644 --- a/usr.bin/ssh/sshkey.c +++ b/usr.bin/ssh/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. @@ -51,8 +51,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" @@ -67,6 +70,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); @@ -83,6 +88,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 }, @@ -262,6 +272,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; @@ -275,6 +287,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; @@ -302,6 +315,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; } @@ -441,6 +456,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: @@ -474,6 +491,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: @@ -522,6 +541,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: @@ -576,6 +597,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: @@ -653,6 +688,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; } @@ -672,7 +714,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; @@ -696,6 +739,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) @@ -738,6 +784,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; } @@ -747,32 +806,40 @@ 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); return r; } +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; @@ -784,7 +851,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) @@ -805,13 +872,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 @@ -830,7 +897,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; @@ -1147,6 +1215,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; @@ -1242,6 +1314,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; @@ -1496,6 +1587,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); @@ -1635,6 +1731,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; } @@ -1776,7 +1895,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; @@ -1925,6 +2044,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; @@ -1947,6 +2096,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); @@ -2039,6 +2189,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; } @@ -2070,6 +2225,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; } @@ -2093,6 +2253,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 @@ -2152,6 +2314,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: @@ -2183,6 +2368,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; } @@ -2265,6 +2455,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; @@ -2422,7 +2624,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; @@ -2506,6 +2709,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; @@ -2516,14 +2749,22 @@ sshkey_private_serialize(const struct sshkey *key, struct sshbuf *b) return r; } +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 */ @@ -2666,6 +2907,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; @@ -2697,6 +2980,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; } @@ -2951,7 +3237,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; @@ -3310,6 +3597,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: @@ -3491,6 +3781,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: @@ -3522,3 +3815,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/usr.bin/ssh/sshkey.h b/usr.bin/ssh/sshkey.h index 5057bc40631..b2fdc1037e2 100644 --- a/usr.bin/ssh/sshkey.h +++ b/usr.bin/ssh/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. @@ -55,6 +55,8 @@ enum sshkey_types { KEY_DSA_CERT, KEY_ECDSA_CERT, KEY_ED25519_CERT, + KEY_XMSS, + KEY_XMSS_CERT, KEY_UNSPEC }; @@ -70,6 +72,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 @@ -98,6 +108,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; }; @@ -165,6 +180,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 *); @@ -180,6 +197,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 */ @@ -194,6 +213,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, @@ -216,6 +244,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 #ifndef WITH_OPENSSL diff --git a/usr.bin/ssh/xmss_commons.c b/usr.bin/ssh/xmss_commons.c new file mode 100644 index 00000000000..51171af91b2 --- /dev/null +++ b/usr.bin/ssh/xmss_commons.c @@ -0,0 +1,27 @@ +/* +xmss_commons.c 20160722 +Andreas Hülsing +Joost Rijneveld +Public domain. +*/ + +#include "xmss_commons.h" +#include +#include +#include + +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/usr.bin/ssh/xmss_commons.h b/usr.bin/ssh/xmss_commons.h new file mode 100644 index 00000000000..32fd4e2dc1a --- /dev/null +++ b/usr.bin/ssh/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 +#include + +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/usr.bin/ssh/xmss_fast.c b/usr.bin/ssh/xmss_fast.c new file mode 100644 index 00000000000..7ddc92f83d3 --- /dev/null +++ b/usr.bin/ssh/xmss_fast.c @@ -0,0 +1,1099 @@ +/* +xmss_fast.c version 20160722 +Andreas Hülsing +Joost Rijneveld +Public domain. +*/ + +#include "xmss_fast.h" +#include +#include +#include + +#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<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/usr.bin/ssh/xmss_fast.h b/usr.bin/ssh/xmss_fast.h new file mode 100644 index 00000000000..657cd27f47c --- /dev/null +++ b/usr.bin/ssh/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/usr.bin/ssh/xmss_hash.c b/usr.bin/ssh/xmss_hash.c new file mode 100644 index 00000000000..963b584b917 --- /dev/null +++ b/usr.bin/ssh/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 +#include +#include +#include +#include +#include +#include + +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/usr.bin/ssh/xmss_hash.h b/usr.bin/ssh/xmss_hash.h new file mode 100644 index 00000000000..2fed73009f1 --- /dev/null +++ b/usr.bin/ssh/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/usr.bin/ssh/xmss_hash_address.c b/usr.bin/ssh/xmss_hash_address.c new file mode 100644 index 00000000000..223c6f8ab4e --- /dev/null +++ b/usr.bin/ssh/xmss_hash_address.c @@ -0,0 +1,59 @@ +/* +hash_address.c version 20160722 +Andreas Hülsing +Joost Rijneveld +Public domain. +*/ +#include +#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/usr.bin/ssh/xmss_hash_address.h b/usr.bin/ssh/xmss_hash_address.h new file mode 100644 index 00000000000..73cbfd61cf0 --- /dev/null +++ b/usr.bin/ssh/xmss_hash_address.h @@ -0,0 +1,37 @@ +/* +hash_address.h version 20160722 +Andreas Hülsing +Joost Rijneveld +Public domain. +*/ + +#include + +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/usr.bin/ssh/xmss_wots.c b/usr.bin/ssh/xmss_wots.c new file mode 100644 index 00000000000..fcd03340532 --- /dev/null +++ b/usr.bin/ssh/xmss_wots.c @@ -0,0 +1,185 @@ +/* +wots.c version 20160722 +Andreas Hülsing +Joost Rijneveld +Public domain. +*/ + +#include +#include +#include +#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/usr.bin/ssh/xmss_wots.h b/usr.bin/ssh/xmss_wots.h new file mode 100644 index 00000000000..49543108776 --- /dev/null +++ b/usr.bin/ssh/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 -- 2.20.1