[PATCH] dh: fix curve25519-sha256@xxxxxxxxxx 'K' padding

[Jon Simons <jon@xxxxxxxxxxxxx>]

Hi,

Attached is a patch based off of 79d51099ac3273aa73c3bd3bd047b3fa996fef18 on
the master branch which should resolve https://red.libssh.org/issues/159.

Before the patch, I'm able to reproduce failure when testing with OpenSSH
clients at or beyond 6.5p1, using the 'pkd_hello' test like so:

    ./pkd_hello -t torture_pkd_openssh_rsa_curve25519_sha256 -i 1000

After the patch I'm unable to reproduce the failure.


Thanks,
-Jon

From 689fa761b4f0968dff511af638c411ef6def14c6 Mon Sep 17 00:00:00 2001
From: Jon Simons <jon@xxxxxxxxxxxxx>
Date: Mon, 14 Apr 2014 20:04:00 -0700
Subject: [PATCH] dh: fix curve25519-sha256@xxxxxxxxxx 'K' padding

Ensure that bignum strings used for the shared-secret 'K' value in
key exchange with curve25519-sha256@xxxxxxxxxx are indeed 32 bytes.

Before this change, OpenSSH clients starting at version 6.5p1 will
sometimes, but not always, error out in the early key exchange
phase along the lines of:

    debug2: kex_parse_kexinit: curve25519-sha256@xxxxxxxxxx,ecdh-sha2-nistp256,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
    ...
    debug1: sending SSH2_MSG_KEX_ECDH_INIT
    debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
    ...
    Warning: Permanently added '[localhost]:1234' (RSA) to the list of known hosts.
    hash mismatch
    debug1: ssh_rsa_verify: signature incorrect
    key_verify failed for server_host_key

After some digging it looks like there are some cases where the
ssh_string computed by libssh for its 'K' value does not have a
length of 32 bytes.  It is in these cases that OpenSSH clients
will fail signature verification during initial key exchange.

To fix, use a new helper for generating 'K' strings which inputs
both a bignum and minimal size.  For the curve25519 case, the 32
byte value is provided for the size; other key exchange algorithms
continue to use plain 'make_bignum_string' as before.

With this change I am no longer able to reproduce failure when
testing against OpenSSH clients.

BUG: https://red.libssh.org/issues/159

Signed-off-by: Jon Simons <jon@xxxxxxxxxxxxx>
---
 include/libssh/curve25519.h |   6 ++-
 src/dh.c                    | 104 ++++++++++++++++++++++++++++++++------------
 2 files changed, 79 insertions(+), 31 deletions(-)

diff --git a/include/libssh/curve25519.h b/include/libssh/curve25519.h
index 0406b9e..1f8b915 100644
--- a/include/libssh/curve25519.h
+++ b/include/libssh/curve25519.h
@@ -27,14 +27,16 @@
 #ifdef WITH_NACL
 
 #include <nacl/crypto_scalarmult_curve25519.h>
+#define CURVE25519_SIZE 32
 #define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES
 #define CURVE25519_PRIVKEY_SIZE crypto_scalarmult_curve25519_SCALARBYTES
 #define crypto_scalarmult_base crypto_scalarmult_curve25519_base
 #define crypto_scalarmult crypto_scalarmult_curve25519
 #else
 
-#define CURVE25519_PUBKEY_SIZE 32
-#define CURVE25519_PRIVKEY_SIZE 32
+#define CURVE25519_SIZE 32
+#define CURVE25519_PUBKEY_SIZE CURVE25519_SIZE
+#define CURVE25519_PRIVKEY_SIZE CURVE25519_SIZE
 int crypto_scalarmult_base(unsigned char *q, const unsigned char *n);
 int crypto_scalarmult(unsigned char *q, const unsigned char *n, const unsigned char *p);
 #endif /* WITH_NACL */
diff --git a/src/dh.c b/src/dh.c
index 3255ac7..be04db5 100644
--- a/src/dh.c
+++ b/src/dh.c
@@ -351,42 +351,59 @@ int dh_generate_f(ssh_session session) {
   return 0;
 }
 
