crypto_ope.c 4.9 KB

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