Tor  0.4.7.0-alpha-dev
crypto_ope.c
Go to the documentation of this file.
1 /* Copyright (c) 2018-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
4 /**
5  * @file crypto_ope.c
6  * @brief A rudimentary order-preserving encryption scheme.
7  *
8  * To compute the encryption of N, this scheme uses an AES-CTR stream to
9  * generate M-byte values, and adds the first N of them together. (+1 each to
10  * insure that the ciphertexts are strictly decreasing.)
11  *
12  * We use this for generating onion service revision counters based on the
13  * current time, without leaking the amount of skew in our view of the current
14  * time. MUCH more analysis would be needed before using it for anything
15  * else!
16  */
17 
18 #include "orconfig.h"
19 
20 #define CRYPTO_OPE_PRIVATE
24 #include "lib/log/util_bug.h"
25 #include "lib/malloc/malloc.h"
26 #include "lib/arch/bytes.h"
27 
28 #include <string.h>
29 
30 /**
31  * How infrequent should the precomputed values be for this encryption?
32  * The choice of this value creates a space/time tradeoff.
33  *
34  * Note that this value must be a multiple of 16; see
35  * ope_get_cipher()
36  */
37 #define SAMPLE_INTERVAL 1024
38 /** Number of precomputed samples to make for each OPE key. */
39 #define N_SAMPLES (OPE_INPUT_MAX / SAMPLE_INTERVAL)
40 
41 struct crypto_ope_t {
42  /** An AES key for use with this object. */
43  uint8_t key[OPE_KEY_LEN];
44  /** Cached intermediate encryption values at SAMPLE_INTERVAL,
45  * SAMPLE_INTERVAL*2,...SAMPLE_INTERVAL*N_SAMPLES */
46  uint64_t samples[N_SAMPLES];
47 };
48 
49 /** The type to add up in order to produce our OPE ciphertexts */
50 typedef uint16_t ope_val_t;
51 
52 #ifdef WORDS_BIGENDIAN
53 /** Convert an OPE value from little-endian. */
54 static inline ope_val_t
55 ope_val_from_le(ope_val_t x)
56 {
57  return
58  ((x) >> 8) |
59  (((x)&0xff) << 8);
60 }
61 #else /* !defined(WORDS_BIGENDIAN) */
62 #define ope_val_from_le(x) (x)
63 #endif /* defined(WORDS_BIGENDIAN) */
64 
65 /**
66  * Return a new AES256-CTR stream cipher object for <b>ope</b>, ready to yield
67  * bytes from the stream at position <b>initial_idx</b>.
68  *
69  * Note that because the index is converted directly to an IV, it must be a
70  * multiple of the AES block size (16).
71  */
72 STATIC crypto_cipher_t *
73 ope_get_cipher(const crypto_ope_t *ope, uint32_t initial_idx)
74 {
75  uint8_t iv[CIPHER_IV_LEN];
76  tor_assert((initial_idx & 0xf) == 0);
77  uint32_t n = tor_htonl(initial_idx >> 4);
78  memset(iv, 0, sizeof(iv));
79  memcpy(iv + CIPHER_IV_LEN - sizeof(n), &n, sizeof(n));
80 
82  iv,
83  OPE_KEY_LEN * 8);
84 }
85 
86 /**
87  * Retrieve and add the next <b>n</b> values from the stream cipher <b>c</b>,
88  * and return their sum.
89  *
90  * Note that values are taken in little-endian order (for performance on
91  * prevalent hardware), and are mapped from range 0..2^n-1 to range 1..2^n (so
92  * that each input encrypts to a different output).
93  *
94  * NOTE: this function is not constant-time.
95  */
96 STATIC uint64_t
97 sum_values_from_cipher(crypto_cipher_t *c, size_t n)
98 {
99 #define BUFSZ 256
100  ope_val_t buf[BUFSZ];
101  uint64_t total = 0;
102  unsigned i;
103  while (n >= BUFSZ) {
104  memset(buf, 0, sizeof(buf));
105  crypto_cipher_crypt_inplace(c, (char*)buf, BUFSZ*sizeof(ope_val_t));
106 
107  for (i = 0; i < BUFSZ; ++i) {
108  total += ope_val_from_le(buf[i]);
109  total += 1;
110  }
111  n -= BUFSZ;
112  }
113 
114  memset(buf, 0, n*sizeof(ope_val_t));
115  crypto_cipher_crypt_inplace(c, (char*)buf, n*sizeof(ope_val_t));
116  for (i = 0; i < n; ++i) {
117  total += ope_val_from_le(buf[i]);
118  total += 1;
119  }
120 
121  memset(buf, 0, sizeof(buf));
122  return total;
123 }
124 
125 /**
126  * Return a new crypto_ope_t object, using the provided 256-bit key.
127  */
128 crypto_ope_t *
129 crypto_ope_new(const uint8_t *key)
130 {
131  crypto_ope_t *ope = tor_malloc_zero(sizeof(crypto_ope_t));
132  memcpy(ope->key, key, OPE_KEY_LEN);
133 
134  crypto_cipher_t *cipher = ope_get_cipher(ope, 0);
135 
136  uint64_t v = 0;
137  int i;
138  for (i = 0; i < N_SAMPLES; ++i) {
140  ope->samples[i] = v;
141  }
142 
143  crypto_cipher_free(cipher);
144  return ope;
145 }
146 
147 /** Free all storage held in <b>ope</b>. */
148 void
150 {
151  if (!ope)
152  return;
153  memwipe(ope, 0, sizeof(*ope));
154  tor_free(ope);
155 }
156 
157 /**
158  * Return the encrypted value corresponding to <b>input</b>. The input value
159  * must be in range 1..OPE_INPUT_MAX. Returns CRYPTO_OPE_ERROR on an invalid
160  * input.
161  *
162  * NOTE: this function is not constant-time.
163  */
164 uint64_t
165 crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext)
166 {
167  if (plaintext <= 0 || plaintext > OPE_INPUT_MAX)
168  return CRYPTO_OPE_ERROR;
169 
170  const int sample_idx = (plaintext / SAMPLE_INTERVAL);
171  const int starting_iv = sample_idx * SAMPLE_INTERVAL;
172  const int remaining_values = plaintext - starting_iv;
173  uint64_t v;
174  if (sample_idx == 0) {
175  v = 0;
176  } else {
177  v = ope->samples[sample_idx - 1];
178  }
179  crypto_cipher_t *cipher = ope_get_cipher(ope, starting_iv*sizeof(ope_val_t));
180 
181  v += sum_values_from_cipher(cipher, remaining_values);
182 
183  crypto_cipher_free(cipher);
184 
185  return v;
186 }
Inline functions for reading and writing multibyte values from the middle of strings,...
static uint32_t tor_htonl(uint32_t a)
Definition: bytes.h:163
void crypto_cipher_crypt_inplace(crypto_cipher_t *env, char *buf, size_t len)
crypto_cipher_t * crypto_cipher_new_with_iv_and_bits(const uint8_t *key, const uint8_t *iv, int bits)
Definition: crypto_cipher.c:29
Headers for crypto_cipher.c.
#define CIPHER_IV_LEN
Definition: crypto_cipher.h:24
crypto_ope_t * crypto_ope_new(const uint8_t *key)
Definition: crypto_ope.c:129
void crypto_ope_free_(crypto_ope_t *ope)
Definition: crypto_ope.c:149
#define N_SAMPLES
Definition: crypto_ope.c:39
#define SAMPLE_INTERVAL
Definition: crypto_ope.c:37
uint64_t crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext)
Definition: crypto_ope.c:165
uint16_t ope_val_t
Definition: crypto_ope.c:50
STATIC crypto_cipher_t * ope_get_cipher(const crypto_ope_t *ope, uint32_t initial_idx)
Definition: crypto_ope.c:73
STATIC uint64_t sum_values_from_cipher(crypto_cipher_t *c, size_t n)
Definition: crypto_ope.c:97
header for crypto_ope.c
#define OPE_KEY_LEN
Definition: crypto_ope.h:18
#define OPE_INPUT_MAX
Definition: crypto_ope.h:31
void memwipe(void *mem, uint8_t byte, size_t sz)
Definition: crypto_util.c:55
Common functions for cryptographic routines.
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
uint64_t samples[N_SAMPLES]
Definition: crypto_ope.c:46
uint8_t key[OPE_KEY_LEN]
Definition: crypto_ope.c:43
#define STATIC
Definition: testsupport.h:32
Macros to manage assertions, fatal and non-fatal.
#define tor_assert(expr)
Definition: util_bug.h:102