Coverage Report

Created: 2024-11-21 07:03

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