diff options
Diffstat (limited to 'comm/third_party/botan/src/lib/pbkdf/scrypt/scrypt.cpp')
-rw-r--r-- | comm/third_party/botan/src/lib/pbkdf/scrypt/scrypt.cpp | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/pbkdf/scrypt/scrypt.cpp b/comm/third_party/botan/src/lib/pbkdf/scrypt/scrypt.cpp new file mode 100644 index 0000000000..8275ac9567 --- /dev/null +++ b/comm/third_party/botan/src/lib/pbkdf/scrypt/scrypt.cpp @@ -0,0 +1,249 @@ +/** +* (C) 2018 Jack Lloyd +* (C) 2018 Ribose Inc +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include <botan/scrypt.h> +#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 + */ + + 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"); + const auto tune_time = BOTAN_PBKDF_TUNING_TIME; + + timer.run_until_elapsed(tune_time, [&]() { + 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; + } + } + + // Now double N as many times as we can + + 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 we have extra runtime budget, increment p + + if(target_nsec / est_nsec > 2) + p *= std::min<size_t>(1024, static_cast<size_t>(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)); + } + +std::unique_ptr<PasswordHash> Scrypt_Family::from_iterations(size_t iter) const + { + const size_t r = 8; + const size_t p = 1; + + size_t N = 8192; + + if(iter > 50000) + N = 16384; + if(iter > 100000) + N = 32768; + if(iter > 150000) + N = 65536; + + 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) + { + uint32_t B32[16]; + secure_vector<uint8_t> X(64); + copy_mem(X.data(), &B[(2*r-1)*64], 64); + + for(size_t i = 0; i != 2*r; i++) + { + xor_buf(X.data(), &B[64*i], 64); + load_le<uint32_t>(B32, X.data(), 16); + Salsa20::salsa_core(X.data(), B32, 8); + copy_mem(&Y[64*i], X.data(), 64); + } + + for(size_t i = 0; i < r; ++i) + { + copy_mem(&B[i*64], &Y[(i * 2) * 64], 64); + } + + for(size_t i = 0; i < r; ++i) + { + copy_mem(&B[(i + r) * 64], &Y[(i * 2 + 1) * 64], 64); + } + } + +void scryptROMmix(size_t r, size_t N, uint8_t* B, secure_vector<uint8_t>& V) + { + const size_t S = 128 * r; + + for(size_t i = 0; i != N; ++i) + { + copy_mem(&V[S*i], B, S); + scryptBlockMix(r, B, &V[N*S]); + } + + for(size_t i = 0; i != N; ++i) + { + // compiler doesn't know here that N is power of 2 + const size_t j = load_le<uint32_t>(&B[(2*r-1)*64], 0) & (N - 1); + xor_buf(B, &V[j*S], S); + scryptBlockMix(r, B, &V[N*S]); + } + } + +} + +void 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) + { + const size_t S = 128 * r; + secure_vector<uint8_t> B(p * S); + // temp space + secure_vector<uint8_t> V((N+1) * S); + + auto hmac_sha256 = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)"); + + try + { + hmac_sha256->set_key(cast_char_ptr_to_uint8(password), password_len); + } + catch(Invalid_Key_Length&) + { + throw Invalid_Argument("Scrypt cannot accept passphrases of the provided length"); + } + + pbkdf2(*hmac_sha256.get(), + B.data(), B.size(), + salt, salt_len, + 1); + + // these can be parallel + for(size_t i = 0; i != p; ++i) + { + scryptROMmix(r, N, &B[128*r*i], V); + } + + pbkdf2(*hmac_sha256.get(), + output, output_len, + B.data(), B.size(), + 1); + } + +} |