February 2014 - tor-commits - lists.torproject.org

[tor/master] csiphash: avoid unaligned access on non-x86
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit 1bd86b69b6198892a8310f3933a4df483b91713a Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 10:39:22 2014 -0500 csiphash: avoid unaligned access on non-x86 --- src/ext/csiphash.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) diff --git a/src/ext/csiphash.c b/src/ext/csiphash.c index 5df41d7..2f37a5f 100644 --- a/src/ext/csiphash.c +++ b/src/ext/csiphash.c @@ -31,6 +31,7 @@ #include "torint.h" #include "siphash.h" +#include <string.h> #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \ __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ @@ -73,6 +74,11 @@ HALF_ROUND(v0,v1,v2,v3,13,16); \ HALF_ROUND(v2,v1,v0,v3,17,21); +#if (defined(__i386) || defined(__i386__) || defined(_M_IX86) || \ + defined(__x86_64) || defined(__x86_64__) || \ + defined(_M_AMD64) || defined(_M_X64) || defined(__INTEL__)) +# define UNALIGNED_OK 1 +#endif uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key) { uint64_t k0 = key->k0; @@ -89,7 +95,13 @@ uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *k uint64_t v3 = k1 ^ 0x7465646279746573ULL; while (src_sz >= 8) { +#ifdef UNALIGNED_OK uint64_t mi = _le64toh(*in); +#else + uint64_t mi; + memcpy(&mi, in, 8); + mi = _le64toh(mi); +#endif in += 1; src_sz -= 8; v3 ^= mi; DOUBLE_ROUND(v0,v1,v2,v3); @@ -101,7 +113,11 @@ uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *k case 7: pt[6] = m[6]; case 6: pt[5] = m[5]; case 5: pt[4] = m[4]; +#ifdef UNALIGNED_OK case 4: *((uint32_t*)&pt[0]) = *((uint32_t*)&m[0]); break; +#else + case 4: pt[3] = m[3]; +#endif case 3: pt[2] = m[2]; case 2: pt[1] = m[1]; case 1: pt[0] = m[0]; @@ -115,3 +131,4 @@ uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *k DOUBLE_ROUND(v0,v1,v2,v3); return (v0 ^ v1) ^ (v2 ^ v3); } +

1 0

[tor/master] Tests for siphash, from reference implementation.
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit f51df9bb93f889533e7480e6364899ce249fe45b Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 10:58:03 2014 -0500 Tests for siphash, from reference implementation. --- src/ext/siphash.h | 9 +++++ src/test/test_crypto.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 107 insertions(+) diff --git a/src/ext/siphash.h b/src/ext/siphash.h new file mode 100644 index 0000000..ff372bc --- /dev/null +++ b/src/ext/siphash.h @@ -0,0 +1,9 @@ +#ifndef SIPHASH_H +#define SIPHASH_H +struct sipkey { + uint64_t k0; + uint64_t k1; +}; +uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key); + +#endif diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index 22adc6c..b1252a1 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -9,6 +9,7 @@ #include "test.h" #include "aes.h" #include "util.h" +#include "siphash.h" #ifdef CURVE25519_ENABLED #include "crypto_curve25519.h" #endif @@ -1111,6 +1112,102 @@ test_crypto_curve25519_persist(void *arg) #endif +static void +test_crypto_siphash(void *arg) +{ + /* From the reference implementation, taking + k = 00 01 02 ... 0f + and in = 00; 00 01; 00 01 02; ... + */ + const uint8_t VECTORS[64][8] = + { + { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72, }, + { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74, }, + { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d, }, + { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85, }, + { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf, }, + { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18, }, + { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb, }, + { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab, }, + { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93, }, + { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e, }, + { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a, }, + { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4, }, + { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75, }, + { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14, }, + { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7, }, + { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1, }, + { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f, }, + { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69, }, + { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b, }, + { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb, }, + { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe, }, + { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0, }, + { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93, }, + { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8, }, + { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8, }, + { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc, }, + { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17, }, + { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f, }, + { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde, }, + { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6, }, + { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad, }, + { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32, }, + { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71, }, + { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7, }, + { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12, }, + { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15, }, + { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31, }, + { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02, }, + { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca, }, + { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a, }, + { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e, }, + { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad, }, + { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18, }, + { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4, }, + { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9, }, + { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9, }, + { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb, }, + { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0, }, + { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6, }, + { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7, }, + { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee, }, + { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1, }, + { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a, }, + { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81, }, + { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f, }, + { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24, }, + { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7, }, + { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea, }, + { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60, }, + { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66, }, + { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c, }, + { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f, }, + { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5, }, + { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95, } + }; + + const struct sipkey K = { U64_LITERAL(0x0706050403020100), + U64_LITERAL(0x0f0e0d0c0b0a0908) }; + uint8_t IN[64]; + int i, j; + + (void)arg; + + for (i = 0; i < 64; ++i) + IN[i] = i; + + for (i = 0; i < 64; ++i) { + uint64_t r = siphash24(IN, i, &K); + for (j = 0; j < 8; ++j) { + tt_int_op( (r >> (j*8)) & 0xff, ==, VECTORS[i][j]); + } + } + + done: + ; +} + static void * pass_data_setup_fn(const struct testcase_t *testcase) { @@ -1152,6 +1249,7 @@ struct testcase_t crypto_tests[] = { { "curve25519_encode", test_crypto_curve25519_encode, 0, NULL, NULL }, { "curve25519_persist", test_crypto_curve25519_persist, 0, NULL, NULL }, #endif + { "siphash", test_crypto_siphash, 0, NULL, NULL }, END_OF_TESTCASES };

