Line data    Source code

       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         153 : ope_get_cipher(const crypto_ope_t *ope, uint32_t initial_idx)
      74             : {
      75         153 :   uint8_t iv[CIPHER_IV_LEN];
      76         153 :   tor_assert((initial_idx & 0xf) == 0);
      77         153 :   uint32_t n = tor_htonl(initial_idx >> 4);
      78         153 :   memset(iv, 0, sizeof(iv));
      79         153 :   memcpy(iv + CIPHER_IV_LEN - sizeof(n), &n, sizeof(n));
      80             : 
      81         153 :   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       12393 : sum_values_from_cipher(crypto_cipher_t *c, size_t n)
      98             : {
      99             : #define BUFSZ 256
     100       12393 :   ope_val_t buf[BUFSZ];
     101       12393 :   uint64_t total = 0;
     102       12393 :   unsigned i;
     103       62784 :   while (n >= BUFSZ) {
     104       50391 :     memset(buf, 0, sizeof(buf));
     105       50391 :     crypto_cipher_crypt_inplace(c, (char*)buf, BUFSZ*sizeof(ope_val_t));
     106             : 
     107    13000878 :     for (i = 0; i < BUFSZ; ++i) {
     108    12900096 :       total += ope_val_from_le(buf[i]);
     109    12900096 :       total += 1;
     110             :     }
     111       50391 :     n -= BUFSZ;
     112             :   }
     113             : 
     114       12393 :   memset(buf, 0, n*sizeof(ope_val_t));
     115       12393 :   crypto_cipher_crypt_inplace(c, (char*)buf, n*sizeof(ope_val_t));
     116       37377 :   for (i = 0; i < n; ++i) {
     117       12591 :     total += ope_val_from_le(buf[i]);
     118       12591 :     total += 1;
     119             :   }
     120             : 
     121       12393 :   memset(buf, 0, sizeof(buf));
     122       12393 :   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          48 : crypto_ope_new(const uint8_t *key)
     130             : {
     131          48 :   crypto_ope_t *ope = tor_malloc_zero(sizeof(crypto_ope_t));
     132          48 :   memcpy(ope->key, key, OPE_KEY_LEN);
     133             : 
     134          48 :   crypto_cipher_t *cipher = ope_get_cipher(ope, 0);
     135             : 
     136          48 :   uint64_t v = 0;
     137          48 :   int i;
     138       12384 :   for (i = 0; i < N_SAMPLES; ++i) {
     139       12288 :     v += sum_values_from_cipher(cipher, SAMPLE_INTERVAL);
     140       12288 :     ope->samples[i] = v;
     141             :   }
     142             : 
     143          48 :   crypto_cipher_free(cipher);
     144          48 :   return ope;
     145             : }
     146             : 
     147             : /** Free all storage held in <b>ope</b>. */
     148             : void
     149          69 : crypto_ope_free_(crypto_ope_t *ope)
     150             : {
     151          69 :   if (!ope)
     152             :     return;
     153          48 :   memwipe(ope, 0, sizeof(*ope));
     154          48 :   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          99 : crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext)
     166             : {
     167          99 :   if (plaintext <= 0 || plaintext > OPE_INPUT_MAX)
     168             :     return CRYPTO_OPE_ERROR;
     169             : 
     170          94 :   const int sample_idx = (plaintext / SAMPLE_INTERVAL);
     171          94 :   const int starting_iv = sample_idx * SAMPLE_INTERVAL;
     172          94 :   const int remaining_values =  plaintext - starting_iv;
     173          94 :   uint64_t v;
     174          94 :   if (sample_idx == 0) {
     175             :     v = 0;
     176             :   } else {
     177          90 :     v = ope->samples[sample_idx - 1];
     178             :   }
     179          94 :   crypto_cipher_t *cipher = ope_get_cipher(ope, starting_iv*sizeof(ope_val_t));
     180             : 
     181          94 :   v += sum_values_from_cipher(cipher, remaining_values);
     182             : 
     183          94 :   crypto_cipher_free(cipher);
     184             : 
     185          94 :   return v;
     186             : }