diff options
| -rw-r--r-- | src/lib/pbkdf/scrypt/info.txt | 2 | ||||
| -rw-r--r-- | src/lib/pbkdf/scrypt/scrypt.cpp | 238 | ||||
| -rw-r--r-- | src/lib/pbkdf/scrypt/scrypt.h | 96 | ||||
| -rw-r--r-- | src/lib/pubkey/pbes2/pbes2.cpp | 73 |
4 files changed, 281 insertions, 128 deletions
diff --git a/src/lib/pbkdf/scrypt/info.txt b/src/lib/pbkdf/scrypt/info.txt index cd1551d3b..3ba48fd72 100644 --- a/src/lib/pbkdf/scrypt/info.txt +++ b/src/lib/pbkdf/scrypt/info.txt @@ -1,5 +1,5 @@ <defines> -SCRYPT -> 20180515 +SCRYPT -> 20180902 </defines> <requires> diff --git a/src/lib/pbkdf/scrypt/scrypt.cpp b/src/lib/pbkdf/scrypt/scrypt.cpp index e258f391d..e7f2fd96b 100644 --- a/src/lib/pbkdf/scrypt/scrypt.cpp +++ b/src/lib/pbkdf/scrypt/scrypt.cpp @@ -1,5 +1,6 @@ /** * (C) 2018 Jack Lloyd +* (C) 2018 Ribose Inc * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -8,10 +9,137 @@ #include <botan/pbkdf2.h> #include <botan/salsa20.h> #include <botan/loadstor.h> +#include <botan/exceptn.h> #include <botan/internal/bit_ops.h> +#include <botan/internal/timer.h> +#include <sstream> namespace Botan { +std::string Scrypt_Family::name() const + { + return "Scrypt"; + } + +std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const + { + return std::unique_ptr<PasswordHash>(new Scrypt(32768, 8, 1)); + } + +std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length, + std::chrono::milliseconds msec, + size_t max_memory_usage_mb) const + { + BOTAN_UNUSED(output_length); + + /* + * Some rough relations between scrypt parameters and runtime. + * Denote here by stime(N,r,p) the msec it takes to run scrypt. + * + * Emperically for smaller sizes: + * stime(N,8*r,p) / stime(N,r,p) is ~ 6-7 + * stime(N,r,8*p) / stime(N,r,8*p) is ~ 7 + * stime(2*N,r,p) / stime(N,r,p) is ~ 2 + * + * Compute stime(8192,1,1) as baseline and extrapolate + */ + //printf("max mem %d\n", max_memory_usage_mb); + + const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024; + // Starting parameters + size_t N = 8192; + size_t r = 1; + size_t p = 1; + + Timer timer("Scrypt", 0); + const std::chrono::milliseconds tune_msec(30); + + timer.run_until_elapsed(tune_msec, [&]() { + uint8_t output[32] = { 0 }; + scrypt(output, sizeof(output), "test", 4, nullptr, 0, N, r, p); + }); + + // No timer events seems strange, perhaps something is wrong - give + // up on this and just return default params + if(timer.events() == 0) + return default_params(); + + // nsec per eval of scrypt with initial params + const uint64_t measured_time = timer.value() / timer.events(); + + const uint64_t target_nsec = msec.count() * static_cast<uint64_t>(1000000); + + uint64_t est_nsec = measured_time; + + // First move increase r by 8x if possible + + if(max_memory_usage == 0 || scrypt_memory_usage(N, r, p)*8 < max_memory_usage) + { + if(target_nsec / est_nsec >= 5) + { + r *= 8; + est_nsec *= 5; + } + } + + while(max_memory_usage == 0 || scrypt_memory_usage(N, r, p)*2 < max_memory_usage) + { + if(target_nsec / est_nsec >= 2) + { + N *= 2; + est_nsec *= 2; + } + else + break; + } + + if(target_nsec / est_nsec > 2) + p *= std::min<size_t>(1024, (target_nsec / est_nsec)); + + return std::unique_ptr<PasswordHash>(new Scrypt(N, r, p)); + } + +std::unique_ptr<PasswordHash> Scrypt_Family::from_params(size_t N, size_t r, size_t p) const + { + return std::unique_ptr<PasswordHash>(new Scrypt(N, r, p)); + } + +Scrypt::Scrypt(size_t N, size_t r, size_t p) : + m_N(N), m_r(r), m_p(p) + { + if(!is_power_of_2(N)) + throw Invalid_Argument("Scrypt N parameter must be a power of 2"); + + if(p == 0 || p > 1024) + throw Invalid_Argument("Invalid or unsupported scrypt p"); + if(r == 0 || r > 256) + throw Invalid_Argument("Invalid or unsupported scrypt r"); + if(N < 1 || N > 4194304) + throw Invalid_Argument("Invalid or unsupported scrypt N"); + } + +std::string Scrypt::to_string() const + { + std::ostringstream oss; + oss << "Scrypt(" << m_N << "," << m_r << "," << m_p << ")"; + return oss.str(); + } + +size_t Scrypt::total_memory_usage() const + { + return scrypt_memory_usage(m_N, m_r, m_p); + } + +void Scrypt::derive_key(uint8_t output[], size_t output_len, + const char* password, size_t password_len, + const uint8_t salt[], size_t salt_len) const + { + scrypt(output, output_len, + password, password_len, + salt, salt_len, + N(), r(), p()); + } + namespace { void scryptBlockMix(size_t r, uint8_t* B, uint8_t* Y) @@ -60,101 +188,31 @@ void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V) } -Scrypt_Params::Scrypt_Params(size_t N, size_t r, size_t p) : - m_N(N), m_r(r), m_p(p) - { - BOTAN_ARG_CHECK(p <= 128, "Invalid scrypt p"); - BOTAN_ARG_CHECK(N <= 4194304 && is_power_of_2(N), "Invalid scrypt N"); - BOTAN_ARG_CHECK(r <= 64, "Invalid scrypt r"); - } - -Scrypt_Params::Scrypt_Params(std::chrono::milliseconds msec) - { - /* - This mapping is highly subjective and machine specific - For simplicity we fix r=8 and p=4 - */ - m_r = 8; - m_p = 4; - - if(msec.count() <= 10) - { - m_N = 4096; - m_p = 1; - } - else if(msec.count() <= 50) - { - m_N = 8192; - } - else if(msec.count() <= 100) - { - m_N = 16384; - } - else if(msec.count() <= 500) - { - m_N = 32768; - } - else - { - m_N = 65536; - } - } - -Scrypt_Params::Scrypt_Params(size_t iterations) - { - // This mapping is highly subjective and machine specific - m_r = 8; - m_p = 4; - - if(iterations < 1000) - { - m_N = 8192; - } - else if(iterations < 5000) - { - m_N = 16384; - } - else if(iterations < 10000) - { - m_N = 32768; - } - else - { - m_N = 65536; - } - } - -void scrypt(uint8_t output[], size_t output_len, - const std::string& password, - const uint8_t salt[], size_t salt_len, - const Scrypt_Params& params) - { - scrypt(output, output_len, password, salt, salt_len, - params.N(), params.r(), params.p()); - } - void scrypt(uint8_t output[], size_t output_len, - const std::string& password, + const char* password, size_t password_len, const uint8_t salt[], size_t salt_len, size_t N, size_t r, size_t p) { - // Upper bounds here are much lower than scrypt maximums yet seem sufficient - BOTAN_ARG_CHECK(p <= 128, "Invalid scrypt p"); - BOTAN_ARG_CHECK(N <= 4194304 && is_power_of_2(N), "Invalid scrypt N"); - BOTAN_ARG_CHECK(r <= 64, "Invalid scrypt r"); - const size_t S = 128 * r; secure_vector<uint8_t> B(p * S); + // temp space + secure_vector<uint8_t> V((N+1) * S); - PKCS5_PBKDF2 pbkdf2(MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)").release()); + auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)"); - pbkdf2.pbkdf(B.data(), B.size(), - password, - salt, salt_len, - 1, std::chrono::milliseconds(0)); + try + { + hmac_sha256->set_key(cast_char_ptr_to_uint8(password), password_len); + } + catch(Invalid_Key_Length&) + { + throw Exception("Scrypt cannot accept passphrases of the provided length"); + } - // temp space - secure_vector<uint8_t> V((N+1) * S); + pbkdf2(*hmac_sha256.get(), + B.data(), B.size(), + salt, salt_len, + 1); // these can be parallel for(size_t i = 0; i != p; ++i) @@ -162,10 +220,10 @@ void scrypt(uint8_t output[], size_t output_len, scryptROMmix(r, N, &B[128*r*i], V); } - pbkdf2.pbkdf(output, output_len, - password, - B.data(), B.size(), - 1, std::chrono::milliseconds(0)); + pbkdf2(*hmac_sha256.get(), + output, output_len, + B.data(), B.size(), + 1); } } diff --git a/src/lib/pbkdf/scrypt/scrypt.h b/src/lib/pbkdf/scrypt/scrypt.h index 199caa4c8..8db46f779 100644 --- a/src/lib/pbkdf/scrypt/scrypt.h +++ b/src/lib/pbkdf/scrypt/scrypt.h @@ -1,5 +1,6 @@ /** * (C) 2018 Jack Lloyd +* (C) 2018 Ribose Inc * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -7,28 +8,61 @@ #ifndef BOTAN_SCRYPT_H_ #define BOTAN_SCRYPT_H_ -#include <botan/types.h> -#include <chrono> -#include <string> +#include <botan/pwdhash.h> namespace Botan { -class Scrypt_Params +/** +* Scrypt key derivation function (RFC 7914) +*/ +class BOTAN_PUBLIC_API(2,8) Scrypt final : public PasswordHash { public: - Scrypt_Params(size_t N, size_t r, size_t p); + Scrypt(size_t N, size_t r, size_t p); - Scrypt_Params(std::chrono::milliseconds msec); + Scrypt(const Scrypt& other) = default; + Scrypt& operator=(const Scrypt&) = default; - Scrypt_Params(size_t iterations); + /** + * Derive a new key under the current Scrypt parameter set + */ + void derive_key(uint8_t out[], size_t out_len, + const char* password, const size_t password_len, + const uint8_t salt[], size_t salt_len) const override; + + std::string to_string() const override; size_t N() const { return m_N; } size_t r() const { return m_r; } size_t p() const { return m_p; } + + size_t iterations() const override { return r(); } + + size_t parallelism() const override { return p(); } + + size_t memory_param() const override { return N(); } + + size_t total_memory_usage() const override; + private: size_t m_N, m_r, m_p; }; +class BOTAN_PUBLIC_API(2,8) Scrypt_Family final : public PasswordHashFamily + { + public: + std::string name() const override; + + std::unique_ptr<PasswordHash> tune(size_t output_length, + std::chrono::milliseconds msec, + size_t max_memory) const override; + + std::unique_ptr<PasswordHash> default_params() const override; + + std::unique_ptr<PasswordHash> from_params( + size_t N, size_t r, size_t p) const override; + }; + /** * Scrypt key derivation function (RFC 7914) * @@ -41,19 +75,47 @@ class Scrypt_Params * @param r the block size parameter * @param p the parallelization parameter * -* Suitable parameters for most uses would be N = 16384, r = 8, p = 1 +* Suitable parameters for most uses would be N = 32768, r = 8, p = 1 * * Scrypt uses approximately (p + N + 1) * 128 * r bytes of memory */ -void BOTAN_UNSTABLE_API scrypt(uint8_t output[], size_t output_len, - const std::string& password, - const uint8_t salt[], size_t salt_len, - size_t N, size_t r, size_t p); - -void BOTAN_UNSTABLE_API scrypt(uint8_t output[], size_t output_len, - const std::string& password, - const uint8_t salt[], size_t salt_len, - const Scrypt_Params& params); +void BOTAN_PUBLIC_API(2,8) scrypt(uint8_t output[], size_t output_len, + const char* password, size_t password_len, + const uint8_t salt[], size_t salt_len, + size_t N, size_t r, size_t p); + +/** +* Scrypt key derivation function (RFC 7914) +* Before 2.8 this function was the primary interface for scrypt +* +* @param output the output will be placed here +* @param output_len length of output +* @param password the user password +* @param salt the salt +* @param salt_len length of salt +* @param N the CPU/Memory cost parameter, must be power of 2 +* @param r the block size parameter +* @param p the parallelization parameter +* +* Suitable parameters for most uses would be N = 32768, r = 8, p = 1 +* +* Scrypt uses approximately (p + N + 1) * 128 * r bytes of memory +*/ +inline void scrypt(uint8_t output[], size_t output_len, + const std::string& password, + const uint8_t salt[], size_t salt_len, + size_t N, size_t r, size_t p) + { + return scrypt(output, output_len, + password.c_str(), password.size(), + salt, salt_len, + N, r, p); + } + +inline size_t scrypt_memory_usage(size_t N, size_t r, size_t p) + { + return 128 * r * (N + p); + } } diff --git a/src/lib/pubkey/pbes2/pbes2.cpp b/src/lib/pubkey/pbes2/pbes2.cpp index fce225e99..e9c2a9df1 100644 --- a/src/lib/pubkey/pbes2/pbes2.cpp +++ b/src/lib/pubkey/pbes2/pbes2.cpp @@ -1,6 +1,7 @@ /* * PKCS #5 PBES2 * (C) 1999-2008,2014 Jack Lloyd +* (C) 2018 Ribose Inc * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -51,13 +52,11 @@ SymmetricKey derive_key(const std::string& passphrase, if(salt.size() < 8) throw Decoding_Error("PBE-PKCS5 v2.0: Encoded salt is too small"); - const std::string prf = OIDS::lookup(prf_algo.get_oid()); - - std::unique_ptr<PBKDF> pbkdf(get_pbkdf("PBKDF2(" + prf + ")")); - if(key_length == 0) key_length = default_key_size; + const std::string prf = OIDS::lookup(prf_algo.get_oid()); + std::unique_ptr<PBKDF> pbkdf(get_pbkdf("PBKDF2(" + prf + ")")); return pbkdf->pbkdf_iterations(key_length, passphrase, salt.data(), salt.size(), iterations); } #if defined(BOTAN_HAS_SCRYPT) @@ -100,30 +99,54 @@ secure_vector<uint8_t> derive_key(const std::string& passphrase, size_t key_length, AlgorithmIdentifier& kdf_algo) { + // TODO should be configurable + const size_t MAX_PBKDF_MEMORY = 32; + const secure_vector<uint8_t> salt = rng.random_vec(12); if(digest == "Scrypt") { #if defined(BOTAN_HAS_SCRYPT) - Scrypt_Params params(32768, 8, 4); + std::unique_ptr<PasswordHashFamily> pwhash_fam = PasswordHashFamily::create_or_throw("Scrypt"); + + std::unique_ptr<PasswordHash> pwhash; if(msec_in_iterations_out) - params = Scrypt_Params(std::chrono::milliseconds(*msec_in_iterations_out)); + { + const std::chrono::milliseconds msec(*msec_in_iterations_out); + pwhash = pwhash_fam->tune(key_length, msec, MAX_PBKDF_MEMORY); + } + else if(iterations_if_msec_null <= 100000) + { + pwhash = pwhash_fam->default_params(); + } else - params = Scrypt_Params(iterations_if_msec_null); + { + //const std::chrono::milliseconds msec(iterations_if_msec_null / 100000); + //pwhash = pwhash_fam->tune(key_length, msec, MAX_PBKDF_MEMORY); + pwhash = pwhash_fam->default_params(); + } secure_vector<uint8_t> key(key_length); - scrypt(key.data(), key.size(), passphrase, - salt.data(), salt.size(), params); + pwhash->derive_key(key.data(), key.size(), + passphrase.c_str(), passphrase.size(), + salt.data(), salt.size()); + + const size_t N = pwhash->memory_param(); + const size_t r = pwhash->iterations(); + const size_t p = pwhash->parallelism(); + + if(msec_in_iterations_out) + *msec_in_iterations_out = 0; std::vector<uint8_t> scrypt_params; DER_Encoder(scrypt_params) .start_cons(SEQUENCE) .encode(salt, OCTET_STRING) - .encode(params.N()) - .encode(params.r()) - .encode(params.p()) + .encode(N) + .encode(r) + .encode(p) .encode(key_length) .end_cons(); @@ -136,26 +159,36 @@ secure_vector<uint8_t> derive_key(const std::string& passphrase, else { const std::string prf = "HMAC(" + digest + ")"; + const std::string pbkdf_name = "PBKDF2(" + prf + ")"; - std::unique_ptr<PBKDF> pbkdf(get_pbkdf("PBKDF2(" + prf + ")")); - - size_t iterations = iterations_if_msec_null; + std::unique_ptr<PasswordHashFamily> pwhash_fam = PasswordHashFamily::create(pbkdf_name); + if(!pwhash_fam) + throw Invalid_Argument("Unknown password hash digest " + digest); - secure_vector<uint8_t> key; + std::unique_ptr<PasswordHash> pwhash; if(msec_in_iterations_out) { - std::chrono::milliseconds msec(*msec_in_iterations_out); - key = pbkdf->derive_key(key_length, passphrase, salt.data(), salt.size(), msec, iterations).bits_of(); - *msec_in_iterations_out = iterations; + const std::chrono::milliseconds msec(*msec_in_iterations_out); + pwhash = pwhash_fam->tune(key_length, msec, MAX_PBKDF_MEMORY); } else { - key = pbkdf->pbkdf_iterations(key_length, passphrase, salt.data(), salt.size(), iterations); + pwhash = pwhash_fam->from_params(iterations_if_msec_null); } + secure_vector<uint8_t> key(key_length); + pwhash->derive_key(key.data(), key.size(), + passphrase.c_str(), passphrase.size(), + salt.data(), salt.size()); + std::vector<uint8_t> pbkdf2_params; + const size_t iterations = pwhash->iterations(); + + if(msec_in_iterations_out) + *msec_in_iterations_out = iterations; + DER_Encoder(pbkdf2_params) .start_cons(SEQUENCE) .encode(salt, OCTET_STRING) |