1 0

[tor/master] csiphash: Add functions to take a global key.
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit f05820531a1e4bc5935609900f0067b2643f0529 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 11:27:03 2014 -0500 csiphash: Add functions to take a global key. --- src/ext/csiphash.c | 14 ++++++++++++++ src/ext/siphash.h | 3 +++ 2 files changed, 17 insertions(+) diff --git a/src/ext/csiphash.c b/src/ext/csiphash.c index 2f37a5f..9a8833d 100644 --- a/src/ext/csiphash.c +++ b/src/ext/csiphash.c @@ -132,3 +132,17 @@ uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *k return (v0 ^ v1) ^ (v2 ^ v3); } + +static int the_siphash_key_is_set = 0; +static struct sipkey the_siphash_key; + +uint64_t siphash24g(const void *src, unsigned long src_sz) { + return siphash24(src, src_sz, &the_siphash_key); +} + +void siphash_set_global_key(const struct sipkey *key) +{ + the_siphash_key.k0 = key->k0; + the_siphash_key.k1 = key->k1; + the_siphash_key_is_set = 1; +} diff --git a/src/ext/siphash.h b/src/ext/siphash.h index ff372bc..964fe7d 100644 --- a/src/ext/siphash.h +++ b/src/ext/siphash.h @@ -6,4 +6,7 @@ struct sipkey { }; uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key); +void siphash_set_global_key(const struct sipkey *key); +uint64_t siphash24g(const void *src, unsigned long src_sz); + #endif

1 0

