diff options
author | djm@openbsd.org <djm@openbsd.org> | 2019-01-21 10:20:12 +0000 |
---|---|---|
committer | Damien Miller <djm@mindrot.org> | 2019-01-21 22:07:02 +1100 |
commit | dfd591618cdf2c96727ac0eb65f89cf54af0d97e (patch) | |
tree | 59700563da0dc6f1de649394ffb4c787710eda5a | |
parent | b1b2ff4ed559051d1035419f8f236275fa66d5d6 (diff) |
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
-rw-r--r-- | Makefile.in | 2 | ||||
-rw-r--r-- | crypto_api.h | 18 | ||||
-rw-r--r-- | kex.c | 7 | ||||
-rw-r--r-- | kex.h | 25 | ||||
-rw-r--r-- | kexc25519.c | 47 | ||||
-rw-r--r-- | kexc25519c.c | 10 | ||||
-rw-r--r-- | kexc25519s.c | 8 | ||||
-rw-r--r-- | kexkemc.c | 128 | ||||
-rw-r--r-- | kexkems.c | 116 | ||||
-rw-r--r-- | kexsntrup4591761x25519.c | 213 | ||||
-rw-r--r-- | monitor.c | 3 | ||||
-rw-r--r-- | sntrup4591761.c | 1068 | ||||
-rw-r--r-- | sntrup4591761.sh | 47 | ||||
-rw-r--r-- | ssh-keyscan.c | 3 | ||||
-rw-r--r-- | ssh_api.c | 4 | ||||
-rw-r--r-- | sshconnect2.c | 3 | ||||
-rw-r--r-- | sshd.c | 3 |
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} \ | |||
100 | kex.o kexdh.o kexgex.o kexecdh.o kexc25519.o \ | 100 | kex.o kexdh.o kexgex.o kexecdh.o kexc25519.o \ |
101 | kexdhc.o kexgexc.o kexecdhc.o kexc25519c.o \ | 101 | kexdhc.o kexgexc.o kexecdhc.o kexc25519c.o \ |
102 | kexdhs.o kexgexs.o kexecdhs.o kexc25519s.o \ | 102 | kexdhs.o kexgexs.o kexecdhs.o kexc25519s.o \ |
103 | sntrup4591761.o kexsntrup4591761x25519.o kexkemc.o kexkems.o \ | ||
103 | platform-pledge.o platform-tracing.o platform-misc.o | 104 | platform-pledge.o platform-tracing.o platform-misc.o |
104 | 105 | ||
106 | |||
105 | SSHOBJS= ssh.o readconf.o clientloop.o sshtty.o \ | 107 | SSHOBJS= ssh.o readconf.o clientloop.o sshtty.o \ |
106 | sshconnect.o sshconnect2.o mux.o | 108 | sshconnect.o sshconnect2.o mux.o |
107 | 109 | ||
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 @@ | |||
1 | /* $OpenBSD: crypto_api.h,v 1.4 2017/12/14 21:07:39 naddy Exp $ */ | 1 | /* $OpenBSD: crypto_api.h,v 1.5 2019/01/21 10:20:12 djm Exp $ */ |
2 | 2 | ||
3 | /* | 3 | /* |
4 | * Assembled from generated headers and source files by Markus Friedl. | 4 | * Assembled from generated headers and source files by Markus Friedl. |
@@ -15,10 +15,15 @@ | |||
15 | #endif | 15 | #endif |
16 | #include <stdlib.h> | 16 | #include <stdlib.h> |
17 | 17 | ||
18 | typedef int8_t crypto_int8; | ||
19 | typedef uint8_t crypto_uint8; | ||
20 | typedef int16_t crypto_int16; | ||
21 | typedef uint16_t crypto_uint16; | ||
18 | typedef int32_t crypto_int32; | 22 | typedef int32_t crypto_int32; |
19 | typedef uint32_t crypto_uint32; | 23 | typedef uint32_t crypto_uint32; |
20 | 24 | ||
21 | #define randombytes(buf, buf_len) arc4random_buf((buf), (buf_len)) | 25 | #define randombytes(buf, buf_len) arc4random_buf((buf), (buf_len)) |
26 | #define small_random32() arc4random() | ||
22 | 27 | ||
23 | #define crypto_hash_sha512_BYTES 64U | 28 | #define crypto_hash_sha512_BYTES 64U |
24 | 29 | ||
@@ -37,4 +42,15 @@ int crypto_sign_ed25519_open(unsigned char *, unsigned long long *, | |||
37 | const unsigned char *, unsigned long long, const unsigned char *); | 42 | const unsigned char *, unsigned long long, const unsigned char *); |
38 | int crypto_sign_ed25519_keypair(unsigned char *, unsigned char *); | 43 | int crypto_sign_ed25519_keypair(unsigned char *, unsigned char *); |
39 | 44 | ||
45 | #define crypto_kem_sntrup4591761_PUBLICKEYBYTES 1218 | ||
46 | #define crypto_kem_sntrup4591761_SECRETKEYBYTES 1600 | ||
47 | #define crypto_kem_sntrup4591761_CIPHERTEXTBYTES 1047 | ||
48 | #define crypto_kem_sntrup4591761_BYTES 32 | ||
49 | |||
50 | int crypto_kem_sntrup4591761_enc(unsigned char *cstr, unsigned char *k, | ||
51 | const unsigned char *pk); | ||
52 | int crypto_kem_sntrup4591761_dec(unsigned char *k, | ||
53 | const unsigned char *cstr, const unsigned char *sk); | ||
54 | int crypto_kem_sntrup4591761_keypair(unsigned char *pk, unsigned char *sk); | ||
55 | |||
40 | #endif /* crypto_api_h */ | 56 | #endif /* crypto_api_h */ |
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: kex.c,v 1.146 2019/01/21 10:07:22 djm Exp $ */ | 1 | /* $OpenBSD: kex.c,v 1.147 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2000, 2001 Markus Friedl. All rights reserved. | 3 | * Copyright (c) 2000, 2001 Markus Friedl. All rights reserved. |
4 | * | 4 | * |
@@ -108,6 +108,8 @@ static const struct kexalg kexalgs[] = { | |||
108 | #if defined(HAVE_EVP_SHA256) || !defined(WITH_OPENSSL) | 108 | #if defined(HAVE_EVP_SHA256) || !defined(WITH_OPENSSL) |
109 | { KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 }, | 109 | { KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 }, |
110 | { KEX_CURVE25519_SHA256_OLD, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 }, | 110 | { KEX_CURVE25519_SHA256_OLD, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 }, |
111 | { KEX_SNTRUP4591761X25519_SHA512, KEX_KEM_SNTRUP4591761X25519_SHA512, 0, | ||
112 | SSH_DIGEST_SHA512 }, | ||
111 | #endif /* HAVE_EVP_SHA256 || !WITH_OPENSSL */ | 113 | #endif /* HAVE_EVP_SHA256 || !WITH_OPENSSL */ |
112 | { NULL, -1, -1, -1}, | 114 | { NULL, -1, -1, -1}, |
113 | }; | 115 | }; |
@@ -653,6 +655,7 @@ kex_free(struct kex *kex) | |||
653 | sshbuf_free(kex->my); | 655 | sshbuf_free(kex->my); |
654 | sshbuf_free(kex->client_version); | 656 | sshbuf_free(kex->client_version); |
655 | sshbuf_free(kex->server_version); | 657 | sshbuf_free(kex->server_version); |
658 | sshbuf_free(kex->kem_client_pub); | ||
656 | free(kex->session_id); | 659 | free(kex->session_id); |
657 | free(kex->failed_choice); | 660 | free(kex->failed_choice); |
658 | free(kex->hostkey_alg); | 661 | free(kex->hostkey_alg); |
@@ -1089,7 +1092,7 @@ kex_verify_host_key(struct ssh *ssh, struct sshkey *server_host_key) | |||
1089 | 1092 | ||
1090 | #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH) | 1093 | #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH) |
1091 | void | 1094 | void |
1092 | dump_digest(char *msg, u_char *digest, int len) | 1095 | dump_digest(const char *msg, const u_char *digest, int len) |
1093 | { | 1096 | { |
1094 | fprintf(stderr, "%s\n", msg); | 1097 | fprintf(stderr, "%s\n", msg); |
1095 | sshbuf_dump_data(digest, len, stderr); | 1098 | sshbuf_dump_data(digest, len, stderr); |
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: kex.h,v 1.98 2019/01/21 10:07:22 djm Exp $ */ | 1 | /* $OpenBSD: kex.h,v 1.99 2019/01/21 10:20:12 djm Exp $ */ |
2 | 2 | ||
3 | /* | 3 | /* |
4 | * Copyright (c) 2000, 2001 Markus Friedl. All rights reserved. | 4 | * Copyright (c) 2000, 2001 Markus Friedl. All rights reserved. |
@@ -27,6 +27,7 @@ | |||
27 | #define KEX_H | 27 | #define KEX_H |
28 | 28 | ||
29 | #include "mac.h" | 29 | #include "mac.h" |
30 | #include "crypto_api.h" | ||
30 | 31 | ||
31 | #ifdef WITH_LEAKMALLOC | 32 | #ifdef WITH_LEAKMALLOC |
32 | #include "leakmalloc.h" | 33 | #include "leakmalloc.h" |
@@ -62,6 +63,7 @@ | |||
62 | #define KEX_ECDH_SHA2_NISTP521 "ecdh-sha2-nistp521" | 63 | #define KEX_ECDH_SHA2_NISTP521 "ecdh-sha2-nistp521" |
63 | #define KEX_CURVE25519_SHA256 "curve25519-sha256" | 64 | #define KEX_CURVE25519_SHA256 "curve25519-sha256" |
64 | #define KEX_CURVE25519_SHA256_OLD "curve25519-sha256@libssh.org" | 65 | #define KEX_CURVE25519_SHA256_OLD "curve25519-sha256@libssh.org" |
66 | #define KEX_SNTRUP4591761X25519_SHA512 "sntrup4591761x25519-sha512@tinyssh.org" | ||
65 | 67 | ||
66 | #define COMP_NONE 0 | 68 | #define COMP_NONE 0 |
67 | /* pre-auth compression (COMP_ZLIB) is only supported in the client */ | 69 | /* pre-auth compression (COMP_ZLIB) is only supported in the client */ |
@@ -100,6 +102,7 @@ enum kex_exchange { | |||
100 | KEX_DH_GEX_SHA256, | 102 | KEX_DH_GEX_SHA256, |
101 | KEX_ECDH_SHA2, | 103 | KEX_ECDH_SHA2, |
102 | KEX_C25519_SHA256, | 104 | KEX_C25519_SHA256, |
105 | KEX_KEM_SNTRUP4591761X25519_SHA512, | ||
103 | KEX_MAX | 106 | KEX_MAX |
104 | }; | 107 | }; |
105 | 108 | ||
@@ -164,8 +167,10 @@ struct kex { | |||
164 | u_int min, max, nbits; /* GEX */ | 167 | u_int min, max, nbits; /* GEX */ |
165 | EC_KEY *ec_client_key; /* ECDH */ | 168 | EC_KEY *ec_client_key; /* ECDH */ |
166 | const EC_GROUP *ec_group; /* ECDH */ | 169 | const EC_GROUP *ec_group; /* ECDH */ |
167 | u_char c25519_client_key[CURVE25519_SIZE]; /* 25519 */ | 170 | u_char c25519_client_key[CURVE25519_SIZE]; /* 25519 + KEM */ |
168 | u_char c25519_client_pubkey[CURVE25519_SIZE]; /* 25519 */ | 171 | u_char c25519_client_pubkey[CURVE25519_SIZE]; /* 25519 */ |
172 | u_char sntrup4591761_client_key[crypto_kem_sntrup4591761_SECRETKEYBYTES]; /* KEM */ | ||
173 | struct sshbuf *kem_client_pub; /* KEM */ | ||
169 | }; | 174 | }; |
170 | 175 | ||
171 | int kex_names_valid(const char *); | 176 | int kex_names_valid(const char *); |
@@ -203,6 +208,14 @@ int kexecdh_client(struct ssh *); | |||
203 | int kexecdh_server(struct ssh *); | 208 | int kexecdh_server(struct ssh *); |
204 | int kexc25519_client(struct ssh *); | 209 | int kexc25519_client(struct ssh *); |
205 | int kexc25519_server(struct ssh *); | 210 | int kexc25519_server(struct ssh *); |
211 | int kex_kem_client(struct ssh *); | ||
212 | int kex_kem_server(struct ssh *); | ||
213 | |||
214 | int kex_kem_sntrup4591761x25519_keypair(struct kex *); | ||
215 | int kex_kem_sntrup4591761x25519_enc(struct kex *, const u_char *, size_t, | ||
216 | struct sshbuf **, struct sshbuf **); | ||
217 | int kex_kem_sntrup4591761x25519_dec(struct kex *, const u_char *, size_t, | ||
218 | struct sshbuf **); | ||
206 | 219 | ||
207 | int kex_dh_keygen(struct kex *); | 220 | int kex_dh_keygen(struct kex *); |
208 | int kex_dh_compute_key(struct kex *, BIGNUM *, struct sshbuf *); | 221 | int kex_dh_compute_key(struct kex *, BIGNUM *, struct sshbuf *); |
@@ -224,7 +237,7 @@ int kex_ecdh_hash(int, const EC_GROUP *, | |||
224 | 237 | ||
225 | int kex_c25519_hash(int, const struct sshbuf *, const struct sshbuf *, | 238 | int kex_c25519_hash(int, const struct sshbuf *, const struct sshbuf *, |
226 | const u_char *, size_t, const u_char *, size_t, | 239 | const u_char *, size_t, const u_char *, size_t, |
227 | const u_char *, size_t, const u_char *, const u_char *, | 240 | const u_char *, size_t, const u_char *, size_t, const u_char *, size_t, |
228 | const u_char *, size_t, u_char *, size_t *); | 241 | const u_char *, size_t, u_char *, size_t *); |
229 | 242 | ||
230 | void kexc25519_keygen(u_char key[CURVE25519_SIZE], u_char pub[CURVE25519_SIZE]) | 243 | 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], | |||
234 | const u_char pub[CURVE25519_SIZE], struct sshbuf *out) | 247 | const u_char pub[CURVE25519_SIZE], struct sshbuf *out) |
235 | __attribute__((__bounded__(__minbytes__, 1, CURVE25519_SIZE))) | 248 | __attribute__((__bounded__(__minbytes__, 1, CURVE25519_SIZE))) |
236 | __attribute__((__bounded__(__minbytes__, 2, CURVE25519_SIZE))); | 249 | __attribute__((__bounded__(__minbytes__, 2, CURVE25519_SIZE))); |
250 | int kexc25519_shared_key_ext(const u_char key[CURVE25519_SIZE], | ||
251 | const u_char pub[CURVE25519_SIZE], struct sshbuf *out, int) | ||
252 | __attribute__((__bounded__(__minbytes__, 1, CURVE25519_SIZE))) | ||
253 | __attribute__((__bounded__(__minbytes__, 2, CURVE25519_SIZE))); | ||
237 | 254 | ||
238 | #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH) | 255 | #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH) |
239 | void dump_digest(char *, u_char *, int); | 256 | void dump_digest(const char *, const u_char *, int); |
240 | #endif | 257 | #endif |
241 | 258 | ||
242 | #if !defined(WITH_OPENSSL) || !defined(OPENSSL_HAS_ECC) | 259 | #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 @@ | |||
1 | /* $OpenBSD: kexc25519.c,v 1.12 2019/01/21 09:49:37 djm Exp $ */ | 1 | /* $OpenBSD: kexc25519.c,v 1.13 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2001, 2013 Markus Friedl. All rights reserved. | 3 | * Copyright (c) 2001, 2013 Markus Friedl. All rights reserved. |
4 | * Copyright (c) 2010 Damien Miller. All rights reserved. | 4 | * Copyright (c) 2010 Damien Miller. All rights reserved. |
@@ -60,8 +60,8 @@ kexc25519_keygen(u_char key[CURVE25519_SIZE], u_char pub[CURVE25519_SIZE]) | |||
60 | } | 60 | } |
61 | 61 | ||
62 | int | 62 | int |
63 | kexc25519_shared_key(const u_char key[CURVE25519_SIZE], | 63 | kexc25519_shared_key_ext(const u_char key[CURVE25519_SIZE], |
64 | const u_char pub[CURVE25519_SIZE], struct sshbuf *out) | 64 | const u_char pub[CURVE25519_SIZE], struct sshbuf *out, int raw) |
65 | { | 65 | { |
66 | u_char shared_key[CURVE25519_SIZE]; | 66 | u_char shared_key[CURVE25519_SIZE]; |
67 | u_char zero[CURVE25519_SIZE]; | 67 | u_char zero[CURVE25519_SIZE]; |
@@ -77,13 +77,22 @@ kexc25519_shared_key(const u_char key[CURVE25519_SIZE], | |||
77 | #ifdef DEBUG_KEXECDH | 77 | #ifdef DEBUG_KEXECDH |
78 | dump_digest("shared secret", shared_key, CURVE25519_SIZE); | 78 | dump_digest("shared secret", shared_key, CURVE25519_SIZE); |
79 | #endif | 79 | #endif |
80 | sshbuf_reset(out); | 80 | if (raw) |
81 | r = sshbuf_put_bignum2_bytes(out, shared_key, CURVE25519_SIZE); | 81 | r = sshbuf_put(out, shared_key, CURVE25519_SIZE); |
82 | else | ||
83 | r = sshbuf_put_bignum2_bytes(out, shared_key, CURVE25519_SIZE); | ||
82 | explicit_bzero(shared_key, CURVE25519_SIZE); | 84 | explicit_bzero(shared_key, CURVE25519_SIZE); |
83 | return r; | 85 | return r; |
84 | } | 86 | } |
85 | 87 | ||
86 | int | 88 | int |
89 | kexc25519_shared_key(const u_char key[CURVE25519_SIZE], | ||
90 | const u_char pub[CURVE25519_SIZE], struct sshbuf *out) | ||
91 | { | ||
92 | return kexc25519_shared_key_ext(key, pub, out, 0); | ||
93 | } | ||
94 | |||
95 | int | ||
87 | kex_c25519_hash( | 96 | kex_c25519_hash( |
88 | int hash_alg, | 97 | int hash_alg, |
89 | const struct sshbuf *client_version, | 98 | const struct sshbuf *client_version, |
@@ -91,8 +100,8 @@ kex_c25519_hash( | |||
91 | const u_char *ckexinit, size_t ckexinitlen, | 100 | const u_char *ckexinit, size_t ckexinitlen, |
92 | const u_char *skexinit, size_t skexinitlen, | 101 | const u_char *skexinit, size_t skexinitlen, |
93 | const u_char *serverhostkeyblob, size_t sbloblen, | 102 | const u_char *serverhostkeyblob, size_t sbloblen, |
94 | const u_char client_dh_pub[CURVE25519_SIZE], | 103 | const u_char *client_pub, size_t client_pub_len, |
95 | const u_char server_dh_pub[CURVE25519_SIZE], | 104 | const u_char *server_pub, size_t server_pub_len, |
96 | const u_char *shared_secret, size_t secretlen, | 105 | const u_char *shared_secret, size_t secretlen, |
97 | u_char *hash, size_t *hashlen) | 106 | u_char *hash, size_t *hashlen) |
98 | { | 107 | { |
@@ -103,19 +112,19 @@ kex_c25519_hash( | |||
103 | return SSH_ERR_INVALID_ARGUMENT; | 112 | return SSH_ERR_INVALID_ARGUMENT; |
104 | if ((b = sshbuf_new()) == NULL) | 113 | if ((b = sshbuf_new()) == NULL) |
105 | return SSH_ERR_ALLOC_FAIL; | 114 | return SSH_ERR_ALLOC_FAIL; |
106 | if ((r = sshbuf_put_stringb(b, client_version)) < 0 || | 115 | if ((r = sshbuf_put_stringb(b, client_version)) != 0 || |
107 | (r = sshbuf_put_stringb(b, server_version)) < 0 || | 116 | (r = sshbuf_put_stringb(b, server_version)) != 0 || |
108 | /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */ | 117 | /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */ |
109 | (r = sshbuf_put_u32(b, ckexinitlen+1)) < 0 || | 118 | (r = sshbuf_put_u32(b, ckexinitlen+1)) != 0 || |
110 | (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) < 0 || | 119 | (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) != 0 || |
111 | (r = sshbuf_put(b, ckexinit, ckexinitlen)) < 0 || | 120 | (r = sshbuf_put(b, ckexinit, ckexinitlen)) != 0 || |
112 | (r = sshbuf_put_u32(b, skexinitlen+1)) < 0 || | 121 | (r = sshbuf_put_u32(b, skexinitlen+1)) != 0 || |
113 | (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) < 0 || | 122 | (r = sshbuf_put_u8(b, SSH2_MSG_KEXINIT)) != 0 || |
114 | (r = sshbuf_put(b, skexinit, skexinitlen)) < 0 || | 123 | (r = sshbuf_put(b, skexinit, skexinitlen)) != 0 || |
115 | (r = sshbuf_put_string(b, serverhostkeyblob, sbloblen)) < 0 || | 124 | (r = sshbuf_put_string(b, serverhostkeyblob, sbloblen)) != 0 || |
116 | (r = sshbuf_put_string(b, client_dh_pub, CURVE25519_SIZE)) < 0 || | 125 | (r = sshbuf_put_string(b, client_pub, client_pub_len)) != 0 || |
117 | (r = sshbuf_put_string(b, server_dh_pub, CURVE25519_SIZE)) < 0 || | 126 | (r = sshbuf_put_string(b, server_pub, server_pub_len)) != 0 || |
118 | (r = sshbuf_put(b, shared_secret, secretlen)) < 0) { | 127 | (r = sshbuf_put(b, shared_secret, secretlen)) != 0) { |
119 | sshbuf_free(b); | 128 | sshbuf_free(b); |
120 | return r; | 129 | return r; |
121 | } | 130 | } |
diff --git a/kexc25519c.c b/kexc25519c.c index 1c7f79000..cc6e54cc7 100644 --- a/kexc25519c.c +++ b/kexc25519c.c | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: kexc25519c.c,v 1.12 2019/01/21 10:07:22 djm Exp $ */ | 1 | /* $OpenBSD: kexc25519c.c,v 1.13 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2001 Markus Friedl. All rights reserved. | 3 | * Copyright (c) 2001 Markus Friedl. All rights reserved. |
4 | * Copyright (c) 2010 Damien Miller. All rights reserved. | 4 | * 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) | |||
109 | goto out; | 109 | goto out; |
110 | } | 110 | } |
111 | if ((r = kexc25519_shared_key(kex->c25519_client_key, server_pubkey, | 111 | if ((r = kexc25519_shared_key(kex->c25519_client_key, server_pubkey, |
112 | shared_secret)) < 0) | 112 | shared_secret)) != 0) |
113 | goto out; | 113 | goto out; |
114 | 114 | ||
115 | /* calc and verify H */ | 115 | /* calc and verify H */ |
@@ -121,10 +121,10 @@ input_kex_c25519_reply(int type, u_int32_t seq, struct ssh *ssh) | |||
121 | sshbuf_ptr(kex->my), sshbuf_len(kex->my), | 121 | sshbuf_ptr(kex->my), sshbuf_len(kex->my), |
122 | sshbuf_ptr(kex->peer), sshbuf_len(kex->peer), | 122 | sshbuf_ptr(kex->peer), sshbuf_len(kex->peer), |
123 | server_host_key_blob, sbloblen, | 123 | server_host_key_blob, sbloblen, |
124 | kex->c25519_client_pubkey, | 124 | kex->c25519_client_pubkey, sizeof(kex->c25519_client_pubkey), |
125 | server_pubkey, | 125 | server_pubkey, pklen, |
126 | sshbuf_ptr(shared_secret), sshbuf_len(shared_secret), | 126 | sshbuf_ptr(shared_secret), sshbuf_len(shared_secret), |
127 | hash, &hashlen)) < 0) | 127 | hash, &hashlen)) != 0) |
128 | goto out; | 128 | goto out; |
129 | 129 | ||
130 | if ((r = sshkey_verify(server_host_key, signature, slen, hash, hashlen, | 130 | 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 @@ | |||
1 | /* $OpenBSD: kexc25519s.c,v 1.15 2019/01/21 10:05:09 djm Exp $ */ | 1 | /* $OpenBSD: kexc25519s.c,v 1.16 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2001 Markus Friedl. All rights reserved. | 3 | * Copyright (c) 2001 Markus Friedl. All rights reserved. |
4 | * Copyright (c) 2010 Damien Miller. All rights reserved. | 4 | * 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) | |||
104 | sshbuf_ptr(kex->peer), sshbuf_len(kex->peer), | 104 | sshbuf_ptr(kex->peer), sshbuf_len(kex->peer), |
105 | sshbuf_ptr(kex->my), sshbuf_len(kex->my), | 105 | sshbuf_ptr(kex->my), sshbuf_len(kex->my), |
106 | server_host_key_blob, sbloblen, | 106 | server_host_key_blob, sbloblen, |
107 | client_pubkey, | 107 | client_pubkey, pklen, |
108 | server_pubkey, | 108 | server_pubkey, sizeof(server_pubkey), |
109 | sshbuf_ptr(shared_secret), sshbuf_len(shared_secret), | 109 | sshbuf_ptr(shared_secret), sshbuf_len(shared_secret), |
110 | hash, &hashlen)) < 0) | 110 | hash, &hashlen)) != 0) |
111 | goto out; | 111 | goto out; |
112 | 112 | ||
113 | /* sign H */ | 113 | /* 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 @@ | |||
1 | /* $OpenBSD: kexkemc.c,v 1.1 2019/01/21 10:20:12 djm Exp $ */ | ||
2 | /* | ||
3 | * Copyright (c) 2019 Markus Friedl. All rights reserved. | ||
4 | * | ||
5 | * Redistribution and use in source and binary forms, with or without | ||
6 | * modification, are permitted provided that the following conditions | ||
7 | * are met: | ||
8 | * 1. Redistributions of source code must retain the above copyright | ||
9 | * notice, this list of conditions and the following disclaimer. | ||
10 | * 2. Redistributions in binary form must reproduce the above copyright | ||
11 | * notice, this list of conditions and the following disclaimer in the | ||
12 | * documentation and/or other materials provided with the distribution. | ||
13 | * | ||
14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | ||
15 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | ||
16 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | ||
17 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
18 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
19 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
20 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
21 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | ||
23 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
24 | */ | ||
25 | |||
26 | #include <sys/types.h> | ||
27 | |||
28 | #include <stdio.h> | ||
29 | #include <string.h> | ||
30 | #include <signal.h> | ||
31 | |||
32 | #include "sshkey.h" | ||
33 | #include "kex.h" | ||
34 | #include "log.h" | ||
35 | #include "packet.h" | ||
36 | #include "ssh2.h" | ||
37 | #include "sshbuf.h" | ||
38 | #include "digest.h" | ||
39 | #include "ssherr.h" | ||
40 | |||
41 | static int | ||
42 | input_kex_kem_reply(int type, u_int32_t seq, struct ssh *ssh); | ||
43 | |||
44 | int | ||
45 | kex_kem_client(struct ssh *ssh) | ||
46 | { | ||
47 | struct kex *kex = ssh->kex; | ||
48 | int r; | ||
49 | |||
50 | if ((r = kex_kem_sntrup4591761x25519_keypair(kex)) != 0) | ||
51 | return r; | ||
52 | if ((r = sshpkt_start(ssh, SSH2_MSG_KEX_ECDH_INIT)) != 0 || | ||
53 | (r = sshpkt_put_stringb(ssh, kex->kem_client_pub)) != 0 || | ||
54 | (r = sshpkt_send(ssh)) != 0) | ||
55 | return r; | ||
56 | debug("expecting SSH2_MSG_KEX_ECDH_REPLY"); | ||
57 | ssh_dispatch_set(ssh, SSH2_MSG_KEX_ECDH_REPLY, &input_kex_kem_reply); | ||
58 | return 0; | ||
59 | } | ||
60 | |||
61 | static int | ||
62 | input_kex_kem_reply(int type, u_int32_t seq, struct ssh *ssh) | ||
63 | { | ||
64 | struct kex *kex = ssh->kex; | ||
65 | struct sshkey *server_host_key = NULL; | ||
66 | struct sshbuf *shared_secret = NULL; | ||
67 | u_char *server_pubkey = NULL; | ||
68 | u_char *server_host_key_blob = NULL, *signature = NULL; | ||
69 | u_char hash[SSH_DIGEST_MAX_LENGTH]; | ||
70 | size_t slen, pklen, sbloblen, hashlen; | ||
71 | int r; | ||
72 | |||
73 | /* hostkey */ | ||
74 | if ((r = sshpkt_get_string(ssh, &server_host_key_blob, | ||
75 | &sbloblen)) != 0 || | ||
76 | (r = sshkey_from_blob(server_host_key_blob, sbloblen, | ||
77 | &server_host_key)) != 0) | ||
78 | goto out; | ||
79 | if ((r = kex_verify_host_key(ssh, server_host_key)) != 0) | ||
80 | goto out; | ||
81 | |||
82 | /* Q_S, server public key */ | ||
83 | /* signed H */ | ||
84 | if ((r = sshpkt_get_string(ssh, &server_pubkey, &pklen)) != 0 || | ||
85 | (r = sshpkt_get_string(ssh, &signature, &slen)) != 0 || | ||
86 | (r = sshpkt_get_end(ssh)) != 0) | ||
87 | goto out; | ||
88 | |||
89 | /* compute shared secret */ | ||
90 | if ((r = kex_kem_sntrup4591761x25519_dec(kex, server_pubkey, pklen, | ||
91 | &shared_secret)) != 0) | ||
92 | goto out; | ||
93 | |||
94 | /* calc and verify H */ | ||
95 | hashlen = sizeof(hash); | ||
96 | if ((r = kex_c25519_hash( | ||
97 | kex->hash_alg, | ||
98 | kex->client_version, | ||
99 | kex->server_version, | ||
100 | sshbuf_ptr(kex->my), sshbuf_len(kex->my), | ||
101 | sshbuf_ptr(kex->peer), sshbuf_len(kex->peer), | ||
102 | server_host_key_blob, sbloblen, | ||
103 | sshbuf_ptr(kex->kem_client_pub), sshbuf_len(kex->kem_client_pub), | ||
104 | server_pubkey, pklen, | ||
105 | sshbuf_ptr(shared_secret), sshbuf_len(shared_secret), | ||
106 | hash, &hashlen)) != 0) | ||
107 | goto out; | ||
108 | |||
109 | if ((r = sshkey_verify(server_host_key, signature, slen, hash, hashlen, | ||
110 | kex->hostkey_alg, ssh->compat)) != 0) | ||
111 | goto out; | ||
112 | |||
113 | if ((r = kex_derive_keys(ssh, hash, hashlen, shared_secret)) == 0) | ||
114 | r = kex_send_newkeys(ssh); | ||
115 | out: | ||
116 | explicit_bzero(hash, sizeof(hash)); | ||
117 | explicit_bzero(kex->c25519_client_key, sizeof(kex->c25519_client_key)); | ||
118 | explicit_bzero(kex->sntrup4591761_client_key, | ||
119 | sizeof(kex->sntrup4591761_client_key)); | ||
120 | free(server_host_key_blob); | ||
121 | free(server_pubkey); | ||
122 | free(signature); | ||
123 | sshkey_free(server_host_key); | ||
124 | sshbuf_free(shared_secret); | ||
125 | sshbuf_free(kex->kem_client_pub); | ||
126 | kex->kem_client_pub = NULL; | ||
127 | return r; | ||
128 | } | ||
diff --git a/kexkems.c b/kexkems.c new file mode 100644 index 000000000..43cf82018 --- /dev/null +++ b/kexkems.c | |||
@@ -0,0 +1,116 @@ | |||
1 | /* $OpenBSD: kexkems.c,v 1.1 2019/01/21 10:20:12 djm Exp $ */ | ||
2 | /* | ||
3 | * Copyright (c) 2019 Markus Friedl. All rights reserved. | ||
4 | * | ||
5 | * modification, are permitted provided that the following conditions | ||
6 | * are met: | ||
7 | * 1. Redistributions of source code must retain the above copyright | ||
8 | * notice, this list of conditions and the following disclaimer. | ||
9 | * 2. Redistributions in binary form must reproduce the above copyright | ||
10 | * notice, this list of conditions and the following disclaimer in the | ||
11 | * documentation and/or other materials provided with the distribution. | ||
12 | * | ||
13 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | ||
14 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | ||
15 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | ||
16 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
17 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
18 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
19 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
20 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
21 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | ||
22 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
23 | */ | ||
24 | |||
25 | #include <sys/types.h> | ||
26 | #include <stdio.h> | ||
27 | #include <string.h> | ||
28 | #include <signal.h> | ||
29 | |||
30 | #include "sshkey.h" | ||
31 | #include "digest.h" | ||
32 | #include "kex.h" | ||
33 | #include "log.h" | ||
34 | #include "packet.h" | ||
35 | #include "ssh2.h" | ||
36 | #include "sshbuf.h" | ||
37 | #include "ssherr.h" | ||
38 | |||
39 | static int input_kex_kem_init(int, u_int32_t, struct ssh *); | ||
40 | |||
41 | int | ||
42 | kex_kem_server(struct ssh *ssh) | ||
43 | { | ||
44 | debug("expecting SSH2_MSG_KEX_ECDH_INIT"); | ||
45 | ssh_dispatch_set(ssh, SSH2_MSG_KEX_ECDH_INIT, &input_kex_kem_init); | ||
46 | return 0; | ||
47 | } | ||
48 | |||
49 | static int | ||
50 | input_kex_kem_init(int type, u_int32_t seq, struct ssh *ssh) | ||
51 | { | ||
52 | struct kex *kex = ssh->kex; | ||
53 | struct sshkey *server_host_private, *server_host_public; | ||
54 | struct sshbuf *shared_secret = NULL; | ||
55 | struct sshbuf *server_pubkey = NULL; | ||
56 | u_char *server_host_key_blob = NULL, *signature = NULL; | ||
57 | u_char *client_pubkey = NULL; | ||
58 | u_char hash[SSH_DIGEST_MAX_LENGTH]; | ||
59 | size_t slen, pklen, sbloblen, hashlen; | ||
60 | int r; | ||
61 | |||
62 | if ((r = kex_load_hostkey(ssh, &server_host_private, | ||
63 | &server_host_public)) != 0) | ||
64 | goto out; | ||
65 | |||
66 | if ((r = sshpkt_get_string(ssh, &client_pubkey, &pklen)) != 0 || | ||
67 | (r = sshpkt_get_end(ssh)) != 0) | ||
68 | goto out; | ||
69 | |||
70 | /* compute shared secret */ | ||
71 | if ((r = kex_kem_sntrup4591761x25519_enc(kex, client_pubkey, pklen, | ||
72 | &server_pubkey, &shared_secret)) != 0) | ||
73 | goto out; | ||
74 | |||
75 | /* calc H */ | ||
76 | if ((r = sshkey_to_blob(server_host_public, &server_host_key_blob, | ||
77 | &sbloblen)) != 0) | ||
78 | goto out; | ||
79 | hashlen = sizeof(hash); | ||
80 | if ((r = kex_c25519_hash( | ||
81 | kex->hash_alg, | ||
82 | kex->client_version, | ||
83 | kex->server_version, | ||
84 | sshbuf_ptr(kex->peer), sshbuf_len(kex->peer), | ||
85 | sshbuf_ptr(kex->my), sshbuf_len(kex->my), | ||
86 | server_host_key_blob, sbloblen, | ||
87 | client_pubkey, pklen, | ||
88 | sshbuf_ptr(server_pubkey), sshbuf_len(server_pubkey), | ||
89 | sshbuf_ptr(shared_secret), sshbuf_len(shared_secret), | ||
90 | hash, &hashlen)) != 0) | ||
91 | goto out; | ||
92 | |||
93 | /* sign H */ | ||
94 | if ((r = kex->sign(ssh, server_host_private, server_host_public, | ||
95 | &signature, &slen, hash, hashlen, kex->hostkey_alg)) != 0) | ||
96 | goto out; | ||
97 | |||
98 | /* send server hostkey, ECDH pubkey 'Q_S' and signed H */ | ||
99 | if ((r = sshpkt_start(ssh, SSH2_MSG_KEX_ECDH_REPLY)) != 0 || | ||
100 | (r = sshpkt_put_string(ssh, server_host_key_blob, sbloblen)) != 0 || | ||
101 | (r = sshpkt_put_stringb(ssh, server_pubkey)) != 0 || | ||
102 | (r = sshpkt_put_string(ssh, signature, slen)) != 0 || | ||
103 | (r = sshpkt_send(ssh)) != 0) | ||
104 | goto out; | ||
105 | |||
106 | if ((r = kex_derive_keys(ssh, hash, hashlen, shared_secret)) == 0) | ||
107 | r = kex_send_newkeys(ssh); | ||
108 | out: | ||
109 | explicit_bzero(hash, sizeof(hash)); | ||
110 | free(server_host_key_blob); | ||
111 | free(signature); | ||
112 | free(client_pubkey); | ||
113 | sshbuf_free(shared_secret); | ||
114 | sshbuf_free(server_pubkey); | ||
115 | return r; | ||
116 | } | ||
diff --git a/kexsntrup4591761x25519.c b/kexsntrup4591761x25519.c new file mode 100644 index 000000000..ffe05f420 --- /dev/null +++ b/kexsntrup4591761x25519.c | |||
@@ -0,0 +1,213 @@ | |||
1 | /* $OpenBSD: kexsntrup4591761x25519.c,v 1.1 2019/01/21 10:20:12 djm Exp $ */ | ||
2 | /* | ||
3 | * Copyright (c) 2019 Markus Friedl. All rights reserved. | ||
4 | * | ||
5 | * Redistribution and use in source and binary forms, with or without | ||
6 | * modification, are permitted provided that the following conditions | ||
7 | * are met: | ||
8 | * 1. Redistributions of source code must retain the above copyright | ||
9 | * notice, this list of conditions and the following disclaimer. | ||
10 | * 2. Redistributions in binary form must reproduce the above copyright | ||
11 | * notice, this list of conditions and the following disclaimer in the | ||
12 | * documentation and/or other materials provided with the distribution. | ||
13 | * | ||
14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | ||
15 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | ||
16 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. | ||
17 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, | ||
18 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
19 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
20 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
21 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF | ||
23 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
24 | */ | ||
25 | |||
26 | #include <sys/types.h> | ||
27 | |||
28 | #include <stdio.h> | ||
29 | #include <string.h> | ||
30 | #include <signal.h> | ||
31 | |||
32 | #include "sshkey.h" | ||
33 | #include "kex.h" | ||
34 | #include "sshbuf.h" | ||
35 | #include "digest.h" | ||
36 | #include "ssherr.h" | ||
37 | |||
38 | int | ||
39 | kex_kem_sntrup4591761x25519_keypair(struct kex *kex) | ||
40 | { | ||
41 | struct sshbuf *buf = NULL; | ||
42 | u_char *cp = NULL; | ||
43 | size_t need; | ||
44 | int r; | ||
45 | |||
46 | if ((buf = sshbuf_new()) == NULL) | ||
47 | return SSH_ERR_ALLOC_FAIL; | ||
48 | need = crypto_kem_sntrup4591761_PUBLICKEYBYTES + CURVE25519_SIZE; | ||
49 | if ((r = sshbuf_reserve(buf, need, &cp)) != 0) | ||
50 | goto out; | ||
51 | crypto_kem_sntrup4591761_keypair(cp, kex->sntrup4591761_client_key); | ||
52 | #ifdef DEBUG_KEXECDH | ||
53 | dump_digest("client public key sntrup4591761:", cp, | ||
54 | crypto_kem_sntrup4591761_PUBLICKEYBYTES); | ||
55 | #endif | ||
56 | cp += crypto_kem_sntrup4591761_PUBLICKEYBYTES; | ||
57 | kexc25519_keygen(kex->c25519_client_key, cp); | ||
58 | #ifdef DEBUG_KEXECDH | ||
59 | dump_digest("client public key c25519:", cp, CURVE25519_SIZE); | ||
60 | #endif | ||
61 | kex->kem_client_pub = buf; | ||
62 | buf = NULL; | ||
63 | out: | ||
64 | sshbuf_free(buf); | ||
65 | return r; | ||
66 | } | ||
67 | |||
68 | int | ||
69 | kex_kem_sntrup4591761x25519_enc(struct kex *kex, const u_char *pkblob, | ||
70 | size_t pklen, struct sshbuf **server_blobp, struct sshbuf **shared_secretp) | ||
71 | { | ||
72 | struct sshbuf *server_blob = NULL; | ||
73 | struct sshbuf *buf = NULL; | ||
74 | u_char *kem_key, *ciphertext, *server_pub; | ||
75 | u_char server_key[CURVE25519_SIZE]; | ||
76 | u_char hash[SSH_DIGEST_MAX_LENGTH]; | ||
77 | size_t need; | ||
78 | int r; | ||
79 | |||
80 | *server_blobp = NULL; | ||
81 | *shared_secretp = NULL; | ||
82 | |||
83 | /* pkblob contains both KEM and ECDH client pubkeys */ | ||
84 | need = crypto_kem_sntrup4591761_PUBLICKEYBYTES + CURVE25519_SIZE; | ||
85 | if (pklen != need) { | ||
86 | r = SSH_ERR_SIGNATURE_INVALID; | ||
87 | goto out; | ||
88 | } | ||
89 | #ifdef DEBUG_KEXECDH | ||
90 | dump_digest("client public key sntrup4591761:", pkblob, | ||
91 | crypto_kem_sntrup4591761_PUBLICKEYBYTES); | ||
92 | dump_digest("client public key 25519:", | ||
93 | pkblob + crypto_kem_sntrup4591761_PUBLICKEYBYTES, CURVE25519_SIZE); | ||
94 | #endif | ||
95 | /* allocate buffer for concatenation of KEM key and ECDH shared key */ | ||
96 | /* the buffer will be hashed and the result is the shared secret */ | ||
97 | if ((buf = sshbuf_new()) == NULL) { | ||
98 | r = SSH_ERR_ALLOC_FAIL; | ||
99 | goto out; | ||
100 | } | ||
101 | if ((r = sshbuf_reserve(buf, crypto_kem_sntrup4591761_BYTES, | ||
102 | &kem_key)) != 0) | ||
103 | goto out; | ||
104 | /* allocate space for encrypted KEM key and ECDH pub key */ | ||
105 | if ((server_blob = sshbuf_new()) == NULL) { | ||
106 | r = SSH_ERR_ALLOC_FAIL; | ||
107 | goto out; | ||
108 | } | ||
109 | need = crypto_kem_sntrup4591761_CIPHERTEXTBYTES + CURVE25519_SIZE; | ||
110 | if ((r = sshbuf_reserve(server_blob, need, &ciphertext)) != 0) | ||
111 | goto out; | ||
112 | /* generate and encrypt KEM key with client key */ | ||
113 | crypto_kem_sntrup4591761_enc(ciphertext, kem_key, pkblob); | ||
114 | /* generate ECDH key pair, store server pubkey after ciphertext */ | ||
115 | server_pub = ciphertext + crypto_kem_sntrup4591761_CIPHERTEXTBYTES; | ||
116 | kexc25519_keygen(server_key, server_pub); | ||
117 | /* append ECDH shared key */ | ||
118 | if ((r = kexc25519_shared_key_ext(server_key, | ||
119 | pkblob + crypto_kem_sntrup4591761_PUBLICKEYBYTES, buf, 1)) < 0) | ||
120 | goto out; | ||
121 | if ((r = ssh_digest_buffer(kex->hash_alg, buf, hash, sizeof(hash))) != 0) | ||
122 | goto out; | ||
123 | #ifdef DEBUG_KEXECDH | ||
124 | dump_digest("server public key 25519:", server_pub, CURVE25519_SIZE); | ||
125 | dump_digest("server cipher text:", ciphertext, | ||
126 | crypto_kem_sntrup4591761_CIPHERTEXTBYTES); | ||
127 | dump_digest("server kem key:", kem_key, sizeof(kem_key)); | ||
128 | dump_digest("concatenation of KEM key and ECDH shared key:", | ||
129 | sshbuf_ptr(buf), sshbuf_len(buf)); | ||
130 | #endif | ||
131 | /* string-encoded hash is resulting shared secret */ | ||
132 | sshbuf_reset(buf); | ||
133 | if ((r = sshbuf_put_string(buf, hash, | ||
134 | ssh_digest_bytes(kex->hash_alg))) != 0) | ||
135 | goto out; | ||
136 | #ifdef DEBUG_KEXECDH | ||
137 | dump_digest("encoded shared secret:", sshbuf_ptr(buf), sshbuf_len(buf)); | ||
138 | #endif | ||
139 | *server_blobp = server_blob; | ||
140 | *shared_secretp = buf; | ||
141 | server_blob = NULL; | ||
142 | buf = NULL; | ||
143 | out: | ||
144 | explicit_bzero(hash, sizeof(hash)); | ||
145 | explicit_bzero(server_key, sizeof(server_key)); | ||
146 | sshbuf_free(server_blob); | ||
147 | sshbuf_free(buf); | ||
148 | return r; | ||
149 | } | ||
150 | |||
151 | int | ||
152 | kex_kem_sntrup4591761x25519_dec(struct kex *kex, const u_char *pkblob, | ||
153 | size_t pklen, struct sshbuf **shared_secretp) | ||
154 | { | ||
155 | struct sshbuf *buf = NULL; | ||
156 | u_char *kem_key = NULL; | ||
157 | const u_char *ciphertext, *server_pub; | ||
158 | u_char hash[SSH_DIGEST_MAX_LENGTH]; | ||
159 | size_t need; | ||
160 | int r, decoded; | ||
161 | |||
162 | *shared_secretp = NULL; | ||
163 | |||
164 | need = crypto_kem_sntrup4591761_CIPHERTEXTBYTES + CURVE25519_SIZE; | ||
165 | if (pklen != need) { | ||
166 | r = SSH_ERR_SIGNATURE_INVALID; | ||
167 | goto out; | ||
168 | } | ||
169 | ciphertext = pkblob; | ||
170 | server_pub = pkblob + crypto_kem_sntrup4591761_CIPHERTEXTBYTES; | ||
171 | #ifdef DEBUG_KEXECDH | ||
172 | dump_digest("server cipher text:", ciphertext, | ||
173 | crypto_kem_sntrup4591761_CIPHERTEXTBYTES); | ||
174 | dump_digest("server public key c25519:", server_pub, CURVE25519_SIZE); | ||
175 | #endif | ||
176 | /* hash concatenation of KEM key and ECDH shared key */ | ||
177 | if ((buf = sshbuf_new()) == NULL) { | ||
178 | r = SSH_ERR_ALLOC_FAIL; | ||
179 | goto out; | ||
180 | } | ||
181 | if ((r = sshbuf_reserve(buf, crypto_kem_sntrup4591761_BYTES, | ||
182 | &kem_key)) != 0) | ||
183 | goto out; | ||
184 | decoded = crypto_kem_sntrup4591761_dec(kem_key, ciphertext, | ||
185 | kex->sntrup4591761_client_key); | ||
186 | if ((r = kexc25519_shared_key_ext(kex->c25519_client_key, server_pub, | ||
187 | buf, 1)) < 0) | ||
188 | goto out; | ||
189 | if ((r = ssh_digest_buffer(kex->hash_alg, buf, hash, sizeof(hash))) != 0) | ||
190 | goto out; | ||
191 | #ifdef DEBUG_KEXECDH | ||
192 | dump_digest("client kem key:", kem_key, sizeof(kem_key)); | ||
193 | dump_digest("concatenation of KEM key and ECDH shared key:", | ||
194 | sshbuf_ptr(buf), sshbuf_len(buf)); | ||
195 | #endif | ||
196 | sshbuf_reset(buf); | ||
197 | if ((r = sshbuf_put_string(buf, hash, | ||
198 | ssh_digest_bytes(kex->hash_alg))) != 0) | ||
199 | goto out; | ||
200 | #ifdef DEBUG_KEXECDH | ||
201 | dump_digest("encoded shared secret:", sshbuf_ptr(buf), sshbuf_len(buf)); | ||
202 | #endif | ||
203 | if (decoded != 0) { | ||
204 | r = SSH_ERR_SIGNATURE_INVALID; | ||
205 | goto out; | ||
206 | } | ||
207 | *shared_secretp = buf; | ||
208 | buf = NULL; | ||
209 | out: | ||
210 | explicit_bzero(hash, sizeof(hash)); | ||
211 | sshbuf_free(buf); | ||
212 | return r; | ||
213 | } | ||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: monitor.c,v 1.192 2019/01/19 21:43:56 djm Exp $ */ | 1 | /* $OpenBSD: monitor.c,v 1.193 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright 2002 Niels Provos <provos@citi.umich.edu> | 3 | * Copyright 2002 Niels Provos <provos@citi.umich.edu> |
4 | * Copyright 2002 Markus Friedl <markus@openbsd.org> | 4 | * Copyright 2002 Markus Friedl <markus@openbsd.org> |
@@ -1689,6 +1689,7 @@ monitor_apply_keystate(struct ssh *ssh, struct monitor *pmonitor) | |||
1689 | # endif | 1689 | # endif |
1690 | #endif /* WITH_OPENSSL */ | 1690 | #endif /* WITH_OPENSSL */ |
1691 | kex->kex[KEX_C25519_SHA256] = kexc25519_server; | 1691 | kex->kex[KEX_C25519_SHA256] = kexc25519_server; |
1692 | kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_server; | ||
1692 | kex->load_host_public_key=&get_hostkey_public_by_type; | 1693 | kex->load_host_public_key=&get_hostkey_public_by_type; |
1693 | kex->load_host_private_key=&get_hostkey_private_by_type; | 1694 | kex->load_host_private_key=&get_hostkey_private_by_type; |
1694 | kex->host_key_index=&get_hostkey_index; | 1695 | 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 @@ | |||
1 | #include <string.h> | ||
2 | #include "crypto_api.h" | ||
3 | |||
4 | /* from supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc */ | ||
5 | #define int32_MINMAX(a,b) \ | ||
6 | do { \ | ||
7 | int32 ab = b ^ a; \ | ||
8 | int32 c = b - a; \ | ||
9 | c ^= ab & (c ^ b); \ | ||
10 | c >>= 31; \ | ||
11 | c &= ab; \ | ||
12 | a ^= c; \ | ||
13 | b ^= c; \ | ||
14 | } while(0) | ||
15 | |||
16 | /* from supercop-20181216/crypto_sort/int32/portable3/sort.c */ | ||
17 | #define int32 crypto_int32 | ||
18 | |||
19 | |||
20 | static void crypto_sort_int32(void *array,long long n) | ||
21 | { | ||
22 | long long top,p,q,r,i; | ||
23 | int32 *x = array; | ||
24 | |||
25 | if (n < 2) return; | ||
26 | top = 1; | ||
27 | while (top < n - top) top += top; | ||
28 | |||
29 | for (p = top;p > 0;p >>= 1) { | ||
30 | for (i = 0;i < n - p;++i) | ||
31 | if (!(i & p)) | ||
32 | int32_MINMAX(x[i],x[i+p]); | ||
33 | i = 0; | ||
34 | for (q = top;q > p;q >>= 1) { | ||
35 | for (;i < n - q;++i) { | ||
36 | if (!(i & p)) { | ||
37 | int32 a = x[i + p]; | ||
38 | for (r = q;r > p;r >>= 1) | ||
39 | int32_MINMAX(a,x[i+r]); | ||
40 | x[i + p] = a; | ||
41 | } | ||
42 | } | ||
43 | } | ||
44 | } | ||
45 | } | ||
46 | |||
47 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.h */ | ||
48 | #ifndef small_h | ||
49 | #define small_h | ||
50 | |||
51 | |||
52 | typedef crypto_int8 small; | ||
53 | |||
54 | static void small_encode(unsigned char *,const small *); | ||
55 | |||
56 | static void small_decode(small *,const unsigned char *); | ||
57 | |||
58 | |||
59 | static void small_random(small *); | ||
60 | |||
61 | static void small_random_weightw(small *); | ||
62 | |||
63 | #endif | ||
64 | |||
65 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h */ | ||
66 | #ifndef mod3_h | ||
67 | #define mod3_h | ||
68 | |||
69 | |||
70 | /* -1 if x is nonzero, 0 otherwise */ | ||
71 | static inline int mod3_nonzero_mask(small x) | ||
72 | { | ||
73 | return -x*x; | ||
74 | } | ||
75 | |||
76 | /* input between -100000 and 100000 */ | ||
77 | /* output between -1 and 1 */ | ||
78 | static inline small mod3_freeze(crypto_int32 a) | ||
79 | { | ||
80 | a -= 3 * ((10923 * a) >> 15); | ||
81 | a -= 3 * ((89478485 * a + 134217728) >> 28); | ||
82 | return a; | ||
83 | } | ||
84 | |||
85 | static inline small mod3_minusproduct(small a,small b,small c) | ||
86 | { | ||
87 | crypto_int32 A = a; | ||
88 | crypto_int32 B = b; | ||
89 | crypto_int32 C = c; | ||
90 | return mod3_freeze(A - B * C); | ||
91 | } | ||
92 | |||
93 | static inline small mod3_plusproduct(small a,small b,small c) | ||
94 | { | ||
95 | crypto_int32 A = a; | ||
96 | crypto_int32 B = b; | ||
97 | crypto_int32 C = c; | ||
98 | return mod3_freeze(A + B * C); | ||
99 | } | ||
100 | |||
101 | static inline small mod3_product(small a,small b) | ||
102 | { | ||
103 | return a * b; | ||
104 | } | ||
105 | |||
106 | static inline small mod3_sum(small a,small b) | ||
107 | { | ||
108 | crypto_int32 A = a; | ||
109 | crypto_int32 B = b; | ||
110 | return mod3_freeze(A + B); | ||
111 | } | ||
112 | |||
113 | static inline small mod3_reciprocal(small a1) | ||
114 | { | ||
115 | return a1; | ||
116 | } | ||
117 | |||
118 | static inline small mod3_quotient(small num,small den) | ||
119 | { | ||
120 | return mod3_product(num,mod3_reciprocal(den)); | ||
121 | } | ||
122 | |||
123 | #endif | ||
124 | |||
125 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h */ | ||
126 | #ifndef modq_h | ||
127 | #define modq_h | ||
128 | |||
129 | |||
130 | typedef crypto_int16 modq; | ||
131 | |||
132 | /* -1 if x is nonzero, 0 otherwise */ | ||
133 | static inline int modq_nonzero_mask(modq x) | ||
134 | { | ||
135 | crypto_int32 r = (crypto_uint16) x; | ||
136 | r = -r; | ||
137 | r >>= 30; | ||
138 | return r; | ||
139 | } | ||
140 | |||
141 | /* input between -9000000 and 9000000 */ | ||
142 | /* output between -2295 and 2295 */ | ||
143 | static inline modq modq_freeze(crypto_int32 a) | ||
144 | { | ||
145 | a -= 4591 * ((228 * a) >> 20); | ||
146 | a -= 4591 * ((58470 * a + 134217728) >> 28); | ||
147 | return a; | ||
148 | } | ||
149 | |||
150 | static inline modq modq_minusproduct(modq a,modq b,modq c) | ||
151 | { | ||
152 | crypto_int32 A = a; | ||
153 | crypto_int32 B = b; | ||
154 | crypto_int32 C = c; | ||
155 | return modq_freeze(A - B * C); | ||
156 | } | ||
157 | |||
158 | static inline modq modq_plusproduct(modq a,modq b,modq c) | ||
159 | { | ||
160 | crypto_int32 A = a; | ||
161 | crypto_int32 B = b; | ||
162 | crypto_int32 C = c; | ||
163 | return modq_freeze(A + B * C); | ||
164 | } | ||
165 | |||
166 | static inline modq modq_product(modq a,modq b) | ||
167 | { | ||
168 | crypto_int32 A = a; | ||
169 | crypto_int32 B = b; | ||
170 | return modq_freeze(A * B); | ||
171 | } | ||
172 | |||
173 | static inline modq modq_square(modq a) | ||
174 | { | ||
175 | crypto_int32 A = a; | ||
176 | return modq_freeze(A * A); | ||
177 | } | ||
178 | |||
179 | static inline modq modq_sum(modq a,modq b) | ||
180 | { | ||
181 | crypto_int32 A = a; | ||
182 | crypto_int32 B = b; | ||
183 | return modq_freeze(A + B); | ||
184 | } | ||
185 | |||
186 | static inline modq modq_reciprocal(modq a1) | ||
187 | { | ||
188 | modq a2 = modq_square(a1); | ||
189 | modq a3 = modq_product(a2,a1); | ||
190 | modq a4 = modq_square(a2); | ||
191 | modq a8 = modq_square(a4); | ||
192 | modq a16 = modq_square(a8); | ||
193 | modq a32 = modq_square(a16); | ||
194 | modq a35 = modq_product(a32,a3); | ||
195 | modq a70 = modq_square(a35); | ||
196 | modq a140 = modq_square(a70); | ||
197 | modq a143 = modq_product(a140,a3); | ||
198 | modq a286 = modq_square(a143); | ||
199 | modq a572 = modq_square(a286); | ||
200 | modq a1144 = modq_square(a572); | ||
201 | modq a1147 = modq_product(a1144,a3); | ||
202 | modq a2294 = modq_square(a1147); | ||
203 | modq a4588 = modq_square(a2294); | ||
204 | modq a4589 = modq_product(a4588,a1); | ||
205 | return a4589; | ||
206 | } | ||
207 | |||
208 | static inline modq modq_quotient(modq num,modq den) | ||
209 | { | ||
210 | return modq_product(num,modq_reciprocal(den)); | ||
211 | } | ||
212 | |||
213 | #endif | ||
214 | |||
215 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/params.h */ | ||
216 | #ifndef params_h | ||
217 | #define params_h | ||
218 | |||
219 | #define q 4591 | ||
220 | /* XXX: also built into modq in various ways */ | ||
221 | |||
222 | #define qshift 2295 | ||
223 | #define p 761 | ||
224 | #define w 286 | ||
225 | |||
226 | #define rq_encode_len 1218 | ||
227 | #define small_encode_len 191 | ||
228 | |||
229 | #endif | ||
230 | |||
231 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h */ | ||
232 | #ifndef r3_h | ||
233 | #define r3_h | ||
234 | |||
235 | |||
236 | static void r3_mult(small *,const small *,const small *); | ||
237 | |||
238 | extern int r3_recip(small *,const small *); | ||
239 | |||
240 | #endif | ||
241 | |||
242 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h */ | ||
243 | #ifndef rq_h | ||
244 | #define rq_h | ||
245 | |||
246 | |||
247 | static void rq_encode(unsigned char *,const modq *); | ||
248 | |||
249 | static void rq_decode(modq *,const unsigned char *); | ||
250 | |||
251 | static void rq_encoderounded(unsigned char *,const modq *); | ||
252 | |||
253 | static void rq_decoderounded(modq *,const unsigned char *); | ||
254 | |||
255 | static void rq_round3(modq *,const modq *); | ||
256 | |||
257 | static void rq_mult(modq *,const modq *,const small *); | ||
258 | |||
259 | int rq_recip3(modq *,const small *); | ||
260 | |||
261 | #endif | ||
262 | |||
263 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h */ | ||
264 | #ifndef swap_h | ||
265 | #define swap_h | ||
266 | |||
267 | static void swap(void *,void *,int,int); | ||
268 | |||
269 | #endif | ||
270 | |||
271 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c */ | ||
272 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
273 | |||
274 | #ifdef KAT | ||
275 | #endif | ||
276 | |||
277 | |||
278 | int crypto_kem_sntrup4591761_dec( | ||
279 | unsigned char *k, | ||
280 | const unsigned char *cstr, | ||
281 | const unsigned char *sk | ||
282 | ) | ||
283 | { | ||
284 | small f[p]; | ||
285 | modq h[p]; | ||
286 | small grecip[p]; | ||
287 | modq c[p]; | ||
288 | modq t[p]; | ||
289 | small t3[p]; | ||
290 | small r[p]; | ||
291 | modq hr[p]; | ||
292 | unsigned char rstr[small_encode_len]; | ||
293 | unsigned char hash[64]; | ||
294 | int i; | ||
295 | int result = 0; | ||
296 | int weight; | ||
297 | |||
298 | small_decode(f,sk); | ||
299 | small_decode(grecip,sk + small_encode_len); | ||
300 | rq_decode(h,sk + 2 * small_encode_len); | ||
301 | |||
302 | rq_decoderounded(c,cstr + 32); | ||
303 | |||
304 | rq_mult(t,c,f); | ||
305 | for (i = 0;i < p;++i) t3[i] = mod3_freeze(modq_freeze(3*t[i])); | ||
306 | |||
307 | r3_mult(r,t3,grecip); | ||
308 | |||
309 | #ifdef KAT | ||
310 | { | ||
311 | int j; | ||
312 | printf("decrypt r:"); | ||
313 | for (j = 0;j < p;++j) | ||
314 | if (r[j] == 1) printf(" +%d",j); | ||
315 | else if (r[j] == -1) printf(" -%d",j); | ||
316 | printf("\n"); | ||
317 | } | ||
318 | #endif | ||
319 | |||
320 | weight = 0; | ||
321 | for (i = 0;i < p;++i) weight += (1 & r[i]); | ||
322 | weight -= w; | ||
323 | result |= modq_nonzero_mask(weight); /* XXX: puts limit on p */ | ||
324 | |||
325 | rq_mult(hr,h,r); | ||
326 | rq_round3(hr,hr); | ||
327 | for (i = 0;i < p;++i) result |= modq_nonzero_mask(hr[i] - c[i]); | ||
328 | |||
329 | small_encode(rstr,r); | ||
330 | crypto_hash_sha512(hash,rstr,sizeof rstr); | ||
331 | result |= crypto_verify_32(hash,cstr); | ||
332 | |||
333 | for (i = 0;i < 32;++i) k[i] = (hash[32 + i] & ~result); | ||
334 | return result; | ||
335 | } | ||
336 | |||
337 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c */ | ||
338 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
339 | |||
340 | #ifdef KAT | ||
341 | #endif | ||
342 | |||
343 | |||
344 | int crypto_kem_sntrup4591761_enc( | ||
345 | unsigned char *cstr, | ||
346 | unsigned char *k, | ||
347 | const unsigned char *pk | ||
348 | ) | ||
349 | { | ||
350 | small r[p]; | ||
351 | modq h[p]; | ||
352 | modq c[p]; | ||
353 | unsigned char rstr[small_encode_len]; | ||
354 | unsigned char hash[64]; | ||
355 | |||
356 | small_random_weightw(r); | ||
357 | |||
358 | #ifdef KAT | ||
359 | { | ||
360 | int i; | ||
361 | printf("encrypt r:"); | ||
362 | for (i = 0;i < p;++i) | ||
363 | if (r[i] == 1) printf(" +%d",i); | ||
364 | else if (r[i] == -1) printf(" -%d",i); | ||
365 | printf("\n"); | ||
366 | } | ||
367 | #endif | ||
368 | |||
369 | small_encode(rstr,r); | ||
370 | crypto_hash_sha512(hash,rstr,sizeof rstr); | ||
371 | |||
372 | rq_decode(h,pk); | ||
373 | rq_mult(c,h,r); | ||
374 | rq_round3(c,c); | ||
375 | |||
376 | memcpy(k,hash + 32,32); | ||
377 | memcpy(cstr,hash,32); | ||
378 | rq_encoderounded(cstr + 32,c); | ||
379 | |||
380 | return 0; | ||
381 | } | ||
382 | |||
383 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c */ | ||
384 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
385 | |||
386 | |||
387 | #if crypto_kem_sntrup4591761_PUBLICKEYBYTES != rq_encode_len | ||
388 | #error "crypto_kem_sntrup4591761_PUBLICKEYBYTES must match rq_encode_len" | ||
389 | #endif | ||
390 | #if crypto_kem_sntrup4591761_SECRETKEYBYTES != rq_encode_len + 2 * small_encode_len | ||
391 | #error "crypto_kem_sntrup4591761_SECRETKEYBYTES must match rq_encode_len + 2 * small_encode_len" | ||
392 | #endif | ||
393 | |||
394 | int crypto_kem_sntrup4591761_keypair(unsigned char *pk,unsigned char *sk) | ||
395 | { | ||
396 | small g[p]; | ||
397 | small grecip[p]; | ||
398 | small f[p]; | ||
399 | modq f3recip[p]; | ||
400 | modq h[p]; | ||
401 | |||
402 | do | ||
403 | small_random(g); | ||
404 | while (r3_recip(grecip,g) != 0); | ||
405 | |||
406 | small_random_weightw(f); | ||
407 | rq_recip3(f3recip,f); | ||
408 | |||
409 | rq_mult(h,f3recip,g); | ||
410 | |||
411 | rq_encode(pk,h); | ||
412 | small_encode(sk,f); | ||
413 | small_encode(sk + small_encode_len,grecip); | ||
414 | memcpy(sk + 2 * small_encode_len,pk,rq_encode_len); | ||
415 | |||
416 | return 0; | ||
417 | } | ||
418 | |||
419 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c */ | ||
420 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
421 | |||
422 | |||
423 | static void r3_mult(small *h,const small *f,const small *g) | ||
424 | { | ||
425 | small fg[p + p - 1]; | ||
426 | small result; | ||
427 | int i, j; | ||
428 | |||
429 | for (i = 0;i < p;++i) { | ||
430 | result = 0; | ||
431 | for (j = 0;j <= i;++j) | ||
432 | result = mod3_plusproduct(result,f[j],g[i - j]); | ||
433 | fg[i] = result; | ||
434 | } | ||
435 | for (i = p;i < p + p - 1;++i) { | ||
436 | result = 0; | ||
437 | for (j = i - p + 1;j < p;++j) | ||
438 | result = mod3_plusproduct(result,f[j],g[i - j]); | ||
439 | fg[i] = result; | ||
440 | } | ||
441 | |||
442 | for (i = p + p - 2;i >= p;--i) { | ||
443 | fg[i - p] = mod3_sum(fg[i - p],fg[i]); | ||
444 | fg[i - p + 1] = mod3_sum(fg[i - p + 1],fg[i]); | ||
445 | } | ||
446 | |||
447 | for (i = 0;i < p;++i) | ||
448 | h[i] = fg[i]; | ||
449 | } | ||
450 | |||
451 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c */ | ||
452 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
453 | |||
454 | |||
455 | /* caller must ensure that x-y does not overflow */ | ||
456 | static int smaller_mask_r3_recip(int x,int y) | ||
457 | { | ||
458 | return (x - y) >> 31; | ||
459 | } | ||
460 | |||
461 | static void vectormod3_product(small *z,int len,const small *x,const small c) | ||
462 | { | ||
463 | int i; | ||
464 | for (i = 0;i < len;++i) z[i] = mod3_product(x[i],c); | ||
465 | } | ||
466 | |||
467 | static void vectormod3_minusproduct(small *z,int len,const small *x,const small *y,const small c) | ||
468 | { | ||
469 | int i; | ||
470 | for (i = 0;i < len;++i) z[i] = mod3_minusproduct(x[i],y[i],c); | ||
471 | } | ||
472 | |||
473 | static void vectormod3_shift(small *z,int len) | ||
474 | { | ||
475 | int i; | ||
476 | for (i = len - 1;i > 0;--i) z[i] = z[i - 1]; | ||
477 | z[0] = 0; | ||
478 | } | ||
479 | |||
480 | /* | ||
481 | r = s^(-1) mod m, returning 0, if s is invertible mod m | ||
482 | or returning -1 if s is not invertible mod m | ||
483 | r,s are polys of degree <p | ||
484 | m is x^p-x-1 | ||
485 | */ | ||
486 | int r3_recip(small *r,const small *s) | ||
487 | { | ||
488 | const int loops = 2*p + 1; | ||
489 | int loop; | ||
490 | small f[p + 1]; | ||
491 | small g[p + 1]; | ||
492 | small u[loops + 1]; | ||
493 | small v[loops + 1]; | ||
494 | small c; | ||
495 | int i; | ||
496 | int d = p; | ||
497 | int e = p; | ||
498 | int swapmask; | ||
499 | |||
500 | for (i = 2;i < p;++i) f[i] = 0; | ||
501 | f[0] = -1; | ||
502 | f[1] = -1; | ||
503 | f[p] = 1; | ||
504 | /* generalization: can initialize f to any polynomial m */ | ||
505 | /* requirements: m has degree exactly p, nonzero constant coefficient */ | ||
506 | |||
507 | for (i = 0;i < p;++i) g[i] = s[i]; | ||
508 | g[p] = 0; | ||
509 | |||
510 | for (i = 0;i <= loops;++i) u[i] = 0; | ||
511 | |||
512 | v[0] = 1; | ||
513 | for (i = 1;i <= loops;++i) v[i] = 0; | ||
514 | |||
515 | loop = 0; | ||
516 | for (;;) { | ||
517 | /* e == -1 or d + e + loop <= 2*p */ | ||
518 | |||
519 | /* f has degree p: i.e., f[p]!=0 */ | ||
520 | /* f[i]==0 for i < p-d */ | ||
521 | |||
522 | /* g has degree <=p (so it fits in p+1 coefficients) */ | ||
523 | /* g[i]==0 for i < p-e */ | ||
524 | |||
525 | /* u has degree <=loop (so it fits in loop+1 coefficients) */ | ||
526 | /* u[i]==0 for i < p-d */ | ||
527 | /* if invertible: u[i]==0 for i < loop-p (so can look at just p+1 coefficients) */ | ||
528 | |||
529 | /* v has degree <=loop (so it fits in loop+1 coefficients) */ | ||
530 | /* v[i]==0 for i < p-e */ | ||
531 | /* v[i]==0 for i < loop-p (so can look at just p+1 coefficients) */ | ||
532 | |||
533 | if (loop >= loops) break; | ||
534 | |||
535 | c = mod3_quotient(g[p],f[p]); | ||
536 | |||
537 | vectormod3_minusproduct(g,p + 1,g,f,c); | ||
538 | vectormod3_shift(g,p + 1); | ||
539 | |||
540 | #ifdef SIMPLER | ||
541 | vectormod3_minusproduct(v,loops + 1,v,u,c); | ||
542 | vectormod3_shift(v,loops + 1); | ||
543 | #else | ||
544 | if (loop < p) { | ||
545 | vectormod3_minusproduct(v,loop + 1,v,u,c); | ||
546 | vectormod3_shift(v,loop + 2); | ||
547 | } else { | ||
548 | vectormod3_minusproduct(v + loop - p,p + 1,v + loop - p,u + loop - p,c); | ||
549 | vectormod3_shift(v + loop - p,p + 2); | ||
550 | } | ||
551 | #endif | ||
552 | |||
553 | e -= 1; | ||
554 | |||
555 | ++loop; | ||
556 | |||
557 | swapmask = smaller_mask_r3_recip(e,d) & mod3_nonzero_mask(g[p]); | ||
558 | swap(&e,&d,sizeof e,swapmask); | ||
559 | swap(f,g,(p + 1) * sizeof(small),swapmask); | ||
560 | |||
561 | #ifdef SIMPLER | ||
562 | swap(u,v,(loops + 1) * sizeof(small),swapmask); | ||
563 | #else | ||
564 | if (loop < p) { | ||
565 | swap(u,v,(loop + 1) * sizeof(small),swapmask); | ||
566 | } else { | ||
567 | swap(u + loop - p,v + loop - p,(p + 1) * sizeof(small),swapmask); | ||
568 | } | ||
569 | #endif | ||
570 | } | ||
571 | |||
572 | c = mod3_reciprocal(f[p]); | ||
573 | vectormod3_product(r,p,u + p,c); | ||
574 | return smaller_mask_r3_recip(0,d); | ||
575 | } | ||
576 | |||
577 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c */ | ||
578 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
579 | |||
580 | |||
581 | static void small_random(small *g) | ||
582 | { | ||
583 | int i; | ||
584 | |||
585 | for (i = 0;i < p;++i) { | ||
586 | crypto_uint32 r = small_random32(); | ||
587 | g[i] = (small) (((1073741823 & r) * 3) >> 30) - 1; | ||
588 | } | ||
589 | } | ||
590 | |||
591 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c */ | ||
592 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
593 | |||
594 | |||
595 | static void small_random_weightw(small *f) | ||
596 | { | ||
597 | crypto_int32 r[p]; | ||
598 | int i; | ||
599 | |||
600 | for (i = 0;i < p;++i) r[i] = small_random32(); | ||
601 | for (i = 0;i < w;++i) r[i] &= -2; | ||
602 | for (i = w;i < p;++i) r[i] = (r[i] & -3) | 1; | ||
603 | crypto_sort_int32(r,p); | ||
604 | for (i = 0;i < p;++i) f[i] = ((small) (r[i] & 3)) - 1; | ||
605 | } | ||
606 | |||
607 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c */ | ||
608 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
609 | |||
610 | |||
611 | static void rq_encode(unsigned char *c,const modq *f) | ||
612 | { | ||
613 | crypto_int32 f0, f1, f2, f3, f4; | ||
614 | int i; | ||
615 | |||
616 | for (i = 0;i < p/5;++i) { | ||
617 | f0 = *f++ + qshift; | ||
618 | f1 = *f++ + qshift; | ||
619 | f2 = *f++ + qshift; | ||
620 | f3 = *f++ + qshift; | ||
621 | f4 = *f++ + qshift; | ||
622 | /* now want f0 + 6144*f1 + ... as a 64-bit integer */ | ||
623 | f1 *= 3; | ||
624 | f2 *= 9; | ||
625 | f3 *= 27; | ||
626 | f4 *= 81; | ||
627 | /* now want f0 + f1<<11 + f2<<22 + f3<<33 + f4<<44 */ | ||
628 | f0 += f1 << 11; | ||
629 | *c++ = f0; f0 >>= 8; | ||
630 | *c++ = f0; f0 >>= 8; | ||
631 | f0 += f2 << 6; | ||
632 | *c++ = f0; f0 >>= 8; | ||
633 | *c++ = f0; f0 >>= 8; | ||
634 | f0 += f3 << 1; | ||
635 | *c++ = f0; f0 >>= 8; | ||
636 | f0 += f4 << 4; | ||
637 | *c++ = f0; f0 >>= 8; | ||
638 | *c++ = f0; f0 >>= 8; | ||
639 | *c++ = f0; | ||
640 | } | ||
641 | /* XXX: using p mod 5 = 1 */ | ||
642 | f0 = *f++ + qshift; | ||
643 | *c++ = f0; f0 >>= 8; | ||
644 | *c++ = f0; | ||
645 | } | ||
646 | |||
647 | static void rq_decode(modq *f,const unsigned char *c) | ||
648 | { | ||
649 | crypto_uint32 c0, c1, c2, c3, c4, c5, c6, c7; | ||
650 | crypto_uint32 f0, f1, f2, f3, f4; | ||
651 | int i; | ||
652 | |||
653 | for (i = 0;i < p/5;++i) { | ||
654 | c0 = *c++; | ||
655 | c1 = *c++; | ||
656 | c2 = *c++; | ||
657 | c3 = *c++; | ||
658 | c4 = *c++; | ||
659 | c5 = *c++; | ||
660 | c6 = *c++; | ||
661 | c7 = *c++; | ||
662 | |||
663 | /* f0 + f1*6144 + f2*6144^2 + f3*6144^3 + f4*6144^4 */ | ||
664 | /* = c0 + c1*256 + ... + c6*256^6 + c7*256^7 */ | ||
665 | /* with each f between 0 and 4590 */ | ||
666 | |||
667 | c6 += c7 << 8; | ||
668 | /* c6 <= 23241 = floor(4591*6144^4/2^48) */ | ||
669 | /* f4 = (16/81)c6 + (1/1296)(c5+[0,1]) - [0,0.75] */ | ||
670 | /* claim: 2^19 f4 < x < 2^19(f4+1) */ | ||
671 | /* where x = 103564 c6 + 405(c5+1) */ | ||
672 | /* proof: x - 2^19 f4 = (76/81)c6 + (37/81)c5 + 405 - (32768/81)[0,1] + 2^19[0,0.75] */ | ||
673 | /* at least 405 - 32768/81 > 0 */ | ||
674 | /* at most (76/81)23241 + (37/81)255 + 405 + 2^19 0.75 < 2^19 */ | ||
675 | f4 = (103564*c6 + 405*(c5+1)) >> 19; | ||
676 | |||
677 | c5 += c6 << 8; | ||
678 | c5 -= (f4 * 81) << 4; | ||
679 | c4 += c5 << 8; | ||
680 | |||
681 | /* f0 + f1*6144 + f2*6144^2 + f3*6144^3 */ | ||
682 | /* = c0 + c1*256 + c2*256^2 + c3*256^3 + c4*256^4 */ | ||
683 | /* c4 <= 247914 = floor(4591*6144^3/2^32) */ | ||
684 | /* f3 = (1/54)(c4+[0,1]) - [0,0.75] */ | ||
685 | /* claim: 2^19 f3 < x < 2^19(f3+1) */ | ||
686 | /* where x = 9709(c4+2) */ | ||
687 | /* proof: x - 2^19 f3 = 19418 - (1/27)c4 - (262144/27)[0,1] + 2^19[0,0.75] */ | ||
688 | /* at least 19418 - 247914/27 - 262144/27 > 0 */ | ||
689 | /* at most 19418 + 2^19 0.75 < 2^19 */ | ||
690 | f3 = (9709*(c4+2)) >> 19; | ||
691 | |||
692 | c4 -= (f3 * 27) << 1; | ||
693 | c3 += c4 << 8; | ||
694 | /* f0 + f1*6144 + f2*6144^2 */ | ||
695 | /* = c0 + c1*256 + c2*256^2 + c3*256^3 */ | ||
696 | /* c3 <= 10329 = floor(4591*6144^2/2^24) */ | ||
697 | /* f2 = (4/9)c3 + (1/576)c2 + (1/147456)c1 + (1/37748736)c0 - [0,0.75] */ | ||
698 | /* claim: 2^19 f2 < x < 2^19(f2+1) */ | ||
699 | /* where x = 233017 c3 + 910(c2+2) */ | ||
700 | /* proof: x - 2^19 f2 = 1820 + (1/9)c3 - (2/9)c2 - (32/9)c1 - (1/72)c0 + 2^19[0,0.75] */ | ||
701 | /* at least 1820 - (2/9)255 - (32/9)255 - (1/72)255 > 0 */ | ||
702 | /* at most 1820 + (1/9)10329 + 2^19 0.75 < 2^19 */ | ||
703 | f2 = (233017*c3 + 910*(c2+2)) >> 19; | ||
704 | |||
705 | c2 += c3 << 8; | ||
706 | c2 -= (f2 * 9) << 6; | ||
707 | c1 += c2 << 8; | ||
708 | /* f0 + f1*6144 */ | ||
709 | /* = c0 + c1*256 */ | ||
710 | /* c1 <= 110184 = floor(4591*6144/2^8) */ | ||
711 | /* f1 = (1/24)c1 + (1/6144)c0 - (1/6144)f0 */ | ||
712 | /* claim: 2^19 f1 < x < 2^19(f1+1) */ | ||
713 | /* where x = 21845(c1+2) + 85 c0 */ | ||
714 | /* proof: x - 2^19 f1 = 43690 - (1/3)c1 - (1/3)c0 + 2^19 [0,0.75] */ | ||
715 | /* at least 43690 - (1/3)110184 - (1/3)255 > 0 */ | ||
716 | /* at most 43690 + 2^19 0.75 < 2^19 */ | ||
717 | f1 = (21845*(c1+2) + 85*c0) >> 19; | ||
718 | |||
719 | c1 -= (f1 * 3) << 3; | ||
720 | c0 += c1 << 8; | ||
721 | f0 = c0; | ||
722 | |||
723 | *f++ = modq_freeze(f0 + q - qshift); | ||
724 | *f++ = modq_freeze(f1 + q - qshift); | ||
725 | *f++ = modq_freeze(f2 + q - qshift); | ||
726 | *f++ = modq_freeze(f3 + q - qshift); | ||
727 | *f++ = modq_freeze(f4 + q - qshift); | ||
728 | } | ||
729 | |||
730 | c0 = *c++; | ||
731 | c1 = *c++; | ||
732 | c0 += c1 << 8; | ||
733 | *f++ = modq_freeze(c0 + q - qshift); | ||
734 | } | ||
735 | |||
736 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c */ | ||
737 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
738 | |||
739 | |||
740 | static void rq_mult(modq *h,const modq *f,const small *g) | ||
741 | { | ||
742 | modq fg[p + p - 1]; | ||
743 | modq result; | ||
744 | int i, j; | ||
745 | |||
746 | for (i = 0;i < p;++i) { | ||
747 | result = 0; | ||
748 | for (j = 0;j <= i;++j) | ||
749 | result = modq_plusproduct(result,f[j],g[i - j]); | ||
750 | fg[i] = result; | ||
751 | } | ||
752 | for (i = p;i < p + p - 1;++i) { | ||
753 | result = 0; | ||
754 | for (j = i - p + 1;j < p;++j) | ||
755 | result = modq_plusproduct(result,f[j],g[i - j]); | ||
756 | fg[i] = result; | ||
757 | } | ||
758 | |||
759 | for (i = p + p - 2;i >= p;--i) { | ||
760 | fg[i - p] = modq_sum(fg[i - p],fg[i]); | ||
761 | fg[i - p + 1] = modq_sum(fg[i - p + 1],fg[i]); | ||
762 | } | ||
763 | |||
764 | for (i = 0;i < p;++i) | ||
765 | h[i] = fg[i]; | ||
766 | } | ||
767 | |||
768 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c */ | ||
769 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
770 | |||
771 | |||
772 | /* caller must ensure that x-y does not overflow */ | ||
773 | static int smaller_mask_rq_recip3(int x,int y) | ||
774 | { | ||
775 | return (x - y) >> 31; | ||
776 | } | ||
777 | |||
778 | static void vectormodq_product(modq *z,int len,const modq *x,const modq c) | ||
779 | { | ||
780 | int i; | ||
781 | for (i = 0;i < len;++i) z[i] = modq_product(x[i],c); | ||
782 | } | ||
783 | |||
784 | static void vectormodq_minusproduct(modq *z,int len,const modq *x,const modq *y,const modq c) | ||
785 | { | ||
786 | int i; | ||
787 | for (i = 0;i < len;++i) z[i] = modq_minusproduct(x[i],y[i],c); | ||
788 | } | ||
789 | |||
790 | static void vectormodq_shift(modq *z,int len) | ||
791 | { | ||
792 | int i; | ||
793 | for (i = len - 1;i > 0;--i) z[i] = z[i - 1]; | ||
794 | z[0] = 0; | ||
795 | } | ||
796 | |||
797 | /* | ||
798 | r = (3s)^(-1) mod m, returning 0, if s is invertible mod m | ||
799 | or returning -1 if s is not invertible mod m | ||
800 | r,s are polys of degree <p | ||
801 | m is x^p-x-1 | ||
802 | */ | ||
803 | int rq_recip3(modq *r,const small *s) | ||
804 | { | ||
805 | const int loops = 2*p + 1; | ||
806 | int loop; | ||
807 | modq f[p + 1]; | ||
808 | modq g[p + 1]; | ||
809 | modq u[loops + 1]; | ||
810 | modq v[loops + 1]; | ||
811 | modq c; | ||
812 | int i; | ||
813 | int d = p; | ||
814 | int e = p; | ||
815 | int swapmask; | ||
816 | |||
817 | for (i = 2;i < p;++i) f[i] = 0; | ||
818 | f[0] = -1; | ||
819 | f[1] = -1; | ||
820 | f[p] = 1; | ||
821 | /* generalization: can initialize f to any polynomial m */ | ||
822 | /* requirements: m has degree exactly p, nonzero constant coefficient */ | ||
823 | |||
824 | for (i = 0;i < p;++i) g[i] = 3 * s[i]; | ||
825 | g[p] = 0; | ||
826 | |||
827 | for (i = 0;i <= loops;++i) u[i] = 0; | ||
828 | |||
829 | v[0] = 1; | ||
830 | for (i = 1;i <= loops;++i) v[i] = 0; | ||
831 | |||
832 | loop = 0; | ||
833 | for (;;) { | ||
834 | /* e == -1 or d + e + loop <= 2*p */ | ||
835 | |||
836 | /* f has degree p: i.e., f[p]!=0 */ | ||
837 | /* f[i]==0 for i < p-d */ | ||
838 | |||
839 | /* g has degree <=p (so it fits in p+1 coefficients) */ | ||
840 | /* g[i]==0 for i < p-e */ | ||
841 | |||
842 | /* u has degree <=loop (so it fits in loop+1 coefficients) */ | ||
843 | /* u[i]==0 for i < p-d */ | ||
844 | /* if invertible: u[i]==0 for i < loop-p (so can look at just p+1 coefficients) */ | ||
845 | |||
846 | /* v has degree <=loop (so it fits in loop+1 coefficients) */ | ||
847 | /* v[i]==0 for i < p-e */ | ||
848 | /* v[i]==0 for i < loop-p (so can look at just p+1 coefficients) */ | ||
849 | |||
850 | if (loop >= loops) break; | ||
851 | |||
852 | c = modq_quotient(g[p],f[p]); | ||
853 | |||
854 | vectormodq_minusproduct(g,p + 1,g,f,c); | ||
855 | vectormodq_shift(g,p + 1); | ||
856 | |||
857 | #ifdef SIMPLER | ||
858 | vectormodq_minusproduct(v,loops + 1,v,u,c); | ||
859 | vectormodq_shift(v,loops + 1); | ||
860 | #else | ||
861 | if (loop < p) { | ||
862 | vectormodq_minusproduct(v,loop + 1,v,u,c); | ||
863 | vectormodq_shift(v,loop + 2); | ||
864 | } else { | ||
865 | vectormodq_minusproduct(v + loop - p,p + 1,v + loop - p,u + loop - p,c); | ||
866 | vectormodq_shift(v + loop - p,p + 2); | ||
867 | } | ||
868 | #endif | ||
869 | |||
870 | e -= 1; | ||
871 | |||
872 | ++loop; | ||
873 | |||
874 | swapmask = smaller_mask_rq_recip3(e,d) & modq_nonzero_mask(g[p]); | ||
875 | swap(&e,&d,sizeof e,swapmask); | ||
876 | swap(f,g,(p + 1) * sizeof(modq),swapmask); | ||
877 | |||
878 | #ifdef SIMPLER | ||
879 | swap(u,v,(loops + 1) * sizeof(modq),swapmask); | ||
880 | #else | ||
881 | if (loop < p) { | ||
882 | swap(u,v,(loop + 1) * sizeof(modq),swapmask); | ||
883 | } else { | ||
884 | swap(u + loop - p,v + loop - p,(p + 1) * sizeof(modq),swapmask); | ||
885 | } | ||
886 | #endif | ||
887 | } | ||
888 | |||
889 | c = modq_reciprocal(f[p]); | ||
890 | vectormodq_product(r,p,u + p,c); | ||
891 | return smaller_mask_rq_recip3(0,d); | ||
892 | } | ||
893 | |||
894 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c */ | ||
895 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
896 | |||
897 | |||
898 | static void rq_round3(modq *h,const modq *f) | ||
899 | { | ||
900 | int i; | ||
901 | |||
902 | for (i = 0;i < p;++i) | ||
903 | h[i] = ((21846 * (f[i] + 2295) + 32768) >> 16) * 3 - 2295; | ||
904 | } | ||
905 | |||
906 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c */ | ||
907 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
908 | |||
909 | |||
910 | static void rq_encoderounded(unsigned char *c,const modq *f) | ||
911 | { | ||
912 | crypto_int32 f0, f1, f2; | ||
913 | int i; | ||
914 | |||
915 | for (i = 0;i < p/3;++i) { | ||
916 | f0 = *f++ + qshift; | ||
917 | f1 = *f++ + qshift; | ||
918 | f2 = *f++ + qshift; | ||
919 | f0 = (21846 * f0) >> 16; | ||
920 | f1 = (21846 * f1) >> 16; | ||
921 | f2 = (21846 * f2) >> 16; | ||
922 | /* now want f0 + f1*1536 + f2*1536^2 as a 32-bit integer */ | ||
923 | f2 *= 3; | ||
924 | f1 += f2 << 9; | ||
925 | f1 *= 3; | ||
926 | f0 += f1 << 9; | ||
927 | *c++ = f0; f0 >>= 8; | ||
928 | *c++ = f0; f0 >>= 8; | ||
929 | *c++ = f0; f0 >>= 8; | ||
930 | *c++ = f0; | ||
931 | } | ||
932 | /* XXX: using p mod 3 = 2 */ | ||
933 | f0 = *f++ + qshift; | ||
934 | f1 = *f++ + qshift; | ||
935 | f0 = (21846 * f0) >> 16; | ||
936 | f1 = (21846 * f1) >> 16; | ||
937 | f1 *= 3; | ||
938 | f0 += f1 << 9; | ||
939 | *c++ = f0; f0 >>= 8; | ||
940 | *c++ = f0; f0 >>= 8; | ||
941 | *c++ = f0; | ||
942 | } | ||
943 | |||
944 | static void rq_decoderounded(modq *f,const unsigned char *c) | ||
945 | { | ||
946 | crypto_uint32 c0, c1, c2, c3; | ||
947 | crypto_uint32 f0, f1, f2; | ||
948 | int i; | ||
949 | |||
950 | for (i = 0;i < p/3;++i) { | ||
951 | c0 = *c++; | ||
952 | c1 = *c++; | ||
953 | c2 = *c++; | ||
954 | c3 = *c++; | ||
955 | |||
956 | /* f0 + f1*1536 + f2*1536^2 */ | ||
957 | /* = c0 + c1*256 + c2*256^2 + c3*256^3 */ | ||
958 | /* with each f between 0 and 1530 */ | ||
959 | |||
960 | /* f2 = (64/9)c3 + (1/36)c2 + (1/9216)c1 + (1/2359296)c0 - [0,0.99675] */ | ||
961 | /* claim: 2^21 f2 < x < 2^21(f2+1) */ | ||
962 | /* where x = 14913081*c3 + 58254*c2 + 228*(c1+2) */ | ||
963 | /* proof: x - 2^21 f2 = 456 - (8/9)c0 + (4/9)c1 - (2/9)c2 + (1/9)c3 + 2^21 [0,0.99675] */ | ||
964 | /* at least 456 - (8/9)255 - (2/9)255 > 0 */ | ||
965 | /* at most 456 + (4/9)255 + (1/9)255 + 2^21 0.99675 < 2^21 */ | ||
966 | f2 = (14913081*c3 + 58254*c2 + 228*(c1+2)) >> 21; | ||
967 | |||
968 | c2 += c3 << 8; | ||
969 | c2 -= (f2 * 9) << 2; | ||
970 | /* f0 + f1*1536 */ | ||
971 | /* = c0 + c1*256 + c2*256^2 */ | ||
972 | /* c2 <= 35 = floor((1530+1530*1536)/256^2) */ | ||
973 | /* f1 = (128/3)c2 + (1/6)c1 + (1/1536)c0 - (1/1536)f0 */ | ||
974 | /* claim: 2^21 f1 < x < 2^21(f1+1) */ | ||
975 | /* where x = 89478485*c2 + 349525*c1 + 1365*(c0+1) */ | ||
976 | /* proof: x - 2^21 f1 = 1365 - (1/3)c2 - (1/3)c1 - (1/3)c0 + (4096/3)f0 */ | ||
977 | /* at least 1365 - (1/3)35 - (1/3)255 - (1/3)255 > 0 */ | ||
978 | /* at most 1365 + (4096/3)1530 < 2^21 */ | ||
979 | f1 = (89478485*c2 + 349525*c1 + 1365*(c0+1)) >> 21; | ||
980 | |||
981 | c1 += c2 << 8; | ||
982 | c1 -= (f1 * 3) << 1; | ||
983 | |||
984 | c0 += c1 << 8; | ||
985 | f0 = c0; | ||
986 | |||
987 | *f++ = modq_freeze(f0 * 3 + q - qshift); | ||
988 | *f++ = modq_freeze(f1 * 3 + q - qshift); | ||
989 | *f++ = modq_freeze(f2 * 3 + q - qshift); | ||
990 | } | ||
991 | |||
992 | c0 = *c++; | ||
993 | c1 = *c++; | ||
994 | c2 = *c++; | ||
995 | |||
996 | f1 = (89478485*c2 + 349525*c1 + 1365*(c0+1)) >> 21; | ||
997 | |||
998 | c1 += c2 << 8; | ||
999 | c1 -= (f1 * 3) << 1; | ||
1000 | |||
1001 | c0 += c1 << 8; | ||
1002 | f0 = c0; | ||
1003 | |||
1004 | *f++ = modq_freeze(f0 * 3 + q - qshift); | ||
1005 | *f++ = modq_freeze(f1 * 3 + q - qshift); | ||
1006 | } | ||
1007 | |||
1008 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/small.c */ | ||
1009 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
1010 | |||
1011 | |||
1012 | /* XXX: these functions rely on p mod 4 = 1 */ | ||
1013 | |||
1014 | /* all coefficients in -1, 0, 1 */ | ||
1015 | static void small_encode(unsigned char *c,const small *f) | ||
1016 | { | ||
1017 | small c0; | ||
1018 | int i; | ||
1019 | |||
1020 | for (i = 0;i < p/4;++i) { | ||
1021 | c0 = *f++ + 1; | ||
1022 | c0 += (*f++ + 1) << 2; | ||
1023 | c0 += (*f++ + 1) << 4; | ||
1024 | c0 += (*f++ + 1) << 6; | ||
1025 | *c++ = c0; | ||
1026 | } | ||
1027 | c0 = *f++ + 1; | ||
1028 | *c++ = c0; | ||
1029 | } | ||
1030 | |||
1031 | static void small_decode(small *f,const unsigned char *c) | ||
1032 | { | ||
1033 | unsigned char c0; | ||
1034 | int i; | ||
1035 | |||
1036 | for (i = 0;i < p/4;++i) { | ||
1037 | c0 = *c++; | ||
1038 | *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2; | ||
1039 | *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2; | ||
1040 | *f++ = ((small) (c0 & 3)) - 1; c0 >>= 2; | ||
1041 | *f++ = ((small) (c0 & 3)) - 1; | ||
1042 | } | ||
1043 | c0 = *c++; | ||
1044 | *f++ = ((small) (c0 & 3)) - 1; | ||
1045 | } | ||
1046 | |||
1047 | /* from supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c */ | ||
1048 | /* See https://ntruprime.cr.yp.to/software.html for detailed documentation. */ | ||
1049 | |||
1050 | |||
1051 | static void swap(void *x,void *y,int bytes,int mask) | ||
1052 | { | ||
1053 | int i; | ||
1054 | char xi, yi, c, t; | ||
1055 | |||
1056 | c = mask; | ||
1057 | |||
1058 | for (i = 0;i < bytes;++i) { | ||
1059 | xi = i[(char *) x]; | ||
1060 | yi = i[(char *) y]; | ||
1061 | t = c & (xi ^ yi); | ||
1062 | xi ^= t; | ||
1063 | yi ^= t; | ||
1064 | i[(char *) x] = xi; | ||
1065 | i[(char *) y] = yi; | ||
1066 | } | ||
1067 | } | ||
1068 | |||
diff --git a/sntrup4591761.sh b/sntrup4591761.sh new file mode 100644 index 000000000..5540ca4d9 --- /dev/null +++ b/sntrup4591761.sh | |||
@@ -0,0 +1,47 @@ | |||
1 | #!/bin/sh | ||
2 | FILES=" | ||
3 | supercop-20181216/crypto_sort/int32/portable3/int32_minmax.inc | ||
4 | supercop-20181216/crypto_sort/int32/portable3/sort.c | ||
5 | supercop-20181216/crypto_kem/sntrup4591761/ref/small.h | ||
6 | supercop-20181216/crypto_kem/sntrup4591761/ref/mod3.h | ||
7 | supercop-20181216/crypto_kem/sntrup4591761/ref/modq.h | ||
8 | supercop-20181216/crypto_kem/sntrup4591761/ref/params.h | ||
9 | supercop-20181216/crypto_kem/sntrup4591761/ref/r3.h | ||
10 | supercop-20181216/crypto_kem/sntrup4591761/ref/rq.h | ||
11 | supercop-20181216/crypto_kem/sntrup4591761/ref/swap.h | ||
12 | supercop-20181216/crypto_kem/sntrup4591761/ref/dec.c | ||
13 | supercop-20181216/crypto_kem/sntrup4591761/ref/enc.c | ||
14 | supercop-20181216/crypto_kem/sntrup4591761/ref/keypair.c | ||
15 | supercop-20181216/crypto_kem/sntrup4591761/ref/r3_mult.c | ||
16 | supercop-20181216/crypto_kem/sntrup4591761/ref/r3_recip.c | ||
17 | supercop-20181216/crypto_kem/sntrup4591761/ref/randomsmall.c | ||
18 | supercop-20181216/crypto_kem/sntrup4591761/ref/randomweightw.c | ||
19 | supercop-20181216/crypto_kem/sntrup4591761/ref/rq.c | ||
20 | supercop-20181216/crypto_kem/sntrup4591761/ref/rq_mult.c | ||
21 | supercop-20181216/crypto_kem/sntrup4591761/ref/rq_recip3.c | ||
22 | supercop-20181216/crypto_kem/sntrup4591761/ref/rq_round3.c | ||
23 | supercop-20181216/crypto_kem/sntrup4591761/ref/rq_rounded.c | ||
24 | supercop-20181216/crypto_kem/sntrup4591761/ref/small.c | ||
25 | supercop-20181216/crypto_kem/sntrup4591761/ref/swap.c | ||
26 | " | ||
27 | ### | ||
28 | |||
29 | set -e | ||
30 | DIR=/data/git/mfriedl | ||
31 | cd $DIR | ||
32 | echo '#include <string.h>' | ||
33 | echo '#include "crypto_api.h"' | ||
34 | echo | ||
35 | for i in $FILES; do | ||
36 | echo "/* from $i */" | ||
37 | b=$(basename $i .c) | ||
38 | grep \ | ||
39 | -v '#include' $i | \ | ||
40 | grep -v "extern crypto_int32 small_random32" | | ||
41 | sed -e "s/crypto_kem_/crypto_kem_sntrup4591761_/g" \ | ||
42 | -e "s/smaller_mask/smaller_mask_${b}/g" \ | ||
43 | -e "s/void crypto_sort/void crypto_sort_int32/" \ | ||
44 | -e "s/^extern void /static void /" \ | ||
45 | -e "s/^void /static void /" | ||
46 | echo | ||
47 | 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 @@ | |||
1 | /* $OpenBSD: ssh-keyscan.c,v 1.120 2018/06/06 18:29:18 markus Exp $ */ | 1 | /* $OpenBSD: ssh-keyscan.c,v 1.121 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright 1995, 1996 by David Mazieres <dm@lcs.mit.edu>. | 3 | * Copyright 1995, 1996 by David Mazieres <dm@lcs.mit.edu>. |
4 | * | 4 | * |
@@ -272,6 +272,7 @@ keygrab_ssh2(con *c) | |||
272 | # endif | 272 | # endif |
273 | #endif | 273 | #endif |
274 | c->c_ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client; | 274 | c->c_ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client; |
275 | c->c_ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_client; | ||
275 | ssh_set_verify_host_key_callback(c->c_ssh, key_print_wrapper); | 276 | ssh_set_verify_host_key_callback(c->c_ssh, key_print_wrapper); |
276 | /* | 277 | /* |
277 | * do the key-exchange until an error occurs or until | 278 | * do the key-exchange until an error occurs or until |
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: ssh_api.c,v 1.10 2019/01/19 21:43:56 djm Exp $ */ | 1 | /* $OpenBSD: ssh_api.c,v 1.11 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2012 Markus Friedl. All rights reserved. | 3 | * Copyright (c) 2012 Markus Friedl. All rights reserved. |
4 | * | 4 | * |
@@ -111,6 +111,7 @@ ssh_init(struct ssh **sshp, int is_server, struct kex_params *kex_params) | |||
111 | # endif | 111 | # endif |
112 | #endif /* WITH_OPENSSL */ | 112 | #endif /* WITH_OPENSSL */ |
113 | ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_server; | 113 | ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_server; |
114 | ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_server; | ||
114 | ssh->kex->load_host_public_key=&_ssh_host_public_key; | 115 | ssh->kex->load_host_public_key=&_ssh_host_public_key; |
115 | ssh->kex->load_host_private_key=&_ssh_host_private_key; | 116 | ssh->kex->load_host_private_key=&_ssh_host_private_key; |
116 | ssh->kex->sign=&_ssh_host_key_sign; | 117 | ssh->kex->sign=&_ssh_host_key_sign; |
@@ -128,6 +129,7 @@ ssh_init(struct ssh **sshp, int is_server, struct kex_params *kex_params) | |||
128 | # endif | 129 | # endif |
129 | #endif /* WITH_OPENSSL */ | 130 | #endif /* WITH_OPENSSL */ |
130 | ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client; | 131 | ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client; |
132 | ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_client; | ||
131 | ssh->kex->verify_host_key =&_ssh_verify_host_key; | 133 | ssh->kex->verify_host_key =&_ssh_verify_host_key; |
132 | } | 134 | } |
133 | *sshp = ssh; | 135 | *sshp = ssh; |
diff --git a/sshconnect2.c b/sshconnect2.c index 65d8be667..05657fd73 100644 --- a/sshconnect2.c +++ b/sshconnect2.c | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: sshconnect2.c,v 1.296 2019/01/21 01:05:00 djm Exp $ */ | 1 | /* $OpenBSD: sshconnect2.c,v 1.297 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2000 Markus Friedl. All rights reserved. | 3 | * Copyright (c) 2000 Markus Friedl. All rights reserved. |
4 | * Copyright (c) 2008 Damien Miller. All rights reserved. | 4 | * 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) | |||
213 | # endif | 213 | # endif |
214 | #endif | 214 | #endif |
215 | ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client; | 215 | ssh->kex->kex[KEX_C25519_SHA256] = kexc25519_client; |
216 | ssh->kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_client; | ||
216 | ssh->kex->verify_host_key=&verify_host_key_callback; | 217 | ssh->kex->verify_host_key=&verify_host_key_callback; |
217 | 218 | ||
218 | ssh_dispatch_run_fatal(ssh, DISPATCH_BLOCK, &ssh->kex->done); | 219 | ssh_dispatch_run_fatal(ssh, DISPATCH_BLOCK, &ssh->kex->done); |
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: sshd.c,v 1.527 2019/01/19 21:43:56 djm Exp $ */ | 1 | /* $OpenBSD: sshd.c,v 1.528 2019/01/21 10:20:12 djm Exp $ */ |
2 | /* | 2 | /* |
3 | * Author: Tatu Ylonen <ylo@cs.hut.fi> | 3 | * Author: Tatu Ylonen <ylo@cs.hut.fi> |
4 | * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland | 4 | * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland |
@@ -2219,6 +2219,7 @@ do_ssh2_kex(struct ssh *ssh) | |||
2219 | # endif | 2219 | # endif |
2220 | #endif | 2220 | #endif |
2221 | kex->kex[KEX_C25519_SHA256] = kexc25519_server; | 2221 | kex->kex[KEX_C25519_SHA256] = kexc25519_server; |
2222 | kex->kex[KEX_KEM_SNTRUP4591761X25519_SHA512] = kex_kem_server; | ||
2222 | kex->load_host_public_key=&get_hostkey_public_by_type; | 2223 | kex->load_host_public_key=&get_hostkey_public_by_type; |
2223 | kex->load_host_private_key=&get_hostkey_private_by_type; | 2224 | kex->load_host_private_key=&get_hostkey_private_by_type; |
2224 | kex->host_key_index=&get_hostkey_index; | 2225 | kex->host_key_index=&get_hostkey_index; |