commit 78fad380cda75b0de86f0d8d2b4d7e55f239f326 Author: Yawning Angel yawning@schwanenlied.me Date: Wed Aug 12 16:01:28 2015 +0000
Use ed25519-donna's batch verification support when applicable.
The code was always in our Ed25519 wrappers, so enable it when using the ed25519-donna backend, and deal with the mocking related crypto_rand silliness.
Implements feature 16533. --- changes/feature16533 | 4 + src/common/crypto_ed25519.c | 112 +++++++++++--------- src/ext/ed25519/donna/ed25519-randombytes-custom.h | 2 +- 3 files changed, 69 insertions(+), 49 deletions(-)
diff --git a/changes/feature16533 b/changes/feature16533 new file mode 100644 index 0000000..e9fea94 --- /dev/null +++ b/changes/feature16533 @@ -0,0 +1,4 @@ + o Minor features (performance) + - Improve the runtime speed of Ed25519 signature verification by using + Ed25519-donna's batch verification support when there are a lot of + signatures to verify at once. Implements ticket 16533. diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c index 3a62932..7e995f4 100644 --- a/src/common/crypto_ed25519.c +++ b/src/common/crypto_ed25519.c @@ -37,6 +37,8 @@ typedef struct { unsigned char *); int (*sign)(unsigned char *, const unsigned char *, size_t, const unsigned char *, const unsigned char *); + int (*open_batch)(const unsigned char **, size_t *, const unsigned char **, + const unsigned char **, size_t, int *);
int (*blind_secret_key)(unsigned char *, const unsigned char *, const unsigned char *); @@ -57,6 +59,7 @@ static const ed25519_impl_t impl_ref10 = {
ed25519_ref10_open, ed25519_ref10_sign, + NULL,
ed25519_ref10_blind_secret_key, ed25519_ref10_blind_public_key, @@ -74,6 +77,7 @@ static const ed25519_impl_t impl_donna = {
ed25519_donna_open, ed25519_donna_sign, + ed25519_sign_open_batch_donna,
ed25519_donna_blind_secret_key, ed25519_donna_blind_public_key, @@ -197,57 +201,69 @@ 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 - /* This is how we'd do it if we were using ed25519_donna. I'll keep this - * code around here in case we ever do that. */ - 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); + int i, res; + const ed25519_impl_t *impl = get_ed_impl();
- res = 0; - for (i = 0; i < n_checkable; ++i) { - /* XXX/yawning: Propagate to okay_out? */ - if (!oks[i]) - --res; + if (impl->open_batch == NULL) { + /* No batch verification implementation available, fake it by checking the + * each signature individually. + */ + 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); + } + } else { + /* ed25519-donna style batch verification available. + * + * Theoretically, this should only be called if n_checkable >= 3, since + * that's the threshold where the batch verification actually kicks in, + * but the only difference is a few mallocs/frees. + */ + const uint8_t **ms; + size_t *lens; + const uint8_t **pks; + const uint8_t **sigs; + int *oks; + int all_ok; + + 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; + } + + res = 0; + all_ok = impl->open_batch(ms, lens, pks, sigs, n_checkable, oks); + for (i = 0; i < n_checkable; ++i) { + if (!oks[i]) + --res; + } + /* XXX: For now sanity check oks with the return value. Once we have + * more confidence in the code, if `all_ok == 0` we can skip iterating + * over oks since all the signatures were found to be valid. + */ + tor_assert(((res == 0) && !all_ok) || ((res < 0) && all_ok)); + + tor_free(ms); + tor_free(lens); + tor_free(pks); + if (! okay_out) + tor_free(oks); }
- tor_free(ms); - tor_free(lens); - tor_free(pks); - if (! okay_out) - tor_free(oks); -#endif - return res; }
diff --git a/src/ext/ed25519/donna/ed25519-randombytes-custom.h b/src/ext/ed25519/donna/ed25519-randombytes-custom.h index e49368b..3fb0959 100644 --- a/src/ext/ed25519/donna/ed25519-randombytes-custom.h +++ b/src/ext/ed25519/donna/ed25519-randombytes-custom.h @@ -13,5 +13,5 @@ static void ED25519_FN(ed25519_randombytes_unsafe) (void *p, size_t len) { - crypto_rand(p, len); + crypto_rand_unmocked(p, len); }