[tor/master] Raw import of Marek Majkowski's cisphash.c
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit f4656c0cc9c13d3ba9d069f97771e98f160a87f8 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 10:09:45 2014 -0500 Raw import of Marek Majkowski's cisphash.c siphash is a hash function designed for producing hard-to-predict 64-bit outputs from short inputs and a 128-bit key. It's chosen for security and speed. See https://131002.net/siphash/ for more information on siphash. Source: https://github.com/majek/csiphash/ --- LICENSE | 23 +++++++++++ src/ext/csiphash.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 138 insertions(+) diff --git a/LICENSE b/LICENSE index 8a6fcca..4ebab18 100644 --- a/LICENSE +++ b/LICENSE @@ -101,6 +101,29 @@ src/ext/tor_queue.h is licensed under the following license: * SUCH DAMAGE. =============================================================================== +src/ext/csiphash.c is licensed under the following license: + + Copyright (c) 2013 Marek Majkowski <marek(a)popcount.org> + + Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + + The above copyright notice and this permission notice shall be included in + all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + THE SOFTWARE. + +=============================================================================== src/config/geoip is licensed under the following license: OPEN DATA LICENSE (GeoLite Country and GeoLite City databases) diff --git a/src/ext/csiphash.c b/src/ext/csiphash.c new file mode 100644 index 0000000..0633977 --- /dev/null +++ b/src/ext/csiphash.c @@ -0,0 +1,115 @@ +/* <MIT License> + Copyright (c) 2013 Marek Majkowski <marek(a)popcount.org> + + Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + + The above copyright notice and this permission notice shall be included in + all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + THE SOFTWARE. + </MIT License> + + Original location: + https://github.com/majek/csiphash/ + + Solution inspired by code from: + Samuel Neves (supercop/crypto_auth/siphash24/little) + djb (supercop/crypto_auth/siphash24/little2) + Jean-Philippe Aumasson (https://131002.net/siphash/siphash24.c) +*/ + +#include <stdint.h> + +#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \ + __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ +# define _le64toh(x) ((uint64_t)(x)) +#elif defined(_WIN32) +/* Windows is always little endian, unless you're on xbox360 + http://msdn.microsoft.com/en-us/library/b0084kay(v=vs.80).aspx */ +# define _le64toh(x) ((uint64_t)(x)) +#elif defined(__APPLE__) +# include <libkern/OSByteOrder.h> +# define _le64toh(x) OSSwapLittleToHostInt64(x) +#else + +/* See: http://sourceforge.net/p/predef/wiki/Endianness/ */ +# if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) +# include <sys/endian.h> +# else +# include <endian.h> +# endif +# if defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ + __BYTE_ORDER == __LITTLE_ENDIAN +# define _le64toh(x) ((uint64_t)(x)) +# else +# define _le64toh(x) le64toh(x) +# endif + +#endif + + +#define ROTATE(x, b) (uint64_t)( ((x) << (b)) | ( (x) >> (64 - (b))) ) + +#define HALF_ROUND(a,b,c,d,s,t) \ + a += b; c += d; \ + b = ROTATE(b, s) ^ a; \ + d = ROTATE(d, t) ^ c; \ + a = ROTATE(a, 32); + +#define DOUBLE_ROUND(v0,v1,v2,v3) \ + HALF_ROUND(v0,v1,v2,v3,13,16); \ + HALF_ROUND(v2,v1,v0,v3,17,21); \ + HALF_ROUND(v0,v1,v2,v3,13,16); \ + HALF_ROUND(v2,v1,v0,v3,17,21); + + +uint64_t siphash24(const void *src, unsigned long src_sz, const char key[16]) { + const uint64_t *_key = (uint64_t *)key; + uint64_t k0 = _le64toh(_key[0]); + uint64_t k1 = _le64toh(_key[1]); + uint64_t b = (uint64_t)src_sz << 56; + const uint64_t *in = (uint64_t*)src; + + uint64_t v0 = k0 ^ 0x736f6d6570736575ULL; + uint64_t v1 = k1 ^ 0x646f72616e646f6dULL; + uint64_t v2 = k0 ^ 0x6c7967656e657261ULL; + uint64_t v3 = k1 ^ 0x7465646279746573ULL; + + while (src_sz >= 8) { + uint64_t mi = _le64toh(*in); + in += 1; src_sz -= 8; + v3 ^= mi; + DOUBLE_ROUND(v0,v1,v2,v3); + v0 ^= mi; + } + + uint64_t t = 0; uint8_t *pt = (uint8_t *)&t; uint8_t *m = (uint8_t *)in; + switch (src_sz) { + case 7: pt[6] = m[6]; + case 6: pt[5] = m[5]; + case 5: pt[4] = m[4]; + case 4: *((uint32_t*)&pt[0]) = *((uint32_t*)&m[0]); break; + case 3: pt[2] = m[2]; + case 2: pt[1] = m[1]; + case 1: pt[0] = m[0]; + } + b |= _le64toh(t); + + v3 ^= b; + DOUBLE_ROUND(v0,v1,v2,v3); + v0 ^= b; v2 ^= 0xff; + DOUBLE_ROUND(v0,v1,v2,v3); + DOUBLE_ROUND(v0,v1,v2,v3); + return (v0 ^ v1) ^ (v2 ^ v3); +}

1 0

