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^(128r / 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 } 210
