Implement scrypt from RFC 7914. This imports upstream's scrypt implementation, though it's been heavily revised. I lost track of words vs. blocks vs. bigger blocks too many times in the original code and introduced a typedef for the fixed-width Salsa20 blocks. The downside is going from bytes to blocks is a bit trickier, so I took advantage of our little-endian assumption. This also adds an missing check for N < 2^32. Upstream's code is making this assumption in Integerify. I'll send that change back upstream. I've also removed the weird edge case where a NULL out_key parameter means to validate N/r/p against max_mem and nothing else. That's just in there to get a different error code out of their PKCS#12 code. Performance-wise, the cleanup appears to be the same (up to what little precision I was able to get here), but an optimization to use bitwise AND rather than modulus makes us measurably faster. Though scrypt isn't a fast operation to begin with, so hopefully it isn't anyone's bottleneck. This CL does not route scrypt up to the PKCS#12 code, though we could write our own version of that if we need to later. BUG=chromium:731993 Change-Id: Ib2f43344017ed37b6bafd85a2c2b103d695020b8 Reviewed-on: https://boringssl-review.googlesource.com/17084 Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/CMakeLists.txt b/crypto/CMakeLists.txt index cc5c692..b941f67 100644 --- a/crypto/CMakeLists.txt +++ b/crypto/CMakeLists.txt
@@ -238,6 +238,7 @@ evp/evp_extra_test.cc evp/evp_test.cc evp/pbkdf_test.cc + evp/scrypt_test.cc fipsmodule/aes/aes_test.cc fipsmodule/bn/bn_test.cc fipsmodule/ec/ec_test.cc
diff --git a/crypto/err/evp.errordata b/crypto/err/evp.errordata index 7cad638..aea4a94 100644 --- a/crypto/err/evp.errordata +++ b/crypto/err/evp.errordata
@@ -14,9 +14,11 @@ EVP,113,INVALID_MGF1_MD EVP,114,INVALID_OPERATION EVP,115,INVALID_PADDING_MODE +EVP,133,INVALID_PARAMETERS EVP,116,INVALID_PSS_SALTLEN EVP,131,INVALID_SIGNATURE EVP,117,KEYS_NOT_SET +EVP,132,MEMORY_LIMIT_EXCEEDED EVP,118,MISSING_PARAMETERS EVP,130,NOT_A_PRIVATE_KEY EVP,119,NO_DEFAULT_DIGEST
diff --git a/crypto/evp/CMakeLists.txt b/crypto/evp/CMakeLists.txt index c3b6d90..4b1fe5e 100644 --- a/crypto/evp/CMakeLists.txt +++ b/crypto/evp/CMakeLists.txt
@@ -18,5 +18,6 @@ p_rsa_asn1.c pbkdf.c print.c + scrypt.c sign.c )
diff --git a/crypto/evp/scrypt.c b/crypto/evp/scrypt.c new file mode 100644 index 0000000..3f10214 --- /dev/null +++ b/crypto/evp/scrypt.c
@@ -0,0 +1,209 @@ +/* + * Copyright 2015-2016 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the OpenSSL license (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include <openssl/evp.h> + +#include <assert.h> + +#include <openssl/err.h> +#include <openssl/mem.h> +#include <openssl/type_check.h> + +#include "../internal.h" + + +/* This file implements scrypt, described in RFC 7914. + * + * Note scrypt refers to both "blocks" and a "block size" parameter, r. These + * are two different notions of blocks. A Salsa20 block is 64 bytes long, + * represented in this implementation by 16 |uint32_t|s. |r| determines the + * number of 64-byte Salsa20 blocks in a scryptBlockMix block, which is 2 * |r| + * Salsa20 blocks. This implementation refers to them as Salsa20 blocks and + * scrypt blocks, respectively. */ + +/* A block_t is a Salsa20 block. */ +typedef struct { uint32_t words[16]; } block_t; + +OPENSSL_COMPILE_ASSERT(sizeof(block_t) == 64, block_t_has_padding); + +#define R(a, b) (((a) << (b)) | ((a) >> (32 - (b)))) + +/* salsa208_word_specification implements the Salsa20/8 core function, also + * described in RFC 7914, section 3. It modifies the block at |inout| + * in-place. */ +static void salsa208_word_specification(block_t *inout) { + block_t x; + OPENSSL_memcpy(&x, inout, sizeof(x)); + + for (int i = 8; i > 0; i -= 2) { + x.words[4] ^= R(x.words[0] + x.words[12], 7); + x.words[8] ^= R(x.words[4] + x.words[0], 9); + x.words[12] ^= R(x.words[8] + x.words[4], 13); + x.words[0] ^= R(x.words[12] + x.words[8], 18); + x.words[9] ^= R(x.words[5] + x.words[1], 7); + x.words[13] ^= R(x.words[9] + x.words[5], 9); + x.words[1] ^= R(x.words[13] + x.words[9], 13); + x.words[5] ^= R(x.words[1] + x.words[13], 18); + x.words[14] ^= R(x.words[10] + x.words[6], 7); + x.words[2] ^= R(x.words[14] + x.words[10], 9); + x.words[6] ^= R(x.words[2] + x.words[14], 13); + x.words[10] ^= R(x.words[6] + x.words[2], 18); + x.words[3] ^= R(x.words[15] + x.words[11], 7); + x.words[7] ^= R(x.words[3] + x.words[15], 9); + x.words[11] ^= R(x.words[7] + x.words[3], 13); + x.words[15] ^= R(x.words[11] + x.words[7], 18); + x.words[1] ^= R(x.words[0] + x.words[3], 7); + x.words[2] ^= R(x.words[1] + x.words[0], 9); + x.words[3] ^= R(x.words[2] + x.words[1], 13); + x.words[0] ^= R(x.words[3] + x.words[2], 18); + x.words[6] ^= R(x.words[5] + x.words[4], 7); + x.words[7] ^= R(x.words[6] + x.words[5], 9); + x.words[4] ^= R(x.words[7] + x.words[6], 13); + x.words[5] ^= R(x.words[4] + x.words[7], 18); + x.words[11] ^= R(x.words[10] + x.words[9], 7); + x.words[8] ^= R(x.words[11] + x.words[10], 9); + x.words[9] ^= R(x.words[8] + x.words[11], 13); + x.words[10] ^= R(x.words[9] + x.words[8], 18); + x.words[12] ^= R(x.words[15] + x.words[14], 7); + x.words[13] ^= R(x.words[12] + x.words[15], 9); + x.words[14] ^= R(x.words[13] + x.words[12], 13); + x.words[15] ^= R(x.words[14] + x.words[13], 18); + } + + for (int i = 0; i < 16; ++i) { + inout->words[i] += x.words[i]; + } +} + +/* xor_block sets |*out| to be |*a| XOR |*b|. */ +static void xor_block(block_t *out, const block_t *a, const block_t *b) { + for (size_t i = 0; i < 16; i++) { + out->words[i] = a->words[i] ^ b->words[i]; + } +} + +/* scryptBlockMix implements the function described in RFC 7914, section 4. B' + * is written to |out|. |out| and |B| may not alias and must be each one scrypt + * block (2 * |r| Salsa20 blocks) long. */ +static void scryptBlockMix(block_t *out, const block_t *B, uint64_t r) { + assert(out != B); + + block_t X; + OPENSSL_memcpy(&X, &B[r * 2 - 1], sizeof(X)); + for (uint64_t i = 0; i < r * 2; i++) { + xor_block(&X, &X, &B[i]); + salsa208_word_specification(&X); + + /* This implements the permutation in step 3. */ + OPENSSL_memcpy(&out[i / 2 + (i & 1) * r], &X, sizeof(X)); + } +} + +/* scryptROMix implements the function described in RFC 7914, section 5. |B| is + * an scrypt block (2 * |r| Salsa20 blocks) and is modified in-place. |T| and + * |V| are scratch space allocated by the caller. |T| must have space for one + * scrypt block (2 * |r| Salsa20 blocks). |V| must have space for |N| scrypt + * blocks (2 * |r| * |N| Salsa20 blocks). */ +static void scryptROMix(block_t *B, uint64_t r, uint64_t N, block_t *T, + block_t *V) { + /* Steps 1 and 2. */ + OPENSSL_memcpy(V, B, 2 * r * sizeof(block_t)); + for (uint64_t i = 1; i < N; i++) { + scryptBlockMix(&V[2 * r * i /* scrypt block i */], + &V[2 * r * (i - 1) /* scrypt block i-1 */], r); + } + scryptBlockMix(B, &V[2 * r * (N - 1) /* scrypt block N-1 */], r); + + /* Step 3. */ + for (uint64_t i = 0; i < N; i++) { + /* Note this assumes |N| <= 2^32 and is a power of 2. */ + uint32_t j = B[2 * r - 1].words[0] & (N - 1); + for (size_t k = 0; k < 2 * r; k++) { + xor_block(&T[k], &B[k], &V[2 * r * j + k]); + } + scryptBlockMix(B, T, r); + } +} + +/* SCRYPT_PR_MAX is the maximum value of p * r. This is equivalent to the + * bounds on p in section 6: + * + * p <= ((2^32-1) * hLen) / MFLen iff + * p <= ((2^32-1) * 32) / (128 * r) iff + * p * r <= (2^30-1) */ +#define SCRYPT_PR_MAX ((1 << 30) - 1) + +/* SCRYPT_MAX_MEM is the default maximum memory that may be allocated by + * |EVP_PBE_scrypt|. */ +#define SCRYPT_MAX_MEM (1024 * 1024 * 32) + +int EVP_PBE_scrypt(const char *password, size_t password_len, + const uint8_t *salt, size_t salt_len, uint64_t N, uint64_t r, + uint64_t p, size_t max_mem, uint8_t *out_key, + size_t key_len) { + if (r == 0 || p == 0 || p > SCRYPT_PR_MAX / r || + /* |N| must be a power of two. */ + N < 2 || (N & (N - 1)) || + /* We only support |N| <= 2^32 in |scryptROMix|. */ + N > UINT64_C(1) << 32 || + /* Check that |N| < 2^(128×r / 8). */ + (16 * r <= 63 && N >= UINT64_C(1) << (16 * r))) { + OPENSSL_PUT_ERROR(EVP, EVP_R_INVALID_PARAMETERS); + return 0; + } + + /* Determine the amount of memory needed. B, T, and V are |p|, 1, and |N| + * scrypt blocks, respectively. Each scrypt block is 2*|r| |block_t|s. */ + if (max_mem == 0) { + max_mem = SCRYPT_MAX_MEM; + } + + size_t max_scrypt_blocks = max_mem / (2 * r * sizeof(block_t)); + if (max_scrypt_blocks < p + 1 || + max_scrypt_blocks - p - 1 < N) { + OPENSSL_PUT_ERROR(EVP, EVP_R_MEMORY_LIMIT_EXCEEDED); + return 0; + } + + /* Allocate and divide up the scratch space. |max_mem| fits in a size_t, which + * is no bigger than uint64_t, so none of these operations may overflow. */ + OPENSSL_COMPILE_ASSERT(UINT64_MAX >= ((size_t)-1), size_t_exceeds_u64); + size_t B_blocks = p * 2 * r; + size_t B_bytes = B_blocks * sizeof(block_t); + size_t T_blocks = 2 * r; + size_t V_blocks = N * 2 * r; + block_t *B = OPENSSL_malloc((B_blocks + T_blocks + V_blocks) * sizeof(block_t)); + if (B == NULL) { + OPENSSL_PUT_ERROR(EVP, ERR_R_MALLOC_FAILURE); + return 0; + } + + int ret = 0; + block_t *T = B + B_blocks; + block_t *V = T + T_blocks; + if (!PKCS5_PBKDF2_HMAC(password, password_len, salt, salt_len, 1, + EVP_sha256(), B_bytes, (uint8_t *)B)) { + goto err; + } + + for (uint64_t i = 0; i < p; i++) { + scryptROMix(B + 2 * r * i, r, N, T, V); + } + + if (!PKCS5_PBKDF2_HMAC(password, password_len, (const uint8_t *)B, B_bytes, 1, + EVP_sha256(), key_len, out_key)) { + goto err; + } + + ret = 1; + +err: + OPENSSL_free(B); + return ret; +}
diff --git a/crypto/evp/scrypt_test.cc b/crypto/evp/scrypt_test.cc new file mode 100644 index 0000000..e957fd0 --- /dev/null +++ b/crypto/evp/scrypt_test.cc
@@ -0,0 +1,103 @@ +/* Copyright (c) 2017, Google Inc. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ + +#include <stdlib.h> +#include <string.h> + +#include <vector> + +#include <gtest/gtest.h> + +#include <openssl/err.h> +#include <openssl/evp.h> + +#include "../test/file_test.h" +#include "../test/test_util.h" + + +static bool GetUint64(FileTest *t, uint64_t *out, const char *name) { + std::string str; + if (!t->GetAttribute(&str, name)) { + return false; + } + + char *endptr; + *out = strtoull(str.data(), &endptr, 10); + return !str.empty() && *endptr == '\0'; +} + +TEST(ScryptTest, TestVectors) { + FileTestGTest("crypto/evp/scrypt_tests.txt", [](FileTest *t) { + std::vector<uint8_t> password, salt, key; + uint64_t N, r, p, max_mem = 0; + ASSERT_TRUE(t->GetBytes(&password, "Password")); + ASSERT_TRUE(t->GetBytes(&salt, "Salt")); + ASSERT_TRUE(t->GetBytes(&key, "Key")); + ASSERT_TRUE(GetUint64(t, &N, "N")); + ASSERT_TRUE(GetUint64(t, &r, "r")); + ASSERT_TRUE(GetUint64(t, &p, "p")); + if (t->HasAttribute("MaxMemory")) { + ASSERT_TRUE(GetUint64(t, &max_mem, "MaxMemory")); + } + + std::vector<uint8_t> result(key.size()); + ASSERT_TRUE(EVP_PBE_scrypt(reinterpret_cast<const char *>(password.data()), + password.size(), salt.data(), salt.size(), N, r, + p, max_mem, result.data(), result.size())); + EXPECT_EQ(Bytes(key), Bytes(result)); + }); +} + +TEST(ScryptTest, MemoryLimit) { + static const char kPassword[] = "pleaseletmein"; + static const char kSalt[] = "SodiumChloride"; + + // This test requires more than 1GB to run. + uint8_t key[64]; + EXPECT_FALSE(EVP_PBE_scrypt(kPassword, strlen(kPassword), + reinterpret_cast<const uint8_t *>(kSalt), + strlen(kSalt), 1048576 /* N */, 8 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + uint32_t err = ERR_get_error(); + EXPECT_EQ(ERR_LIB_EVP, ERR_GET_LIB(err)); + EXPECT_EQ(EVP_R_MEMORY_LIMIT_EXCEEDED, ERR_GET_REASON(err)); +} + +TEST(ScryptTest, InvalidParameters) { + uint8_t key[64]; + + // p and r are non-zero. + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 1024 /* N */, 0 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 1024 /* N */, 8 /* r */, + 0 /* p */, 0 /* max_mem */, key, sizeof(key))); + + // N must be a power of 2 > 1. + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 0 /* N */, 8 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 1 /* N */, 8 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 1023 /* N */, 8 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + EXPECT_TRUE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 1024 /* N */, 8 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 1025 /* N */, 8 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + + // N must be below 2^(128 * r / 8). + EXPECT_FALSE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 65536 /* N */, 1 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); + EXPECT_TRUE(EVP_PBE_scrypt(nullptr, 0, nullptr, 0, 32768 /* N */, 1 /* r */, + 1 /* p */, 0 /* max_mem */, key, sizeof(key))); +}
diff --git a/crypto/evp/scrypt_tests.txt b/crypto/evp/scrypt_tests.txt new file mode 100644 index 0000000..7497bd2 --- /dev/null +++ b/crypto/evp/scrypt_tests.txt
@@ -0,0 +1,38 @@ +# +# Copyright 2001-2017 The OpenSSL Project Authors. All Rights Reserved. +# +# Licensed under the OpenSSL license (the "License"). You may not use +# this file except in compliance with the License. You can obtain a copy +# in the file LICENSE in the source distribution or at +# https://www.openssl.org/source/license.html + +Password = "" +Salt = "" +N = 16 +r = 1 +p = 1 +Key = 77d6576238657b203b19ca42c18a0497f16b4844e3074ae8dfdffa3fede21442fcd0069ded0948f8326a753a0fc81f17e8d3e0fb2e0d3628cf35e20c38d18906 + +Password = "password" +Salt = "NaCl" +N = 1024 +r = 8 +p = 16 +Key = fdbabe1c9d3472007856e7190d01e9fe7c6ad7cbc8237830e77376634b3731622eaf30d92e22a3886ff109279d9830dac727afb94a83ee6d8360cbdfa2cc0640 + +Password = "pleaseletmein" +Salt = "SodiumChloride" +N = 16384 +r = 8 +p = 1 +Key = 7023bdcb3afd7348461c06cd81fd38ebfda8fbba904f8e3ea9b543f6545da1f2d5432955613f0fcf62d49705242a9af9e61e85dc0d651e40dfcf017b45575887 + +# NB: this test requires more than 1GB of memory to run so it is disabled by +# default. Uncomment it to run. +# Password = "pleaseletmein" +# Salt = "SodiumChloride" +# N = 1048576 +# r = 8 +# p = 1 +# Key = 2101cb9b6a511aaeaddbbe09cf70f881ec568d574a2ffd4dabe5ee9820adaa478e56fd8f4ba5d09ffa1c6d927c40f4c337304049e8a952fbcbf45c6fa77a41a4 +# MaxMemory = 10000000000
diff --git a/include/openssl/evp.h b/include/openssl/evp.h index f3e96b1..37c965a 100644 --- a/include/openssl/evp.h +++ b/include/openssl/evp.h
@@ -433,6 +433,20 @@ unsigned iterations, size_t key_len, uint8_t *out_key); +/* EVP_PBE_scrypt expands |password| into a secret key of length |key_len| using + * scrypt, as described in RFC 7914, and writes the result to |out_key|. It + * returns one on success and zero on error. + * + * |N|, |r|, and |p| are as described in RFC 7914 section 6. They determine the + * cost of the operation. If the memory required exceeds |max_mem|, the + * operation will fail instead. If |max_mem| is zero, a defult limit of 32MiB + * will be used. */ +OPENSSL_EXPORT int EVP_PBE_scrypt(const char *password, size_t password_len, + const uint8_t *salt, size_t salt_len, + uint64_t N, uint64_t r, uint64_t p, + size_t max_mem, uint8_t *out_key, + size_t key_len); + /* Public key contexts. * @@ -857,5 +871,7 @@ #define EVP_R_UNSUPPORTED_PUBLIC_KEY_TYPE 129 #define EVP_R_NOT_A_PRIVATE_KEY 130 #define EVP_R_INVALID_SIGNATURE 131 +#define EVP_R_MEMORY_LIMIT_EXCEEDED 132 +#define EVP_R_INVALID_PARAMETERS 133 #endif /* OPENSSL_HEADER_EVP_H */
diff --git a/sources.cmake b/sources.cmake index 11fc61a..941a9ed 100644 --- a/sources.cmake +++ b/sources.cmake
@@ -39,6 +39,7 @@ crypto/curve25519/ed25519_tests.txt crypto/ecdh/ecdh_tests.txt crypto/evp/evp_tests.txt + crypto/evp/scrypt_tests.txt crypto/fipsmodule/aes/aes_tests.txt crypto/fipsmodule/bn/bn_tests.txt crypto/fipsmodule/ec/p256-x86_64_tests.txt
diff --git a/tool/speed.cc b/tool/speed.cc index e941b8b..6652298 100644 --- a/tool/speed.cc +++ b/tool/speed.cc
@@ -29,6 +29,7 @@ #include <openssl/ec.h> #include <openssl/ecdsa.h> #include <openssl/ec_key.h> +#include <openssl/evp.h> #include <openssl/nid.h> #include <openssl/rand.h> #include <openssl/rsa.h> @@ -576,6 +577,41 @@ return true; } +static bool SpeedScrypt(const std::string &selected) { + if (!selected.empty() && selected.find("scrypt") == std::string::npos) { + return true; + } + + TimeResults results; + + static const char kPassword[] = "password"; + static const uint8_t kSalt[] = "NaCl"; + + if (!TimeFunction(&results, [&]() -> bool { + uint8_t out[64]; + return !!EVP_PBE_scrypt(kPassword, sizeof(kPassword) - 1, kSalt, + sizeof(kSalt) - 1, 1024, 8, 16, 0 /* max_mem */, + out, sizeof(out)); + })) { + fprintf(stderr, "scrypt failed.\n"); + return false; + } + results.Print("scrypt (N = 1024, r = 8, p = 16)"); + + if (!TimeFunction(&results, [&]() -> bool { + uint8_t out[64]; + return !!EVP_PBE_scrypt(kPassword, sizeof(kPassword) - 1, kSalt, + sizeof(kSalt) - 1, 16384, 8, 1, 0 /* max_mem */, + out, sizeof(out)); + })) { + fprintf(stderr, "scrypt failed.\n"); + return false; + } + results.Print("scrypt (N = 16384, r = 8, p = 1)"); + + return true; +} + static const struct argument kArguments[] = { { "-filter", kOptionalArgument, @@ -666,7 +702,8 @@ !SpeedECDH(selected) || !SpeedECDSA(selected) || !Speed25519(selected) || - !SpeedSPAKE2(selected)) { + !SpeedSPAKE2(selected) || + !SpeedScrypt(selected)) { return false; }