[tor/master] Siphash-2-4 is now our hash in nearly all cases.
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit 0e97c8e23e2572c14dd0f4f4fbfca77ee8a48be2 Author: Nick Mathewson <nickm(a)torproject.org> Date: Fri Feb 7 17:38:16 2014 -0500 Siphash-2-4 is now our hash in nearly all cases. I've made an exception for cases where I'm sure that users can't influence the inputs. This is likely to cause a slowdown somewhere, but it's safer to siphash everything and *then* look for cases to optimize. This patch doesn't actually get us any _benefit_ from siphash yet, since we don't really randomize the key at any point. --- src/common/address.c | 38 +++++++++++++++++++++++++++++++------- src/common/address.h | 3 ++- src/common/container.c | 10 ++-------- src/common/container.h | 21 +++++++++++---------- src/ext/siphash.h | 1 + src/or/channel.c | 7 +------ src/or/dns.c | 2 +- src/or/fp_pair.c | 13 ++----------- src/or/geoip.c | 8 +++++--- src/or/microdesc.c | 7 +------ src/or/nodelist.c | 9 +-------- src/or/policies.c | 30 +++++++++++++++++------------- 12 files changed, 75 insertions(+), 74 deletions(-) diff --git a/src/common/address.c b/src/common/address.c index b9f2d93..69049fa 100644 --- a/src/common/address.c +++ b/src/common/address.c @@ -874,6 +874,32 @@ tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src) memcpy(dest, src, sizeof(tor_addr_t)); } +/** Copy a tor_addr_t from src to dest, taking extra case to + * copy only the well-defined portions. Used for computing hashes of + * addresses. + */ +void +tor_addr_copy_tight(tor_addr_t *dest, const tor_addr_t *src) +{ + tor_assert(src != dest); + tor_assert(src); + tor_assert(dest); + memset(dest, 0, sizeof(tor_addr_t)); + dest->family = src->family; + switch (tor_addr_family(src)) + { + case AF_INET: + dest->addr.in_addr.s_addr = src->addr.in_addr.s_addr; + break; + case AF_INET6: + memcpy(dest->addr.in6_addr.s6_addr, src->addr.in6_addr.s6_addr, 16); + case AF_UNSPEC: + break; + default: + tor_fragile_assert(); + } +} + /** Given two addresses addr1 and addr2, return 0 if the two * addresses are equivalent under the mask mbits, less than 0 if addr1 * precedes addr2, and greater than 0 otherwise. @@ -995,19 +1021,17 @@ tor_addr_compare_masked(const tor_addr_t *addr1, const tor_addr_t *addr2, } } -/** Return a hash code based on the address addr */ -unsigned int +/** Return a hash code based on the address addr. DOCDOC extra */ +uint64_t tor_addr_hash(const tor_addr_t *addr) { switch (tor_addr_family(addr)) { case AF_INET: - return tor_addr_to_ipv4h(addr); + return siphash24g(&addr->addr.in_addr.s_addr, 4); case AF_UNSPEC: return 0x4e4d5342; - case AF_INET6: { - const uint32_t *u = tor_addr_to_in6_addr32(addr); - return u[0] + u[1] + u[2] + u[3]; - } + case AF_INET6: + return siphash24g(&addr->addr.in6_addr.s6_addr, 16); default: tor_fragile_assert(); return 0; diff --git a/src/common/address.h b/src/common/address.h index 77e5855..d41c2f5 100644 --- a/src/common/address.h +++ b/src/common/address.h @@ -167,7 +167,7 @@ int tor_addr_compare_masked(const tor_addr_t *addr1, const tor_addr_t *addr2, * "exactly". */ #define tor_addr_eq(a,b) (0==tor_addr_compare((a),(b),CMP_EXACT)) -unsigned int tor_addr_hash(const tor_addr_t *addr); +uint64_t tor_addr_hash(const tor_addr_t *addr); int tor_addr_is_v4(const tor_addr_t *addr); int tor_addr_is_internal_(const tor_addr_t *ip, int for_listening, const char *filename, int lineno); @@ -192,6 +192,7 @@ const char * tor_addr_to_str(char *dest, const tor_addr_t *addr, size_t len, int decorate); int tor_addr_parse(tor_addr_t *addr, const char *src); void tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src); +void tor_addr_copy_tight(tor_addr_t *dest, const tor_addr_t *src); void tor_addr_from_ipv4n(tor_addr_t *dest, uint32_t v4addr); /** Set dest to the IPv4 address encoded in v4addr in host * order. */ diff --git a/src/common/container.c b/src/common/container.c index 476dc82..f489430 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -1004,7 +1004,7 @@ strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b) static INLINE unsigned int strmap_entry_hash(const strmap_entry_t *a) { - return ht_string_hash(a->key); + return (unsigned) siphash24g(a->key, strlen(a->key)); } /** Helper: compare digestmap_entry_t objects by key value. */ @@ -1018,13 +1018,7 @@ digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b) static INLINE unsigned int digestmap_entry_hash(const digestmap_entry_t *a) { -#if SIZEOF_INT != 8 - const uint32_t *p = (const uint32_t*)a->key; - return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]; -#else - const uint64_t *p = (const uint64_t*)a->key; - return p[0] ^ p[1]; -#endif + return (unsigned) siphash24g(a->key, DIGEST_LEN); } HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, diff --git a/src/common/container.h b/src/common/container.h index 1bcc540..a4691a7 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -7,6 +7,7 @@ #define TOR_CONTAINER_H #include "util.h" +#include "siphash.h" /** A resizeable list of pointers, with associated helpful functionality. * @@ -610,11 +611,11 @@ typedef struct { static INLINE void digestset_add(digestset_t *set, const char *digest) { - const uint32_t *p = (const uint32_t *)digest; - const uint32_t d1 = p[0] + (p[1]>>16); - const uint32_t d2 = p[1] + (p[2]>>16); - const uint32_t d3 = p[2] + (p[3]>>16); - const uint32_t d4 = p[3] + (p[0]>>16); + const uint64_t x = siphash24g(digest, 20); + const uint32_t d1 = (uint32_t) x; + const uint32_t d2 = (uint32_t)( (x>>16) + x); + const uint32_t d3 = (uint32_t)( (x>>32) + x); + const uint32_t d4 = (uint32_t)( (x>>48) + x); bitarray_set(set->ba, BIT(d1)); bitarray_set(set->ba, BIT(d2)); bitarray_set(set->ba, BIT(d3)); @@ -626,11 +627,11 @@ digestset_add(digestset_t *set, const char *digest) static INLINE int digestset_contains(const digestset_t *set, const char *digest) { - const uint32_t *p = (const uint32_t *)digest; - const uint32_t d1 = p[0] + (p[1]>>16); - const uint32_t d2 = p[1] + (p[2]>>16); - const uint32_t d3 = p[2] + (p[3]>>16); - const uint32_t d4 = p[3] + (p[0]>>16); + const uint64_t x = siphash24g(digest, 20); + const uint32_t d1 = (uint32_t) x; + const uint32_t d2 = (uint32_t)( (x>>16) + x); + const uint32_t d3 = (uint32_t)( (x>>32) + x); + const uint32_t d4 = (uint32_t)( (x>>48) + x); return bitarray_is_set(set->ba, BIT(d1)) && bitarray_is_set(set->ba, BIT(d2)) && bitarray_is_set(set->ba, BIT(d3)) && diff --git a/src/ext/siphash.h b/src/ext/siphash.h index 964fe7d..d9b34b8 100644 --- a/src/ext/siphash.h +++ b/src/ext/siphash.h @@ -1,5 +1,6 @@ #ifndef SIPHASH_H #define SIPHASH_H + struct sipkey { uint64_t k0; uint64_t k1; diff --git a/src/or/channel.c b/src/or/channel.c index a345bab..9f68875 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -95,12 +95,7 @@ typedef struct channel_idmap_entry_s { static INLINE unsigned channel_idmap_hash(const channel_idmap_entry_t *ent) { - const unsigned *a = (const unsigned *)ent->digest; -#if SIZEOF_INT == 4 - return a[0] ^ a[1] ^ a[2] ^ a[3] ^ a[4]; -#elif SIZEOF_INT == 8 - return a[0] ^ a[1]; -#endif + return (unsigned) siphash24g(ent->digest, DIGEST_LEN); } static INLINE int diff --git a/src/or/dns.c b/src/or/dns.c index a1fe0de..a88a46e 100644 --- a/src/or/dns.c +++ b/src/or/dns.c @@ -239,7 +239,7 @@ cached_resolves_eq(cached_resolve_t *a, cached_resolve_t *b) static INLINE unsigned int cached_resolve_hash(cached_resolve_t *a) { - return ht_string_hash(a->address); + return (unsigned) siphash24g((const uint8_t*)a->address, strlen(a->address)); } HT_PROTOTYPE(cache_map, cached_resolve_t, node, cached_resolve_hash, diff --git a/src/or/fp_pair.c b/src/or/fp_pair.c index 4d8a835..55e4c89 100644 --- a/src/or/fp_pair.c +++ b/src/or/fp_pair.c @@ -32,17 +32,8 @@ fp_pair_map_entries_eq(const fp_pair_map_entry_t *a, static INLINE unsigned int fp_pair_map_entry_hash(const fp_pair_map_entry_t *a) { - const uint32_t *p; - unsigned int hash; - - p = (const uint32_t *)(a->key.first); - /* Hashes are 20 bytes long, so 5 times uint32_t */ - hash = p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]; - /* Now XOR in the second fingerprint */ - p = (const uint32_t *)(a->key.second); - hash ^= p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]; - - return hash; + tor_assert(sizeof(a->key) == DIGEST_LEN*2); + return (unsigned) siphash24g(&a->key, DIGEST_LEN*2); } /* diff --git a/src/or/geoip.c b/src/or/geoip.c index dc4730c..6088f5d 100644 --- a/src/or/geoip.c +++ b/src/or/geoip.c @@ -486,10 +486,12 @@ static HT_HEAD(clientmap, clientmap_entry_t) client_history = static INLINE unsigned clientmap_entry_hash(const clientmap_entry_t *a) { - unsigned h = tor_addr_hash(&a->addr); + unsigned h = (unsigned) tor_addr_hash(&a->addr); + if (a->transport_name) - h += ht_string_hash(a->transport_name); - return ht_improve_hash(h); + h += (unsigned) siphash24g(a->transport_name, strlen(a->transport_name)); + + return h; } /** Hashtable helper: compare two clientmap_entry_t values for equality. */ static INLINE int diff --git a/src/or/microdesc.c b/src/or/microdesc.c index 1124991..8052ca9 100644 --- a/src/or/microdesc.c +++ b/src/or/microdesc.c @@ -45,12 +45,7 @@ struct microdesc_cache_t { static INLINE unsigned int microdesc_hash_(microdesc_t *md) { - unsigned *d = (unsigned*)md->digest; -#if SIZEOF_INT == 4 - return d[0] ^ d[1] ^ d[2] ^ d[3] ^ d[4] ^ d[5] ^ d[6] ^ d[7]; -#else - return d[0] ^ d[1] ^ d[2] ^ d[3]; -#endif + return (unsigned) siphash24g(md->digest, sizeof(md->digest)); } /** Helper: compares a and for equality for hash-table purposes. */ diff --git a/src/or/nodelist.c b/src/or/nodelist.c index 402fb2e..03fa836 100644 --- a/src/or/nodelist.c +++ b/src/or/nodelist.c @@ -43,14 +43,7 @@ typedef struct nodelist_t { static INLINE unsigned int node_id_hash(const node_t *node) { -#if SIZEOF_INT == 4 - const uint32_t *p = (const uint32_t*)node->identity; - return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]; -#elif SIZEOF_INT == 8 - const uint64_t *p = (const uint32_t*)node->identity; - const uint32_t *p32 = (const uint32_t*)node->identity; - return p[0] ^ p[1] ^ p32[4]; -#endif + return (unsigned) siphash24g(node->identity, DIGEST_LEN); } static INLINE unsigned int diff --git a/src/or/policies.c b/src/or/policies.c index be4da55..05377ec 100644 --- a/src/or/policies.c +++ b/src/or/policies.c @@ -597,21 +597,25 @@ policy_eq(policy_map_ent_t *a, policy_map_ent_t *b) /** Return a hashcode for ent */ static unsigned int -policy_hash(policy_map_ent_t *ent) +policy_hash(const policy_map_ent_t *ent) { - addr_policy_t *a = ent->policy; - unsigned int r; - if (a->is_private) - r = 0x1234abcd; - else - r = tor_addr_hash(&a->addr); - r += a->prt_min << 8; - r += a->prt_max << 16; - r += a->maskbits; - if (a->policy_type == ADDR_POLICY_REJECT) - r ^= 0xffffffff; + const addr_policy_t *a = ent->policy; + addr_policy_t aa; + memset(&aa, 0, sizeof(aa)); + + aa.prt_min = a->prt_min; + aa.prt_max = a->prt_max; + aa.maskbits = a->maskbits; + aa.policy_type = a->policy_type; + aa.is_private = a->is_private; + + if (a->is_private) { + aa.is_private = 1; + } else { + tor_addr_copy_tight(&aa.addr, &a->addr); + } - return r; + return (unsigned) siphash24g(&aa, sizeof(aa)); } HT_PROTOTYPE(policy_map, policy_map_ent_t, node, policy_hash,

1 0

[tor/master] Split crypto_global_init() into pre/post config
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit d3fb846d8c98c13d349762682e714e8312f20270 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 11:56:29 2014 -0500 Split crypto_global_init() into pre/post config It's increasingly apparent that we want to make sure we initialize our PRNG nice and early, or else OpenSSL will do it for us. (OpenSSL doesn't do _too_ bad a job, but it's nice to do it ourselves.) We'll also need this for making sure we initialize the siphash key before we do any hashes. --- src/common/crypto.c | 54 +++++++++++++++++++++++++++++++++++++++++---------- src/common/crypto.h | 1 + src/or/main.c | 7 +++++++ 3 files changed, 52 insertions(+), 10 deletions(-) diff --git a/src/common/crypto.c b/src/common/crypto.c index 9bdb1f4..13095ad 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -132,6 +132,9 @@ crypto_get_rsa_padding(int padding) } /** Boolean: has OpenSSL's crypto been initialized? */ +static int crypto_early_initialized_ = 0; + +/** Boolean: has OpenSSL's crypto been initialized? */ static int crypto_global_initialized_ = 0; /** Log all pending crypto errors at level severity. Use @@ -242,15 +245,31 @@ crypto_openssl_get_header_version_str(void) return crypto_openssl_header_version_str; } -/** Initialize the crypto library. Return 0 on success, -1 on failure. +/** Make sure that openssl is using its default PRNG. Return 1 if we had to + * adjust it; 0 otherwise. */ +static int +crypto_force_rand_ssleay(void) +{ + if (RAND_get_rand_method() != RAND_SSLeay()) { + log_notice(LD_CRYPTO, "It appears that one of our engines has provided " + "a replacement the OpenSSL RNG. Resetting it to the default " + "implementation."); + RAND_set_rand_method(RAND_SSLeay()); + return 1; + } + return 0; +} + +/** Initialize the parts of the crypto library that don't depend on + * settings or options. Return 0 on success, -1 on failure. */ int -crypto_global_init(int useAccel, const char *accelName, const char *accelDir) +crypto_early_init(void) { - if (!crypto_global_initialized_) { + if (!crypto_early_initialized_) { ERR_load_crypto_strings(); OpenSSL_add_all_algorithms(); - crypto_global_initialized_ = 1; + setup_openssl_threading(); if (SSLeay() == OPENSSL_VERSION_NUMBER && @@ -272,6 +291,24 @@ crypto_global_init(int useAccel, const char *accelName, const char *accelDir) crypto_openssl_get_version_str()); } + crypto_force_rand_ssleay(); + + if (crypto_seed_rng(1) < 0) + return -1; + } + return 0; +} + +/** Initialize the crypto library. Return 0 on success, -1 on failure. + */ +int +crypto_global_init(int useAccel, const char *accelName, const char *accelDir) +{ + if (!crypto_global_initialized_) { + crypto_early_init(); + + crypto_global_initialized_ = 1; + if (useAccel > 0) { #ifdef DISABLE_ENGINES (void)accelName; @@ -335,17 +372,14 @@ crypto_global_init(int useAccel, const char *accelName, const char *accelDir) log_info(LD_CRYPTO, "NOT using OpenSSL engine support."); } - if (RAND_get_rand_method() != RAND_SSLeay()) { - log_notice(LD_CRYPTO, "It appears that one of our engines has provided " - "a replacement the OpenSSL RNG. Resetting it to the default " - "implementation."); - RAND_set_rand_method(RAND_SSLeay()); + if (crypto_force_rand_ssleay()) { + if (crypto_seed_rng(1) < 0) + return -1; } evaluate_evp_for_aes(-1); evaluate_ctr_for_aes(); - return crypto_seed_rng(1); } return 0; } diff --git a/src/common/crypto.h b/src/common/crypto.h index 6ce3697..79a8a1b 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -110,6 +110,7 @@ typedef struct crypto_dh_t crypto_dh_t; /* global state */ const char * crypto_openssl_get_version_str(void); const char * crypto_openssl_get_header_version_str(void); +int crypto_early_init(void); int crypto_global_init(int hardwareAccel, const char *accelName, const char *accelPath); diff --git a/src/or/main.c b/src/or/main.c index a970e35..526f000 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -2329,6 +2329,13 @@ tor_init(int argc, char *argv[]) /* Have the log set up with our application name. */ tor_snprintf(progname, sizeof(progname), "Tor %s", get_version()); log_set_application_name(progname); + + /* Set up the crypto nice and early */ + if (crypto_early_init() < 0) { + log_err(LD_GENERAL, "Unable to initialize the crypto subsystem!"); + return 1; + } + /* Initialize the history structures. */ rep_hist_init(); /* Initialize the service cache. */

1 0

[tor/master] Changes file for feature4900
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit 10d1b0b33ed73d9696d1695196bf397ccaab31d9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 12:20:29 2014 -0500 Changes file for feature4900 --- changes/feature4900 | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/changes/feature4900 b/changes/feature4900 new file mode 100644 index 0000000..378ce12 --- /dev/null +++ b/changes/feature4900 @@ -0,0 +1,12 @@ + o Minor features: + + - Avoid hash-flooding denial-of-service attacks by using the secure + SipHash-2-4 hash function for our hashtables. Without this + feature, an attacker could degrade performance of a targeted + client or server by flooding their data structures with a large + number of data entries all calculated to be stored at the same + hash table position, thereby degrading hash table + performance. With this feature, hash table positions are derived + from a randomized cryptographic key using SipHash-2-4, and an + attacker cannot predict which entries will collide. + Closes ticket 4900.

1 0

[tor/master] Randomize the global siphash key at startup
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit c1e98c8afe2973286f9bef28e760cbf95a2738fd Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Feb 12 11:46:58 2014 -0500 Randomize the global siphash key at startup This completes our conversion to using siphash for our hash functions. --- src/common/crypto.c | 22 +++++++++++++++++++--- src/common/crypto.h | 1 + src/ext/csiphash.c | 5 +++++ src/test/bench.c | 1 + 4 files changed, 26 insertions(+), 3 deletions(-) diff --git a/src/common/crypto.c b/src/common/crypto.c index 13095ad..49dc55a 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -260,8 +260,23 @@ crypto_force_rand_ssleay(void) return 0; } -/** Initialize the parts of the crypto library that don't depend on - * settings or options. Return 0 on success, -1 on failure. +/** Set up the siphash key if we haven't already done so. */ +int +crypto_init_siphash_key(void) +{ + static int have_seeded_siphash = 0; + struct sipkey key; + if (have_seeded_siphash) + return 0; + + if (crypto_rand((char*) &key, sizeof(key)) < 0) + return -1; + siphash_set_global_key(&key); + have_seeded_siphash = 1; + return 0; +} + +/** Initialize the crypto library. Return 0 on success, -1 on failure. */ int crypto_early_init(void) @@ -295,6 +310,8 @@ crypto_early_init(void) if (crypto_seed_rng(1) < 0) return -1; + if (crypto_init_siphash_key() < 0) + return -1; } return 0; } @@ -379,7 +396,6 @@ crypto_global_init(int useAccel, const char *accelName, const char *accelDir) evaluate_evp_for_aes(-1); evaluate_ctr_for_aes(); - } return 0; } diff --git a/src/common/crypto.h b/src/common/crypto.h index 79a8a1b..3666d5f 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -257,6 +257,7 @@ uint64_t crypto_rand_uint64(uint64_t max); double crypto_rand_double(void); struct tor_weak_rng_t; void crypto_seed_weak_rng(struct tor_weak_rng_t *rng); +int crypto_init_siphash_key(void); char *crypto_random_hostname(int min_rand_len, int max_rand_len, const char *prefix, const char *suffix); diff --git a/src/ext/csiphash.c b/src/ext/csiphash.c index 9a8833d..30be40b 100644 --- a/src/ext/csiphash.c +++ b/src/ext/csiphash.c @@ -31,6 +31,9 @@ #include "torint.h" #include "siphash.h" +/* for tor_assert */ +#include "util.h" +/* for memcpy */ #include <string.h> #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \ @@ -137,11 +140,13 @@ static int the_siphash_key_is_set = 0; static struct sipkey the_siphash_key; uint64_t siphash24g(const void *src, unsigned long src_sz) { + tor_assert(the_siphash_key_is_set); return siphash24(src, src_sz, &the_siphash_key); } void siphash_set_global_key(const struct sipkey *key) { + tor_assert(! the_siphash_key_is_set); the_siphash_key.k0 = key->k0; the_siphash_key.k1 = key->k1; the_siphash_key_is_set = 1; diff --git a/src/test/bench.c b/src/test/bench.c index ae311b5..c9cc101 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -544,6 +544,7 @@ main(int argc, const char **argv) reset_perftime(); crypto_seed_rng(1); + crypto_init_siphash_key(); options = options_new(); init_logging(); options->command = CMD_RUN_UNITTESTS;

1 0

[tor/master] Merge branch 'bug4900_siphash_v2'
by nickm＠torproject.org 15 Feb '14

15 Feb '14

1 0

[tor/master] Remove string hash in ht.h so we can't accidentally use it
by nickm＠torproject.org 15 Feb '14

15 Feb '14

commit 1ad6dd0dbee7c757ef5f2f2d38b846ab7d991fb2 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat Feb 15 15:45:38 2014 -0500 Remove string hash in ht.h so we can't accidentally use it --- src/ext/ht.h | 2 ++ 1 file changed, 2 insertions(+) diff --git a/src/ext/ht.h b/src/ext/ht.h index 669a2ed..8bf9b80 100644 --- a/src/ext/ht.h +++ b/src/ext/ht.h @@ -86,6 +86,7 @@ ht_string_hash(const char *s) } #endif +#if 0 /** Basic string hash function, from Python's str.__hash__() */ static INLINE unsigned ht_string_hash(const char *s) @@ -100,6 +101,7 @@ ht_string_hash(const char *s) h ^= (unsigned)(cp-(const unsigned char*)s); return h; } +#endif #ifndef HT_NO_CACHE_HASH_VALUES #define HT_SET_HASH_(elm, field, hashfn) \

1 0