- tor-commits - lists.torproject.org

[tor/master] fwd-port test_util_di_ops into tinytest format
by nickm＠torproject.org 13 May '11

13 May '11

commit 9964c314c6c6af4b921875c973f28f8d01b2e9a2 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed May 11 16:25:51 2011 -0400 fwd-port test_util_di_ops into tinytest format --- src/test/test_util.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 54 insertions(+), 0 deletions(-) diff --git a/src/test/test_util.c b/src/test/test_util.c index b1fafc8..0da45df 100644 --- a/src/test/test_util.c +++ b/src/test/test_util.c @@ -1209,6 +1209,59 @@ test_util_load_win_lib(void *ptr) } #endif +static void +test_util_di_ops(void) +{ +#define LT -1 +#define GT 1 +#define EQ 0 + const struct { + const char *a; int want_sign; const char *b; + } examples[] = { + { "Foo", EQ, "Foo" }, + { "foo", GT, "bar", }, + { "foobar", EQ ,"foobar" }, + { "foobar", LT, "foobaw" }, + { "foobar", GT, "f00bar" }, + { "foobar", GT, "boobar" }, + { "", EQ, "" }, + { NULL, 0, NULL }, + }; + + int i; + + for (i = 0; examples[i].a; ++i) { + size_t len = strlen(examples[i].a); + int eq1, eq2, neq1, neq2, cmp1, cmp2; + test_eq(len, strlen(examples[i].b)); + /* We do all of the operations, with operands in both orders. */ + eq1 = tor_memeq(examples[i].a, examples[i].b, len); + eq2 = tor_memeq(examples[i].b, examples[i].a, len); + neq1 = tor_memneq(examples[i].a, examples[i].b, len); + neq2 = tor_memneq(examples[i].b, examples[i].a, len); + cmp1 = tor_memcmp(examples[i].a, examples[i].b, len); + cmp2 = tor_memcmp(examples[i].b, examples[i].a, len); + + /* Check for correctness of cmp1 */ + if (cmp1 < 0 && examples[i].want_sign != LT) + test_fail(); + else if (cmp1 > 0 && examples[i].want_sign != GT) + test_fail(); + else if (cmp1 == 0 && examples[i].want_sign != EQ) + test_fail(); + + /* Check for consistency of everything else with cmp1 */ + test_eq(eq1, eq2); + test_eq(neq1, neq2); + test_eq(cmp1, -cmp2); + test_eq(eq1, cmp1 == 0); + test_eq(neq1, !eq1); + } + + done: + ; +} + #define UTIL_LEGACY(name) \ { #name, legacy_test_helper, 0, &legacy_setup, test_util_ ## name } @@ -1229,6 +1282,7 @@ struct testcase_t util_tests[] = { UTIL_LEGACY(threads), UTIL_LEGACY(sscanf), UTIL_LEGACY(strtok), + UTIL_LEGACY(di_ops), UTIL_TEST(find_str_at_start_of_line, 0), UTIL_TEST(asprintf, 0), UTIL_TEST(listdir, 0),

1 0

[tor/master] Re-apply the automated conversion to 0.2.2 to make handle any memcmps that snuck in
by nickm＠torproject.org 13 May '11

13 May '11

