upstream: Add support for a PQC KEX/KEM:

sntrup4591761x25519-sha512@tinyssh.org using the Streamlined NTRU Prime
4591^761 implementation from SUPERCOP coupled with X25519 as a stop-loss. Not
enabled by default.

introduce KEM API; a simplified framework for DH-ish KEX methods.

from markus@ feedback & ok djm@

OpenBSD-Commit-ID: d687f76cffd3561dd73eb302d17a1c3bf321d1a7

17 files changed, 1665 insertions, 40 deletions

diff --git a/Makefile.in b/Makefile.in
index 7b5de6039..2b22e9f47 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -100,8 +100,10 @@ LIBSSH_OBJS=${LIBOPENSSH_OBJS} \
 	kex.o kexdh.o kexgex.o kexecdh.o kexc25519.o \
 	kexdhc.o kexgexc.o kexecdhc.o kexc25519c.o \
 	kexdhs.o kexgexs.o kexecdhs.o kexc25519s.o \
+	sntrup4591761.o kexsntrup4591761x25519.o kexkemc.o kexkems.o \
 	platform-pledge.o platform-tracing.o platform-misc.o
 
+
 SSHOBJS= ssh.o readconf.o clientloop.o sshtty.o \
 	sshconnect.o sshconnect2.o mux.o
 
diff --git a/crypto_api.h b/crypto_api.h
index 7f45bbd69..eb05251ff 100644
--- a/crypto_api.h
+++ b/crypto_api.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: crypto_api.h,v 1.4 2017/12/14 21:07:39 naddy Exp $ */
+/* $OpenBSD: crypto_api.h,v 1.5 2019/01/21 10:20:12 djm Exp $ */
 
 /*
  * Assembled from generated headers and source files by Markus Friedl.
@@ -15,10 +15,15 @@
 #endif
 #include <stdlib.h>
 
+typedef int8_t crypto_int8;
+typedef uint8_t crypto_uint8;
+typedef int16_t crypto_int16;
+typedef uint16_t crypto_uint16;
 typedef int32_t crypto_int32;
 typedef uint32_t crypto_uint32;
 
 #define randombytes(buf, buf_len) arc4random_buf((buf), (buf_len))
+#define small_random32() arc4random()
 
 #define crypto_hash_sha512_BYTES 64U
 
@@ -37,4 +42,15 @@ int	crypto_sign_ed25519_open(unsigned char *, unsigned long long *,
     const unsigned char *, unsigned long long, const unsigned char *);
 int	crypto_sign_ed25519_keypair(unsigned char *, unsigned char *);
 
+#define crypto_kem_sntrup4591761_PUBLICKEYBYTES 1218
+#define crypto_kem_sntrup4591761_SECRETKEYBYTES 1600
+#define crypto_kem_sntrup4591761_CIPHERTEXTBYTES 1047
+#define crypto_kem_sntrup4591761_BYTES 32
+
+int	crypto_kem_sntrup4591761_enc(unsigned char *cstr, unsigned char *k,
+    const unsigned char *pk);
+int	crypto_kem_sntrup4591761_dec(unsigned char *k,
+    const unsigned char *cstr, const unsigned char *sk);
+int	crypto_kem_sntrup4591761_keypair(unsigned char *pk, unsigned char *sk);
+
 #endif /* crypto_api_h */
diff --git a/kex.c b/kex.c
index d8c71bb3e..0dba2cefa 100644
--- a/kex.c
+++ b/kex.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: kex.c,v 1.146 2019/01/21 10:07:22 djm Exp $ */
+/* $OpenBSD: kex.c,v 1.147 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
  *
@@ -108,6 +108,8 @@ static const struct kexalg kexalgs[] = {
 #if defined(HAVE_EVP_SHA256) || !defined(WITH_OPENSSL)
 	{ KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
 	{ KEX_CURVE25519_SHA256_OLD, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
+	{ KEX_SNTRUP4591761X25519_SHA512, KEX_KEM_SNTRUP4591761X25519_SHA512, 0,
+	    SSH_DIGEST_SHA512 },
 #endif /* HAVE_EVP_SHA256 || !WITH_OPENSSL */
 	{ NULL, -1, -1, -1},
 };
@@ -653,6 +655,7 @@ kex_free(struct kex *kex)
 	sshbuf_free(kex->my);
 	sshbuf_free(kex->client_version);
 	sshbuf_free(kex->server_version);
+	sshbuf_free(kex->kem_client_pub);
 	free(kex->session_id);
 	free(kex->failed_choice);
 	free(kex->hostkey_alg);
@@ -1089,7 +1092,7 @@ kex_verify_host_key(struct ssh *ssh, struct sshkey *server_host_key)
 
 #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH)
 void
