# HG changeset patch # User Matt Johnston # Date 1365871803 -28800 # Node ID 70625eed40c99b176b7f86ad08007bd77a9723d6 # Parent 6e6ce39da2fcf06f78029f868875c078b37dd307 A bit of work on ecdsa for host/auth keys diff -r 6e6ce39da2fc -r 70625eed40c9 algo.h --- a/algo.h Tue Apr 09 22:47:03 2013 +0800 +++ b/algo.h Sun Apr 14 00:50:03 2013 +0800 @@ -74,8 +74,10 @@ }; struct dropbear_hash { - const struct ltc_hash_descriptor *hashdesc; + const struct ltc_hash_descriptor *hash_desc; const unsigned long keysize; + // hashsize may be truncated from the size returned by hash_desc, + // eg sha1-96 const unsigned char hashsize; }; @@ -90,7 +92,7 @@ #endif // both - const struct ltc_hash_descriptor *hashdesc; + const struct ltc_hash_descriptor *hash_desc; }; int have_algo(char* algo, size_t algolen, algo_type algos[]); diff -r 6e6ce39da2fc -r 70625eed40c9 common-kex.c --- a/common-kex.c Tue Apr 09 22:47:03 2013 +0800 +++ b/common-kex.c Sun Apr 14 00:50:03 2013 +0800 @@ -255,25 +255,25 @@ static void hashkeys(unsigned char *out, unsigned int outlen, const hash_state * hs, const unsigned char X) { - const struct ltc_hash_descriptor *hashdesc = ses.newkeys->algo_kex->hashdesc; + const struct ltc_hash_descriptor *hash_desc = ses.newkeys->algo_kex->hash_desc; hash_state hs2; unsigned int offset; - unsigned char tmpout[hashdesc->hashsize]; + unsigned char tmpout[hash_desc->hashsize]; memcpy(&hs2, hs, sizeof(hash_state)); - hashdesc->process(&hs2, &X, 1); - hashdesc->process(&hs2, ses.session_id->data, ses.session_id->len); - hashdesc->done(&hs2, tmpout); - memcpy(out, tmpout, MIN(hashdesc->hashsize, outlen)); - for (offset = hashdesc->hashsize; + hash_desc->process(&hs2, &X, 1); + hash_desc->process(&hs2, ses.session_id->data, ses.session_id->len); + hash_desc->done(&hs2, tmpout); + memcpy(out, tmpout, MIN(hash_desc->hashsize, outlen)); + for (offset = hash_desc->hashsize; offset < outlen; - offset += hashdesc->hashsize) + offset += hash_desc->hashsize) { /* need to extend */ memcpy(&hs2, hs, sizeof(hash_state)); - hashdesc->process(&hs2, out, offset); - hashdesc->done(&hs2, tmpout); - memcpy(&out[offset], tmpout, MIN(outlen - offset, hashdesc->hashsize)); + hash_desc->process(&hs2, out, offset); + hash_desc->done(&hs2, tmpout); + memcpy(&out[offset], tmpout, MIN(outlen - offset, hash_desc->hashsize)); } } @@ -295,17 +295,17 @@ unsigned char *trans_IV, *trans_key, *recv_IV, *recv_key; hash_state hs; - const struct ltc_hash_descriptor *hashdesc = ses.newkeys->algo_kex->hashdesc; + const struct ltc_hash_descriptor *hash_desc = ses.newkeys->algo_kex->hash_desc; char mactransletter, macrecvletter; /* Client or server specific */ TRACE(("enter gen_new_keys")) /* the dh_K and hash are the start of all hashes, we make use of that */ - hashdesc->init(&hs); - hash_process_mp(hashdesc, &hs, ses.dh_K); + hash_desc->init(&hs); + hash_process_mp(hash_desc, &hs, ses.dh_K); mp_clear(ses.dh_K); m_free(ses.dh_K); - hashdesc->process(&hs, ses.hash->data, ses.hash->len); + hash_desc->process(&hs, ses.hash->data, ses.hash->len); buf_burn(ses.hash); buf_free(ses.hash); ses.hash = NULL; @@ -355,16 +355,16 @@ } } - if (ses.newkeys->trans.algo_mac->hashdesc != NULL) { + if (ses.newkeys->trans.algo_mac->hash_desc != NULL) { hashkeys(ses.newkeys->trans.mackey, ses.newkeys->trans.algo_mac->keysize, &hs, mactransletter); - ses.newkeys->trans.hash_index = find_hash(ses.newkeys->trans.algo_mac->hashdesc->name); + ses.newkeys->trans.hash_index = find_hash(ses.newkeys->trans.algo_mac->hash_desc->name); } - if (ses.newkeys->recv.algo_mac->hashdesc != NULL) { + if (ses.newkeys->recv.algo_mac->hash_desc != NULL) { hashkeys(ses.newkeys->recv.mackey, ses.newkeys->recv.algo_mac->keysize, &hs, macrecvletter); - ses.newkeys->recv.hash_index = find_hash(ses.newkeys->recv.algo_mac->hashdesc->name); + ses.newkeys->recv.hash_index = find_hash(ses.newkeys->recv.algo_mac->hash_desc->name); } #ifndef DISABLE_ZLIB @@ -694,15 +694,15 @@ static void finish_kexhashbuf(void) { hash_state hs; - const struct ltc_hash_descriptor *hashdesc = ses.newkeys->algo_kex->hashdesc; + const struct ltc_hash_descriptor *hash_desc = ses.newkeys->algo_kex->hash_desc; - hashdesc->init(&hs); + hash_desc->init(&hs); buf_setpos(ses.kexhashbuf, 0); - hashdesc->process(&hs, buf_getptr(ses.kexhashbuf, ses.kexhashbuf->len), + hash_desc->process(&hs, buf_getptr(ses.kexhashbuf, ses.kexhashbuf->len), ses.kexhashbuf->len); - ses.hash = buf_new(hashdesc->hashsize); - hashdesc->done(&hs, buf_getwriteptr(ses.hash, hashdesc->hashsize)); - buf_setlen(ses.hash, hashdesc->hashsize); + ses.hash = buf_new(hash_desc->hashsize); + hash_desc->done(&hs, buf_getwriteptr(ses.hash, hash_desc->hashsize)); + buf_setlen(ses.hash, hash_desc->hashsize); buf_burn(ses.kexhashbuf); buf_free(ses.kexhashbuf); diff -r 6e6ce39da2fc -r 70625eed40c9 ecc.c --- a/ecc.c Tue Apr 09 22:47:03 2013 +0800 +++ b/ecc.c Sun Apr 14 00:50:03 2013 +0800 @@ -10,21 +10,21 @@ #ifdef DROPBEAR_ECC_256 struct dropbear_ecc_curve ecc_curve_nistp256 = { .ltc_size = 32, - .hashdesc = &sha256_desc, + .hash_desc = &sha256_desc, .name = "nistp256" }; #endif #ifdef DROPBEAR_ECC_384 struct dropbear_ecc_curve ecc_curve_nistp384 = { .ltc_size = 48, - .hashdesc = &sha384_desc, + .hash_desc = &sha384_desc, .name = "nistp384" }; #endif #ifdef DROPBEAR_ECC_521 struct dropbear_ecc_curve ecc_curve_nistp521 = { .ltc_size = 66, - .hashdesc = &sha512_desc, + .hash_desc = &sha512_desc, .name = "nistp521" }; #endif @@ -59,6 +59,17 @@ } } +struct dropbear_ecc_curve* curve_for_dp(const ltc_ecc_set_type *dp) { + struct dropbear_ecc_curve **curve = NULL; + for (curve = dropbear_ecc_curves; *curve; curve++) { + if ((*curve)->dp == dp) { + break; + } + } + assert(*curve); + return *curve; +} + ecc_key * new_ecc_key(void) { ecc_key *key = m_malloc(sizeof(*key)); key->pubkey.x = m_malloc(sizeof(mp_int)); diff -r 6e6ce39da2fc -r 70625eed40c9 ecc.h --- a/ecc.h Tue Apr 09 22:47:03 2013 +0800 +++ b/ecc.h Sun Apr 14 00:50:03 2013 +0800 @@ -11,8 +11,8 @@ struct dropbear_ecc_curve { int ltc_size; // to match the byte sizes in ltc_ecc_sets[] const ltc_ecc_set_type *dp; // curve domain parameters - const struct ltc_hash_descriptor *hashdesc; - const char *name; + const struct ltc_hash_descriptor *hash_desc; + const unsigned char *name; }; extern struct dropbear_ecc_curve ecc_curve_nistp256; @@ -21,6 +21,7 @@ extern struct dropbear_ecc_curve *dropbear_ecc_curves[]; void dropbear_ecc_fill_dp(); +struct dropbear_ecc_curve* curve_for_dp(const ltc_ecc_set_type *dp); // "pubkey" refers to a point, but LTC uses ecc_key structure for both public // and private keys diff -r 6e6ce39da2fc -r 70625eed40c9 ecdsa.c --- a/ecdsa.c Tue Apr 09 22:47:03 2013 +0800 +++ b/ecdsa.c Sun Apr 14 00:50:03 2013 +0800 @@ -2,6 +2,7 @@ #include "dbutil.h" #include "crypto_desc.h" #include "ecc.h" +#include "ecdsa.h" #ifdef DROPBEAR_ECDSA @@ -55,7 +56,7 @@ // string "ecdsa-sha2-[identifier]" key_ident = buf_getstring(buf, &key_ident_len); - // string "ecdsa-sha2-[identifier]" + // string "[identifier]" identifier = buf_getstring(buf, &identifier_len); if (key_ident_len != identifier_len + strlen("ecdsa-sha2-")) { @@ -68,7 +69,7 @@ } for (curve = dropbear_ecc_curves; *curve; curve++) { - if (memcmp(identifier, (*curve)->name, strlen((*curve)->name)) == 0) { + if (memcmp(identifier, (char*)(*curve)->name, strlen((char*)(*curve)->name)) == 0) { break; } } @@ -82,12 +83,8 @@ new_key = buf_get_ecc_raw_pubkey(q_buf, *curve); out: - if (key_ident) { - m_free(key_ident); - } - if (identifier) { - m_free(identifier); - } + m_free(key_ident); + m_free(identifier); if (q_buf) { buf_free(q_buf); q_buf = NULL; @@ -96,5 +93,312 @@ return new_key; } +ecc_key *buf_get_ecdsa_priv_key(buffer *buf) { + ecc_key *new_key = NULL; + TRACE(("enter buf_get_ecdsa_priv_key")) + new_key = buf_get_ecdsa_pub_key(buf); + if (!new_key) { + return NULL; + } + + if (buf_getmpint(buf, new_key->k) != DROPBEAR_SUCCESS) { + ecc_free(new_key); + return NULL; + } + + return new_key; +} + +void buf_put_ecdsa_pub_key(buffer *buf, ecc_key *key) { + struct dropbear_ecc_curve *curve = NULL; + unsigned char key_ident[30]; + + curve = curve_for_dp(key->dp); + snprintf((char*)key_ident, sizeof(key_ident), "ecdsa-sha2-%s", curve->name); + buf_putstring(buf, key_ident, strlen(key_ident)); + buf_putstring(buf, curve->name, strlen(curve->name)); + buf_put_ecc_raw_pubkey_string(buf, key); +} + +void buf_put_ecdsa_priv_key(buffer *buf, ecc_key *key) { + buf_put_ecdsa_pub_key(buf, key); + buf_putmpint(buf, key->k); +} + +void buf_put_ecdsa_sign(buffer *buf, ecc_key *key, buffer *data_buf) { + /* Based on libtomcrypt's ecc_sign_hash but without the asn1 */ + int err = DROPBEAR_FAILURE; + struct dropbear_ecc_curve *curve = NULL; + hash_state hs; + unsigned char hash[64]; + void *e = NULL, *p = NULL, *s = NULL, *r; + unsigned char key_ident[30]; + buffer *sigbuf = NULL; + + TRACE(("buf_put_ecdsa_sign")) + curve = curve_for_dp(key->dp); + + if (ltc_init_multi(&r, &s, &p, &e, NULL) != CRYPT_OK) { + goto out; + } + + curve->hash_desc->init(&hs); + curve->hash_desc->process(&hs, data_buf->data, data_buf->len); + curve->hash_desc->done(&hs, hash); + + if (ltc_mp.unsigned_read(e, hash, curve->hash_desc->hashsize) != CRYPT_OK) { + goto out; + } + + if (ltc_mp.read_radix(p, (char *)key->dp->order, 16) != CRYPT_OK) { + goto out; + } + + for (;;) { + ecc_key R_key; // ephemeral key + if (ecc_make_key_ex(NULL, dropbear_ltc_prng, &R_key, key->dp) != CRYPT_OK) { + goto out; + } + if (ltc_mp.mpdiv(R_key.pubkey.x, p, NULL, r) != CRYPT_OK) { + goto out; + } + if (ltc_mp.compare_d(r, 0) == LTC_MP_EQ) { + // try again + ecc_free(&R_key); + continue; + } + /* k = 1/k */ + if (ltc_mp.invmod(R_key.k, p, R_key.k) != CRYPT_OK) { + goto out; + } + /* s = xr */ + if (ltc_mp.mulmod(key->k, r, p, s) != CRYPT_OK) { + goto out; + } + /* s = e + xr */ + if (ltc_mp.add(e, s, s) != CRYPT_OK) { + goto out; + } + if (ltc_mp.mpdiv(s, p, NULL, s) != CRYPT_OK) { + goto out; + } + /* s = (e + xr)/k */ + if (ltc_mp.mulmod(s, R_key.k, p, s) != CRYPT_OK) { + goto out; + } + ecc_free(&R_key); + + if (ltc_mp.compare_d(s, 0) != LTC_MP_EQ) { + break; + } + } + + snprintf((char*)key_ident, sizeof(key_ident), "ecdsa-sha2-%s", curve->name); + buf_putstring(buf, key_ident, strlen(key_ident)); + // enough for nistp521 + sigbuf = buf_new(200); + buf_putmpint(sigbuf, (mp_int*)r); + buf_putmpint(sigbuf, (mp_int*)s); + buf_putbufstring(buf, sigbuf); + + err = DROPBEAR_SUCCESS; + +out: + if (r && s && p && e) { + ltc_deinit_multi(r, s, p, e, NULL); + } + + if (sigbuf) { + buf_free(sigbuf); + } + + if (err == DROPBEAR_FAILURE) { + dropbear_exit("ECC error"); + } +} + +// returns values in s and r +// returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE +static int buf_get_ecdsa_verify_params(buffer *buf, struct dropbear_ecc_curve *curve, + void *r, void* s) { + int ret = DROPBEAR_FAILURE; + unsigned char* ident = NULL; + unsigned int ident_len; + unsigned int sig_len; + unsigned int sig_pos; + unsigned char key_ident[30]; + + ident = buf_getstring(buf, &ident_len); + snprintf((char*)key_ident, sizeof(key_ident), "ecdsa-sha2-%s", curve->name); + if (strlen((char*)key_ident) != ident_len) { + goto out; + } + if (memcmp(key_ident, ident, ident_len) != 0) { + goto out; + } + sig_len = buf_getint(buf); + sig_pos = buf->pos; + if (buf_getmpint(buf, r) != DROPBEAR_SUCCESS) { + goto out; + } + if (buf_getmpint(buf, s) != DROPBEAR_SUCCESS) { + goto out; + } + if (buf->pos - sig_pos != sig_len) { + goto out; + } + ret = DROPBEAR_SUCCESS; + +out: + m_free(ident); + return ret; +} + + +int buf_ecdsa_verify(buffer *buf, ecc_key *key, buffer *data_buf) { + /* Based on libtomcrypt's ecc_verify_hash but without the asn1 */ + int ret = DROPBEAR_FAILURE; + hash_state hs; + struct dropbear_ecc_curve *curve = NULL; + unsigned char hash[64]; + ecc_point *mG = NULL, *mQ = NULL; + void *r = NULL, *s = NULL, *v = NULL, *w = NULL, *u1 = NULL, *u2 = NULL, + *e = NULL, *p = NULL, *m = NULL; + void *mp = NULL; + + /* verify + * + * w = s^-1 mod n + * u1 = xw + * u2 = rw + * X = u1*G + u2*Q + * v = X_x1 mod n + * accept if v == r + */ + + TRACE(("buf_ecdsa_verify")) + curve = curve_for_dp(key->dp); + + mG = ltc_ecc_new_point(); + mQ = ltc_ecc_new_point(); + if (ltc_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL) != CRYPT_OK + || !mG + || !mQ) { + dropbear_exit("ECC error"); + } + + if (buf_get_ecdsa_verify_params(buf, curve, r, s) != DROPBEAR_SUCCESS) { + goto out; + } + + curve->hash_desc->init(&hs); + curve->hash_desc->process(&hs, data_buf->data, data_buf->len); + curve->hash_desc->done(&hs, hash); + + if (ltc_mp.unsigned_read(e, hash, curve->hash_desc->hashsize) != CRYPT_OK) { + goto out; + } + + /* get the order */ + if (ltc_mp.read_radix(p, (char *)key->dp->order, 16) != CRYPT_OK) { + goto out; + } + + /* get the modulus */ + if (ltc_mp.read_radix(m, (char *)key->dp->prime, 16) != CRYPT_OK) { + goto out; + } + + /* check for zero */ + if (ltc_mp.compare_d(r, 0) == LTC_MP_EQ + || ltc_mp.compare_d(s, 0) == LTC_MP_EQ + || ltc_mp.compare(r, p) != LTC_MP_LT + || ltc_mp.compare(s, p) != LTC_MP_LT) { + goto out; + } + + /* w = s^-1 mod n */ + if (ltc_mp.invmod(s, p, w) != CRYPT_OK) { + goto out; + } + + /* u1 = ew */ + if (ltc_mp.mulmod(e, w, p, u1) != CRYPT_OK) { + goto out; + } + + /* u2 = rw */ + if (ltc_mp.mulmod(r, w, p, u2) != CRYPT_OK) { + goto out; + } + + /* find mG and mQ */ + if (ltc_mp.read_radix(mG->x, (char *)key->dp->Gx, 16) != CRYPT_OK) { + goto out; + } + if (ltc_mp.read_radix(mG->y, (char *)key->dp->Gy, 16) != CRYPT_OK) { + goto out; + } + if (ltc_mp.set_int(mG->z, 1) != CRYPT_OK) { + goto out; + } + + if (ltc_mp.copy(key->pubkey.x, mQ->x) != CRYPT_OK + || ltc_mp.copy(key->pubkey.y, mQ->y) != CRYPT_OK + || ltc_mp.copy(key->pubkey.z, mQ->z) != CRYPT_OK) { + goto out; + } + + /* compute u1*mG + u2*mQ = mG */ + if (ltc_mp.ecc_mul2add == NULL) { + if (ltc_mp.ecc_ptmul(u1, mG, mG, m, 0) != CRYPT_OK) { + goto out; + } + if (ltc_mp.ecc_ptmul(u2, mQ, mQ, m, 0) != CRYPT_OK) { + goto out; + } + + /* find the montgomery mp */ + if (ltc_mp.montgomery_setup(m, &mp) != CRYPT_OK) { + goto out; + } + + /* add them */ + if (ltc_mp.ecc_ptadd(mQ, mG, mG, m, mp) != CRYPT_OK) { + goto out; + } + + /* reduce */ + if (ltc_mp.ecc_map(mG, m, mp) != CRYPT_OK) { + goto out; + } + } else { + /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */ + if (ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, m) != CRYPT_OK) { + goto out; + } + } + + /* v = X_x1 mod n */ + if (ltc_mp.mpdiv(mG->x, p, NULL, v) != CRYPT_OK) { + goto out; + } + + /* does v == r */ + if (ltc_mp.compare(v, r) == LTC_MP_EQ) { + ret = DROPBEAR_SUCCESS; + } + +out: + ltc_ecc_del_point(mG); + ltc_ecc_del_point(mQ); + mp_clear_multi(r, s, v, w, u1, u2, p, e, m, NULL); + if (mp != NULL) { + ltc_mp.montgomery_deinit(mp); + } + return ret; +} + + #endif // DROPBEAR_ECDSA diff -r 6e6ce39da2fc -r 70625eed40c9 ecdsa.h --- a/ecdsa.h Tue Apr 09 22:47:03 2013 +0800 +++ b/ecdsa.h Sun Apr 14 00:50:03 2013 +0800 @@ -0,0 +1,16 @@ +#ifndef _ECDSA_H_ +#define _ECDSA_H_ + +#include "includes.h" +#include "buffer.h" + +ecc_key *gen_ecdsa_priv_key(unsigned int bit_size); +ecc_key *buf_get_ecdsa_pub_key(buffer* buf); +ecc_key *buf_get_ecdsa_priv_key(buffer *buf); +void buf_put_ecdsa_pub_key(buffer *buf, ecc_key *key); +void buf_put_ecdsa_priv_key(buffer *buf, ecc_key *key); + +void buf_put_ecdsa_sign(buffer *buf, ecc_key *key, buffer *data_buf); +int buf_ecdsa_verify(buffer *buf, ecc_key *key, buffer *data_buf); + +#endif // _ECDSA_H_ \ No newline at end of file diff -r 6e6ce39da2fc -r 70625eed40c9 keyimport.c --- a/keyimport.c Tue Apr 09 22:47:03 2013 +0800 +++ b/keyimport.c Sun Apr 14 00:50:03 2013 +0800 @@ -349,7 +349,7 @@ * Code to read and write OpenSSH private keys. */ -enum { OSSH_DSA, OSSH_RSA }; +enum { OSSH_DSA, OSSH_RSA, OSSH_EC }; struct openssh_key { int type; int encrypted; @@ -392,6 +392,8 @@ ret->type = OSSH_RSA; else if (!strcmp(buffer, "-----BEGIN DSA PRIVATE KEY-----\n")) ret->type = OSSH_DSA; + else if (!strcmp(buffer, "-----BEGIN EC PRIVATE KEY-----\n")) + ret->type = OSSH_EC; else { errmsg = "Unrecognised key type"; goto error; diff -r 6e6ce39da2fc -r 70625eed40c9 libtomcrypt/src/headers/tomcrypt_custom.h --- a/libtomcrypt/src/headers/tomcrypt_custom.h Tue Apr 09 22:47:03 2013 +0800 +++ b/libtomcrypt/src/headers/tomcrypt_custom.h Sun Apr 14 00:50:03 2013 +0800 @@ -138,6 +138,8 @@ #ifdef DROPBEAR_ECC #define MECC +#define LTC_ECC_SHAMIR +#define LTC_ECC_TIMING_RESISTANT #define MPI #define LTM_DESC #ifdef DROPBEAR_ECC_256 diff -r 6e6ce39da2fc -r 70625eed40c9 signkey.c --- a/signkey.c Tue Apr 09 22:47:03 2013 +0800 +++ b/signkey.c Sun Apr 14 00:50:03 2013 +0800 @@ -34,13 +34,6 @@ sign_key * ret; ret = (sign_key*)m_malloc(sizeof(sign_key)); -#ifdef DROPBEAR_DSS - ret->dsskey = NULL; -#endif -#ifdef DROPBEAR_RSA - ret->rsakey = NULL; -#endif - ret->filename = NULL; ret->type = DROPBEAR_SIGNKEY_NONE; ret->source = SIGNKEY_SOURCE_INVALID; return ret;