commit e2b744ce38edb8901cff3288634c4ebb5b4568b9 Merge: 12afdcc15 14b507e52 Author: Nick Mathewson nickm@torproject.org Date: Tue Jul 17 16:19:32 2018 -0400
Merge branch 'bug25552_ope_squashed'
changes/bug25552 | 5 + src/feature/dircommon/voting_schedule.c | 2 +- src/feature/hs/hs_common.c | 3 +- src/feature/hs/hs_service.c | 309 +++++++++------------------ src/feature/hs/hs_service.h | 14 +- src/feature/hs_common/shared_random_client.c | 36 +++- src/feature/hs_common/shared_random_client.h | 3 +- src/lib/crypt_ops/crypto_ope.c | 185 ++++++++++++++++ src/lib/crypt_ops/crypto_ope.h | 46 ++++ src/lib/crypt_ops/include.am | 2 + src/test/include.am | 1 + src/test/ope_ref.py | 40 ++++ src/test/test.c | 1 + src/test/test.h | 1 + src/test/test_crypto_ope.c | 152 +++++++++++++ src/test/test_hs_common.c | 12 +- src/test/test_hs_service.c | 82 ++----- src/test/test_shared_random.c | 14 +- 18 files changed, 605 insertions(+), 303 deletions(-)
diff --cc src/feature/hs/hs_service.c index 8b4de2138,560f48fb5..54204dd07 --- a/src/feature/hs/hs_service.c +++ b/src/feature/hs/hs_service.c @@@ -8,48 -8,44 +8,49 @@@
#define HS_SERVICE_PRIVATE
-#include "or/or.h" -#include "or/circpathbias.h" -#include "or/circuitbuild.h" -#include "or/circuitlist.h" -#include "or/circuituse.h" -#include "or/config.h" -#include "or/connection.h" +#include "core/or/or.h" +#include "feature/client/circpathbias.h" +#include "core/or/circuitbuild.h" +#include "core/or/circuitlist.h" +#include "core/or/circuituse.h" +#include "app/config/config.h" +#include "core/mainloop/connection.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" -#include "or/directory.h" -#include "or/main.h" -#include "or/networkstatus.h" -#include "or/nodelist.h" -#include "or/relay.h" -#include "or/rendservice.h" -#include "or/router.h" -#include "or/routerkeys.h" -#include "or/routerlist.h" -#include "or/shared_random_client.h" -#include "or/statefile.h" - -#include "or/hs_circuit.h" -#include "or/hs_common.h" -#include "or/hs_config.h" -#include "or/hs_control.h" -#include "or/hs_descriptor.h" -#include "or/hs_ident.h" -#include "or/hs_intropoint.h" -#include "or/hs_service.h" -#include "or/hs_stats.h" - -#include "or/dir_connection_st.h" -#include "or/edge_connection_st.h" -#include "or/extend_info_st.h" -#include "or/networkstatus_st.h" -#include "or/node_st.h" -#include "or/origin_circuit_st.h" -#include "or/routerstatus_st.h" ++#include "lib/crypt_ops/crypto_ope.h" +#include "feature/dircache/directory.h" +#include "core/mainloop/main.h" +#include "feature/nodelist/networkstatus.h" +#include "feature/nodelist/nodelist.h" +#include "core/or/relay.h" +#include "feature/rend/rendservice.h" +#include "feature/relay/router.h" +#include "feature/relay/routerkeys.h" +#include "feature/nodelist/routerlist.h" +#include "feature/hs_common/shared_random_client.h" +#include "app/config/statefile.h" + +#include "feature/hs/hs_circuit.h" +#include "feature/hs/hs_common.h" +#include "feature/hs/hs_config.h" +#include "feature/hs/hs_control.h" +#include "feature/hs/hs_descriptor.h" +#include "feature/hs/hs_ident.h" +#include "feature/hs/hs_intropoint.h" +#include "feature/hs/hs_service.h" +#include "feature/hs/hs_stats.h" + +#include "feature/dircommon/dir_connection_st.h" +#include "core/or/edge_connection_st.h" +#include "core/or/extend_info_st.h" +#include "feature/nodelist/networkstatus_st.h" +#include "feature/nodelist/node_st.h" +#include "core/or/origin_circuit_st.h" +#include "app/config/or_state_st.h" +#include "feature/nodelist/routerstatus_st.h" + +#include "lib/encoding/confline.h" +#include "lib/crypt_ops/crypto_format.h"
/* Trunnel */ #include "trunnel/ed25519_cert.h" diff --cc src/feature/hs/hs_service.h index 22bfcacc2,e1f125d76..4cd05e389 --- a/src/feature/hs/hs_service.h +++ b/src/feature/hs/hs_service.h @@@ -131,6 -131,10 +131,10 @@@ typedef struct hs_service_descriptor_t * from this list, this means we received new dirinfo and we need to * reupload our descriptor. */ smartlist_t *previous_hsdirs; + + /** The OPE cipher for encrypting revision counters for this descriptor. + * Tied to the descriptor blinded key. */ - crypto_ope_t *ope_cipher; ++ struct crypto_ope_t *ope_cipher; } hs_service_descriptor_t;
/* Service key material. */ @@@ -375,4 -370,4 +370,3 @@@ STATIC int service_desc_hsdirs_changed( #endif /* defined(HS_SERVICE_PRIVATE) */
#endif /* !defined(TOR_HS_SERVICE_H) */ -- diff --cc src/lib/crypt_ops/crypto_ope.c index 000000000,644f3bae4..ca42ae434 mode 000000,100644..100644 --- a/src/lib/crypt_ops/crypto_ope.c +++ b/src/lib/crypt_ops/crypto_ope.c @@@ -1,0 -1,180 +1,185 @@@ + /* Copyright (c) 2018, The Tor Project, Inc. */ + /* See LICENSE for licensing information */ + + /** + * A rudimentary order-preserving encryption scheme. + * + * To compute the encryption of N, this scheme uses an AES-CTR stream to + * generate M-byte values, and adds the first N of them together. (+1 each to + * insure that the ciphertexts are strictly decreasing.) + * + * We use this for generating onion service revision counters based on the + * current time, without leaking the amount of skew in our view of the current + * time. MUCH more analysis would be needed before using it for anything + * else! + */ + + #include "orconfig.h" -#include "crypto.h" + + #define CRYPTO_OPE_PRIVATE ++#include "lib/crypt_ops/crypto_ope.h" ++#include "lib/crypt_ops/crypto.h" ++#include "lib/crypt_ops/crypto_util.h" ++#include "lib/log/util_bug.h" ++#include "lib/malloc/malloc.h" ++#include "lib/arch/bytes.h" ++ ++#include <string.h> + -#include "crypto_ope.h" + /** + * How infrequent should the precomputed values be for this encryption? + * The choice of this value creates a space/time tradeoff. + * + * Note that this value must be a multiple of 16; see + * ope_get_cipher() + */ + #define SAMPLE_INTERVAL 1024 + /** Number of precomputed samples to make for each OPE key. */ + #define N_SAMPLES (OPE_INPUT_MAX / SAMPLE_INTERVAL) + -struct crypto_ope_c { ++struct crypto_ope_t { + /** An AES key for use with this object. */ + uint8_t key[OPE_KEY_LEN]; + /** Cached intermediate encryption values at SAMPLE_INTERVAL, + * SAMPLE_INTERVAL*2,...SAMPLE_INTERVAL*N_SAMPLES */ + uint64_t samples[N_SAMPLES]; + }; + + /** The type to add up in order to produce our OPE ciphertexts */ + typedef uint16_t ope_val_t; + + #ifdef WORDS_BIG_ENDIAN + /** Convert an OPE value to little-endian */ + static inline ope_val_t + ope_val_to_le(ope_val_t x) + { + return + ((x) >> 8) | + (((x)&0xff) << 8); + } + #else + #define ope_val_to_le(x) (x) + #endif + + /** + * Return a new AES256-CTR stream cipher object for <b>ope</b>, ready to yield + * bytes from the stream at position <b>initial_idx</b>. + * + * Note that because the index is converted directly to an IV, it must be a + * multiple of the AES block size (16). + */ + STATIC crypto_cipher_t * + ope_get_cipher(const crypto_ope_t *ope, uint32_t initial_idx) + { + uint8_t iv[CIPHER_IV_LEN]; + tor_assert((initial_idx & 0xf) == 0); - uint32_t n = htonl(initial_idx >> 4); ++ uint32_t n = tor_htonl(initial_idx >> 4); + memset(iv, 0, sizeof(iv)); + memcpy(iv + CIPHER_IV_LEN - sizeof(n), &n, sizeof(n)); + + return crypto_cipher_new_with_iv_and_bits(ope->key, + iv, + OPE_KEY_LEN * 8); + } + + /** + * Retrieve and add the next <b>n</b> values from the stream cipher <b>c</b>, + * and return their sum. + * + * Note that values are taken in little-endian order (for performance on + * prevalent hardware), and are mapped from range 0..2^n-1 to range 1..2^n (so + * that each input encrypts to a different output). + * + * NOTE: this function is not constant-time. + */ + STATIC uint64_t + sum_values_from_cipher(crypto_cipher_t *c, size_t n) + { + #define BUFSZ 256 + ope_val_t buf[BUFSZ]; + uint64_t total = 0; + unsigned i; + while (n >= BUFSZ) { + memset(buf, 0, sizeof(buf)); + crypto_cipher_crypt_inplace(c, (char*)buf, BUFSZ*sizeof(ope_val_t)); + + for (i = 0; i < BUFSZ; ++i) { + total += ope_val_to_le(buf[i]); + total += 1; + } + n -= BUFSZ; + } + + memset(buf, 0, n*sizeof(ope_val_t)); + crypto_cipher_crypt_inplace(c, (char*)buf, n*sizeof(ope_val_t)); + for (i = 0; i < n; ++i) { + total += ope_val_to_le(buf[i]); + total += 1; + } + + memset(buf, 0, sizeof(buf)); + return total; + } + + /** + * Return a new crypto_ope_t object, using the provided 256-bit key. + */ + crypto_ope_t * + crypto_ope_new(const uint8_t *key) + { + crypto_ope_t *ope = tor_malloc_zero(sizeof(crypto_ope_t)); + memcpy(ope->key, key, OPE_KEY_LEN); + + crypto_cipher_t *cipher = ope_get_cipher(ope, 0); + + uint64_t v = 0; + int i; + for (i = 0; i < N_SAMPLES; ++i) { + v += sum_values_from_cipher(cipher, SAMPLE_INTERVAL); + ope->samples[i] = v; + } + + crypto_cipher_free(cipher); + return ope; + } + + /** Free all storage held in <>ope</b>. */ + void + crypto_ope_free_(crypto_ope_t *ope) + { + if (!ope) + return; + memwipe(ope, 0, sizeof(*ope)); + tor_free(ope); + } + + /** + * Return the encrypted value corresponding to <b>input</b>. The input value + * must be in range 1..OPE_INPUT_MAX. Returns CRYPTO_OPE_ERROR on an invalid + * input. + * + * NOTE: this function is not constant-time. + */ + uint64_t + crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext) + { + if (plaintext <= 0 || plaintext > OPE_INPUT_MAX) + return CRYPTO_OPE_ERROR; + + const int sample_idx = (plaintext / SAMPLE_INTERVAL); + const int starting_iv = sample_idx * SAMPLE_INTERVAL; + const int remaining_values = plaintext - starting_iv; + uint64_t v; + if (sample_idx == 0) { + v = 0; + } else { + v = ope->samples[sample_idx - 1]; + } + crypto_cipher_t *cipher = ope_get_cipher(ope, starting_iv*sizeof(ope_val_t)); + + v += sum_values_from_cipher(cipher, remaining_values); + + crypto_cipher_free(cipher); + + return v; + } - diff --cc src/lib/crypt_ops/crypto_ope.h index 000000000,19ec3e495..c62ed2a94 mode 000000,100644..100644 --- a/src/lib/crypt_ops/crypto_ope.h +++ b/src/lib/crypt_ops/crypto_ope.h @@@ -1,0 -1,47 +1,46 @@@ + /* Copyright (c) 2018, The Tor Project, Inc. */ + /* See LICENSE for licensing information */ + + #ifndef CRYPTO_OPE_H + #define CRYPTO_OPE_H + + #include "orconfig.h" -#include "crypto.h" -#include "crypto_util.h" - -#include "crypto_ope.h" ++#include "lib/cc/torint.h" ++#include "lib/crypt_ops/crypto_ope.h" ++#include "lib/testsupport/testsupport.h" + + /** Length of OPE key, in bytes. */ + #define OPE_KEY_LEN 32 + + /** Largest value that can be passed to crypto_ope_encrypt(). + * + * Expressed as 2^18 because the OPE system prefers powers of two. + * + * The current max value stands for about 70 hours. The rationale here is as + * follows: The rev counter is the time of seconds since the start of an SRV + * period. SRVs are useful for about 48 hours (that's how long they stick + * around on the consensus). Let's also add 12 hours of drift for clock skewed + * services that might be using an old consensus and we arrive to 60 + * hours. The max value should be beyond that. + */ + #define OPE_INPUT_MAX (1<<18) + + #define CRYPTO_OPE_ERROR UINT64_MAX + -typedef struct crypto_ope_c crypto_ope_t; ++typedef struct crypto_ope_t crypto_ope_t; + + crypto_ope_t *crypto_ope_new(const uint8_t *key); + void crypto_ope_free_(crypto_ope_t *ope); + #define crypto_ope_free(ope) \ + FREE_AND_NULL(crypto_ope_t, crypto_ope_free_, (ope)) + + uint64_t crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext); + + #ifdef CRYPTO_OPE_PRIVATE -STATIC crypto_cipher_t *ope_get_cipher(const crypto_ope_t *ope, - uint32_t initial_idx); -STATIC uint64_t sum_values_from_cipher(crypto_cipher_t *c, size_t n); ++struct aes_cnt_cipher; ++STATIC struct aes_cnt_cipher *ope_get_cipher(const crypto_ope_t *ope, ++ uint32_t initial_idx); ++STATIC uint64_t sum_values_from_cipher(struct aes_cnt_cipher *c, size_t n); + #endif + + #endif - diff --cc src/lib/crypt_ops/include.am index 1b88b880d,6b0b0d200..017d7956d --- a/src/lib/crypt_ops/include.am +++ b/src/lib/crypt_ops/include.am @@@ -14,6 -14,7 +14,7 @@@ src_lib_libtor_crypt_ops_a_SOURCES = src/lib/crypt_ops/crypto_ed25519.c \ src/lib/crypt_ops/crypto_format.c \ src/lib/crypt_ops/crypto_hkdf.c \ - src/lib/crypt_ops/crypto_ope.c \ ++ src/lib/crypt_ops/crypto_ope.c \ src/lib/crypt_ops/crypto_openssl_mgt.c \ src/lib/crypt_ops/crypto_pwbox.c \ src/lib/crypt_ops/crypto_rand.c \ @@@ -38,6 -38,7 +39,7 @@@ noinst_HEADERS += src/lib/crypt_ops/crypto.h \ src/lib/crypt_ops/crypto_hkdf.h \ src/lib/crypt_ops/crypto_openssl_mgt.h \ - src/lib/crypt_ops/crypto_ope.h \ ++ src/lib/crypt_ops/crypto_ope.h \ src/lib/crypt_ops/crypto_pwbox.h \ src/lib/crypt_ops/crypto_rand.h \ src/lib/crypt_ops/crypto_rsa.h \ diff --cc src/test/test_crypto_ope.c index 000000000,1b93e6981..7dcad7b4b mode 000000,100644..100644 --- a/src/test/test_crypto_ope.c +++ b/src/test/test_crypto_ope.c @@@ -1,0 -1,148 +1,152 @@@ + /* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2017, The Tor Project, Inc. */ + /* See LICENSE for licensing information */ + + #include "orconfig.h" + + #define CRYPTO_OPE_PRIVATE + + #include "lib/crypt_ops/crypto_ope.h" -#include "common/util_format.h" ++#include "lib/crypt_ops/crypto.h" ++#include "lib/encoding/binascii.h" + #include "test/test.h" ++#include "tinytest.h" ++ ++#include <stddef.h> ++#include <string.h> + + static void + test_crypto_ope_consistency(void *arg) + { + (void)arg; + + crypto_ope_t *ope = NULL; + crypto_cipher_t *aes = NULL; + const int TEST_VALS[] = { 5, 500, 1023, 1024, 1025, 2046, 2047, 2048, 2049, + 10000, OPE_INPUT_MAX }; + unsigned i; + const uint8_t key[32] = "A fixed key, chosen arbitrarily."; + + ope = crypto_ope_new(key); + tt_assert(ope); + + uint64_t last_val = 0; + for (i = 0; i < ARRAY_LENGTH(TEST_VALS); ++i) { + aes = ope_get_cipher(ope, 0); + int val = TEST_VALS[i]; + uint64_t v1 = crypto_ope_encrypt(ope, val); + uint64_t v2 = sum_values_from_cipher(aes, val); + tt_u64_op(v1, OP_EQ, v2); + tt_u64_op(v2, OP_GT, last_val); + last_val = v2; + crypto_cipher_free(aes); + } + + done: + crypto_cipher_free(aes); + crypto_ope_free(ope); + } + + static void + test_crypto_ope_oob(void *arg) + { + (void)arg; + + crypto_ope_t *ope = NULL; + const uint8_t key[32] = "A fixed key, chosen arbitrarily."; + ope = crypto_ope_new(key); + + tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,INT_MIN)); + tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,-100)); + tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,0)); + tt_u64_op(UINT64_MAX, OP_NE, crypto_ope_encrypt(ope,1)); + tt_u64_op(UINT64_MAX, OP_NE, crypto_ope_encrypt(ope,7000)); + tt_u64_op(UINT64_MAX, OP_NE, crypto_ope_encrypt(ope,OPE_INPUT_MAX)); + tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,OPE_INPUT_MAX+1)); + tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,INT_MAX)); + done: + crypto_ope_free(ope); + } + + static const char OPE_TEST_KEY[] = + "19e05891d55232c08c2cad91d612fdb9cbd6691949a0742434a76c80bc6992fe"; + + /* generated by a separate python implementation. */ + static const struct { + int v; + uint64_t r; + } OPE_TEST_VECTORS[] = { + { 121132, UINT64_C(3971694514) }, + { 82283, UINT64_C(2695743564) }, + { 72661, UINT64_C(2381548866) }, + { 72941, UINT64_C(2390408421) }, + { 123122, UINT64_C(4036781069) }, + { 12154, UINT64_C(402067100) }, + { 121574, UINT64_C(3986197593) }, + { 11391, UINT64_C(376696838) }, + { 65845, UINT64_C(2161801517) }, + { 86301, UINT64_C(2828270975) }, + { 61284, UINT64_C(2013616892) }, + { 70505, UINT64_C(2313368870) }, + { 30438, UINT64_C(1001394664) }, + { 60150, UINT64_C(1977329668) }, + { 114800, UINT64_C(3764946628) }, + { 109403, UINT64_C(3585352477) }, + { 21893, UINT64_C(721388468) }, + { 123569, UINT64_C(4051780471) }, + { 95617, UINT64_C(3134921876) }, + { 48561, UINT64_C(1597596985) }, + { 53334, UINT64_C(1753691710) }, + { 92746, UINT64_C(3040874493) }, + { 7110, UINT64_C(234966492) }, + { 9612, UINT64_C(318326551) }, + { 106958, UINT64_C(3506124249) }, + { 46889, UINT64_C(1542219146) }, + { 87790, UINT64_C(2877361609) }, + { 68878, UINT64_C(2260369112) }, + { 47917, UINT64_C(1576681737) }, + { 121128, UINT64_C(3971553290) }, + { 108602, UINT64_C(3559176081) }, + { 28217, UINT64_C(929692460) }, + { 69498, UINT64_C(2280554161) }, + { 63870, UINT64_C(2098322675) }, + { 57542, UINT64_C(1891698992) }, + { 122148, UINT64_C(4004515805) }, + { 46254, UINT64_C(1521227949) }, + { 42850, UINT64_C(1408996941) }, + { 92661, UINT64_C(3037901517) }, + { 57720, UINT64_C(1897369989) }, + }; + + static void + test_crypto_ope_vectors(void *arg) + { + (void)arg; + uint8_t key[32]; + crypto_ope_t *ope = NULL, *ope2 = NULL; + + base16_decode((char*)key, 32, OPE_TEST_KEY, strlen(OPE_TEST_KEY)); + + ope = crypto_ope_new(key); + key[8] += 1; + ope2 = crypto_ope_new(key); + unsigned i; + for (i = 0; i < ARRAY_LENGTH(OPE_TEST_VECTORS); ++i) { + int val = OPE_TEST_VECTORS[i].v; + uint64_t res = OPE_TEST_VECTORS[i].r; + + tt_u64_op(crypto_ope_encrypt(ope, val), OP_EQ, res); + tt_u64_op(crypto_ope_encrypt(ope2, val), OP_NE, res); + } + done: + crypto_ope_free(ope); + crypto_ope_free(ope2); + } + + struct testcase_t crypto_ope_tests[] = { + { "consistency", test_crypto_ope_consistency, 0, NULL, NULL }, + { "oob", test_crypto_ope_oob, 0, NULL, NULL }, + { "vectors", test_crypto_ope_vectors, 0, NULL, NULL }, + END_OF_TESTCASES + }; -