commit 3a45f6ffe95d4c51e4ad4e14f468feb3f4bd6b1e Author: Nick Mathewson <nickm@torproject.org> Date: Thu May 10 08:46:36 2018 -0400 Implementation for a simple order-preserving encryption scheme. This is meant for use when encrypting the current time within the period in order to get a monotonically increasing revision counter without actually revealing our view of the time. This scheme is far from the most state-of-the-art: don't use it for anything else without careful analysis by somebody much smarter than I am. See ticket #25552 for some rationale for this logic. --- src/lib/crypt_ops/crypto_ope.c | 179 +++++++++++++++++++++++++++++++++++++++++ src/lib/crypt_ops/crypto_ope.h | 35 ++++++++ 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 | 148 ++++++++++++++++++++++++++++++++++ 8 files changed, 407 insertions(+) diff --git a/src/lib/crypt_ops/crypto_ope.c b/src/lib/crypt_ops/crypto_ope.c new file mode 100644 index 000000000..dd04ffbaa --- /dev/null +++ b/src/lib/crypt_ops/crypto_ope.c @@ -0,0 +1,179 @@ +/* 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 "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 { + /** 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); + 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 UINT64_MAX 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 UINT64_MAX; + + 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 --git a/src/lib/crypt_ops/crypto_ope.h b/src/lib/crypt_ops/crypto_ope.h new file mode 100644 index 000000000..885ce84b2 --- /dev/null +++ b/src/lib/crypt_ops/crypto_ope.h @@ -0,0 +1,35 @@ +/* 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" + +/** Length of OPE key, in bytes. */ +#define OPE_KEY_LEN 32 + +/** Largest value that can be passed to crypto_ope_encrypt() */ +#define OPE_INPUT_MAX 131072 + +typedef struct crypto_ope_c 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); +#endif + +#endif + diff --git a/src/lib/crypt_ops/include.am b/src/lib/crypt_ops/include.am index b881c689d..6b0b0d200 100644 --- a/src/lib/crypt_ops/include.am +++ b/src/lib/crypt_ops/include.am @@ -14,6 +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_openssl_mgt.c \ src/lib/crypt_ops/crypto_pwbox.c \ src/lib/crypt_ops/crypto_rand.c \ @@ -37,6 +38,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_pwbox.h \ src/lib/crypt_ops/crypto_rand.h \ src/lib/crypt_ops/crypto_rsa.h \ diff --git a/src/test/include.am b/src/test/include.am index 7e5ad4611..390c84ebe 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -117,6 +117,7 @@ src_test_test_SOURCES += \ src/test/test_controller.c \ src/test/test_controller_events.c \ src/test/test_crypto.c \ + src/test/test_crypto_ope.c \ src/test/test_crypto_openssl.c \ src/test/test_data.c \ src/test/test_dir.c \ diff --git a/src/test/ope_ref.py b/src/test/ope_ref.py new file mode 100644 index 000000000..3677e57a6 --- /dev/null +++ b/src/test/ope_ref.py @@ -0,0 +1,40 @@ +#!/usr/bin/python3 +# Copyright 2018, The Tor Project, Inc. See LICENSE for licensing info. + +# Reference implementation for our rudimentary OPE code, used to +# generate test vectors. See crypto_ope.c for more details. + +from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes +from cryptography.hazmat.primitives.ciphers.algorithms import AES +from cryptography.hazmat.backends import default_backend + +from binascii import a2b_hex + +#randomly generated and values. +KEY = a2b_hex( + "19e05891d55232c08c2cad91d612fdb9cbd6691949a0742434a76c80bc6992fe") +PTS = [ 121132, 82283, 72661, 72941, 123122, 12154, 121574, 11391, 65845, + 86301, 61284, 70505, 30438, 60150, 114800, 109403, 21893, 123569, + 95617, 48561, 53334, 92746, 7110, 9612, 106958, 46889, 87790, 68878, + 47917, 121128, 108602, 28217, 69498, 63870, 57542, 122148, 46254, + 42850, 92661, 57720] + +IV = b'\x00' * 16 + +backend = default_backend() + +def words(): + cipher = Cipher(algorithms.AES(KEY), modes.CTR(IV), backend=backend) + e = cipher.encryptor() + while True: + v = e.update(b'\x00\x00') + yield v[0] + 256 * v[1] + 1 + +def encrypt(n): + return sum(w for w, _ in zip(words(), range(n))) + +def example(n): + return ' {{ {}, UINT64_C({}) }},'.format(n, encrypt(n)) + +for v in PTS: + print(example(v)) diff --git a/src/test/test.c b/src/test/test.c index 1a3f4f8eb..baf9e05be 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -861,6 +861,7 @@ struct testgroup_t testgroups[] = { { "control/", controller_tests }, { "control/event/", controller_event_tests }, { "crypto/", crypto_tests }, + { "crypto/ope/", crypto_ope_tests }, { "crypto/openssl/", crypto_openssl_tests }, { "dir/", dir_tests }, { "dir_handle_get/", dir_handle_get_tests }, diff --git a/src/test/test.h b/src/test/test.h index 9abd46008..b24163ed3 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -212,6 +212,7 @@ extern struct testcase_t container_tests[]; extern struct testcase_t controller_tests[]; extern struct testcase_t controller_event_tests[]; extern struct testcase_t crypto_tests[]; +extern struct testcase_t crypto_ope_tests[]; extern struct testcase_t crypto_openssl_tests[]; extern struct testcase_t dir_tests[]; extern struct testcase_t dir_handle_get_tests[]; diff --git a/src/test/test_crypto_ope.c b/src/test/test_crypto_ope.c new file mode 100644 index 000000000..1b93e6981 --- /dev/null +++ b/src/test/test_crypto_ope.c @@ -0,0 +1,148 @@ +/* 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 "test/test.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 +}; +