src/lib/crypt_ops/crypto_ope.c

   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
  21 #include "lib/crypt_ops/crypto_ope.h"
  22 #include "lib/crypt_ops/crypto_util.h"
  23 #include "lib/crypt_ops/crypto_cipher.h"
  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
  81   return crypto_cipher_new_with_iv_and_bits(ope->key,
  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) {
 139     v += sum_values_from_cipher(cipher, SAMPLE_INTERVAL);
 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
 149 crypto_ope_free_(crypto_ope_t *ope)
 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 }