/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 | } |