-dump_digest(char *msg, u_char *digest, int len)
+dump_digest(const char *msg, const u_char *digest, int len)
 {
 	fprintf(stderr, "%s\n", msg);
 	sshbuf_dump_data(digest, len, stderr);
diff --git a/kex.h b/kex.h
index e404d0365..258a64712 100644
--- a/kex.h
+++ b/kex.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: kex.h,v 1.98 2019/01/21 10:07:22 djm Exp $ */
+/* $OpenBSD: kex.h,v 1.99 2019/01/21 10:20:12 djm Exp $ */
 
 /*
  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
@@ -27,6 +27,7 @@
 #define KEX_H
 
 #include "mac.h"
+#include "crypto_api.h"
 
 #ifdef WITH_LEAKMALLOC
 #include "leakmalloc.h"
@@ -62,6 +63,7 @@
 #define	KEX_ECDH_SHA2_NISTP521		"ecdh-sha2-nistp521"
 #define	KEX_CURVE25519_SHA256		"curve25519-sha256"
 #define	KEX_CURVE25519_SHA256_OLD	"curve25519-sha256@libssh.org"
+#define	KEX_SNTRUP4591761X25519_SHA512	"sntrup4591761x25519-sha512@tinyssh.org"
 
 #define COMP_NONE	0
 /* pre-auth compression (COMP_ZLIB) is only supported in the client */
@@ -100,6 +102,7 @@ enum kex_exchange {
 	KEX_DH_GEX_SHA256,
 	KEX_ECDH_SHA2,
 	KEX_C25519_SHA256,
+	KEX_KEM_SNTRUP4591761X25519_SHA512,
 	KEX_MAX
 };
 
@@ -164,8 +167,10 @@ struct kex {
 	u_int	min, max, nbits;	/* GEX */
 	EC_KEY	*ec_client_key;		/* ECDH */
 	const EC_GROUP *ec_group;	/* ECDH */
-	u_char c25519_client_key[CURVE25519_SIZE]; /* 25519 */
+	u_char c25519_client_key[CURVE25519_SIZE]; /* 25519 + KEM */
 	u_char c25519_client_pubkey[CURVE25519_SIZE]; /* 25519 */
+	u_char sntrup4591761_client_key[crypto_kem_sntrup4591761_SECRETKEYBYTES]; /* KEM */
+	struct sshbuf *kem_client_pub;	/* KEM */
 };
 
 int	 kex_names_valid(const char *);
@@ -203,6 +208,14 @@ int	 kexecdh_client(struct ssh *);
 int	 kexecdh_server(struct ssh *);
 int	 kexc25519_client(struct ssh *);
 int	 kexc25519_server(struct ssh *);
+int	 kex_kem_client(struct ssh *);
+int	 kex_kem_server(struct ssh *);
+
+int	 kex_kem_sntrup4591761x25519_keypair(struct kex *);
+int	 kex_kem_sntrup4591761x25519_enc(struct kex *, const u_char *, size_t,
+    struct sshbuf **, struct sshbuf **);
+int	 kex_kem_sntrup4591761x25519_dec(struct kex *, const u_char *, size_t,
+    struct sshbuf **);
 
 int	 kex_dh_keygen(struct kex *);
 int	 kex_dh_compute_key(struct kex *, BIGNUM *, struct sshbuf *);
@@ -224,7 +237,7 @@ int kex_ecdh_hash(int, const EC_GROUP *,
 
 int	 kex_c25519_hash(int, const struct sshbuf *, const struct sshbuf *,
     const u_char *, size_t, const u_char *, size_t,
-    const u_char *, size_t, const u_char *, const u_char *,
+    const u_char *, size_t, const u_char *, size_t, const u_char *, size_t,
     const u_char *, size_t, u_char *, size_t *);
 
 void	kexc25519_keygen(u_char key[CURVE25519_SIZE], u_char pub[CURVE25519_SIZE])
@@ -234,9 +247,13 @@ int	kexc25519_shared_key(const u_char key[CURVE25519_SIZE],
     const u_char pub[CURVE25519_SIZE], struct sshbuf *out)
 	__attribute__((__bounded__(__minbytes__, 1, CURVE25519_SIZE)))
 	__attribute__((__bounded__(__minbytes__, 2, CURVE25519_SIZE)));
+int	kexc25519_shared_key_ext(const u_char key[CURVE25519_SIZE],
+    const u_char pub[CURVE25519_SIZE], struct sshbuf *out, int)
+	__attribute__((__bounded__(__minbytes__, 1, CURVE25519_SIZE)))
+	__attribute__((__bounded__(__minbytes__, 2, CURVE25519_SIZE)));
 
 #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH)
-void	dump_digest(char *, u_char *, int);
+void	dump_digest(const char *, const u_char *, int);
 #endif
 
 #if !defined(WITH_OPENSSL) || !defined(OPENSSL_HAS_ECC)
diff --git a/kexc25519.c b/kexc25519.c
index acddcab37..3911baf14 100644
--- a/kexc25519.c
+++ b/kexc25519.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: kexc25519.c,v 1.12 2019/01/21 09:49:37 djm Exp $ */
+/* $OpenBSD: kexc25519.c,v 1.13 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright (c) 2001, 2013 Markus Friedl.  All rights reserved.
  * Copyright (c) 2010 Damien Miller.  All rights reserved.
@@ -60,8 +60,8 @@ kexc25519_keygen(u_char key[CURVE25519_SIZE], u_char pub[CURVE25519_SIZE])
 }
 
 int
-kexc25519_shared_key(const u_char key[CURVE25519_SIZE],
-    const u_char pub[CURVE25519_SIZE], struct sshbuf *out)
+kexc25519_shared_key_ext(const u_char key[CURVE25519_SIZE],
+    const u_char pub[CURVE25519_SIZE], struct sshbuf *out, int raw)
 {
 	u_char shared_key[CURVE25519_SIZE];
 	u_char zero[CURVE25519_SIZE];
@@ -77,13 +77,22 @@ kexc25519_shared_key(const u_char key[CURVE25519_SIZE],
 #ifdef DEBUG_KEXECDH
 	dump_digest("shared secret", shared_key, CURVE25519_SIZE);
 #endif
-	sshbuf_reset(out);
-	r = sshbuf_put_bignum2_bytes(out, shared_key, CURVE25519_SIZE);
+	if (raw)
+		r = sshbuf_put(out, shared_key, CURVE25519_SIZE);
+	else
+		r = sshbuf_put_bignum2_bytes(out, shared_key, CURVE25519_SIZE);
 	explicit_bzero(shared_key, CURVE25519_SIZE);
 	return r;
 }
 
 int
+kexc25519_shared_key(const u_char key[CURVE25519_SIZE],
+    const u_char pub[CURVE25519_SIZE], struct sshbuf *out)
+{
+	return kexc25519_shared_key_ext(key, pub, out, 0);
+}
+
+int
 kex_c25519_hash(
     int hash_alg,
     const struct sshbuf *client_version,
@@ -91,8 +100,8 @@ kex_c25519_hash(
     const u_char *ckexinit, size_t ckexinitlen,
     const u_char *skexinit, size_t skexinitlen,
     const u_char *serverhostkeyblob, size_t sbloblen,
-    const u_char client_dh_pub[CURVE25519_SIZE],
-    const u_char server_dh_pub[CURVE25519_SIZE],
+    const u_char *client_pub, size_t client_pub_len,
+    const u_char *server_pub, size_t server_pub_len,
     const u_char *shared_secret, size_t secretlen,
     u_char *hash, size_t *hashlen)
 {
@@ -103,19 +112,19 @@ kex_c25519_hash(
 		return SSH_ERR_INVALID_ARGUMENT;
 	if ((b = sshbuf_new()) == NULL)
 		return SSH_ERR_ALLOC_FAIL;
-	if ((r = sshbuf_put_stringb(b, client_version)) < 0 ||
-	    (r = sshbuf_put_stringb(b, server_version)) < 0 ||
+	if ((r = sshbuf_put_stringb(b, client_version)) != 0 ||
+	    (r = sshbuf_put_stringb(b, server_version)) != 0 ||
 	    /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
-	    (r = sshbuf_put_u32(b, ckexinitlen+1)) < 0 ||
-	    (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) < 0 ||
-	    (r = sshbuf_put(b, ckexinit, ckexinitlen)) < 0 ||
-	    (r = sshbuf_put_u32(b, skexinitlen+1)) < 0 ||
-	    (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) < 0 ||
-	    (r = sshbuf_put(b, skexinit, skexinitlen)) < 0 ||
-	    (r = sshbuf_put_string(b, serverhostkeyblob, sbloblen)) < 0 ||
-	    (r = sshbuf_put_string(b, client_dh_pub, CURVE25519_SIZE)) < 0 ||
-	    (r = sshbuf_put_string(b, server_dh_pub, CURVE25519_SIZE)) < 0 ||
-	    (r = sshbuf_put(b, shared_secret, secretlen)) < 0) {
+	    (r = sshbuf_put_u32(b, ckexinitlen+1)) != 0 ||
+	    (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) != 0 ||
+	    (r = sshbuf_put(b, ckexinit, ckexinitlen)) != 0 ||
+	    (r = sshbuf_put_u32(b, skexinitlen+1)) != 0 ||
+	    (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) != 0 ||
+	    (r = sshbuf_put(b, skexinit, skexinitlen)) != 0 ||
+	    (r = sshbuf_put_string(b, serverhostkeyblob, sbloblen)) != 0 ||
+	    (r = sshbuf_put_string(b, client_pub, client_pub_len)) != 0 ||
+	    (r = sshbuf_put_string(b, server_pub, server_pub_len)) != 0 ||
+	    (r = sshbuf_put(b, shared_secret, secretlen)) != 0) {
 		sshbuf_free(b);
 		return r;
 	}
diff --git a/kexc25519c.c b/kexc25519c.c
index 1c7f79000..cc6e54cc7 100644
--- a/kexc25519c.c
+++ b/kexc25519c.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: kexc25519c.c,v 1.12 2019/01/21 10:07:22 djm Exp $ */
+/* $OpenBSD: kexc25519c.c,v 1.13 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright (c) 2001 Markus Friedl.  All rights reserved.
  * Copyright (c) 2010 Damien Miller.  All rights reserved.
@@ -109,7 +109,7 @@ input_kex_c25519_reply(int type, u_int32_t seq, struct ssh *ssh)
 		goto out;
 	}
 	if ((r = kexc25519_shared_key(kex->c25519_client_key, server_pubkey,
-	    shared_secret)) < 0)
+	    shared_secret)) != 0)
 		goto out;
 
 	/* calc and verify H */
@@ -121,10 +121,10 @@ input_kex_c25519_reply(int type, u_int32_t seq, struct ssh *ssh)
 	    sshbuf_ptr(kex->my), sshbuf_len(kex->my),
 	    sshbuf_ptr(kex->peer), sshbuf_len(kex->peer),
 	    server_host_key_blob, sbloblen,
-	    kex->c25519_client_pubkey,
-	    server_pubkey,
+	    kex->c25519_client_pubkey, sizeof(kex->c25519_client_pubkey),
+	    server_pubkey, pklen,
 	    sshbuf_ptr(shared_secret), sshbuf_len(shared_secret),
-	    hash, &hashlen)) < 0)
+	    hash, &hashlen)) != 0)
 		goto out;
 
 	if ((r = sshkey_verify(server_host_key, signature, slen, hash, hashlen,
diff --git a/kexc25519s.c b/kexc25519s.c
index d7cc70fee..ace4d5c79 100644
--- a/kexc25519s.c
+++ b/kexc25519s.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: kexc25519s.c,v 1.15 2019/01/21 10:05:09 djm Exp $ */
+/* $OpenBSD: kexc25519s.c,v 1.16 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright (c) 2001 Markus Friedl.  All rights reserved.
  * Copyright (c) 2010 Damien Miller.  All rights reserved.
@@ -104,10 +104,10 @@ input_kex_c25519_init(int type, u_int32_t seq, struct ssh *ssh)
 	    sshbuf_ptr(kex->peer), sshbuf_len(kex->peer),
 	    sshbuf_ptr(kex->my), sshbuf_len(kex->my),
 	    server_host_key_blob, sbloblen,
-	    client_pubkey,
-	    server_pubkey,
+	    client_pubkey, pklen,
+	    server_pubkey, sizeof(server_pubkey),
 	    sshbuf_ptr(shared_secret), sshbuf_len(shared_secret),
-	    hash, &hashlen)) < 0)
+	    hash, &hashlen)) != 0)
 		goto out;
 
 	/* sign H */
diff --git a/kexkemc.c b/kexkemc.c
new file mode 100644
index 000000000..47f15c30c
--- /dev/null
+++ b/kexkemc.c
@@ -0,0 +1,128 @@
+/* $OpenBSD: kexkemc.c,v 1.1 2019/01/21 10:20:12 djm Exp $ */
+/*
+ * Copyright (c) 2019 Markus Friedl.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/types.h>
+
+#include <stdio.h>
+#include <string.h>
+#include <signal.h>
+
+#include "sshkey.h"
+#include "kex.h"
+#include "log.h"
+#include "packet.h"
+#include "ssh2.h"
+#include "sshbuf.h"
+#include "digest.h"
+#include "ssherr.h"
+
+static int
+input_kex_kem_reply(int type, u_int32_t seq, struct ssh *ssh);
+
+int
+kex_kem_client(struct ssh *ssh)
+{
+	struct kex *kex = ssh->kex;
+	int r;
+
+	if ((r = kex_kem_sntrup4591761x25519_keypair(kex)) != 0)
+		return r;
+	if ((r = sshpkt_start(ssh, SSH2_MSG_KEX_ECDH_INIT)) != 0 ||
+	    (r = sshpkt_put_stringb(ssh, kex->kem_client_pub)) != 0 ||
+	    (r = sshpkt_send(ssh)) != 0)
+		return r;
+	debug("expecting SSH2_MSG_KEX_ECDH_REPLY");
+	ssh_dispatch_set(ssh, SSH2_MSG_KEX_ECDH_REPLY, &input_kex_kem_reply);
+	return 0;
+}
+
+static int
+input_kex_kem_reply(int type, u_int32_t seq, struct ssh *ssh)
+{
+	struct kex *kex = ssh->kex;
+	struct sshkey *server_host_key = NULL;
+	struct sshbuf *shared_secret = NULL;
+	u_char *server_pubkey = NULL;
+	u_char *server_host_key_blob = NULL, *signature = NULL;
+	u_char hash[SSH_DIGEST_MAX_LENGTH];
+	size_t slen, pklen, sbloblen, hashlen;
+	int r;
+
+	/* hostkey */
+	if ((r = sshpkt_get_string(ssh, &server_host_key_blob,
+	    &sbloblen)) != 0 ||
+	    (r = sshkey_from_blob(server_host_key_blob, sbloblen,
+	    &server_host_key)) != 0)
+		goto out;
+	if ((r = kex_verify_host_key(ssh, server_host_key)) != 0)
+		goto out;
+
+	/* Q_S, server public key */
+	/* signed H */
+	if ((r = sshpkt_get_string(ssh, &server_pubkey, &pklen)) != 0 ||
+	    (r = sshpkt_get_string(ssh, &signature, &slen)) != 0 ||
+	    (r = sshpkt_get_end(ssh)) != 0)
+		goto out;
+
+	/* compute shared secret */
+	if ((r = kex_kem_sntrup4591761x25519_dec(kex, server_pubkey, pklen,
+	    &shared_secret)) != 0)
+		goto out;
+
+	/* calc and verify H */
+	hashlen = sizeof(hash);
+	if ((r = kex_c25519_hash(
+	    kex->hash_alg,
+	    kex->client_version,
+	    kex->server_version,
+	    sshbuf_ptr(kex->my), sshbuf_len(kex->my),
+	    sshbuf_ptr(kex->peer), sshbuf_len(kex->peer),
+	    server_host_key_blob, sbloblen,
+	    sshbuf_ptr(kex->kem_client_pub), sshbuf_len(kex->kem_client_pub),
+	    server_pubkey, pklen,
+	    sshbuf_ptr(shared_secret), sshbuf_len(shared_secret),
+	    hash, &hashlen)) != 0)
+		goto out;
+
+	if ((r = sshkey_verify(server_host_key, signature, slen, hash, hashlen,
+	    kex->hostkey_alg, ssh->compat)) != 0)
+		goto out;
+
+	if ((r = kex_derive_keys(ssh, hash, hashlen, shared_secret)) == 0)
+		r = kex_send_newkeys(ssh);
+out:
+	explicit_bzero(hash, sizeof(hash));
+	explicit_bzero(kex->c25519_client_key, sizeof(kex->c25519_client_key));
+	explicit_bzero(kex->sntrup4591761_client_key,
+	    sizeof(kex->sntrup4591761_client_key));
+	free(server_host_key_blob);
+	free(server_pubkey);
+	free(signature);
+	sshkey_free(server_host_key);
+	sshbuf_free(shared_secret);
+	sshbuf_free(kex->kem_client_pub);
+	kex->kem_client_pub = NULL;
+	return r;
+}
diff --git a/kexkems.c b/kexkems.c
new file mode 100644
index 000000000..43cf82018
--- /dev/null
+++ b/kexkems.c
@@ -0,0 +1,116 @@
+/* $OpenBSD: kexkems.c,v 1.1 2019/01/21 10:20:12 djm Exp $ */
+/*
+ * Copyright (c) 2019 Markus Friedl.  All rights reserved.
+ *
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/types.h>
+#include <stdio.h>
+#include <string.h>
+#include <signal.h>
+
+#include "sshkey.h"
+#include "digest.h"
+#include "kex.h"
+#include "log.h"
+#include "packet.h"
+#include "ssh2.h"
+#include "sshbuf.h"
+#include "ssherr.h"
+
+static int input_kex_kem_init(int, u_int32_t, struct ssh *);
+
+int
+kex_kem_server(struct ssh *ssh)
+{
+	debug("expecting SSH2_MSG_KEX_ECDH_INIT");
+	ssh_dispatch_set(ssh, SSH2_MSG_KEX_ECDH_INIT, &input_kex_kem_init);
+	return 0;
+}
+
+static int
+input_kex_kem_init(int type, u_int32_t seq, struct ssh *ssh)
+{
+	struct kex *kex = ssh->kex;
+	struct sshkey *server_host_private, *server_host_public;
+	struct sshbuf *shared_secret = NULL;
+	struct sshbuf *server_pubkey = NULL;
+	u_char *server_host_key_blob = NULL, *signature = NULL;
+	u_char *client_pubkey = NULL;
+	u_char hash[SSH_DIGEST_MAX_LENGTH];
+	size_t slen, pklen, sbloblen, hashlen;
+	int r;
+
+	if ((r = kex_load_hostkey(ssh, &server_host_private,
+	    &server_host_public)) != 0)
+		goto out;
+
+	if ((r = sshpkt_get_string(ssh, &client_pubkey, &pklen)) != 0 ||
+	    (r = sshpkt_get_end(ssh)) != 0)
+		goto out;
+
+	/* compute shared secret */
+	if ((r = kex_kem_sntrup4591761x25519_enc(kex, client_pubkey, pklen,
+	    &server_pubkey, &shared_secret)) != 0)
+		goto out;
+
+	/* calc H */
+	if ((r = sshkey_to_blob(server_host_public, &server_host_key_blob,
+	    &sbloblen)) != 0)
+		goto out;
+	hashlen = sizeof(hash);
+	if ((r = kex_c25519_hash(
+	    kex->hash_alg,
+	    kex->client_version,
+	    kex->server_version,
+	    sshbuf_ptr(kex->peer), sshbuf_len(kex->peer),
+	    sshbuf_ptr(kex->my), sshbuf_len(kex->my),
+	    server_host_key_blob, sbloblen,
+	    client_pubkey, pklen,
+	    sshbuf_ptr(server_pubkey), sshbuf_len(server_pubkey),
+	    sshbuf_ptr(shared_secret), sshbuf_len(shared_secret),
+	    hash, &hashlen)) != 0)
+		goto out;
+
+	/* sign H */
+	if ((r = kex->sign(ssh, server_host_private, server_host_public,
+	    &signature, &slen, hash, hashlen, kex->hostkey_alg)) != 0)
+		goto out;
+
+	/* send server hostkey, ECDH pubkey 'Q_S' and signed H */
+	if ((r = sshpkt_start(ssh, SSH2_MSG_KEX_ECDH_REPLY)) != 0 ||
+	    (r = sshpkt_put_string(ssh, server_host_key_blob, sbloblen)) != 0 ||
+	    (r = sshpkt_put_stringb(ssh, server_pubkey)) != 0 ||
+	    (r = sshpkt_put_string(ssh, signature, slen)) != 0 ||
+	    (r = sshpkt_send(ssh)) != 0)
+		goto out;
+
+	if ((r = kex_derive_keys(ssh, hash, hashlen, shared_secret)) == 0)
+		r = kex_send_newkeys(ssh);
+out:
+	explicit_bzero(hash, sizeof(hash));
+	free(server_host_key_blob);
+	free(signature);
+	free(client_pubkey);
+	sshbuf_free(shared_secret);
+	sshbuf_free(server_pubkey);
+	return r;
+}
diff --git a/kexsntrup4591761x25519.c b/kexsntrup4591761x25519.c
new file mode 100644
index 000000000..ffe05f420
--- /dev/null
+++ b/kexsntrup4591761x25519.c
@@ -0,0 +1,213 @@
+/* $OpenBSD: kexsntrup4591761x25519.c,v 1.1 2019/01/21 10:20:12 djm Exp $ */
+/*
+ * Copyright (c) 2019 Markus Friedl.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/types.h>
+
+#include <stdio.h>
+#include <string.h>
+#include <signal.h>
+
+#include "sshkey.h"
+#include "kex.h"
+#include "sshbuf.h"
+#include "digest.h"
+#include "ssherr.h"
+
+int
+kex_kem_sntrup4591761x25519_keypair(struct kex *kex)
+{
+	struct sshbuf *buf = NULL;
+	u_char *cp = NULL;
+	size_t need;
+	int r;
+
+	if ((buf = sshbuf_new()) == NULL)
+		return SSH_ERR_ALLOC_FAIL;
+	need = crypto_kem_sntrup4591761_PUBLICKEYBYTES + CURVE25519_SIZE;
+	if ((r = sshbuf_reserve(buf, need, &cp)) != 0)
+		goto out;
+	crypto_kem_sntrup4591761_keypair(cp, kex->sntrup4591761_client_key);
+#ifdef DEBUG_KEXECDH
+	dump_digest("client public key sntrup4591761:", cp,
+	    crypto_kem_sntrup4591761_PUBLICKEYBYTES);
+#endif
+	cp += crypto_kem_sntrup4591761_PUBLICKEYBYTES;
+	kexc25519_keygen(kex->c25519_client_key, cp);
+#ifdef DEBUG_KEXECDH
+	dump_digest("client public key c25519:", cp, CURVE25519_SIZE);
+#endif
+	kex->kem_client_pub = buf;
+	buf = NULL;
+ out:
+	sshbuf_free(buf);
+	return r;
+}
+
+int
+kex_kem_sntrup4591761x25519_enc(struct kex *kex, const u_char *pkblob,
+   size_t pklen, struct sshbuf **server_blobp, struct sshbuf **shared_secretp)
+{
+	struct sshbuf *server_blob = NULL;
+	struct sshbuf *buf = NULL;
+	u_char *kem_key, *ciphertext, *server_pub;
+	u_char server_key[CURVE25519_SIZE];
+	u_char hash[SSH_DIGEST_MAX_LENGTH];
+	size_t need;
+	int r;
+
+	*server_blobp = NULL;
+	*shared_secretp = NULL;
+
+	/* pkblob contains both KEM and ECDH client pubkeys */
+	need = crypto_kem_sntrup4591761_PUBLICKEYBYTES + CURVE25519_SIZE;
+	if (pklen != need) {
+		r = SSH_ERR_SIGNATURE_INVALID;
+		goto out;
+	}
+#ifdef DEBUG_KEXECDH
+	dump_digest("client public key sntrup4591761:", pkblob,
+	    crypto_kem_sntrup4591761_PUBLICKEYBYTES);
+	dump_digest("client public key 25519:",
+	    pkblob + crypto_kem_sntrup4591761_PUBLICKEYBYTES, CURVE25519_SIZE);
+#endif
+	/* allocate buffer for concatenation of KEM key and ECDH shared key */
+	/* the buffer will be hashed and the result is the shared secret */
+	if ((buf = sshbuf_new()) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+	if ((r = sshbuf_reserve(buf, crypto_kem_sntrup4591761_BYTES,
+	    &kem_key)) != 0)
+		goto out;
+	/* allocate space for encrypted KEM key and ECDH pub key */
+	if ((server_blob = sshbuf_new()) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+	need = crypto_kem_sntrup4591761_CIPHERTEXTBYTES + CURVE25519_SIZE;
+	if ((r = sshbuf_reserve(server_blob, need, &ciphertext)) != 0)
+		goto out;
+	/* generate and encrypt KEM key with client key */
+	crypto_kem_sntrup4591761_enc(ciphertext, kem_key, pkblob);
+	/* generate ECDH key pair, store server pubkey after ciphertext */
+	server_pub = ciphertext + crypto_kem_sntrup4591761_CIPHERTEXTBYTES;
+	kexc25519_keygen(server_key, server_pub);
+	/* append ECDH shared key */
+	if ((r = kexc25519_shared_key_ext(server_key,
+	    pkblob + crypto_kem_sntrup4591761_PUBLICKEYBYTES, buf, 1)) < 0)
+		goto out;
+	if ((r = ssh_digest_buffer(kex->hash_alg, buf, hash, sizeof(hash))) != 0)
+		goto out;
+#ifdef DEBUG_KEXECDH
+	dump_digest("server public key 25519:", server_pub, CURVE25519_SIZE);
+	dump_digest("server cipher text:", ciphertext,
+	    crypto_kem_sntrup4591761_CIPHERTEXTBYTES);
+	dump_digest("server kem key:", kem_key, sizeof(kem_key));
+	dump_digest("concatenation of KEM key and ECDH shared key:",
+	    sshbuf_ptr(buf), sshbuf_len(buf));
+#endif
+	/* string-encoded hash is resulting shared secret */
+	sshbuf_reset(buf);
+	if ((r = sshbuf_put_string(buf, hash,
+	    ssh_digest_bytes(kex->hash_alg))) != 0)
+		goto out;
+#ifdef DEBUG_KEXECDH
+	dump_digest("encoded shared secret:", sshbuf_ptr(buf), sshbuf_len(buf));
+#endif
+	*server_blobp = server_blob;
+	*shared_secretp = buf;
+	server_blob = NULL;
+	buf = NULL;
+ out:
+	explicit_bzero(hash, sizeof(hash));
+	explicit_bzero(server_key, sizeof(server_key));
+	sshbuf_free(server_blob);
+	sshbuf_free(buf);
+	return r;
+}
+
+int
+kex_kem_sntrup4591761x25519_dec(struct kex *kex, const u_char *pkblob,
+    size_t pklen, struct sshbuf **shared_secretp)
+{
+	struct sshbuf *buf = NULL;
+	u_char *kem_key = NULL;
+	const u_char *ciphertext, *server_pub;
+	u_char hash[SSH_DIGEST_MAX_LENGTH];
+	size_t need;
+	int r, decoded;
+
+	*shared_secretp = NULL;
+
+	need = crypto_kem_sntrup4591761_CIPHERTEXTBYTES + CURVE25519_SIZE;
+	if (pklen != need) {
+		r = SSH_ERR_SIGNATURE_INVALID;
+		goto out;
+	}
+	ciphertext = pkblob;
+	server_pub = pkblob + crypto_kem_sntrup4591761_CIPHERTEXTBYTES;
+#ifdef DEBUG_KEXECDH
+	dump_digest("server cipher text:", ciphertext,
+	    crypto_kem_sntrup4591761_CIPHERTEXTBYTES);
+	dump_digest("server public key c25519:", server_pub, CURVE25519_SIZE);
+#endif
+	/* hash concatenation of KEM key and ECDH shared key */
+	if ((buf = sshbuf_new()) == NULL) {
+		r = SSH_ERR_ALLOC_FAIL;
+		goto out;
+	}
+	if ((r = sshbuf_reserve(buf, crypto_kem_sntrup4591761_BYTES,
+	    &kem_key)) != 0)
+		goto out;
+	decoded = crypto_kem_sntrup4591761_dec(kem_key, ciphertext,
+	    kex->sntrup4591761_client_key);
+	if ((r = kexc25519_shared_key_ext(kex->c25519_client_key, server_pub,
+	    buf, 1)) < 0)
+		goto out;
+	if ((r = ssh_digest_buffer(kex->hash_alg, buf, hash, sizeof(hash))) != 0)
+		goto out;
+#ifdef DEBUG_KEXECDH
+	dump_digest("client kem key:", kem_key, sizeof(kem_key));
+	dump_digest("concatenation of KEM key and ECDH shared key:",
+	    sshbuf_ptr(buf), sshbuf_len(buf));
+#endif
+	sshbuf_reset(buf);
+	if ((r = sshbuf_put_string(buf, hash,
+	    ssh_digest_bytes(kex->hash_alg))) != 0)
+		goto out;
+#ifdef DEBUG_KEXECDH
+	dump_digest("encoded shared secret:", sshbuf_ptr(buf), sshbuf_len(buf));
+#endif
+	if (decoded != 0) {
+		r = SSH_ERR_SIGNATURE_INVALID;
+		goto out;
+	}
+	*shared_secretp = buf;
+	buf = NULL;
+ out:
+	explicit_bzero(hash, sizeof(hash));
+	sshbuf_free(buf);
+	return r;
+}
diff --git a/monitor.c b/monitor.c
index a9546dad2..b10fdebf2 100644
--- a/monitor.c
+++ b/monitor.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: monitor.c,v 1.192 2019/01/19 21:43:56 djm Exp $ */
+/* $OpenBSD: monitor.c,v 1.193 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * Copyright 2002 Markus Friedl <markus@openbsd.org>
@@ -1689,6 +1689,7 @@ monitor_apply_keystate(struct ssh *ssh, struct monitor *pmonitor)
 # endif
 #endif /* WITH_OPENSSL */
 		kex->kex[KEX_C25519_SHA256] = kexc25519_server;
+		kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_server;
 		kex->load_host_public_key=&get_hostkey_public_by_type;
 		kex->load_host_private_key=&get_hostkey_private_by_type;
 		kex->host_key_index=&get_hostkey_index;
diff --git a/sntrup4591761.c b/sntrup4591761.c
new file mode 100644
index 000000000..d3ff549ae
--- /dev/null
+++ b/sntrup4591761.c
@@ -0,0 +1,1068 @@
+#include <string.h>
+#include "crypto_api.h"
+
+/* from supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc */
+#define int32_MINMAX(a,b) \
+do { \
+  int32 ab = b ^ a; \
+  int32 c = b - a; \
+  c ^= ab & (c ^ b); \
+  c >>= 31; \
+  c &= ab; \
+  a ^= c; \
+  b ^= c; \
+} while(0)
+
+/* from supercop-20181216/crypto_sort/int32/portable3/sort.c */
+#define int32 crypto_int32
+
+
+static void crypto_sort_int32(void *array,long long n)
+{
+  long long top,p,q,r,i;
+  int32 *x = array;
+
+  if (n < 2) return;
+  top = 1;
+  while (top < n - top) top += top;
+
+  for (p = top;p > 0;p >>= 1) {
+    for (i = 0;i < n - p;++i)
+      if (!(i & p))
+        int32_MINMAX(x[i],x[i+p]);
+    i = 0;
+    for (q = top;q > p;q >>= 1) {
+      for (;i < n - q;++i) {
+        if (!(i & p)) {
+          int32 a = x[i + p];
+          for (r = q;r > p;r >>= 1)
+            int32_MINMAX(a,x[i+r]);
+	  x[i + p] = a;
+	}
+      }
+    }
+  }
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.h */
+#ifndef small_h
+#define small_h
+
+
+typedef crypto_int8 small;
+
+static void small_encode(unsigned char *,const small *);
+
+static void small_decode(small *,const unsigned char *);
+
+
+static void small_random(small *);
+
+static void small_random_weightw(small *);
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h */
+#ifndef mod3_h
+#define mod3_h
+
+
+/* -1 if x is nonzero, 0 otherwise */
+static inline int mod3_nonzero_mask(small x)
+{
+  return -x*x;
+}
+
+/* input between -100000 and 100000 */
+/* output between -1 and 1 */
+static inline small mod3_freeze(crypto_int32 a)
+{
+  a -= 3 * ((10923 * a) >> 15);
+  a -= 3 * ((89478485 * a + 134217728) >> 28);
+  return a;
+}
+
+static inline small mod3_minusproduct(small a,small b,small c)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  crypto_int32 C = c;
+  return mod3_freeze(A - B * C);
+}
+
+static inline small mod3_plusproduct(small a,small b,small c)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  crypto_int32 C = c;
+  return mod3_freeze(A + B * C);
+}
+
+static inline small mod3_product(small a,small b)
+{
+  return a * b;
+}
+
+static inline small mod3_sum(small a,small b)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  return mod3_freeze(A + B);
+}
+
+static inline small mod3_reciprocal(small a1)
+{
+  return a1;
+}
+
+static inline small mod3_quotient(small num,small den)
+{
+  return mod3_product(num,mod3_reciprocal(den));
+}
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h */
+#ifndef modq_h
+#define modq_h
+
+
+typedef crypto_int16 modq;
+
+/* -1 if x is nonzero, 0 otherwise */
+static inline int modq_nonzero_mask(modq x)
+{
+  crypto_int32 r = (crypto_uint16) x;
+  r = -r;
+  r >>= 30;
+  return r;
+}
+
+/* input between -9000000 and 9000000 */
+/* output between -2295 and 2295 */
+static inline modq modq_freeze(crypto_int32 a)
+{
+  a -= 4591 * ((228 * a) >> 20);
+  a -= 4591 * ((58470 * a + 134217728) >> 28);
+  return a;
+}
+
+static inline modq modq_minusproduct(modq a,modq b,modq c)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  crypto_int32 C = c;
+  return modq_freeze(A - B * C);
+}
+
+static inline modq modq_plusproduct(modq a,modq b,modq c)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  crypto_int32 C = c;
+  return modq_freeze(A + B * C);
+}
+
+static inline modq modq_product(modq a,modq b)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  return modq_freeze(A * B);
+}
+
+static inline modq modq_square(modq a)
+{
+  crypto_int32 A = a;
+  return modq_freeze(A * A);
+}
+
+static inline modq modq_sum(modq a,modq b)
+{
+  crypto_int32 A = a;
+  crypto_int32 B = b;
+  return modq_freeze(A + B);
+}
+
+static inline modq modq_reciprocal(modq a1)
+{
+  modq a2 = modq_square(a1);
+  modq a3 = modq_product(a2,a1);
+  modq a4 = modq_square(a2);
+  modq a8 = modq_square(a4);
+  modq a16 = modq_square(a8);
+  modq a32 = modq_square(a16);
+  modq a35 = modq_product(a32,a3);
+  modq a70 = modq_square(a35);
+  modq a140 = modq_square(a70);
+  modq a143 = modq_product(a140,a3);
+  modq a286 = modq_square(a143);
+  modq a572 = modq_square(a286);
+  modq a1144 = modq_square(a572);
+  modq a1147 = modq_product(a1144,a3);
+  modq a2294 = modq_square(a1147);
+  modq a4588 = modq_square(a2294);
+  modq a4589 = modq_product(a4588,a1);
+  return a4589;
+}
+
+static inline modq modq_quotient(modq num,modq den)
+{
+  return modq_product(num,modq_reciprocal(den));
+}
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/params.h */
+#ifndef params_h
+#define params_h
+
+#define q 4591
+/* XXX: also built into modq in various ways */
+
+#define qshift 2295
+#define p 761
+#define w 286
+
+#define rq_encode_len 1218
+#define small_encode_len 191
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h */
+#ifndef r3_h
+#define r3_h
+
+
+static void r3_mult(small *,const small *,const small *);
+
+extern int r3_recip(small *,const small *);
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h */
+#ifndef rq_h
+#define rq_h
+
+
+static void rq_encode(unsigned char *,const modq *);
+
+static void rq_decode(modq *,const unsigned char *);
+
+static void rq_encoderounded(unsigned char *,const modq *);
+
+static void rq_decoderounded(modq *,const unsigned char *);
+
+static void rq_round3(modq *,const modq *);
+
+static void rq_mult(modq *,const modq *,const small *);
+
+int rq_recip3(modq *,const small *);
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h */
+#ifndef swap_h
+#define swap_h
+
+static void swap(void *,void *,int,int);
+
+#endif
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+#ifdef KAT
+#endif
+
+
+int crypto_kem_sntrup4591761_dec(
+  unsigned char *k,
+  const unsigned char *cstr,
+  const unsigned char *sk
+)
+{
+  small f[p];
+  modq h[p];
+  small grecip[p];
+  modq c[p];
+  modq t[p];
+  small t3[p];
+  small r[p];
+  modq hr[p];
+  unsigned char rstr[small_encode_len];
+  unsigned char hash[64];
+  int i;
+  int result = 0;
+  int weight;
+
+  small_decode(f,sk);
+  small_decode(grecip,sk + small_encode_len);
+  rq_decode(h,sk + 2 * small_encode_len);
+
+  rq_decoderounded(c,cstr + 32);
+
+  rq_mult(t,c,f);
+  for (i = 0;i < p;++i) t3[i] = mod3_freeze(modq_freeze(3*t[i]));
+
+  r3_mult(r,t3,grecip);
+
+#ifdef KAT
+  {
+    int j;
+    printf("decrypt r:");
+    for (j = 0;j < p;++j)
+      if (r[j] == 1) printf(" +%d",j);
+      else if (r[j] == -1) printf(" -%d",j);
+    printf("\n");
+  }
+#endif
+
+  weight = 0;
+  for (i = 0;i < p;++i) weight += (1 & r[i]);
+  weight -= w;
+  result |= modq_nonzero_mask(weight); /* XXX: puts limit on p */
+
+  rq_mult(hr,h,r);
+  rq_round3(hr,hr);
+  for (i = 0;i < p;++i) result |= modq_nonzero_mask(hr[i] - c[i]);
+
+  small_encode(rstr,r);
+  crypto_hash_sha512(hash,rstr,sizeof rstr);
+  result |= crypto_verify_32(hash,cstr);
+
+  for (i = 0;i < 32;++i) k[i] = (hash[32 + i] & ~result);
+  return result;
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+#ifdef KAT
+#endif
+
+
+int crypto_kem_sntrup4591761_enc(
+  unsigned char *cstr,
+  unsigned char *k,
+  const unsigned char *pk
+)
+{
+  small r[p];
+  modq h[p];
+  modq c[p];
+  unsigned char rstr[small_encode_len];
+  unsigned char hash[64];
+
+  small_random_weightw(r);
+
+#ifdef KAT
+  {
+    int i;
+    printf("encrypt r:");
+    for (i = 0;i < p;++i)
+      if (r[i] == 1) printf(" +%d",i);
+      else if (r[i] == -1) printf(" -%d",i);
+    printf("\n");
+  }
+#endif
+
+  small_encode(rstr,r);
+  crypto_hash_sha512(hash,rstr,sizeof rstr);
+
+  rq_decode(h,pk);
+  rq_mult(c,h,r);
+  rq_round3(c,c);
+
+  memcpy(k,hash + 32,32);
+  memcpy(cstr,hash,32);
+  rq_encoderounded(cstr + 32,c);
+
+  return 0;
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+#if crypto_kem_sntrup4591761_PUBLICKEYBYTES != rq_encode_len
+#error "crypto_kem_sntrup4591761_PUBLICKEYBYTES must match rq_encode_len"
+#endif
+#if crypto_kem_sntrup4591761_SECRETKEYBYTES != rq_encode_len + 2 * small_encode_len
+#error "crypto_kem_sntrup4591761_SECRETKEYBYTES must match rq_encode_len + 2 * small_encode_len"
+#endif
+
+int crypto_kem_sntrup4591761_keypair(unsigned char *pk,unsigned char *sk)
+{
+  small g[p];
+  small grecip[p];
+  small f[p];
+  modq f3recip[p];
+  modq h[p];
+
+  do
+    small_random(g);
+  while (r3_recip(grecip,g) != 0);
+
+  small_random_weightw(f);
+  rq_recip3(f3recip,f);
+
+  rq_mult(h,f3recip,g);
+
+  rq_encode(pk,h);
+  small_encode(sk,f);
+  small_encode(sk + small_encode_len,grecip);
+  memcpy(sk + 2 * small_encode_len,pk,rq_encode_len);
+
+  return 0;
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void r3_mult(small *h,const small *f,const small *g)
+{
+  small fg[p + p - 1];
+  small result;
+  int i, j;
+
+  for (i = 0;i < p;++i) {
+    result = 0;
+    for (j = 0;j <= i;++j)
+      result = mod3_plusproduct(result,f[j],g[i - j]);
+    fg[i] = result;
+  }
+  for (i = p;i < p + p - 1;++i) {
+    result = 0;
+    for (j = i - p + 1;j < p;++j)
+      result = mod3_plusproduct(result,f[j],g[i - j]);
+    fg[i] = result;
+  }
+
+  for (i = p + p - 2;i >= p;--i) {
+    fg[i - p] = mod3_sum(fg[i - p],fg[i]);
+    fg[i - p + 1] = mod3_sum(fg[i - p + 1],fg[i]);
+  }
+
+  for (i = 0;i < p;++i)
+    h[i] = fg[i];
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+/* caller must ensure that x-y does not overflow */
+static int smaller_mask_r3_recip(int x,int y)
+{
+  return (x - y) >> 31;
+}
+
+static void vectormod3_product(small *z,int len,const small *x,const small c)
+{
+  int i;
+  for (i = 0;i < len;++i) z[i] = mod3_product(x[i],c);
+}
+
+static void vectormod3_minusproduct(small *z,int len,const small *x,const small *y,const small c)
+{
+  int i;
+  for (i = 0;i < len;++i) z[i] = mod3_minusproduct(x[i],y[i],c);
+}
+
+static void vectormod3_shift(small *z,int len)
+{
+  int i;
+  for (i = len - 1;i > 0;--i) z[i] = z[i - 1];
+  z[0] = 0;
+}
+
+/*
+r = s^(-1) mod m, returning 0, if s is invertible mod m
+or returning -1 if s is not invertible mod m
+r,s are polys of degree <p
+m is x^p-x-1
+*/
+int r3_recip(small *r,const small *s)
+{
+  const int loops = 2*p + 1;
+  int loop;
+  small f[p + 1]; 
+  small g[p + 1]; 
+  small u[loops + 1];
+  small v[loops + 1];
+  small c;
+  int i;
+  int d = p;
+  int e = p;
+  int swapmask;
+
+  for (i = 2;i < p;++i) f[i] = 0;
+  f[0] = -1;
+  f[1] = -1;
+  f[p] = 1;
+  /* generalization: can initialize f to any polynomial m */
+  /* requirements: m has degree exactly p, nonzero constant coefficient */
+
+  for (i = 0;i < p;++i) g[i] = s[i];
+  g[p] = 0;
+
+  for (i = 0;i <= loops;++i) u[i] = 0;
+
+  v[0] = 1;
+  for (i = 1;i <= loops;++i) v[i] = 0;
+
+  loop = 0;
+  for (;;) {
+    /* e == -1 or d + e + loop <= 2*p */
+
+    /* f has degree p: i.e., f[p]!=0 */
+    /* f[i]==0 for i < p-d */
+
+    /* g has degree <=p (so it fits in p+1 coefficients) */
+    /* g[i]==0 for i < p-e */
+
+    /* u has degree <=loop (so it fits in loop+1 coefficients) */
+    /* u[i]==0 for i < p-d */
+    /* if invertible: u[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
+
+    /* v has degree <=loop (so it fits in loop+1 coefficients) */
+    /* v[i]==0 for i < p-e */
+    /* v[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
+
+    if (loop >= loops) break;
+
+    c = mod3_quotient(g[p],f[p]);
+
+    vectormod3_minusproduct(g,p + 1,g,f,c);
+    vectormod3_shift(g,p + 1);
+
+#ifdef SIMPLER
+    vectormod3_minusproduct(v,loops + 1,v,u,c);
+    vectormod3_shift(v,loops + 1);
+#else
+    if (loop < p) {
+      vectormod3_minusproduct(v,loop + 1,v,u,c);
+      vectormod3_shift(v,loop + 2);
+    } else {
+      vectormod3_minusproduct(v + loop - p,p + 1,v + loop - p,u + loop - p,c);
+      vectormod3_shift(v + loop - p,p + 2);
+    }
+#endif
+
+    e -= 1;
+
+    ++loop;
+
+    swapmask = smaller_mask_r3_recip(e,d) & mod3_nonzero_mask(g[p]);
+    swap(&e,&d,sizeof e,swapmask);
+    swap(f,g,(p + 1) * sizeof(small),swapmask);
+
+#ifdef SIMPLER
+    swap(u,v,(loops + 1) * sizeof(small),swapmask);
+#else
+    if (loop < p) {
+      swap(u,v,(loop + 1) * sizeof(small),swapmask);
+    } else {
+      swap(u + loop - p,v + loop - p,(p + 1) * sizeof(small),swapmask);
+    }
+#endif
+  }
+
+  c = mod3_reciprocal(f[p]);
+  vectormod3_product(r,p,u + p,c);
+  return smaller_mask_r3_recip(0,d);
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void small_random(small *g)
+{
+  int i;
+
+  for (i = 0;i < p;++i) {
+    crypto_uint32 r = small_random32();
+    g[i] = (small) (((1073741823 & r) * 3) >> 30) - 1;
+  }
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void small_random_weightw(small *f)
+{
+  crypto_int32 r[p];
+  int i;
+
+  for (i = 0;i < p;++i) r[i] = small_random32();
+  for (i = 0;i < w;++i) r[i] &= -2;
+  for (i = w;i < p;++i) r[i] = (r[i] & -3) | 1;
+  crypto_sort_int32(r,p);
+  for (i = 0;i < p;++i) f[i] = ((small) (r[i] & 3)) - 1;
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void rq_encode(unsigned char *c,const modq *f)
+{
+  crypto_int32 f0, f1, f2, f3, f4;
+  int i;
+
+  for (i = 0;i < p/5;++i) {
+    f0 = *f++ + qshift;
+    f1 = *f++ + qshift;
+    f2 = *f++ + qshift;
+    f3 = *f++ + qshift;
+    f4 = *f++ + qshift;
+    /* now want f0 + 6144*f1 + ... as a 64-bit integer */
+    f1 *= 3;
+    f2 *= 9;
+    f3 *= 27;
+    f4 *= 81;
+    /* now want f0 + f1<<11 + f2<<22 + f3<<33 + f4<<44 */
+    f0 += f1 << 11;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0; f0 >>= 8;
+    f0 += f2 << 6;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0; f0 >>= 8;
+    f0 += f3 << 1;
+    *c++ = f0; f0 >>= 8;
+    f0 += f4 << 4;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0;
+  }
+  /* XXX: using p mod 5 = 1 */
+  f0 = *f++ + qshift;
+  *c++ = f0; f0 >>= 8;
+  *c++ = f0;
+}
+
+static void rq_decode(modq *f,const unsigned char *c)
+{
+  crypto_uint32 c0, c1, c2, c3, c4, c5, c6, c7;
+  crypto_uint32 f0, f1, f2, f3, f4;
+  int i;
+
+  for (i = 0;i < p/5;++i) {
+    c0 = *c++;
+    c1 = *c++;
+    c2 = *c++;
+    c3 = *c++;
+    c4 = *c++;
+    c5 = *c++;
+    c6 = *c++;
+    c7 = *c++;
+
+    /* f0 + f1*6144 + f2*6144^2 + f3*6144^3 + f4*6144^4 */
+    /* = c0 + c1*256 + ... + c6*256^6 + c7*256^7 */
+    /* with each f between 0 and 4590 */
+
+    c6 += c7 << 8;
+    /* c6 <= 23241 = floor(4591*6144^4/2^48) */
+    /* f4 = (16/81)c6 + (1/1296)(c5+[0,1]) - [0,0.75] */
+    /* claim: 2^19 f4 < x < 2^19(f4+1) */
+    /* where x = 103564 c6 + 405(c5+1) */
+    /* proof: x - 2^19 f4 = (76/81)c6 + (37/81)c5 + 405 - (32768/81)[0,1] + 2^19[0,0.75] */
+    /* at least 405 - 32768/81 > 0 */
+    /* at most (76/81)23241 + (37/81)255 + 405 + 2^19 0.75 < 2^19 */
+    f4 = (103564*c6 + 405*(c5+1)) >> 19;
+
+    c5 += c6 << 8;
+    c5 -= (f4 * 81) << 4;
+    c4 += c5 << 8;
+
+    /* f0 + f1*6144 + f2*6144^2 + f3*6144^3 */
+    /* = c0 + c1*256 + c2*256^2 + c3*256^3 + c4*256^4 */
+    /* c4 <= 247914 = floor(4591*6144^3/2^32) */
+    /* f3 = (1/54)(c4+[0,1]) - [0,0.75] */
+    /* claim: 2^19 f3 < x < 2^19(f3+1) */
+    /* where x = 9709(c4+2) */
+    /* proof: x - 2^19 f3 = 19418 - (1/27)c4 - (262144/27)[0,1] + 2^19[0,0.75] */
+    /* at least 19418 - 247914/27 - 262144/27 > 0 */
+    /* at most 19418 + 2^19 0.75 < 2^19 */
+    f3 = (9709*(c4+2)) >> 19;
+
+    c4 -= (f3 * 27) << 1;
+    c3 += c4 << 8;
+    /* f0 + f1*6144 + f2*6144^2 */
+    /* = c0 + c1*256 + c2*256^2 + c3*256^3 */
+    /* c3 <= 10329 = floor(4591*6144^2/2^24) */
+    /* f2 = (4/9)c3 + (1/576)c2 + (1/147456)c1 + (1/37748736)c0 - [0,0.75] */
+    /* claim: 2^19 f2 < x < 2^19(f2+1) */
+    /* where x = 233017 c3 + 910(c2+2) */
+    /* proof: x - 2^19 f2 = 1820 + (1/9)c3 - (2/9)c2 - (32/9)c1 - (1/72)c0 + 2^19[0,0.75] */
+    /* at least 1820 - (2/9)255 - (32/9)255 - (1/72)255 > 0 */
+    /* at most 1820 + (1/9)10329 + 2^19 0.75 < 2^19 */
+    f2 = (233017*c3 + 910*(c2+2)) >> 19;
+
+    c2 += c3 << 8;
+    c2 -= (f2 * 9) << 6;
+    c1 += c2 << 8;
+    /* f0 + f1*6144 */
+    /* = c0 + c1*256 */
+    /* c1 <= 110184 = floor(4591*6144/2^8) */
+    /* f1 = (1/24)c1 + (1/6144)c0 - (1/6144)f0 */
+    /* claim: 2^19 f1 < x < 2^19(f1+1) */
+    /* where x = 21845(c1+2) + 85 c0 */
+    /* proof: x - 2^19 f1 = 43690 - (1/3)c1 - (1/3)c0 + 2^19 [0,0.75] */
+    /* at least 43690 - (1/3)110184 - (1/3)255 > 0 */
+    /* at most 43690 + 2^19 0.75 < 2^19 */
+    f1 = (21845*(c1+2) + 85*c0) >> 19;
+
+    c1 -= (f1 * 3) << 3;
+    c0 += c1 << 8;
+    f0 = c0;
+
+    *f++ = modq_freeze(f0 + q - qshift);
+    *f++ = modq_freeze(f1 + q - qshift);
+    *f++ = modq_freeze(f2 + q - qshift);
+    *f++ = modq_freeze(f3 + q - qshift);
+    *f++ = modq_freeze(f4 + q - qshift);
+  }
+
+  c0 = *c++;
+  c1 = *c++;
+  c0 += c1 << 8;
+  *f++ = modq_freeze(c0 + q - qshift);
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void rq_mult(modq *h,const modq *f,const small *g)
+{
+  modq fg[p + p - 1];
+  modq result;
+  int i, j;
+
+  for (i = 0;i < p;++i) {
+    result = 0;
+    for (j = 0;j <= i;++j)
+      result = modq_plusproduct(result,f[j],g[i - j]);
+    fg[i] = result;
+  }
+  for (i = p;i < p + p - 1;++i) {
+    result = 0;
+    for (j = i - p + 1;j < p;++j)
+      result = modq_plusproduct(result,f[j],g[i - j]);
+    fg[i] = result;
+  }
+
+  for (i = p + p - 2;i >= p;--i) {
+    fg[i - p] = modq_sum(fg[i - p],fg[i]);
+    fg[i - p + 1] = modq_sum(fg[i - p + 1],fg[i]);
+  }
+
+  for (i = 0;i < p;++i)
+    h[i] = fg[i];
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+/* caller must ensure that x-y does not overflow */
+static int smaller_mask_rq_recip3(int x,int y)
+{
+  return (x - y) >> 31;
+}
+
+static void vectormodq_product(modq *z,int len,const modq *x,const modq c)
+{
+  int i;
+  for (i = 0;i < len;++i) z[i] = modq_product(x[i],c);
+}
+
+static void vectormodq_minusproduct(modq *z,int len,const modq *x,const modq *y,const modq c)
+{
+  int i;
+  for (i = 0;i < len;++i) z[i] = modq_minusproduct(x[i],y[i],c);
+}
+
+static void vectormodq_shift(modq *z,int len)
+{
+  int i;
+  for (i = len - 1;i > 0;--i) z[i] = z[i - 1];
+  z[0] = 0;
+}
+
+/*
+r = (3s)^(-1) mod m, returning 0, if s is invertible mod m
+or returning -1 if s is not invertible mod m
+r,s are polys of degree <p
+m is x^p-x-1
+*/
+int rq_recip3(modq *r,const small *s)
+{
+  const int loops = 2*p + 1;
+  int loop;
+  modq f[p + 1]; 
+  modq g[p + 1]; 
+  modq u[loops + 1];
+  modq v[loops + 1];
+  modq c;
+  int i;
+  int d = p;
+  int e = p;
+  int swapmask;
+
+  for (i = 2;i < p;++i) f[i] = 0;
+  f[0] = -1;
+  f[1] = -1;
+  f[p] = 1;
+  /* generalization: can initialize f to any polynomial m */
+  /* requirements: m has degree exactly p, nonzero constant coefficient */
+
+  for (i = 0;i < p;++i) g[i] = 3 * s[i];
+  g[p] = 0;
+
+  for (i = 0;i <= loops;++i) u[i] = 0;
+
+  v[0] = 1;
+  for (i = 1;i <= loops;++i) v[i] = 0;
+
+  loop = 0;
+  for (;;) {
+    /* e == -1 or d + e + loop <= 2*p */
+
+    /* f has degree p: i.e., f[p]!=0 */
+    /* f[i]==0 for i < p-d */
+
+    /* g has degree <=p (so it fits in p+1 coefficients) */
+    /* g[i]==0 for i < p-e */
+
+    /* u has degree <=loop (so it fits in loop+1 coefficients) */
+    /* u[i]==0 for i < p-d */
+    /* if invertible: u[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
+
+    /* v has degree <=loop (so it fits in loop+1 coefficients) */
+    /* v[i]==0 for i < p-e */
+    /* v[i]==0 for i < loop-p (so can look at just p+1 coefficients) */
+
+    if (loop >= loops) break;
+
+    c = modq_quotient(g[p],f[p]);
+
+    vectormodq_minusproduct(g,p + 1,g,f,c);
+    vectormodq_shift(g,p + 1);
+
+#ifdef SIMPLER
+    vectormodq_minusproduct(v,loops + 1,v,u,c);
+    vectormodq_shift(v,loops + 1);
+#else
+    if (loop < p) {
+      vectormodq_minusproduct(v,loop + 1,v,u,c);
+      vectormodq_shift(v,loop + 2);
+    } else {
+      vectormodq_minusproduct(v + loop - p,p + 1,v + loop - p,u + loop - p,c);
+      vectormodq_shift(v + loop - p,p + 2);
+    }
+#endif
+
+    e -= 1;
+
+    ++loop;
+
+    swapmask = smaller_mask_rq_recip3(e,d) & modq_nonzero_mask(g[p]);
+    swap(&e,&d,sizeof e,swapmask);
+    swap(f,g,(p + 1) * sizeof(modq),swapmask);
+
+#ifdef SIMPLER
+    swap(u,v,(loops + 1) * sizeof(modq),swapmask);
+#else
+    if (loop < p) {
+      swap(u,v,(loop + 1) * sizeof(modq),swapmask);
+    } else {
+      swap(u + loop - p,v + loop - p,(p + 1) * sizeof(modq),swapmask);
+    }
+#endif
+  }
+
+  c = modq_reciprocal(f[p]);
+  vectormodq_product(r,p,u + p,c);
+  return smaller_mask_rq_recip3(0,d);
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void rq_round3(modq *h,const modq *f)
+{
+  int i;
+
+  for (i = 0;i < p;++i)
+    h[i] = ((21846 * (f[i] + 2295) + 32768) >> 16) * 3 - 2295;
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void rq_encoderounded(unsigned char *c,const modq *f)
+{
+  crypto_int32 f0, f1, f2;
+  int i;
+
+  for (i = 0;i < p/3;++i) {
+    f0 = *f++ + qshift;
+    f1 = *f++ + qshift;
+    f2 = *f++ + qshift;
+    f0 = (21846 * f0) >> 16;
+    f1 = (21846 * f1) >> 16;
+    f2 = (21846 * f2) >> 16;
+    /* now want f0 + f1*1536 + f2*1536^2 as a 32-bit integer */
+    f2 *= 3;
+    f1 += f2 << 9;
+    f1 *= 3;
+    f0 += f1 << 9;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0; f0 >>= 8;
+    *c++ = f0;
+  }
+  /* XXX: using p mod 3 = 2 */
+  f0 = *f++ + qshift;
+  f1 = *f++ + qshift;
+  f0 = (21846 * f0) >> 16;
+  f1 = (21846 * f1) >> 16;
+  f1 *= 3;
+  f0 += f1 << 9;
+  *c++ = f0; f0 >>= 8;
+  *c++ = f0; f0 >>= 8;
+  *c++ = f0;
+}
+
+static void rq_decoderounded(modq *f,const unsigned char *c)
+{
+  crypto_uint32 c0, c1, c2, c3;
+  crypto_uint32 f0, f1, f2;
+  int i;
+
+  for (i = 0;i < p/3;++i) {
+    c0 = *c++;
+    c1 = *c++;
+    c2 = *c++;
+    c3 = *c++;
+
+    /* f0 + f1*1536 + f2*1536^2 */
+    /* = c0 + c1*256 + c2*256^2 + c3*256^3 */
+    /* with each f between 0 and 1530 */
+
+    /* f2 = (64/9)c3 + (1/36)c2 + (1/9216)c1 + (1/2359296)c0 - [0,0.99675] */
+    /* claim: 2^21 f2 < x < 2^21(f2+1) */
+    /* where x = 14913081*c3 + 58254*c2 + 228*(c1+2) */
+    /* proof: x - 2^21 f2 = 456 - (8/9)c0 + (4/9)c1 - (2/9)c2 + (1/9)c3 + 2^21 [0,0.99675] */
+    /* at least 456 - (8/9)255 - (2/9)255 > 0 */
+    /* at most 456 + (4/9)255 + (1/9)255 + 2^21 0.99675 < 2^21 */
+    f2 = (14913081*c3 + 58254*c2 + 228*(c1+2)) >> 21;
+
+    c2 += c3 << 8;
+    c2 -= (f2 * 9) << 2;
+    /* f0 + f1*1536 */
+    /* = c0 + c1*256 + c2*256^2 */
+    /* c2 <= 35 = floor((1530+1530*1536)/256^2) */
+    /* f1 = (128/3)c2 + (1/6)c1 + (1/1536)c0 - (1/1536)f0 */
+    /* claim: 2^21 f1 < x < 2^21(f1+1) */
+    /* where x = 89478485*c2 + 349525*c1 + 1365*(c0+1) */
+    /* proof: x - 2^21 f1 = 1365 - (1/3)c2 - (1/3)c1 - (1/3)c0 + (4096/3)f0 */
+    /* at least 1365 - (1/3)35 - (1/3)255 - (1/3)255 > 0 */
+    /* at most 1365 + (4096/3)1530 < 2^21 */
+    f1 = (89478485*c2 + 349525*c1 + 1365*(c0+1)) >> 21;
+
+    c1 += c2 << 8;
+    c1 -= (f1 * 3) << 1;
+
+    c0 += c1 << 8;
+    f0 = c0;
+
+    *f++ = modq_freeze(f0 * 3 + q - qshift);
+    *f++ = modq_freeze(f1 * 3 + q - qshift);
+    *f++ = modq_freeze(f2 * 3 + q - qshift);
+  }
+
+  c0 = *c++;
+  c1 = *c++;
+  c2 = *c++;
+
+  f1 = (89478485*c2 + 349525*c1 + 1365*(c0+1)) >> 21;
+
+  c1 += c2 << 8;
+  c1 -= (f1 * 3) << 1;
+
+  c0 += c1 << 8;
+  f0 = c0;
+
+  *f++ = modq_freeze(f0 * 3 + q - qshift);
+  *f++ = modq_freeze(f1 * 3 + q - qshift);
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+/* XXX: these functions rely on p mod 4 = 1 */
+
+/* all coefficients in -1, 0, 1 */
+static void small_encode(unsigned char *c,const small *f)
+{
+  small c0;
+  int i;
+
+  for (i = 0;i < p/4;++i) {
+    c0 = *f++ + 1;
+    c0 += (*f++ + 1) << 2;
+    c0 += (*f++ + 1) << 4;
+    c0 += (*f++ + 1) << 6;
+    *c++ = c0;
+  }
+  c0 = *f++ + 1;
+  *c++ = c0;
+}
+
+static void small_decode(small *f,const unsigned char *c)
+{
+  unsigned char c0;
+  int i;
+
+  for (i = 0;i < p/4;++i) {
+    c0 = *c++;
+    *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2;
+    *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2;
+    *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2;
+    *f++ = ((small) (c0 & 3)) - 1;
+  }
+  c0 = *c++;
+  *f++ = ((small) (c0 & 3)) - 1;
+}
+
+/* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c */
+/* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */
+
+
+static void swap(void *x,void *y,int bytes,int mask)
+{
+  int i;
+  char xi, yi, c, t;
+
+  c = mask;
+  
+  for (i = 0;i < bytes;++i) {
+    xi = i[(char *) x];
+    yi = i[(char *) y];
+    t = c & (xi ^ yi);
+    xi ^= t;
+    yi ^= t;
+    i[(char *) x] = xi;
+    i[(char *) y] = yi;
+  }
+}
+
diff --git a/sntrup4591761.sh b/sntrup4591761.sh
new file mode 100644
index 000000000..5540ca4d9
--- /dev/null
+++ b/sntrup4591761.sh
@@ -0,0 +1,47 @@
+#!/bin/sh
+FILES="
+	supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc
+	supercop-20181216/crypto_sort/int32/portable3/sort.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/small.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/params.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h
+	supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/small.c
+	supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c
+"
+###
+
+set -e
+DIR=/data/git/mfriedl
+cd $DIR
+echo '#include <string.h>'
+echo '#include "crypto_api.h"'
+echo
+for i in $FILES; do
+	echo "/* from $i */"
+	b=$(basename $i .c)
+	grep \
+	   -v '#include' $i | \
+	   grep -v "extern crypto_int32 small_random32" |
+	   sed -e "s/crypto_kem_/crypto_kem_sntrup4591761_/g" \
+		-e "s/smaller_mask/smaller_mask_${b}/g" \
+		-e "s/void crypto_sort/void crypto_sort_int32/" \
+		-e "s/^extern void /static void /" \
+		-e "s/^void /static void /"
+	echo
+done
diff --git a/ssh-keyscan.c b/ssh-keyscan.c
index 88449f672..83a768700 100644
--- a/ssh-keyscan.c
+++ b/ssh-keyscan.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh-keyscan.c,v 1.120 2018/06/06 18:29:18 markus Exp $ */
+/* $OpenBSD: ssh-keyscan.c,v 1.121 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright 1995, 1996 by David Mazieres <dm@lcs.mit.edu>.
  *
@@ -272,6 +272,7 @@ keygrab_ssh2(con *c)
 # endif
 #endif
 	c->c_ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client;
+	c->c_ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_client;
 	ssh_set_verify_host_key_callback(c->c_ssh, key_print_wrapper);
 	/*
 	 * do the key-exchange until an error occurs or until
diff --git a/ssh_api.c b/ssh_api.c
index 182c0d7e4..73981aa37 100644
--- a/ssh_api.c
+++ b/ssh_api.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssh_api.c,v 1.10 2019/01/19 21:43:56 djm Exp $ */
+/* $OpenBSD: ssh_api.c,v 1.11 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright (c) 2012 Markus Friedl.  All rights reserved.
  *
@@ -111,6 +111,7 @@ ssh_init(struct ssh **sshp, int is_server, struct kex_params *kex_params)
 # endif
 #endif /* WITH_OPENSSL */
 		ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_server;
+		ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_server;
 		ssh->kex->load_host_public_key=&_ssh_host_public_key;
 		ssh->kex->load_host_private_key=&_ssh_host_private_key;
 		ssh->kex->sign=&_ssh_host_key_sign;
@@ -128,6 +129,7 @@ ssh_init(struct ssh **sshp, int is_server, struct kex_params *kex_params)
 # endif
 #endif /* WITH_OPENSSL */
 		ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client;
+		ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_client;
 		ssh->kex->verify_host_key =&_ssh_verify_host_key;
 	}
 	*sshp = ssh;
diff --git a/sshconnect2.c b/sshconnect2.c
index 65d8be667..05657fd73 100644
--- a/sshconnect2.c
+++ b/sshconnect2.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshconnect2.c,v 1.296 2019/01/21 01:05:00 djm Exp $ */
+/* $OpenBSD: sshconnect2.c,v 1.297 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
  * Copyright (c) 2008 Damien Miller.  All rights reserved.
@@ -213,6 +213,7 @@ ssh_kex2(struct ssh *ssh, char *host, struct sockaddr *hostaddr, u_short port)
 # endif
 #endif
 	ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client;
+	ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_client;
 	ssh->kex->verify_host_key=&verify_host_key_callback;
 
 	ssh_dispatch_run_fatal(ssh, DISPATCH_BLOCK, &ssh->kex->done);
diff --git a/sshd.c b/sshd.c
index f6927672e..330b8052d 100644
--- a/sshd.c
+++ b/sshd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: sshd.c,v 1.527 2019/01/19 21:43:56 djm Exp $ */
+/* $OpenBSD: sshd.c,v 1.528 2019/01/21 10:20:12 djm Exp $ */
 /*
  * Author: Tatu Ylonen <ylo@cs.hut.fi>
  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
@@ -2219,6 +2219,7 @@ do_ssh2_kex(struct ssh *ssh)
 # endif
 #endif
 	kex->kex[KEX_C25519_SHA256] = kexc25519_server;
+	kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_server;
 	kex->load_host_public_key=&get_hostkey_public_by_type;
 	kex->load_host_private_key=&get_hostkey_private_by_type;
 	kex->host_key_index=&get_hostkey_index;