Convert Scrypt

This also changes some (library only) APIs so PBES2 needed to
be modified.

This is a contribution of Ribose Inc (@riboseinc)

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)