-ssh_string make_bignum_string(bignum num) {
-  ssh_string ptr = NULL;
-  int pad = 0;
-  unsigned int len = bignum_num_bytes(num);
-  unsigned int bits = bignum_num_bits(num);
-
-  if (len == 0) {
-      return NULL;
-  }
+/**
+ * @internal
+ * @brief return a bignum string of at least the given size
+ *
+ * Returns a bignum string of at least the given size, prepending
+ * zeroes as necessary.  A given size of zero will be ignored.
+ *
+ * @param num       the bignum source for the resulting string
+ * @param min_size  size in bytes of result, or zero for no minimum size
+ *
+ * @returns an ssh_string of at least the given size
+ */
+static ssh_string make_sized_bignum_string(bignum num, unsigned int min_size) {
+    ssh_string ptr = NULL;
+    unsigned int p = 0;
+    unsigned int pad = 0;
+    unsigned int len = bignum_num_bytes(num);
+    unsigned int bits = bignum_num_bits(num);
+
+    if (len == 0) {
+        return NULL;
+    }
 
-  /* If the first bit is set we have a negative number */
-  if (!(bits % 8) && bignum_is_bit_set(num, bits - 1)) {
-    pad++;
-  }
+    /* Prepend zero if MSB is set (negative number). */
+    if (!(bits % 8) && bignum_is_bit_set(num, bits - 1)) {
+        pad += 1;
+    }
 
-#ifdef DEBUG_CRYPTO
-  fprintf(stderr, "%d bits, %d bytes, %d padding\n", bits, len, pad);
-#endif /* DEBUG_CRYPTO */
+    /* Ensure padding adds up to min_size. */
+    if ((min_size > 0) && ((len + pad) < min_size)) {
+        pad += (min_size - (len + pad));
+    }
 
-  ptr = ssh_string_new(len + pad);
-  if (ptr == NULL) {
-    return NULL;
-  }
+    ptr = ssh_string_new(len + pad);
+    if (ptr == NULL) {
+        return NULL;
+    }
 
-  /* We have a negative number so we need a leading zero */
-  if (pad) {
-    ptr->data[0] = 0;
-  }
+    while (p < pad) {
+        ptr->data[p++] = 0;
+    }
 
 #ifdef HAVE_LIBGCRYPT
-  bignum_bn2bin(num, len, ptr->data + pad);
+    bignum_bn2bin(num, len, ptr->data + pad);
 #elif HAVE_LIBCRYPTO
-  bignum_bn2bin(num, ptr->data + pad);
+    bignum_bn2bin(num, ptr->data + pad);
 #endif
 
-  return ptr;
+    return ptr;
+}
+
+ssh_string make_bignum_string(bignum num) {
+    return make_sized_bignum_string(num, 0);
 }
 
 bignum make_string_bn(ssh_string string){
@@ -416,6 +433,34 @@ ssh_string dh_get_f(ssh_session session) {
   return make_bignum_string(session->next_crypto->f);
 }
 
+/**
+ * @internal
+ * @brief return given session's shared secret 'K' as an ssh_string
+ * @param session  the session whose 'K' value to retrieve
+ * @returns an ssh_string for the given session's shared secret 'K'
+ * @returns NULL upon error
+ */
+static ssh_string dh_get_k(ssh_session session) {
+    ssh_string k_string = NULL;
+    bignum k = session->next_crypto->k;
+    enum ssh_key_exchange_e kex_type = session->next_crypto->kex_type;
+
+    switch (kex_type) {
+    case SSH_KEX_DH_GROUP1_SHA1:
+    case SSH_KEX_DH_GROUP14_SHA1:
+    case SSH_KEX_ECDH_SHA2_NISTP256:
+        k_string = make_bignum_string(k);
+        break;
+    case SSH_KEX_CURVE25519_SHA256_LIBSSH_ORG:
+        k_string = make_sized_bignum_string(k, CURVE25519_SIZE);
+        break;
+    default:
+        break;
+    }
+
+    return k_string;
+}
+
 void dh_import_pubkey(ssh_session session, ssh_string pubkey_string) {
   session->next_crypto->server_pubkey = pubkey_string;
 }
@@ -742,7 +787,8 @@ int make_sessionid(ssh_session session) {
 #endif
     }
 
-    num = make_bignum_string(session->next_crypto->k);
+    /* Build shared secret 'K' according to session's kex type. */
+    num = dh_get_k(session);
     if (num == NULL) {
         goto error;
     }
@@ -888,7 +934,7 @@ int generate_session_keys(ssh_session session) {
   unsigned char *tmp;
   int rc = -1;
 
-  k_string = make_bignum_string(crypto->k);
+  k_string = dh_get_k(session);
   if (k_string == NULL) {
     ssh_set_error_oom(session);
     goto error;
-- 
1.8.4.21.g992c386