legacy-libs/grpc/deps/grpc/third_party/boringssl/crypto/evp/scrypt.c

   1 /*
   2  * Copyright 2015-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <openssl/evp.h>
  11
  12 #include <assert.h>
  13
  14 #include <openssl/err.h>
  15 #include <openssl/mem.h>
  16 #include <openssl/type_check.h>
  17
  18 #include "../internal.h"
  19
  20
  21 // This file implements scrypt, described in RFC 7914.
  22 //
  23 // Note scrypt refers to both "blocks" and a "block size" parameter, r. These
  24 // are two different notions of blocks. A Salsa20 block is 64 bytes long,
  25 // represented in this implementation by 16 |uint32_t|s. |r| determines the
  26 // number of 64-byte Salsa20 blocks in a scryptBlockMix block, which is 2 * |r|
  27 // Salsa20 blocks. This implementation refers to them as Salsa20 blocks and
  28 // scrypt blocks, respectively.
  29
  30 // A block_t is a Salsa20 block.
  31 typedef struct { uint32_t words[16]; } block_t;
  32
  33 OPENSSL_COMPILE_ASSERT(sizeof(block_t) == 64, block_t_has_padding);
  34
  35 #define R(a, b) (((a) << (b)) | ((a) >> (32 - (b))))
  36
  37 // salsa208_word_specification implements the Salsa20/8 core function, also
  38 // described in RFC 7914, section 3. It modifies the block at |inout|
  39 // in-place.
  40 static void salsa208_word_specification(block_t *inout) {
  41   block_t x;
  42   OPENSSL_memcpy(&x, inout, sizeof(x));
  43
  44   for (int i = 8; i > 0; i -= 2) {
  45     x.words[4] ^= R(x.words[0] + x.words[12], 7);
  46     x.words[8] ^= R(x.words[4] + x.words[0], 9);
  47     x.words[12] ^= R(x.words[8] + x.words[4], 13);
  48     x.words[0] ^= R(x.words[12] + x.words[8], 18);
  49     x.words[9] ^= R(x.words[5] + x.words[1], 7);
  50     x.words[13] ^= R(x.words[9] + x.words[5], 9);
  51     x.words[1] ^= R(x.words[13] + x.words[9], 13);
  52     x.words[5] ^= R(x.words[1] + x.words[13], 18);
  53     x.words[14] ^= R(x.words[10] + x.words[6], 7);
  54     x.words[2] ^= R(x.words[14] + x.words[10], 9);
  55     x.words[6] ^= R(x.words[2] + x.words[14], 13);
  56     x.words[10] ^= R(x.words[6] + x.words[2], 18);
  57     x.words[3] ^= R(x.words[15] + x.words[11], 7);
  58     x.words[7] ^= R(x.words[3] + x.words[15], 9);
  59     x.words[11] ^= R(x.words[7] + x.words[3], 13);
  60     x.words[15] ^= R(x.words[11] + x.words[7], 18);
  61     x.words[1] ^= R(x.words[0] + x.words[3], 7);
  62     x.words[2] ^= R(x.words[1] + x.words[0], 9);
  63     x.words[3] ^= R(x.words[2] + x.words[1], 13);
  64     x.words[0] ^= R(x.words[3] + x.words[2], 18);
  65     x.words[6] ^= R(x.words[5] + x.words[4], 7);
  66     x.words[7] ^= R(x.words[6] + x.words[5], 9);
  67     x.words[4] ^= R(x.words[7] + x.words[6], 13);
  68     x.words[5] ^= R(x.words[4] + x.words[7], 18);
  69     x.words[11] ^= R(x.words[10] + x.words[9], 7);
  70     x.words[8] ^= R(x.words[11] + x.words[10], 9);
  71     x.words[9] ^= R(x.words[8] + x.words[11], 13);
  72     x.words[10] ^= R(x.words[9] + x.words[8], 18);
  73     x.words[12] ^= R(x.words[15] + x.words[14], 7);
  74     x.words[13] ^= R(x.words[12] + x.words[15], 9);
  75     x.words[14] ^= R(x.words[13] + x.words[12], 13);
  76     x.words[15] ^= R(x.words[14] + x.words[13], 18);
  77   }
  78
  79   for (int i = 0; i < 16; ++i) {
  80     inout->words[i] += x.words[i];
  81   }
  82 }
  83
  84 // xor_block sets |*out| to be |*a| XOR |*b|.
  85 static void xor_block(block_t *out, const block_t *a, const block_t *b) {
  86   for (size_t i = 0; i < 16; i++) {
  87     out->words[i] = a->words[i] ^ b->words[i];
  88   }
  89 }
  90
  91 // scryptBlockMix implements the function described in RFC 7914, section 4. B'
  92 // is written to |out|. |out| and |B| may not alias and must be each one scrypt
  93 // block (2 * |r| Salsa20 blocks) long.
  94 static void scryptBlockMix(block_t *out, const block_t *B, uint64_t r) {
  95   assert(out != B);
  96
  97   block_t X;
  98   OPENSSL_memcpy(&X, &B[r * 2 - 1], sizeof(X));
  99   for (uint64_t i = 0; i < r * 2; i++) {
 100     xor_block(&X, &X, &B[i]);
 101     salsa208_word_specification(&X);
 102
 103     // This implements the permutation in step 3.
 104     OPENSSL_memcpy(&out[i / 2 + (i & 1) * r], &X, sizeof(X));
 105   }
 106 }
 107
 108 // scryptROMix implements the function described in RFC 7914, section 5.  |B| is
 109 // an scrypt block (2 * |r| Salsa20 blocks) and is modified in-place. |T| and
 110 // |V| are scratch space allocated by the caller. |T| must have space for one
 111 // scrypt block (2 * |r| Salsa20 blocks). |V| must have space for |N| scrypt
 112 // blocks (2 * |r| * |N| Salsa20 blocks).
 113 static void scryptROMix(block_t *B, uint64_t r, uint64_t N, block_t *T,
 114                         block_t *V) {
 115   // Steps 1 and 2.
 116   OPENSSL_memcpy(V, B, 2 * r * sizeof(block_t));
 117   for (uint64_t i = 1; i < N; i++) {
 118     scryptBlockMix(&V[2 * r * i /* scrypt block i */],
 119                    &V[2 * r * (i - 1) /* scrypt block i-1 */], r);
 120   }
 121   scryptBlockMix(B, &V[2 * r * (N - 1) /* scrypt block N-1 */], r);
 122
 123   // Step 3.
 124   for (uint64_t i = 0; i < N; i++) {
 125     // Note this assumes |N| <= 2^32 and is a power of 2.
 126     uint32_t j = B[2 * r - 1].words[0] & (N - 1);
 127     for (size_t k = 0; k < 2 * r; k++) {
 128       xor_block(&T[k], &B[k], &V[2 * r * j + k]);
 129     }
 130     scryptBlockMix(B, T, r);
 131   }
 132 }
 133
 134 // SCRYPT_PR_MAX is the maximum value of p * r. This is equivalent to the
 135 // bounds on p in section 6:
 136 //
 137 //   p <= ((2^32-1) * hLen) / MFLen iff
 138 //   p <= ((2^32-1) * 32) / (128 * r) iff
 139 //   p * r <= (2^30-1)
 140 #define SCRYPT_PR_MAX ((1 << 30) - 1)
 141
 142 // SCRYPT_MAX_MEM is the default maximum memory that may be allocated by
 143 // |EVP_PBE_scrypt|.
 144 #define SCRYPT_MAX_MEM (1024 * 1024 * 32)
 145
 146 int EVP_PBE_scrypt(const char *password, size_t password_len,
 147                    const uint8_t *salt, size_t salt_len, uint64_t N, uint64_t r,
 148                    uint64_t p, size_t max_mem, uint8_t *out_key,
 149                    size_t key_len) {
 150   if (r == 0 || p == 0 || p > SCRYPT_PR_MAX / r ||
 151       // |N| must be a power of two.
 152       N < 2 || (N & (N - 1)) ||
 153       // We only support |N| <= 2^32 in |scryptROMix|.
 154       N > UINT64_C(1) << 32 ||
 155       // Check that |N| < 2^(128×r / 8).
 156       (16 * r <= 63 && N >= UINT64_C(1) << (16 * r))) {
 157     OPENSSL_PUT_ERROR(EVP, EVP_R_INVALID_PARAMETERS);
 158     return 0;
 159   }
 160
 161   // Determine the amount of memory needed. B, T, and V are |p|, 1, and |N|
 162   // scrypt blocks, respectively. Each scrypt block is 2*|r| |block_t|s.
 163   if (max_mem == 0) {
 164     max_mem = SCRYPT_MAX_MEM;
 165   }
 166
 167   size_t max_scrypt_blocks = max_mem / (2 * r * sizeof(block_t));
 168   if (max_scrypt_blocks < p + 1 ||
 169       max_scrypt_blocks - p - 1 < N) {
 170     OPENSSL_PUT_ERROR(EVP, EVP_R_MEMORY_LIMIT_EXCEEDED);
 171     return 0;
 172   }
 173
 174   // Allocate and divide up the scratch space. |max_mem| fits in a size_t, which
 175   // is no bigger than uint64_t, so none of these operations may overflow.
 176   OPENSSL_COMPILE_ASSERT(UINT64_MAX >= ((size_t)-1), size_t_exceeds_u64);
 177   size_t B_blocks = p * 2 * r;
 178   size_t B_bytes = B_blocks * sizeof(block_t);
 179   size_t T_blocks = 2 * r;
 180   size_t V_blocks = N * 2 * r;
 181   block_t *B = OPENSSL_malloc((B_blocks + T_blocks + V_blocks) * sizeof(block_t));
 182   if (B == NULL) {
 183     OPENSSL_PUT_ERROR(EVP, ERR_R_MALLOC_FAILURE);
 184     return 0;
 185   }
 186
 187   int ret = 0;
 188   block_t *T = B + B_blocks;
 189   block_t *V = T + T_blocks;
 190   if (!PKCS5_PBKDF2_HMAC(password, password_len, salt, salt_len, 1,
 191                          EVP_sha256(), B_bytes, (uint8_t *)B)) {
 192     goto err;
 193   }
 194
 195   for (uint64_t i = 0; i < p; i++) {
 196     scryptROMix(B + 2 * r * i, r, N, T, V);
 197   }
 198
 199   if (!PKCS5_PBKDF2_HMAC(password, password_len, (const uint8_t *)B, B_bytes, 1,
 200                          EVP_sha256(), key_len, out_key)) {
 201     goto err;
 202   }
 203
 204   ret = 1;
 205
 206 err:
 207   OPENSSL_free(B);
 208   return ret;
 209 }