openssh unix dev - Nov 2013 - [PATCH] curve25519-sha256@libssh.org key exchange proposal

On Tue, 24 Sep 2013, Aris Adamantiadis wrote:
> Dear OpenSSH developers,
> 
> I've worked this week on an alternative key exchange mechanism, in
> reaction to the whole NSA leaks and claims over cryptographic backdoors
> and/or cracking advances. The key exchange is in my opinion the most
> critical defense against passive eavesdropping attacks.
> I believe Curve25519 from DJB can give users a secure alternative to
> classical Diffie-Hellman (with fixed groups or group exchanges) and
> NIST-approved elliptic curves.
...

I just had a quick look at the patch. Overall it's good; some preliminary
comments below.

diff --git a/kexc25519.c b/kexc25519.c
new file mode 100644
index 0000000..8260fad
--- /dev/null
+++ b/kexc25519.c
...
+#include <nacl/crypto_scalarmult_curve25519.h>
+#define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES

For OpenSSH, I think we could just include the portable C version from
https://code.google.com/p/curve25519-donna/ rather than depending on
the entirety of nacl. nacl includes a heap of stuff that we don't need
and makes some unusual design choices like choosing between native
implementations by measuring the host it is being compiled on.

The downside to the -donna implementation is that it doesn't promise
constant time execution. AFAIK this isn't a killer for the SSH case as
an attacker doesn't get to measure the processing time for any set of DH
public values more than once. It would be worse if we reused DH values,
but we don't. (-donna also has the disadvantage of being slower, but were
quibbling over single-digit milliseconds here so IMO it doesn't matter at
all.)

+void
+kex_c25519_hash(
+    const EVP_MD *evp_md,
+    char *client_version_string,
+    char *server_version_string,
+    char *ckexinit, int ckexinitlen,
+    char *skexinit, int skexinitlen,
+    u_char *serverhostkeyblob, int sbloblen,
+    const unsigned char client_dh_pub[CURVE25519_PUBKEY_SIZE],
+    const unsigned char server_dh_pub[CURVE25519_PUBKEY_SIZE],
+    const BIGNUM *shared_secret,
...
+	buffer_put_bignum2(&b, shared_secret);

It would be simpler to pass the shared_secret as a const u_char* and
length here - saving a round-trip to BIGNUM and back.

diff --git a/kexc25519c.c b/kexc25519c.c
new file mode 100644
index 0000000..b2000f0
--- /dev/null
+++ b/kexc25519c.c
...
+void
+kexc25519_client(Kex *kex)
+{
...
+	/* generate private key */
+	for (i = 0; i < sizeof(client_key); i++) {
+		if (i % 4 == 0)
+			rnd = arc4random();
+		client_key[i] = rnd;
+		rnd >>= 8;
+        }

easier to use arc4random_buf() here. If we use the -donna implementation
then we need to do the 

client_key[0] &= 248;
client_key[31] &= 127;
client_key[31] |= 64;

ourselves. It might be better to have put a kex_c25519_genkey() in
kexc25519.c that does it all and use it in both the client and server.

-d

Le 30/10/13 07:27, Damien Miller a ?crit :
> For OpenSSH, I think we could just include the portable C version from
> https://code.google.com/p/curve25519-donna/ rather than depending on
> the entirety of nacl. nacl includes a heap of stuff that we don't need
> and makes some unusual design choices like choosing between native
> implementations by measuring the host it is being compiled on.
> 
> The downside to the -donna implementation is that it doesn't promise
> constant time execution. AFAIK this isn't a killer for the SSH case as
> an attacker doesn't get to measure the processing time for any set of
DH
> public values more than once. It would be worse if we reused DH values,
> but we don't. (-donna also has the disadvantage of being slower, but
were
> quibbling over single-digit milliseconds here so IMO it doesn't matter
at
> all.)
Hi Damien,

I did some research. It seems the two portable alternatives either are:
-curve25519-donna (non constant time, BSD-with-don't-use-google-name-clause)
--> https://github.com/agl/curve25519-donna/blob/master/curve25519-donna.c
-Nacl's C implementation (Public domain, Matthew Dempsky, 2008, see on
github)
-->
https://github.com/cjdelisle/cnacl/blob/master/crypto_scalarmult/curve25519/ref/smult.c

Unfortunately the lack of metrics and claims in the latter code makes it
harder to decide which one to use. But NaCl's code looks simpler (which
doesn't mean faster or constant time).
Up to you guys to decide :)
> +    const BIGNUM *shared_secret,
> ...
> +	buffer_put_bignum2(&b, shared_secret);
> 
> It would be simpler to pass the shared_secret as a const u_char* and
> length here - saving a round-trip to BIGNUM and back.
I must say I just copied ecdh implementation that did this. I can change
it, I only have to verify if there's no trick in the encoding of bignums
(prepending a 0 if first bit is set pops to my head).
I wouldn't change the specs to use a standard string because that would
differ from all other existing key exchanges.
> +	for (i = 0; i < sizeof(client_key); i++) {
> +		if (i % 4 == 0)
> +			rnd = arc4random();
> +		client_key[i] = rnd;
> +		rnd >>= 8;
> +        }
> 
> easier to use arc4random_buf() here.
ack, but I think I copied that loop from somewhere else in openssh and
deduced that was the way to go.
> If we use the -donna implementation
> then we need to do the 
> 
> client_key[0] &= 248;
> client_key[31] &= 127;
> client_key[31] |= 64;
> 
> ourselves. It might be better to have put a kex_c25519_genkey() in
> kexc25519.c that does it all and use it in both the client and server.
> 
The implementation I pointed to already does this, at least in the git
version.