commit 0cbcbc3412b667537b6ec54da0a4c9173a19d6de Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed May 11 16:27:27 2011 -0400 Re-apply the automated conversion to 0.2.2 to make handle any memcmps that snuck in --- src/common/container.c | 2 +- src/or/connection_or.c | 2 +- src/or/dirserv.c | 4 ++-- src/or/dirvote.c | 4 ++-- src/or/eventdns.c | 2 +- src/or/microdesc.c | 4 ++-- src/or/networkstatus.c | 2 +- src/or/routerlist.c | 4 ++-- src/or/routerparse.c | 6 +++--- 9 files changed, 15 insertions(+), 15 deletions(-) diff --git a/src/common/container.c b/src/common/container.c index 5476c60..09d4bb1 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -824,7 +824,7 @@ smartlist_uniq_digests(smartlist_t *sl) static int _compare_digests256(const void **_a, const void **_b) { - return memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); + return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); } /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */ diff --git a/src/or/connection_or.c b/src/or/connection_or.c index 4ce08af..ed174c9 100644 --- a/src/or/connection_or.c +++ b/src/or/connection_or.c @@ -748,7 +748,7 @@ connection_or_set_bad_connections(const char *digest, int force) return; DIGESTMAP_FOREACH(orconn_identity_map, identity, or_connection_t *, conn) { - if (!digest || !memcmp(digest, conn->identity_digest, DIGEST_LEN)) + if (!digest || tor_memeq(digest, conn->identity_digest, DIGEST_LEN)) connection_or_group_set_badness(conn, force); } DIGESTMAP_FOREACH_END; } diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1f4489a..1fd0cd2 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2087,7 +2087,7 @@ routerstatus_format_entry(char *buf, size_t buf_len, /* This assert can fire for the control port, because * it can request NS documents before all descriptors * have been fetched. */ - if (memcmp(desc->cache_info.signed_descriptor_digest, + if (tor_memcmp(desc->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)) { char rl_d[HEX_DIGEST_LEN+1]; @@ -2103,7 +2103,7 @@ routerstatus_format_entry(char *buf, size_t buf_len, "(router %s)\n", rl_d, rs_d, id); - tor_assert(!memcmp(desc->cache_info.signed_descriptor_digest, + tor_assert(tor_memeq(desc->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)); }; diff --git a/src/or/dirvote.c b/src/or/dirvote.c index a95cea4..a017cfb 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -2211,7 +2211,7 @@ networkstatus_add_detached_signatures(networkstatus_t *target, } for (alg = DIGEST_SHA1; alg < N_DIGEST_ALGORITHMS; ++alg) { if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) { - if (!memcmp(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { + if (tor_memeq(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { ++n_matches; } else { *msg_out = "Mismatched digest."; @@ -3615,7 +3615,7 @@ vote_routerstatus_find_microdesc_hash(char *digest256_out, * the first part. */ while (1) { num_len = strspn(cp, "1234567890"); - if (num_len == mlen && !memcmp(mstr, cp, mlen)) { + if (num_len == mlen && tor_memeq(mstr, cp, mlen)) { /* This is the line. */ char buf[BASE64_DIGEST256_LEN+1]; /* XXXX ignores extraneous stuff if the digest is too long. This diff --git a/src/or/eventdns.c b/src/or/eventdns.c index 9e3b426..33238b2 100644 --- a/src/or/eventdns.c +++ b/src/or/eventdns.c @@ -2253,7 +2253,7 @@ sockaddr_is_loopback(const struct sockaddr *addr) return (ntohl(sin->sin_addr.s_addr) & 0xff000000) == 0x7f000000; } else if (addr->sa_family == AF_INET6) { struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *)addr; - return !memcmp(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); + return tor_memeq(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); } return 0; } diff --git a/src/or/microdesc.c b/src/or/microdesc.c index 5740c40..139f2f8 100644 --- a/src/or/microdesc.c +++ b/src/or/microdesc.c @@ -48,7 +48,7 @@ _microdesc_hash(microdesc_t *md) static INLINE int _microdesc_eq(microdesc_t *a, microdesc_t *b) { - return !memcmp(a->digest, b->digest, DIGEST256_LEN); + return tor_memeq(a->digest, b->digest, DIGEST256_LEN); } HT_PROTOTYPE(microdesc_map, microdesc_t, node, @@ -414,7 +414,7 @@ microdesc_cache_rebuild(microdesc_cache_t *cache, int force) SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) { tor_assert(md->saved_location == SAVED_IN_CACHE); md->body = (char*)cache->cache_content->data + md->off; - tor_assert(!memcmp(md->body, "onion-key", 9)); + tor_assert(tor_memeq(md->body, "onion-key", 9)); } SMARTLIST_FOREACH_END(md); smartlist_free(wrote); diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index ff20566..1aa4e4a 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -494,7 +494,7 @@ networkstatus_check_consensus_signature(networkstatus_t *consensus, authority_cert_t *cert = authority_cert_get_by_digests(sig->identity_digest, sig->signing_key_digest); - tor_assert(!memcmp(sig->identity_digest, voter->identity_digest, + tor_assert(tor_memeq(sig->identity_digest, voter->identity_digest, DIGEST_LEN)); if (!is_v3_auth) { diff --git a/src/or/routerlist.c b/src/or/routerlist.c index b0909eb..c54025b 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -3083,7 +3083,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, &ri_new->cache_info); } - same_descriptors = ! memcmp(ri_old->cache_info.signed_descriptor_digest, + same_descriptors = tor_memeq(ri_old->cache_info.signed_descriptor_digest, ri_new->cache_info.signed_descriptor_digest, DIGEST_LEN); @@ -3105,7 +3105,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, sdmap_remove(rl->desc_digest_map, ri_old->cache_info.signed_descriptor_digest); - if (memcmp(ri_old->cache_info.extra_info_digest, + if (tor_memcmp(ri_old->cache_info.extra_info_digest, ri_new->cache_info.extra_info_digest, DIGEST_LEN)) { ei_tmp = eimap_remove(rl->extra_info_map, ri_old->cache_info.extra_info_digest); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index 3b669ad..12d1dfe 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -3499,8 +3499,8 @@ networkstatus_parse_detached_signatures(const char *s, const char *eos) is_duplicate = 0; SMARTLIST_FOREACH(siglist, document_signature_t *, s, { if (s->alg == alg && - !memcmp(id_digest, s->identity_digest, DIGEST_LEN) && - !memcmp(sk_digest, s->signing_key_digest, DIGEST_LEN)) { + tor_memeq(id_digest, s->identity_digest, DIGEST_LEN) && + tor_memeq(sk_digest, s->signing_key_digest, DIGEST_LEN)) { is_duplicate = 1; } }); @@ -4538,7 +4538,7 @@ tor_version_compare(tor_version_t *a, tor_version_t *b) else if ((i = a->git_tag_len - b->git_tag_len)) return i; else if (a->git_tag_len) - return memcmp(a->git_tag, b->git_tag, a->git_tag_len); + return tor_memcmp(a->git_tag, b->git_tag, a->git_tag_len); else return 0; }

1 0

[tor/master] Hand-tune the new tor_memcmp instances in 0.2.2
by nickm＠torproject.org 13 May '11

13 May '11

commit 8fb38331c3213caef2d2e003e02cdb361504f14f Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed May 11 16:32:30 2011 -0400 Hand-tune the new tor_memcmp instances in 0.2.2 --- src/or/dirserv.c | 2 +- src/or/dirvote.c | 4 ++-- src/or/eventdns.c | 2 +- src/or/microdesc.c | 2 +- src/or/routerlist.c | 2 +- src/or/routerparse.c | 2 +- 6 files changed, 7 insertions(+), 7 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1fd0cd2..eadc2d7 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2087,7 +2087,7 @@ routerstatus_format_entry(char *buf, size_t buf_len, /* This assert can fire for the control port, because * it can request NS documents before all descriptors * have been fetched. */ - if (tor_memcmp(desc->cache_info.signed_descriptor_digest, + if (tor_memneq(desc->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)) { char rl_d[HEX_DIGEST_LEN+1]; diff --git a/src/or/dirvote.c b/src/or/dirvote.c index a017cfb..dd156bd 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -2211,7 +2211,7 @@ networkstatus_add_detached_signatures(networkstatus_t *target, } for (alg = DIGEST_SHA1; alg < N_DIGEST_ALGORITHMS; ++alg) { if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) { - if (tor_memeq(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { + if (fast_memeq(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { ++n_matches; } else { *msg_out = "Mismatched digest."; @@ -3615,7 +3615,7 @@ vote_routerstatus_find_microdesc_hash(char *digest256_out, * the first part. */ while (1) { num_len = strspn(cp, "1234567890"); - if (num_len == mlen && tor_memeq(mstr, cp, mlen)) { + if (num_len == mlen && fast_memeq(mstr, cp, mlen)) { /* This is the line. */ char buf[BASE64_DIGEST256_LEN+1]; /* XXXX ignores extraneous stuff if the digest is too long. This diff --git a/src/or/eventdns.c b/src/or/eventdns.c index 33238b2..fc005df 100644 --- a/src/or/eventdns.c +++ b/src/or/eventdns.c @@ -2253,7 +2253,7 @@ sockaddr_is_loopback(const struct sockaddr *addr) return (ntohl(sin->sin_addr.s_addr) & 0xff000000) == 0x7f000000; } else if (addr->sa_family == AF_INET6) { struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *)addr; - return tor_memeq(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); + return fast_memeq(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); } return 0; } diff --git a/src/or/microdesc.c b/src/or/microdesc.c index 139f2f8..b87e0d9 100644 --- a/src/or/microdesc.c +++ b/src/or/microdesc.c @@ -414,7 +414,7 @@ microdesc_cache_rebuild(microdesc_cache_t *cache, int force) SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) { tor_assert(md->saved_location == SAVED_IN_CACHE); md->body = (char*)cache->cache_content->data + md->off; - tor_assert(tor_memeq(md->body, "onion-key", 9)); + tor_assert(fast_memeq(md->body, "onion-key", 9)); } SMARTLIST_FOREACH_END(md); smartlist_free(wrote); diff --git a/src/or/routerlist.c b/src/or/routerlist.c index c54025b..6c649ab 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -3105,7 +3105,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, sdmap_remove(rl->desc_digest_map, ri_old->cache_info.signed_descriptor_digest); - if (tor_memcmp(ri_old->cache_info.extra_info_digest, + if (tor_memneq(ri_old->cache_info.extra_info_digest, ri_new->cache_info.extra_info_digest, DIGEST_LEN)) { ei_tmp = eimap_remove(rl->extra_info_map, ri_old->cache_info.extra_info_digest); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index 12d1dfe..389f22f 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -4538,7 +4538,7 @@ tor_version_compare(tor_version_t *a, tor_version_t *b) else if ((i = a->git_tag_len - b->git_tag_len)) return i; else if (a->git_tag_len) - return tor_memcmp(a->git_tag, b->git_tag, a->git_tag_len); + return fast_memcmp(a->git_tag, b->git_tag, a->git_tag_len); else return 0; }

1 0

[tor/master] Add a data-independent variant of memcmp and a d-i memeq function.
by nickm＠torproject.org 13 May '11

13 May '11

commit 4b19730c8234de3587bd50256fcb11660fb07388 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon May 9 18:39:23 2011 -0400 Add a data-independent variant of memcmp and a d-i memeq function. The tor_memcmp code is by Robert Ransom, and the tor_memeq code is by me. Both incorporate some ideas from DJB's stuff. --- changes/bug3122_memcmp | 7 +++ configure.in | 18 +++++++ src/common/Makefile.am | 4 +- src/common/di_ops.c | 133 ++++++++++++++++++++++++++++++++++++++++++++++++ src/common/di_ops.h | 28 ++++++++++ src/or/test.c | 55 ++++++++++++++++++++ 6 files changed, 243 insertions(+), 2 deletions(-) diff --git a/changes/bug3122_memcmp b/changes/bug3122_memcmp new file mode 100644 index 0000000..a049476 --- /dev/null +++ b/changes/bug3122_memcmp @@ -0,0 +1,7 @@ + o Security fixes + - Replace all potentially sensitive memory comparison operations + with versions whose runtime does not depend on the data being + compared. This will help resist a class of attacks where an + adversary can use variations in timing information to learn + sensitive data. Fix for one case of bug 3122. (Safe memcmp + implementation by Robert Ransom based partially on code by DJB.) diff --git a/configure.in b/configure.in index 1fddaca..eead014 100644 --- a/configure.in +++ b/configure.in @@ -626,6 +626,24 @@ if test "$tor_cv_twos_complement" != no ; then [Define to 1 iff we represent negative integers with two's complement]) fi +# What does shifting a negative value do? +AC_CACHE_CHECK([whether right-shift on negative values does sign-extension], tor_cv_sign_extend, +[AC_RUN_IFELSE([AC_LANG_SOURCE( +[[int main () { int okay = (-60 >> 8) == -1; return okay ? 0 : 1; }]])], + [tor_cv_sign_extend=yes], + [tor_cv_sign_extend=no], + [tor_cv_sign_extend=cross])]) + +if test "$tor_cv_sign_extend" = cross ; then + # Cross-compiling; let's hope that the target isn't raving mad. + AC_MSG_NOTICE([Cross-compiling: we'll assume that right-shifting negative integers causes sign-extension]) +fi + +if test "$tor_cv_sign_extend" != no ; then + AC_DEFINE([RSHIFT_DOES_SIGN_EXTEND], 1, + [Define to 1 iff right-shifting a negative value performs sign-extension]) +fi + # Whether we should use the dmalloc memory allocation debugging library. AC_MSG_CHECKING(whether to use dmalloc (debug memory allocation library)) AC_ARG_WITH(dmalloc, diff --git a/src/common/Makefile.am b/src/common/Makefile.am index 105c413..db94a98 100644 --- a/src/common/Makefile.am +++ b/src/common/Makefile.am @@ -10,7 +10,7 @@ libor_extra_source= endif libor_a_SOURCES = address.c log.c util.c compat.c container.c mempool.c \ - memarea.c $(libor_extra_source) + memarea.c di_ops.c $(libor_extra_source) libor_crypto_a_SOURCES = crypto.c aes.c tortls.c torgzip.c -noinst_HEADERS = address.h log.h crypto.h test.h util.h compat.h aes.h torint.h tortls.h strlcpy.c strlcat.c torgzip.h container.h ht.h mempool.h memarea.h ciphers.inc +noinst_HEADERS = address.h log.h crypto.h test.h util.h compat.h aes.h torint.h tortls.h strlcpy.c strlcat.c torgzip.h container.h ht.h mempool.h memarea.h di_ops.h ciphers.inc diff --git a/src/common/di_ops.c b/src/common/di_ops.c new file mode 100644 index 0000000..c1e292f --- /dev/null +++ b/src/common/di_ops.c @@ -0,0 +1,133 @@ +/* Copyright (c) 2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file di_ops.c + * \brief Functions for data-independent operations + **/ + +#include "orconfig.h" +#include "di_ops.h" + +/** + * Timing-safe version of memcmp. As memcmp, compare the sz bytes + * at a with the sz bytes at , and returns less than 0 if the + * bytes at a lexically precede those at b, 0 if the byte ranges + * are equal, and greater than zero if the bytes at a lexically follow + * those at . + * + * This implementation differs from memcmp in that its timing behavior is not + * data-dependent: it should return in the same amount of time regardless of + * the contents of a and b. + */ +int +tor_memcmp(const void *a, const void *b, size_t len) +{ + const uint8_t *x = a; + const uint8_t *y = b; + size_t i = len; + int retval = 0; + + /* This loop goes from the end of the arrays to the start. At the + * start of every iteration, before we decrement i, we have set + * "retval" equal to the result of memcmp(a+i,b+i,len-i). During the + * loop, we update retval by leaving it unchanged if x[i]==y[i] and + * setting it to x[i]-y[i] if x[i]!= y[i]. + * + * The following assumes we are on a system with two's-complement + * arithmetic. We check for this at configure-time with the check + * that sets USING_TWOS_COMPLEMENT. If we aren't two's complement, then + * torint.h will stop compilation with an error. + */ + while (i--) { + int v1 = x[i]; + int v2 = y[i]; + int equal_p = v1 ^ v2; + + /* The following sets bits 8 and above of equal_p to 'equal_p == + * 0', and thus to v1 == v2. (To see this, note that if v1 == + * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the + * same as ~0 on a two's-complement machine. Then note that if + * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.) + */ + --equal_p; + + equal_p >>= 8; + /* Thanks to (sign-preserving) arithmetic shift, equal_p is now + * equal to -(v1 == v2), which is exactly what we need below. + * (Since we're assuming two's-complement arithmetic, -1 is the + * same as ~0 (all bits set).) + * + * (The result of an arithmetic shift on a negative value is + * actually implementation-defined in standard C. So how do we + * get away with assuming it? Easy. We check.) */ +#if ((-60 >> 8) != -1) +#error "According to cpp, right-shift doesn't perform sign-extension." +#endif +#ifndef RSHIFT_DOES_SIGN_EXTEND +#error "According to configure, right-shift doesn't perform sign-extension." +#endif + + /* If v1 == v2, equal_p is ~0, so this will leave retval + * unchanged; otherwise, equal_p is 0, so this will zero it. */ + retval &= equal_p; + + /* If v1 == v2, then this adds 0, and leaves retval unchanged. + * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */ + retval += (v1 - v2); + + /* There. Now retval is equal to its previous value if v1 == v2, and + * equal to v1 - v2 if v1 != v2. */ + } + + return retval; +} + +/** + * Timing-safe memory comparison. Return true if the sz bytes at + * a are the same as the sz bytes at , and 0 otherwise. + * + * This implementation differs from !memcmp(a,b,sz) in that its timing + * behavior is not data-dependent: it should return in the same amount of time + * regardless of the contents of a and b. It differs from + * !tor_memcmp(a,b,sz) by being faster. + */ +int +tor_memeq(const void *a, const void *b, size_t sz) +{ + /* Treat a and b as byte ranges. */ + const uint8_t *ba = a, *bb = b; + uint32_t any_difference = 0; + while (sz--) { + /* Set byte_diff to all of those bits that are different in *ba and *bb, + * and advance both ba and bb. */ + const uint8_t byte_diff = *ba++ ^ *bb++; + + /* Set bits in any_difference if they are set in byte_diff. */ + any_difference |= byte_diff; + } + + /* Now any_difference is 0 if there are no bits different between + * a and b, and is nonzero if there are bits different between a + * and b. Now for paranoia's sake, let's convert it to 0 or 1. + * + * (If we say "!any_difference", the compiler might get smart enough + * to optimize-out our data-independence stuff above.) + * + * To unpack: + * + * If any_difference == 0: + * any_difference - 1 == ~0 + * (any_difference - 1) >> 8 == 0x00ffffff + * 1 & ((any_difference - 1) >> 8) == 1 + * + * If any_difference != 0: + * 0 < any_difference < 256, so + * 0 < any_difference - 1 < 255 + * (any_difference - 1) >> 8 == 0 + * 1 & ((any_difference - 1) >> 8) == 0 + */ + + return 1 & ((any_difference - 1) >> 8); +} + diff --git a/src/common/di_ops.h b/src/common/di_ops.h new file mode 100644 index 0000000..1b223d9 --- /dev/null +++ b/src/common/di_ops.h @@ -0,0 +1,28 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2011, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file di_ops.h + * \brief Headers for di_ops.c + **/ + +#ifndef TOR_DI_OPS_H +#define TOR_DI_OPS_H + +#include "orconfig.h" +#include "torint.h" + +int tor_memcmp(const void *a, const void *b, size_t sz); +int tor_memeq(const void *a, const void *b, size_t sz); +#define tor_memneq(a,b,sz) (!tor_memeq((a),(b),(sz))) + +/** Alias for the platform's memcmp() function. This function is + * not data-independent: we define this alias so that we can + * mark cases where we are deliberately using a data-dependent memcmp() + * implementation. + */ +#define fast_memcmp(a,b,c) (memcmp((a),(b),(c))) + +#endif diff --git a/src/or/test.c b/src/or/test.c index b08f202..dc71db4 100644 --- a/src/or/test.c +++ b/src/or/test.c @@ -43,6 +43,7 @@ const char tor_svn_revision[] = ""; #include "torgzip.h" #include "mempool.h" #include "memarea.h" +#include "di_ops.h" #ifdef USE_DMALLOC #include <dmalloc.h> @@ -1331,6 +1332,59 @@ test_util(void) ; } +static void +test_util_di_ops(void) +{ +#define LT -1 +#define GT 1 +#define EQ 0 + const struct { + const char *a; int want_sign; const char *b; + } examples[] = { + { "Foo", EQ, "Foo" }, + { "foo", GT, "bar", }, + { "foobar", EQ ,"foobar" }, + { "foobar", LT, "foobaw" }, + { "foobar", GT, "f00bar" }, + { "foobar", GT, "boobar" }, + { "", EQ, "" }, + { NULL, 0, NULL }, + }; + + int i; + + for (i = 0; examples[i].a; ++i) { + size_t len = strlen(examples[i].a); + int eq1, eq2, neq1, neq2, cmp1, cmp2; + test_eq(len, strlen(examples[i].b)); + /* We do all of the operations, with operands in both orders. */ + eq1 = tor_memeq(examples[i].a, examples[i].b, len); + eq2 = tor_memeq(examples[i].b, examples[i].a, len); + neq1 = tor_memneq(examples[i].a, examples[i].b, len); + neq2 = tor_memneq(examples[i].b, examples[i].a, len); + cmp1 = tor_memcmp(examples[i].a, examples[i].b, len); + cmp2 = tor_memcmp(examples[i].b, examples[i].a, len); + + /* Check for correctness of cmp1 */ + if (cmp1 < 0 && examples[i].want_sign != LT) + test_fail(); + else if (cmp1 > 0 && examples[i].want_sign != GT) + test_fail(); + else if (cmp1 == 0 && examples[i].want_sign != EQ) + test_fail(); + + /* Check for consistency of everything else with cmp1 */ + test_eq(eq1, eq2); + test_eq(neq1, neq2); + test_eq(cmp1, -cmp2); + test_eq(eq1, cmp1 == 0); + test_eq(neq1, !eq1); + } + + done: + ; +} + /** Helper: assert that IPv6 addresses a and b are the same. On * failure, reports an error, describing the addresses as e1 and * e2, and reporting the line number as line. */ @@ -4753,6 +4807,7 @@ static struct { SUBENT(crypto, aes_iv), SUBENT(crypto, base32_decode), ENT(util), + SUBENT(util, di_ops), SUBENT(util, ip6_helpers), SUBENT(util, gzip), SUBENT(util, datadir),

1 0

[tor/master] Add a "di_ops.h" include to util.h
by nickm＠torproject.org 13 May '11

13 May '11

commit 1d703ed22b249567c2df31db9035a4dda66483ca Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue May 10 16:19:58 2011 -0400 Add a "di_ops.h" include to util.h --- src/common/util.h | 1 + 1 files changed, 1 insertions(+), 0 deletions(-) diff --git a/src/common/util.h b/src/common/util.h index fcea9c5..7bc5286 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -14,6 +14,7 @@ #include "orconfig.h" #include "torint.h" #include "compat.h" +#include "di_ops.h" #include <stdio.h> #include <stdlib.h>

1 0

[tor/maint-0.2.2] Hand-tune the new tor_memcmp instances in 0.2.2
by nickm＠torproject.org 13 May '11

13 May '11

commit 8fb38331c3213caef2d2e003e02cdb361504f14f Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed May 11 16:32:30 2011 -0400 Hand-tune the new tor_memcmp instances in 0.2.2 --- src/or/dirserv.c | 2 +- src/or/dirvote.c | 4 ++-- src/or/eventdns.c | 2 +- src/or/microdesc.c | 2 +- src/or/routerlist.c | 2 +- src/or/routerparse.c | 2 +- 6 files changed, 7 insertions(+), 7 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1fd0cd2..eadc2d7 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2087,7 +2087,7 @@ routerstatus_format_entry(char *buf, size_t buf_len, /* This assert can fire for the control port, because * it can request NS documents before all descriptors * have been fetched. */ - if (tor_memcmp(desc->cache_info.signed_descriptor_digest, + if (tor_memneq(desc->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)) { char rl_d[HEX_DIGEST_LEN+1]; diff --git a/src/or/dirvote.c b/src/or/dirvote.c index a017cfb..dd156bd 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -2211,7 +2211,7 @@ networkstatus_add_detached_signatures(networkstatus_t *target, } for (alg = DIGEST_SHA1; alg < N_DIGEST_ALGORITHMS; ++alg) { if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) { - if (tor_memeq(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { + if (fast_memeq(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { ++n_matches; } else { *msg_out = "Mismatched digest."; @@ -3615,7 +3615,7 @@ vote_routerstatus_find_microdesc_hash(char *digest256_out, * the first part. */ while (1) { num_len = strspn(cp, "1234567890"); - if (num_len == mlen && tor_memeq(mstr, cp, mlen)) { + if (num_len == mlen && fast_memeq(mstr, cp, mlen)) { /* This is the line. */ char buf[BASE64_DIGEST256_LEN+1]; /* XXXX ignores extraneous stuff if the digest is too long. This diff --git a/src/or/eventdns.c b/src/or/eventdns.c index 33238b2..fc005df 100644 --- a/src/or/eventdns.c +++ b/src/or/eventdns.c @@ -2253,7 +2253,7 @@ sockaddr_is_loopback(const struct sockaddr *addr) return (ntohl(sin->sin_addr.s_addr) & 0xff000000) == 0x7f000000; } else if (addr->sa_family == AF_INET6) { struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *)addr; - return tor_memeq(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); + return fast_memeq(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); } return 0; } diff --git a/src/or/microdesc.c b/src/or/microdesc.c index 139f2f8..b87e0d9 100644 --- a/src/or/microdesc.c +++ b/src/or/microdesc.c @@ -414,7 +414,7 @@ microdesc_cache_rebuild(microdesc_cache_t *cache, int force) SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) { tor_assert(md->saved_location == SAVED_IN_CACHE); md->body = (char*)cache->cache_content->data + md->off; - tor_assert(tor_memeq(md->body, "onion-key", 9)); + tor_assert(fast_memeq(md->body, "onion-key", 9)); } SMARTLIST_FOREACH_END(md); smartlist_free(wrote); diff --git a/src/or/routerlist.c b/src/or/routerlist.c index c54025b..6c649ab 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -3105,7 +3105,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, sdmap_remove(rl->desc_digest_map, ri_old->cache_info.signed_descriptor_digest); - if (tor_memcmp(ri_old->cache_info.extra_info_digest, + if (tor_memneq(ri_old->cache_info.extra_info_digest, ri_new->cache_info.extra_info_digest, DIGEST_LEN)) { ei_tmp = eimap_remove(rl->extra_info_map, ri_old->cache_info.extra_info_digest); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index 12d1dfe..389f22f 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -4538,7 +4538,7 @@ tor_version_compare(tor_version_t *a, tor_version_t *b) else if ((i = a->git_tag_len - b->git_tag_len)) return i; else if (a->git_tag_len) - return tor_memcmp(a->git_tag, b->git_tag, a->git_tag_len); + return fast_memcmp(a->git_tag, b->git_tag, a->git_tag_len); else return 0; }

1 0

[tor/maint-0.2.2] Re-apply the automated conversion to 0.2.2 to make handle any memcmps that snuck in
by nickm＠torproject.org 13 May '11

13 May '11

commit 0cbcbc3412b667537b6ec54da0a4c9173a19d6de Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed May 11 16:27:27 2011 -0400 Re-apply the automated conversion to 0.2.2 to make handle any memcmps that snuck in --- src/common/container.c | 2 +- src/or/connection_or.c | 2 +- src/or/dirserv.c | 4 ++-- src/or/dirvote.c | 4 ++-- src/or/eventdns.c | 2 +- src/or/microdesc.c | 4 ++-- src/or/networkstatus.c | 2 +- src/or/routerlist.c | 4 ++-- src/or/routerparse.c | 6 +++--- 9 files changed, 15 insertions(+), 15 deletions(-) diff --git a/src/common/container.c b/src/common/container.c index 5476c60..09d4bb1 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -824,7 +824,7 @@ smartlist_uniq_digests(smartlist_t *sl) static int _compare_digests256(const void **_a, const void **_b) { - return memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); + return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); } /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */ diff --git a/src/or/connection_or.c b/src/or/connection_or.c index 4ce08af..ed174c9 100644 --- a/src/or/connection_or.c +++ b/src/or/connection_or.c @@ -748,7 +748,7 @@ connection_or_set_bad_connections(const char *digest, int force) return; DIGESTMAP_FOREACH(orconn_identity_map, identity, or_connection_t *, conn) { - if (!digest || !memcmp(digest, conn->identity_digest, DIGEST_LEN)) + if (!digest || tor_memeq(digest, conn->identity_digest, DIGEST_LEN)) connection_or_group_set_badness(conn, force); } DIGESTMAP_FOREACH_END; } diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1f4489a..1fd0cd2 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2087,7 +2087,7 @@ routerstatus_format_entry(char *buf, size_t buf_len, /* This assert can fire for the control port, because * it can request NS documents before all descriptors * have been fetched. */ - if (memcmp(desc->cache_info.signed_descriptor_digest, + if (tor_memcmp(desc->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)) { char rl_d[HEX_DIGEST_LEN+1]; @@ -2103,7 +2103,7 @@ routerstatus_format_entry(char *buf, size_t buf_len, "(router %s)\n", rl_d, rs_d, id); - tor_assert(!memcmp(desc->cache_info.signed_descriptor_digest, + tor_assert(tor_memeq(desc->cache_info.signed_descriptor_digest, rs->descriptor_digest, DIGEST_LEN)); }; diff --git a/src/or/dirvote.c b/src/or/dirvote.c index a95cea4..a017cfb 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -2211,7 +2211,7 @@ networkstatus_add_detached_signatures(networkstatus_t *target, } for (alg = DIGEST_SHA1; alg < N_DIGEST_ALGORITHMS; ++alg) { if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) { - if (!memcmp(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { + if (tor_memeq(target->digests.d[alg], digests->d[alg], DIGEST256_LEN)) { ++n_matches; } else { *msg_out = "Mismatched digest."; @@ -3615,7 +3615,7 @@ vote_routerstatus_find_microdesc_hash(char *digest256_out, * the first part. */ while (1) { num_len = strspn(cp, "1234567890"); - if (num_len == mlen && !memcmp(mstr, cp, mlen)) { + if (num_len == mlen && tor_memeq(mstr, cp, mlen)) { /* This is the line. */ char buf[BASE64_DIGEST256_LEN+1]; /* XXXX ignores extraneous stuff if the digest is too long. This diff --git a/src/or/eventdns.c b/src/or/eventdns.c index 9e3b426..33238b2 100644 --- a/src/or/eventdns.c +++ b/src/or/eventdns.c @@ -2253,7 +2253,7 @@ sockaddr_is_loopback(const struct sockaddr *addr) return (ntohl(sin->sin_addr.s_addr) & 0xff000000) == 0x7f000000; } else if (addr->sa_family == AF_INET6) { struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *)addr; - return !memcmp(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); + return tor_memeq(sin6->sin6_addr.s6_addr, LOOPBACK_S6, 16); } return 0; } diff --git a/src/or/microdesc.c b/src/or/microdesc.c index 5740c40..139f2f8 100644 --- a/src/or/microdesc.c +++ b/src/or/microdesc.c @@ -48,7 +48,7 @@ _microdesc_hash(microdesc_t *md) static INLINE int _microdesc_eq(microdesc_t *a, microdesc_t *b) { - return !memcmp(a->digest, b->digest, DIGEST256_LEN); + return tor_memeq(a->digest, b->digest, DIGEST256_LEN); } HT_PROTOTYPE(microdesc_map, microdesc_t, node, @@ -414,7 +414,7 @@ microdesc_cache_rebuild(microdesc_cache_t *cache, int force) SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) { tor_assert(md->saved_location == SAVED_IN_CACHE); md->body = (char*)cache->cache_content->data + md->off; - tor_assert(!memcmp(md->body, "onion-key", 9)); + tor_assert(tor_memeq(md->body, "onion-key", 9)); } SMARTLIST_FOREACH_END(md); smartlist_free(wrote); diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index ff20566..1aa4e4a 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -494,7 +494,7 @@ networkstatus_check_consensus_signature(networkstatus_t *consensus, authority_cert_t *cert = authority_cert_get_by_digests(sig->identity_digest, sig->signing_key_digest); - tor_assert(!memcmp(sig->identity_digest, voter->identity_digest, + tor_assert(tor_memeq(sig->identity_digest, voter->identity_digest, DIGEST_LEN)); if (!is_v3_auth) { diff --git a/src/or/routerlist.c b/src/or/routerlist.c index b0909eb..c54025b 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -3083,7 +3083,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, &ri_new->cache_info); } - same_descriptors = ! memcmp(ri_old->cache_info.signed_descriptor_digest, + same_descriptors = tor_memeq(ri_old->cache_info.signed_descriptor_digest, ri_new->cache_info.signed_descriptor_digest, DIGEST_LEN); @@ -3105,7 +3105,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, sdmap_remove(rl->desc_digest_map, ri_old->cache_info.signed_descriptor_digest); - if (memcmp(ri_old->cache_info.extra_info_digest, + if (tor_memcmp(ri_old->cache_info.extra_info_digest, ri_new->cache_info.extra_info_digest, DIGEST_LEN)) { ei_tmp = eimap_remove(rl->extra_info_map, ri_old->cache_info.extra_info_digest); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index 3b669ad..12d1dfe 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -3499,8 +3499,8 @@ networkstatus_parse_detached_signatures(const char *s, const char *eos) is_duplicate = 0; SMARTLIST_FOREACH(siglist, document_signature_t *, s, { if (s->alg == alg && - !memcmp(id_digest, s->identity_digest, DIGEST_LEN) && - !memcmp(sk_digest, s->signing_key_digest, DIGEST_LEN)) { + tor_memeq(id_digest, s->identity_digest, DIGEST_LEN) && + tor_memeq(sk_digest, s->signing_key_digest, DIGEST_LEN)) { is_duplicate = 1; } }); @@ -4538,7 +4538,7 @@ tor_version_compare(tor_version_t *a, tor_version_t *b) else if ((i = a->git_tag_len - b->git_tag_len)) return i; else if (a->git_tag_len) - return memcmp(a->git_tag, b->git_tag, a->git_tag_len); + return tor_memcmp(a->git_tag, b->git_tag, a->git_tag_len); else return 0; }

1 0

[tor/maint-0.2.2] Merge remote-tracking branch 'public/bug3122_memcmp_squashed' into maint-0.2.1
by nickm＠torproject.org 13 May '11

13 May '11

1 0

[tor/maint-0.2.2] Merge remote-tracking branch 'origin/maint-0.2.1' into maint-0.2.2
by nickm＠torproject.org 13 May '11

13 May '11

commit 98870f2eada31ee7efca62ab7adf98cb843e2937 Merge: 59a6df8 1f67827 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu May 12 19:25:21 2011 -0400 Merge remote-tracking branch 'origin/maint-0.2.1' into maint-0.2.2

1 0

[tor/maint-0.2.2] Merge remote-tracking branch 'public/bug3122_memcmp_022' into maint-0.2.2
by nickm＠torproject.org 13 May '11

13 May '11

1 0