commit 87ba033cd57e57e10a19ca77005c8c740ae70181 Author: Nick Mathewson nickm@torproject.org Date: Sun Sep 29 13:30:24 2013 -0400
Add Ed25519 support, wrappers, and tests.
Taken from earlier ed25519 branch based on floodyberry's ed25519-donna. Tweaked so that it applies to ref10 instead. --- .gitignore | 4 + src/common/crypto_curve25519.c | 36 ++++++-- src/common/crypto_curve25519.h | 2 + src/common/crypto_ed25519.c | 181 +++++++++++++++++++++++++++++++++++++++ src/common/crypto_ed25519.h | 72 ++++++++++++++++ src/common/include.am | 7 +- src/ext/include.am | 4 +- src/test/test_crypto.c | 185 ++++++++++++++++++++++++++++++++++++++++ 8 files changed, 480 insertions(+), 11 deletions(-)
diff --git a/.gitignore b/.gitignore index de1eb04..df94237 100644 --- a/.gitignore +++ b/.gitignore @@ -134,6 +134,10 @@ /src/config/torrc /src/config/torrc.sample
+# /src/ext/ +/src/ext/ed25519/ref10/libed25519_ref10.a +/src/ext/ed25519/ref10/libed25519_ref10.lib + # /src/or/ /src/or/Makefile /src/or/Makefile.in diff --git a/src/common/crypto_curve25519.c b/src/common/crypto_curve25519.c index 9e83440..290e88d 100644 --- a/src/common/crypto_curve25519.c +++ b/src/common/crypto_curve25519.c @@ -63,26 +63,44 @@ curve25519_public_key_is_ok(const curve25519_public_key_t *key) return !safe_mem_is_zero(key->public_key, CURVE25519_PUBKEY_LEN); }
-/** Generate a new keypair and return the secret key. If <b>extra_strong</b> - * is true, this key is possibly going to get used more than once, so - * use a better-than-usual RNG. Return 0 on success, -1 on failure. */ +/** + * Generate CURVE25519_SECKEY_LEN random bytes in <b>out</b>. If + * <b>extra_strong</b> is true, this key is possibly going to get used more + * than once, so use a better-than-usual RNG. Return 0 on success, -1 on + * failure. + * + * This function does not adjust the output of the RNG at all; the will caller + * will need to clear or set the appropriate bits to make curve25519 work. + */ int -curve25519_secret_key_generate(curve25519_secret_key_t *key_out, - int extra_strong) +curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong) { uint8_t k_tmp[CURVE25519_SECKEY_LEN];
- if (crypto_rand((char*)key_out->secret_key, CURVE25519_SECKEY_LEN) < 0) + if (crypto_rand((char*)out, CURVE25519_SECKEY_LEN) < 0) return -1; if (extra_strong && !crypto_strongest_rand(k_tmp, CURVE25519_SECKEY_LEN)) { /* If they asked for extra-strong entropy and we have some, use it as an * HMAC key to improve not-so-good entropy rather than using it directly, * just in case the extra-strong entropy is less amazing than we hoped. */ - crypto_hmac_sha256((char *)key_out->secret_key, - (const char *)k_tmp, sizeof(k_tmp), - (const char *)key_out->secret_key, CURVE25519_SECKEY_LEN); + crypto_hmac_sha256((char*) out, + (const char *)k_tmp, sizeof(k_tmp), + (const char *)out, CURVE25519_SECKEY_LEN); } memwipe(k_tmp, 0, sizeof(k_tmp)); + return 0; +} + +/** Generate a new keypair and return the secret key. If <b>extra_strong</b> + * is true, this key is possibly going to get used more than once, so + * use a better-than-usual RNG. Return 0 on success, -1 on failure. */ +int +curve25519_secret_key_generate(curve25519_secret_key_t *key_out, + int extra_strong) +{ + if (curve25519_rand_seckey_bytes(key_out->secret_key, extra_strong) < 0) + return -1; + key_out->secret_key[0] &= 248; key_out->secret_key[31] &= 127; key_out->secret_key[31] |= 64; diff --git a/src/common/crypto_curve25519.h b/src/common/crypto_curve25519.h index 57018ac..fece2fe 100644 --- a/src/common/crypto_curve25519.h +++ b/src/common/crypto_curve25519.h @@ -57,6 +57,8 @@ int curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out, char **tag_out, const char *fname);
+int curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong); + #ifdef CRYPTO_CURVE25519_PRIVATE STATIC int curve25519_impl(uint8_t *output, const uint8_t *secret, const uint8_t *basepoint); diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c new file mode 100644 index 0000000..c39f4f4 --- /dev/null +++ b/src/common/crypto_ed25519.c @@ -0,0 +1,181 @@ +/* Copyright (c) 2013, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/* Wrapper code for an ed25519 implementation. */ + +#include "orconfig.h" +#ifdef HAVE_SYS_STAT_H +#include <sys/stat.h> +#endif + +#include "crypto.h" + +#include "crypto_curve25519.h" +#include "crypto_ed25519.h" +#include "torlog.h" +#include "util.h" + +#include "ed25519/ref10/ed25519_ref10.h" + +int +ed25519_secret_key_generate(ed25519_secret_key_t *seckey_out, + int extra_strong) +{ + (void) extra_strong; + if (ed25519_ref10_seckey(seckey_out->seckey) < 0) + return -1; + return 0; +} + +int +ed25519_public_key_generate(ed25519_public_key_t *pubkey_out, + const ed25519_secret_key_t *seckey) +{ + if (ed25519_ref10_pubkey(pubkey_out->pubkey, seckey->seckey) < 0) + return -1; + return 0; +} + +/** Generate a new ed25519 keypair in <b>keypair_out</b>. If + * <b>extra_strong</b> is set, try to mix some system entropy into the key + * generation process. Return 0 on success, -1 on failure. */ +int +ed25519_keypair_generate(ed25519_keypair_t *keypair_out, int extra_strong) +{ + (void) extra_strong; + + if (ed25519_ref10_keygen(keypair_out->pubkey.pubkey, + keypair_out->seckey.seckey)<0) + return -1; + return 0; +} + +/** + * Set <b>signature_out</b> to a signature of the <b>len</b>-byte message + * <b>msg</b>, using the secret and public key in <b>keypair</b>. + */ +int +ed25519_sign(ed25519_signature_t *signature_out, + const uint8_t *msg, size_t len, + const ed25519_keypair_t *keypair) +{ + uint8_t keys[64]; + uint8_t *tmp; + uint64_t tmplen; + + /* XXXX Make crypto_sign in ref10 friendlier so we don't need this stupid + * copying. */ + tor_assert(len < SIZE_T_CEILING - 64); + tmplen = ((uint64_t)len) + 64; + tmp = tor_malloc(tmplen); + + memcpy(keys, keypair->seckey.seckey, 32); + memcpy(keys+32, keypair->pubkey.pubkey, 32); + + if (ed25519_ref10_sign(tmp, &tmplen, msg, len, keys) < 0) { + tor_free(tmp); + return -1; + } + + memcpy(signature_out->sig, tmp, 64); + memwipe(keys, 0, sizeof(keys)); + + tor_free(tmp); + + return 0; +} + +/** + * Check whether if <b>signature</b> is a valid signature for the + * <b>len</b>-byte message in <b>msg</b> made with the key <b>pubkey</b>. + * + * Return 0 if the signature is valid; -1 if it isn't. + */ +int +ed25519_checksig(const ed25519_signature_t *signature, + const uint8_t *msg, size_t len, + const ed25519_public_key_t *pubkey) +{ + uint8_t *smtmp; + uint8_t *tmp; + uint64_t tmplen; + int r; + + tor_assert(len < SIZE_T_CEILING - 64); + tmplen = len + 64; + tmp = tor_malloc(tmplen); + smtmp = tor_malloc(tmplen); + memcpy(smtmp, signature->sig, 64); + memcpy(smtmp+64, msg, len); + + r = ed25519_ref10_open(tmp, &tmplen, smtmp, tmplen, pubkey->pubkey); + + tor_free(tmp); + tor_free(smtmp); + + return r; +} + +/** Validate every signature among those in <b>checkable</b>, which contains + * exactly <b>n_checkable</b> elements. If <b>okay_out</b> is non-NULL, set + * the i'th element of <b>okay_out</b> to 1 if the i'th element of + * <b>checkable</b> is valid, and to 0 otherwise. Return 0 if every signature + * was valid. Otherwise return -N, where N is the number of invalid + * signatures. + */ +int +ed25519_checksig_batch(int *okay_out, + const ed25519_checkable_t *checkable, + int n_checkable) +{ + int res, i; + + res = 0; + for (i = 0; i < n_checkable; ++i) { + const ed25519_checkable_t *ch = &checkable[i]; + int r = ed25519_checksig(&ch->signature, ch->msg, ch->len, ch->pubkey); + if (r < 0) + --res; + if (okay_out) + okay_out[i] = (r == 0); + } + +#if 0 + const uint8_t **ms; + size_t *lens; + const uint8_t **pks; + const uint8_t **sigs; + int *oks; + + ms = tor_malloc(sizeof(uint8_t*)*n_checkable); + lens = tor_malloc(sizeof(size_t)*n_checkable); + pks = tor_malloc(sizeof(uint8_t*)*n_checkable); + sigs = tor_malloc(sizeof(uint8_t*)*n_checkable); + oks = okay_out ? okay_out : tor_malloc(sizeof(int)*n_checkable); + + for (i = 0; i < n_checkable; ++i) { + ms[i] = checkable[i].msg; + lens[i] = checkable[i].len; + pks[i] = checkable[i].pubkey->pubkey; + sigs[i] = checkable[i].signature.sig; + oks[i] = 0; + } + + ed25519_sign_open_batch_donna_fb(ms, lens, pks, sigs, n_checkable, oks); + + res = 0; + for (i = 0; i < n_checkable; ++i) { + if (!oks[i]) + --res; + } + + tor_free(ms); + tor_free(lens); + tor_free(pks); + if (! okay_out) + tor_free(oks); +#endif + + return res; +} + diff --git a/src/common/crypto_ed25519.h b/src/common/crypto_ed25519.h new file mode 100644 index 0000000..6b00c3d --- /dev/null +++ b/src/common/crypto_ed25519.h @@ -0,0 +1,72 @@ +/* Copyright (c) 2012-2013, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_CRYPTO_ED25519_H +#define TOR_CRYPTO_ED25519_H + +#include "testsupport.h" +#include "torint.h" + +#define ED25519_PUBKEY_LEN 32 +#define ED25519_SECKEY_LEN 32 +#define ED25519_SIG_LEN 64 + +/** An Ed25519 signature. */ +typedef struct { + uint8_t sig[ED25519_SIG_LEN]; +} ed25519_signature_t; + +/** An Ed25519 public key */ +typedef struct { + uint8_t pubkey[ED25519_PUBKEY_LEN]; +} ed25519_public_key_t; + +/** An Ed25519 secret key */ +typedef struct { + uint8_t seckey[ED25519_SECKEY_LEN]; +} ed25519_secret_key_t; + +/** An Ed25519 keypair. */ +typedef struct { + ed25519_public_key_t pubkey; + ed25519_secret_key_t seckey; +} ed25519_keypair_t; + +#ifdef CURVE25519_ENABLED +int ed25519_secret_key_generate(ed25519_secret_key_t *seckey_out, + int extra_strong); +int ed25519_public_key_generate(ed25519_public_key_t *pubkey_out, + const ed25519_secret_key_t *seckey); +int ed25519_keypair_generate(ed25519_keypair_t *keypair_out, int extra_strong); +int ed25519_sign(ed25519_signature_t *signature_out, + const uint8_t *msg, size_t len, + const ed25519_keypair_t *key); +int ed25519_checksig(const ed25519_signature_t *signature, + const uint8_t *msg, size_t len, + const ed25519_public_key_t *pubkey); + +/** + * A collection of information necessary to check an Ed25519 signature. Used + * for batch verification. + */ +typedef struct { + /** The public key that supposedly generated the signature. */ + ed25519_public_key_t *pubkey; + /** The signature to check. */ + ed25519_signature_t signature; + /** The message that the signature is supposed to have been applied to. */ + const uint8_t *msg; + /** The length of the message. */ + size_t len; +} ed25519_checkable_t; + +int ed25519_checksig_batch(int *okay_out, + const ed25519_checkable_t *checkable, + int n_checkable); +#endif + +/* XXXX write secret keys to disk, load secret keys from disk, read encrypted, + * write encrypted. serialize public. parse public. */ + +#endif + diff --git a/src/common/include.am b/src/common/include.am index 68e0110..8fc1ff9 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -52,8 +52,12 @@ LIBDONNA= endif endif
+LIBDONNA += $(LIBED25519_REF10) + if CURVE25519_ENABLED -libcrypto_extra_source=src/common/crypto_curve25519.c +libcrypto_extra_source = \ + src/common/crypto_curve25519.c \ + src/common/crypto_ed25519.c endif
LIBOR_A_SOURCES = \ @@ -110,6 +114,7 @@ COMMONHEADERS = \ src/common/container.h \ src/common/crypto.h \ src/common/crypto_curve25519.h \ + src/common/crypto_ed25519.h \ src/common/di_ops.h \ src/common/memarea.h \ src/common/linux_syscalls.inc \ diff --git a/src/ext/include.am b/src/ext/include.am index 88025f6..69e7823 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -77,5 +77,7 @@ ED25519_REF10_HDRS = \ src/ext/ed25519/ref10/sqrtm1.h
noinst_HEADERS += $(ED25519_REF10_HDRS) -noinst_LIBRARIES += src/ext/ed25519/ref10/libed25519_ref10.a + +LIBED25519_REF10=src/ext/ed25519/ref10/libed25519_ref10.a +noinst_LIBRARIES += $(LIBED25519_REF10)
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index 5d8edb6..8b04bc8 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -12,6 +12,7 @@ #include "siphash.h" #ifdef CURVE25519_ENABLED #include "crypto_curve25519.h" +#include "crypto_ed25519.h" #endif
extern const char AUTHORITY_SIGNKEY_3[]; @@ -1161,6 +1162,188 @@ test_crypto_curve25519_persist(void *arg) tor_free(tag); }
+static void +test_crypto_ed25519_simple(void *arg) +{ + ed25519_keypair_t kp1, kp2; + ed25519_public_key_t pub1, pub2; + ed25519_secret_key_t sec1, sec2; + ed25519_signature_t sig1, sig2; + const uint8_t msg[] = + "GNU will be able to run Unix programs, " + "but will not be identical to Unix."; + const uint8_t msg2[] = + "Microsoft Windows extends the features of the DOS operating system, " + "yet is compatible with most existing applications that run under DOS."; + size_t msg_len = strlen((const char*)msg); + size_t msg2_len = strlen((const char*)msg2); + + (void)arg; + + tt_int_op(0, ==, ed25519_secret_key_generate(&sec1, 0)); + tt_int_op(0, ==, ed25519_secret_key_generate(&sec2, 1)); + + tt_int_op(0, ==, ed25519_public_key_generate(&pub1, &sec1)); + tt_int_op(0, ==, ed25519_public_key_generate(&pub2, &sec1)); + + test_memeq(pub1.pubkey, pub2.pubkey, sizeof(pub1.pubkey)); + + memcpy(&kp1.pubkey, &pub1, sizeof(pub1)); + memcpy(&kp1.seckey, &sec1, sizeof(sec1)); + tt_int_op(0, ==, ed25519_sign(&sig1, msg, msg_len, &kp1)); + tt_int_op(0, ==, ed25519_sign(&sig2, msg, msg_len, &kp1)); + + /* Ed25519 signatures are deterministic */ + test_memeq(sig1.sig, sig2.sig, sizeof(sig1.sig)); + + /* Basic signature is valid. */ + tt_int_op(0, ==, ed25519_checksig(&sig1, msg, msg_len, &pub1)); + + /* Altered signature doesn't work. */ + sig1.sig[0] ^= 3; + tt_int_op(-1, ==, ed25519_checksig(&sig1, msg, msg_len, &pub1)); + + /* Wrong public key doesn't work. */ + tt_int_op(0, ==, ed25519_public_key_generate(&pub2, &sec2)); + tt_int_op(-1, ==, ed25519_checksig(&sig2, msg, msg_len, &pub2)); + + /* Wrong message doesn't work. */ + tt_int_op(0, ==, ed25519_checksig(&sig2, msg, msg_len, &pub1)); + tt_int_op(-1, ==, ed25519_checksig(&sig2, msg, msg_len-1, &pub1)); + tt_int_op(-1, ==, ed25519_checksig(&sig2, msg2, msg2_len, &pub1)); + + /* Batch signature checking works with some bad. */ + tt_int_op(0, ==, ed25519_keypair_generate(&kp2, 0)); + tt_int_op(0, ==, ed25519_sign(&sig1, msg, msg_len, &kp2)); + { + ed25519_checkable_t ch[] = { + { &pub1, sig2, msg, msg_len }, /*ok*/ + { &pub1, sig2, msg, msg_len-1 }, /*bad*/ + { &kp2.pubkey, sig2, msg2, msg2_len }, /*bad*/ + { &kp2.pubkey, sig1, msg, msg_len }, /*ok*/ + }; + int okay[4]; + tt_int_op(-2, ==, ed25519_checksig_batch(okay, ch, 4)); + tt_int_op(okay[0], ==, 1); + tt_int_op(okay[1], ==, 0); + tt_int_op(okay[2], ==, 0); + tt_int_op(okay[3], ==, 1); + tt_int_op(-2, ==, ed25519_checksig_batch(NULL, ch, 4)); + } + + /* Batch signature checking works with all good. */ + { + ed25519_checkable_t ch[] = { + { &pub1, sig2, msg, msg_len }, /*ok*/ + { &kp2.pubkey, sig1, msg, msg_len }, /*ok*/ + }; + int okay[2]; + tt_int_op(0, ==, ed25519_checksig_batch(okay, ch, 2)); + tt_int_op(okay[0], ==, 1); + tt_int_op(okay[1], ==, 1); + tt_int_op(0, ==, ed25519_checksig_batch(NULL, ch, 2)); + } + + done: + ; +} + +static void +test_crypto_ed25519_test_vectors(void *arg) +{ + char *mem_op_hex_tmp=NULL; + int i; + struct { + const char *sk; + const char *pk; + const char *sig; + const char *msg; + } items[] = { + /* These test vectors were generated with the "ref" implementation of + * ed25519 from SUPERCOP-20130419 */ + { "4c6574277320686f706520746865726520617265206e6f206275677320696e20", + "f3e0e493b30f56e501aeb868fc912fe0c8b76621efca47a78f6d75875193dd87", + "b5d7fd6fd3adf643647ce1fe87a2931dedd1a4e38e6c662bedd35cdd80bfac51" + "1b2c7d1ee6bd929ac213014e1a8dc5373854c7b25dbe15ec96bf6c94196fae06", + "506c6561736520657863757365206d7920667269656e642e2048652069736e2774" + "204e554c2d7465726d696e617465642e" + }, + + { "74686520696d706c656d656e746174696f6e20776869636820617265206e6f74", + "407f0025a1e1351a4cb68e92f5c0ebaf66e7aaf93a4006a4d1a66e3ede1cfeac", + "02884fde1c3c5944d0ecf2d133726fc820c303aae695adceabf3a1e01e95bf28" + "da88c0966f5265e9c6f8edc77b3b96b5c91baec3ca993ccd21a3f64203600601", + "506c6561736520657863757365206d7920667269656e642e2048652069736e2774" + "204e554c2d7465726d696e617465642e" + }, + { "6578706f73656420627920456e676c697368207465787420617320696e707574", + "61681cb5fbd69f9bc5a462a21a7ab319011237b940bc781cdc47fcbe327e7706", + "6a127d0414de7510125d4bc214994ffb9b8857a46330832d05d1355e882344ad" + "f4137e3ca1f13eb9cc75c887ef2309b98c57528b4acd9f6376c6898889603209", + "506c6561736520657863757365206d7920667269656e642e2048652069736e2774" + "204e554c2d7465726d696e617465642e" + }, + + /* These come from "sign.input" in ed25519's page */ + { "5b5a619f8ce1c66d7ce26e5a2ae7b0c04febcd346d286c929e19d0d5973bfef9", + "6fe83693d011d111131c4f3fbaaa40a9d3d76b30012ff73bb0e39ec27ab18257", + "0f9ad9793033a2fa06614b277d37381e6d94f65ac2a5a94558d09ed6ce922258" + "c1a567952e863ac94297aec3c0d0c8ddf71084e504860bb6ba27449b55adc40e", + "5a8d9d0a22357e6655f9c785" + }, + { "940c89fe40a81dafbdb2416d14ae469119869744410c3303bfaa0241dac57800", + "a2eb8c0501e30bae0cf842d2bde8dec7386f6b7fc3981b8c57c9792bb94cf2dd", + "d8bb64aad8c9955a115a793addd24f7f2b077648714f49c4694ec995b330d09d" + "640df310f447fd7b6cb5c14f9fe9f490bcf8cfadbfd2169c8ac20d3b8af49a0c", + "b87d3813e03f58cf19fd0b6395" + }, + { "9acad959d216212d789a119252ebfe0c96512a23c73bd9f3b202292d6916a738", + "cf3af898467a5b7a52d33d53bc037e2642a8da996903fc252217e9c033e2f291", + "6ee3fe81e23c60eb2312b2006b3b25e6838e02106623f844c44edb8dafd66ab0" + "671087fd195df5b8f58a1d6e52af42908053d55c7321010092748795ef94cf06", + "55c7fa434f5ed8cdec2b7aeac173", + }, + { "d5aeee41eeb0e9d1bf8337f939587ebe296161e6bf5209f591ec939e1440c300", + "fd2a565723163e29f53c9de3d5e8fbe36a7ab66e1439ec4eae9c0a604af291a5", + "f68d04847e5b249737899c014d31c805c5007a62c0a10d50bb1538c5f3550395" + "1fbc1e08682f2cc0c92efe8f4985dec61dcbd54d4b94a22547d24451271c8b00", + "0a688e79be24f866286d4646b5d81c" + }, + + { NULL, NULL, NULL, NULL} + }; + + (void)arg; + + for (i = 0; items[i].pk; ++i) { + ed25519_keypair_t kp; + ed25519_signature_t sig; + uint8_t *msg; + size_t msg_len; + base16_decode((char*)kp.seckey.seckey, sizeof(kp.seckey.seckey), + items[i].sk, 64); + tt_int_op(0, ==, ed25519_public_key_generate(&kp.pubkey, &kp.seckey)); + test_memeq_hex(kp.pubkey.pubkey, items[i].pk); + + msg_len = strlen(items[i].msg) / 2; + msg = tor_malloc(msg_len); + base16_decode((char*)msg, msg_len, items[i].msg, strlen(items[i].msg)); + + tt_int_op(0, ==, ed25519_sign(&sig, msg, msg_len, &kp)); + test_memeq_hex(sig.sig, items[i].sig); + + tor_free(msg); + } + + done: + tor_free(mem_op_hex_tmp); +} + +/* XXX + Check known values for secret->public, for public,msg->signature. + */ + + #endif
static void @@ -1300,6 +1483,8 @@ struct testcase_t crypto_tests[] = { { "curve25519_wrappers", test_crypto_curve25519_wrappers, 0, NULL, NULL }, { "curve25519_encode", test_crypto_curve25519_encode, 0, NULL, NULL }, { "curve25519_persist", test_crypto_curve25519_persist, 0, NULL, NULL }, + { "ed25519_simple", test_crypto_ed25519_simple, 0, NULL, NULL }, + { "ed25519_test_vectors", test_crypto_ed25519_test_vectors, 0, NULL, NULL }, #endif { "siphash", test_crypto_siphash, 0, NULL, NULL }, END_OF_TESTCASES