Regards,

Aris

Here are three versions (patch against openbsd cvs)

1) repace nacl w/libsodium, so i could test
2) curve25519-donna
3) Matthew's public domain reference implementation.

i'd vote for #3



-------------- next part --------------




Am 30.10.2013 um 07:27 schrieb Damien Miller <djm at mindrot.org>:
> On Tue, 24 Sep 2013, Aris Adamantiadis wrote:
> 
>> Dear OpenSSH developers,
>> 
>> I've worked this week on an alternative key exchange mechanism, in
>> reaction to the whole NSA leaks and claims over cryptographic backdoors
>> and/or cracking advances. The key exchange is in my opinion the most
>> critical defense against passive eavesdropping attacks.
>> I believe Curve25519 from DJB can give users a secure alternative to
>> classical Diffie-Hellman (with fixed groups or group exchanges) and
>> NIST-approved elliptic curves.
> 
> ...
> 
> I just had a quick look at the patch. Overall it's good; some
preliminary
> comments below.
> 
> diff --git a/kexc25519.c b/kexc25519.c
> new file mode 100644
> index 0000000..8260fad
> --- /dev/null
> +++ b/kexc25519.c
> ...
> +#include <nacl/crypto_scalarmult_curve25519.h>
> +#define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES
> 
> For OpenSSH, I think we could just include the portable C version from
> https://code.google.com/p/curve25519-donna/ rather than depending on
> the entirety of nacl. nacl includes a heap of stuff that we don't need
> and makes some unusual design choices like choosing between native
> implementations by measuring the host it is being compiled on.
> 
> The downside to the -donna implementation is that it doesn't promise
> constant time execution. AFAIK this isn't a killer for the SSH case as
> an attacker doesn't get to measure the processing time for any set of
DH
> public values more than once. It would be worse if we reused DH values,
> but we don't. (-donna also has the disadvantage of being slower, but
were
> quibbling over single-digit milliseconds here so IMO it doesn't matter
at
> all.)
> 
> +void
> +kex_c25519_hash(
> +    const EVP_MD *evp_md,
> +    char *client_version_string,
> +    char *server_version_string,
> +    char *ckexinit, int ckexinitlen,
> +    char *skexinit, int skexinitlen,
> +    u_char *serverhostkeyblob, int sbloblen,
> +    const unsigned char client_dh_pub[CURVE25519_PUBKEY_SIZE],
> +    const unsigned char server_dh_pub[CURVE25519_PUBKEY_SIZE],
> +    const BIGNUM *shared_secret,
> ...
> +	buffer_put_bignum2(&b, shared_secret);
> 
> It would be simpler to pass the shared_secret as a const u_char* and
> length here - saving a round-trip to BIGNUM and back.
> 
> diff --git a/kexc25519c.c b/kexc25519c.c
> new file mode 100644
> index 0000000..b2000f0
> --- /dev/null
> +++ b/kexc25519c.c
> ...
> +void
> +kexc25519_client(Kex *kex)
> +{
> ...
> +	/* generate private key */
> +	for (i = 0; i < sizeof(client_key); i++) {
> +		if (i % 4 == 0)
> +			rnd = arc4random();
> +		client_key[i] = rnd;
> +		rnd >>= 8;
> +        }
> 
> easier to use arc4random_buf() here. If we use the -donna implementation
> then we need to do the 
> 
> client_key[0] &= 248;
> client_key[31] &= 127;
> client_key[31] |= 64;
> 
> ourselves. It might be better to have put a kex_c25519_genkey() in
> kexc25519.c that does it all and use it in both the client and server.
> 
> -d
>