Repository: randombit/botan
Pull request #3401 (2023-03-20 22:29:49)

Allow runtime configuration of PBKDF tuning runtime
Previously this was a hardcoded parameter in build.h


Patch:
diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index 9fa9a4bb3..3d67876c6 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -240,12 +240,6 @@
 #define BOTAN_SYSTEM_RNG_POLL_REQUEST 64
 #define BOTAN_SYSTEM_RNG_POLL_TIMEOUT_MS 20
 
-/**
-* When a PBKDF is self-tuning parameters, it will attempt to take about this
-* amount of time to self-benchmark.
-*/
-#define BOTAN_PBKDF_TUNING_TIME std::chrono::milliseconds(10)
-
 /**
 * If no way of dynamically determining the cache line size for the
 * system exists, this value is used as the default. Used by the side
diff --git a/src/cli/pbkdf.cpp b/src/cli/pbkdf.cpp
index 079e121e7..81959a518 100644
--- a/src/cli/pbkdf.cpp
+++ b/src/cli/pbkdf.cpp
@@ -18,7 +18,7 @@ namespace Botan_CLI {
 class PBKDF_Tune final : public Command
    {
    public:
-      PBKDF_Tune() : Command("pbkdf_tune --algo=Scrypt --max-mem=256 --output-len=32 --check *times") {}
+      PBKDF_Tune() : Command("pbkdf_tune --algo=Scrypt --max-mem=256 --tune-msec=10 --output-len=32 --check *times") {}
 
       std::string group() const override
          {
@@ -33,12 +33,12 @@ class PBKDF_Tune final : public Command
       void go() override
          {
          const size_t output_len = get_arg_sz("output-len");
-         const std::string algo = get_arg("algo");
          const size_t max_mem = get_arg_sz("max-mem");
+         const auto tune_msec = std::chrono::milliseconds(get_arg_sz("tune-msec"));
+         const std::string algo = get_arg("algo");
          const bool check_time = flag_set("check");
 
-         std::unique_ptr<Botan::PasswordHashFamily> pwdhash_fam =
-            Botan::PasswordHashFamily::create(algo);
+         auto pwdhash_fam = Botan::PasswordHashFamily::create(algo);
 
          if(!pwdhash_fam)
             throw CLI_Error_Unsupported("Password hashing", algo);
@@ -63,7 +63,7 @@ class PBKDF_Tune final : public Command
                   throw CLI_Usage_Error("Unknown time value '" + time + "' for pbkdf_tune");
                   }
 
-               pwhash = pwdhash_fam->tune(output_len, std::chrono::milliseconds(msec), max_mem);
+               pwhash = pwdhash_fam->tune(output_len, std::chrono::milliseconds(msec), max_mem, tune_msec);
                }
 
             output() << "For " << time << " ms selected " << pwhash->to_string();
diff --git a/src/lib/pbkdf/argon2/argon2.h b/src/lib/pbkdf/argon2/argon2.h
index 25833e9e3..4e125dd7d 100644
--- a/src/lib/pbkdf/argon2/argon2.h
+++ b/src/lib/pbkdf/argon2/argon2.h
@@ -90,7 +90,8 @@ class BOTAN_PUBLIC_API(2,11) Argon2_Family final : public PasswordHashFamily
 
       std::unique_ptr<PasswordHash> tune(size_t output_length,
                                          std::chrono::milliseconds msec,
-                                         size_t max_memory) const override;
+                                         size_t max_memory,
+                                         std::chrono::milliseconds tune_msec) const override;
 
       std::unique_ptr<PasswordHash> default_params() const override;
 
diff --git a/src/lib/pbkdf/argon2/argon2pwhash.cpp b/src/lib/pbkdf/argon2/argon2pwhash.cpp
index 0bf2210d0..e97f1c2e8 100644
--- a/src/lib/pbkdf/argon2/argon2pwhash.cpp
+++ b/src/lib/pbkdf/argon2/argon2pwhash.cpp
@@ -86,18 +86,18 @@ std::string Argon2_Family::name() const
 
 std::unique_ptr<PasswordHash> Argon2_Family::tune(size_t /*output_length*/,
                                                   std::chrono::milliseconds msec,
-                                                  size_t max_memory) const
+                                                  size_t max_memory,
+                                                  std::chrono::milliseconds tune_time) const
    {
    const size_t max_kib = (max_memory == 0) ? 256*1024 : max_memory*1024;
 
    // Tune with a large memory otherwise we measure cache vs RAM speeds and underestimate
    // costs for larger params. Default is 36 MiB, or use 128 for long times.
-   const size_t tune_M = (msec >= std::chrono::milliseconds(500) ? 128 : 36) * 1024;
+   const size_t tune_M = (msec >= std::chrono::milliseconds(200) ? 128 : 36) * 1024;
    const size_t p = 1;
    size_t t = 1;
 
    Timer timer("Argon2");
-   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
 
    auto pwhash = this->from_params(tune_M, t, p);
 
@@ -139,7 +139,7 @@ std::unique_ptr<PasswordHash> Argon2_Family::tune(size_t /*output_length*/,
       est_nsec *= M_mult;
       }
 
-   if(est_nsec < target_nsec)
+   if(est_nsec < target_nsec / 2)
       {
       const uint64_t desired_cost_increase = (target_nsec + est_nsec - 1) / est_nsec;
       t *= static_cast<size_t>(desired_cost_increase);
diff --git a/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.cpp b/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.cpp
index da0dd791b..f312c7e51 100644
--- a/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.cpp
+++ b/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.cpp
@@ -30,10 +30,10 @@ std::string Bcrypt_PBKDF_Family::name() const
 
 std::unique_ptr<PasswordHash> Bcrypt_PBKDF_Family::tune(size_t output_length,
                                                         std::chrono::milliseconds msec,
-                                                        size_t /*max_memory*/) const
+                                                        size_t /*max_memory*/,
+                                                        std::chrono::milliseconds tune_time) const
    {
    Timer timer("Bcrypt_PBKDF");
-   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
 
    const size_t blocks = (output_length + 32 - 1) / 32;
 
diff --git a/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.h b/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.h
index ce6a3c718..85f1bad33 100644
--- a/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.h
+++ b/src/lib/pbkdf/bcrypt_pbkdf/bcrypt_pbkdf.h
@@ -54,7 +54,8 @@ class BOTAN_PUBLIC_API(2,11) Bcrypt_PBKDF_Family final : public PasswordHashFami
 
       std::unique_ptr<PasswordHash> tune(size_t output_length,
                                          std::chrono::milliseconds msec,
-                                         size_t max_memory) const override;
+                                         size_t max_memory,
+                                         std::chrono::milliseconds tune_msec) const override;
 
       std::unique_ptr<PasswordHash> default_params() const override;
 
diff --git a/src/lib/pbkdf/pbkdf2/pbkdf2.cpp b/src/lib/pbkdf/pbkdf2/pbkdf2.cpp
index 8e2b56f65..873d8040a 100644
--- a/src/lib/pbkdf/pbkdf2/pbkdf2.cpp
+++ b/src/lib/pbkdf/pbkdf2/pbkdf2.cpp
@@ -28,36 +28,10 @@ void pbkdf2_set_key(MessageAuthenticationCode& prf,
       }
    }
 
-}
-
-size_t
-pbkdf2(MessageAuthenticationCode& prf,
-       uint8_t out[],
-       size_t out_len,
-       const std::string& password,
-       const uint8_t salt[], size_t salt_len,
-       size_t iterations,
-       std::chrono::milliseconds msec)
-   {
-   if(iterations == 0)
-      {
-      iterations = PBKDF2(prf, out_len, msec).iterations();
-      }
-
-   PBKDF2 pbkdf2(prf, iterations);
-
-   pbkdf2.derive_key(out, out_len,
-                     password.c_str(), password.size(),
-                     salt, salt_len);
-
-   return iterations;
-   }
-
-namespace {
-
 size_t tune_pbkdf2(MessageAuthenticationCode& prf,
                    size_t output_length,
-                   uint32_t msec)
+                   std::chrono::milliseconds msec,
+                   std::chrono::milliseconds tune_time = std::chrono::milliseconds(10))
    {
    if(output_length == 0)
       output_length = 1;
@@ -72,8 +46,6 @@ size_t tune_pbkdf2(MessageAuthenticationCode& prf,
 
    Timer timer("PBKDF2");
 
-   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
-
    prf.set_key(nullptr, 0);
 
    timer.run_until_elapsed(tune_time, [&]() {
@@ -87,7 +59,7 @@ size_t tune_pbkdf2(MessageAuthenticationCode& prf,
 
    const uint64_t duration_nsec = timer.value() / timer.events();
 
-   const uint64_t desired_nsec = static_cast<uint64_t>(msec) * 1000000;
+   const uint64_t desired_nsec = static_cast<uint64_t>(msec.count()) * 1000000;
 
    if(duration_nsec > desired_nsec)
       return trial_iterations;
@@ -104,6 +76,29 @@ size_t tune_pbkdf2(MessageAuthenticationCode& prf,
 
 }
 
+size_t
+pbkdf2(MessageAuthenticationCode& prf,
+       uint8_t out[],
+       size_t out_len,
+       const std::string& password,
+       const uint8_t salt[], size_t salt_len,
+       size_t iterations,
+       std::chrono::milliseconds msec)
+   {
+   if(iterations == 0)
+      {
+      iterations = tune_pbkdf2(prf, out_len, msec);
+      }
+
+   PBKDF2 pbkdf2(prf, iterations);
+
+   pbkdf2.derive_key(out, out_len,
+                     password.c_str(), password.size(),
+                     salt, salt_len);
+
+   return iterations;
+   }
+
 void pbkdf2(MessageAuthenticationCode& prf,
             uint8_t out[],
             size_t out_len,
@@ -157,7 +152,7 @@ PKCS5_PBKDF2::pbkdf(uint8_t key[], size_t key_len,
    {
    if(iterations == 0)
       {
-      iterations = PBKDF2(*m_mac, key_len, msec).iterations();
+      iterations = tune_pbkdf2(*m_mac, key_len, msec);
       }
 
    PBKDF2 pbkdf2(*m_mac, iterations);
@@ -183,7 +178,7 @@ std::unique_ptr<PBKDF> PKCS5_PBKDF2::new_object() const
 
 PBKDF2::PBKDF2(const MessageAuthenticationCode& prf, size_t olen, std::chrono::milliseconds msec) :
    m_prf(prf.new_object()),
-   m_iterations(tune_pbkdf2(*m_prf, olen, static_cast<uint32_t>(msec.count())))
+   m_iterations(tune_pbkdf2(*m_prf, olen, msec))
    {}
 
 std::string PBKDF2::to_string() const
@@ -204,9 +199,14 @@ std::string PBKDF2_Family::name() const
    return "PBKDF2(" + m_prf->name() + ")";
    }
 
-std::unique_ptr<PasswordHash> PBKDF2_Family::tune(size_t output_len, std::chrono::milliseconds msec, size_t /*max_memory_usage_mb*/) const
+std::unique_ptr<PasswordHash> PBKDF2_Family::tune(
+   size_t output_len,
+   std::chrono::milliseconds msec,
+   size_t /*max_memory_usage_mb*/,
+   std::chrono::milliseconds tune_time) const
    {
-   return std::make_unique<PBKDF2>(*m_prf, output_len, msec);
+   auto iterations = tune_pbkdf2(*m_prf, output_len, msec, tune_time);
+   return std::make_unique<PBKDF2>(*m_prf, iterations);
    }
 
 std::unique_ptr<PasswordHash> PBKDF2_Family::default_params() const
diff --git a/src/lib/pbkdf/pbkdf2/pbkdf2.h b/src/lib/pbkdf/pbkdf2/pbkdf2.h
index d56e53db7..d87e18613 100644
--- a/src/lib/pbkdf/pbkdf2/pbkdf2.h
+++ b/src/lib/pbkdf/pbkdf2/pbkdf2.h
@@ -44,6 +44,7 @@ class BOTAN_PUBLIC_API(2,8) PBKDF2 final : public PasswordHash
          m_iterations(iter)
          {}
 
+      BOTAN_DEPRECATED("For runtime tuning use PBKDF2_Family::tune")
       PBKDF2(const MessageAuthenticationCode& prf, size_t olen, std::chrono::milliseconds msec);
 
       size_t iterations() const override { return m_iterations; }
@@ -71,7 +72,8 @@ class BOTAN_PUBLIC_API(2,8) PBKDF2_Family final : public PasswordHashFamily
 
       std::unique_ptr<PasswordHash> tune(size_t output_len,
                                          std::chrono::milliseconds msec,
-                                         size_t max_memory) const override;
+                                         size_t max_memory,
+                                         std::chrono::milliseconds tune_msec) const override;
 
       /**
       * Return some default parameter set for this PBKDF that should be good
diff --git a/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp b/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
index ae0b476cb..abcb81cd3 100644
--- a/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
+++ b/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
@@ -82,7 +82,7 @@ size_t OpenPGP_S2K::pbkdf(uint8_t output_buf[], size_t output_len,
    if(iterations == 0)
       {
       RFC4880_S2K_Family s2k_params(m_hash->new_object());
-      iterations = s2k_params.tune(output_len, msec, 0)->iterations();
+      iterations = s2k_params.tune(output_len, msec, 0, std::chrono::milliseconds(10))->iterations();
       }
 
    pgp_s2k(*m_hash, output_buf, output_len,
@@ -98,10 +98,12 @@ std::string RFC4880_S2K_Family::name() const
    return "OpenPGP-S2K(" + m_hash->name() + ")";
    }
 
-std::unique_ptr<PasswordHash> RFC4880_S2K_Family::tune(size_t output_len, std::chrono::milliseconds msec, size_t /*max_memory_usage_mb*/) const
+std::unique_ptr<PasswordHash> RFC4880_S2K_Family::tune(
+   size_t output_len,
+   std::chrono::milliseconds msec,
+   size_t /*max_memory_usage_mb*/,
+   std::chrono::milliseconds tune_time) const
    {
-   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
-
    const size_t buf_size = 1024;
    std::vector<uint8_t> buffer(buf_size);
 
diff --git a/src/lib/pbkdf/pgp_s2k/pgp_s2k.h b/src/lib/pbkdf/pgp_s2k/pgp_s2k.h
index 73fb1f449..687eee239 100644
--- a/src/lib/pbkdf/pgp_s2k/pgp_s2k.h
+++ b/src/lib/pbkdf/pgp_s2k/pgp_s2k.h
@@ -118,7 +118,8 @@ class BOTAN_PUBLIC_API(2,8) RFC4880_S2K_Family final : public PasswordHashFamily
 
       std::unique_ptr<PasswordHash> tune(size_t output_len,
                                          std::chrono::milliseconds msec,
-                                         size_t max_mem) const override;
+                                         size_t max_mem,
+                                         std::chrono::milliseconds tune_msec) const override;
 
       /**
       * Return some default parameter set for this PBKDF that should be good
diff --git a/src/lib/pbkdf/pwdhash.h b/src/lib/pbkdf/pwdhash.h
index 775e8b79c..7f44a3db2 100644
--- a/src/lib/pbkdf/pwdhash.h
+++ b/src/lib/pbkdf/pwdhash.h
@@ -146,10 +146,12 @@ class BOTAN_PUBLIC_API(2,8) PasswordHashFamily
       * the returned parameters will require, in mebibytes (2**20 bytes). It may
       * require some small amount above the request. Set to zero to place no
       * limit at all.
+      * @pram tuning_msec how long to run the tuning loop
       */
       virtual std::unique_ptr<PasswordHash> tune(size_t output_length,
                                                  std::chrono::milliseconds msec,
-                                                 size_t max_memory_usage_mb = 0) const = 0;
+                                                 size_t max_memory_usage_mb = 0,
+                                                 std::chrono::milliseconds tuning_msec = std::chrono::milliseconds(10)) const = 0;
 
       /**
       * Return some default parameter set for this PBKDF that should be good
diff --git a/src/lib/pbkdf/scrypt/scrypt.cpp b/src/lib/pbkdf/scrypt/scrypt.cpp
index 6f2c6a54b..b1a05db26 100644
--- a/src/lib/pbkdf/scrypt/scrypt.cpp
+++ b/src/lib/pbkdf/scrypt/scrypt.cpp
@@ -37,7 +37,8 @@ std::unique_ptr<PasswordHash> Scrypt_Family::default_params() const
 
 std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
                                                   std::chrono::milliseconds msec,
-                                                  size_t max_memory_usage_mb) const
+                                                  size_t max_memory_usage_mb,
+                                                  std::chrono::milliseconds tune_time) const
    {
    BOTAN_UNUSED(output_length);
 
@@ -53,14 +54,17 @@ std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
    * Compute stime(8192,1,1) as baseline and extrapolate
    */
 
-   const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024;
+   // We include a bit of slop here (the + 512) to handle the fact that scrypt's
+   // memory consumption is modified by all three parameters, and otherwise we
+   // stop before hitting the desired target.
+
+   const size_t max_memory_usage = max_memory_usage_mb * 1024 * 1024 + 512;
    // Starting parameters
-   size_t N = 8192;
+   size_t N = 8*1024;
    size_t r = 1;
    size_t p = 1;
 
    Timer timer("Scrypt");
-   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
 
    auto pwdhash = this->from_params(N, r, p);
 
@@ -85,7 +89,7 @@ std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
 
    // First move increase r by 8x if possible
 
-   if(max_memory_usage == 0 || scrypt_memory_usage(N, r, p)*8 < max_memory_usage)
+   if(max_memory_usage == 0 || scrypt_memory_usage(N, r*8, p) <= max_memory_usage)
       {
       if(target_nsec / est_nsec >= 5)
          {
@@ -96,7 +100,7 @@ std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
 
    // Now double N as many times as we can
 
-   while(max_memory_usage == 0 || scrypt_memory_usage(N, r, p)*2 < max_memory_usage)
+   while(max_memory_usage == 0 || scrypt_memory_usage(N*2, r, p) <= max_memory_usage)
       {
       if(target_nsec / est_nsec >= 2)
          {
diff --git a/src/lib/pbkdf/scrypt/scrypt.h b/src/lib/pbkdf/scrypt/scrypt.h
index 7a5b3478c..0eec830f0 100644
--- a/src/lib/pbkdf/scrypt/scrypt.h
+++ b/src/lib/pbkdf/scrypt/scrypt.h
@@ -53,7 +53,8 @@ class BOTAN_PUBLIC_API(2,8) Scrypt_Family final : public PasswordHashFamily
 
       std::unique_ptr<PasswordHash> tune(size_t output_length,
                                          std::chrono::milliseconds msec,
-                                         size_t max_memory) const override;
+                                         size_t max_memory,
+                                         std::chrono::milliseconds tune_msec) const override;
 
       std::unique_ptr<PasswordHash> default_params() const override;
 


Test patch:
diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py
index cf4250c9c..72ffb70d3 100755
--- a/src/scripts/test_cli.py
+++ b/src/scripts/test_cli.py
@@ -433,7 +433,7 @@ def cli_pbkdf_tune_tests(_tmp_dir):
 
     expected = re.compile(r'For (default|[1-9][0-9]*) ms selected Scrypt\([0-9]+,[0-9]+,[0-9]+\) using [0-9]+ MiB')
 
-    output = test_cli("pbkdf_tune", ["--check", "1", "10", "50", "default"], None).split('\n')
+    output = test_cli("pbkdf_tune", ["--tune-msec=1", "--check", "1", "10", "50", "default"], None).split('\n')
 
     for line in output:
         if expected.match(line) is None:
diff --git a/src/tests/test_c25519.cpp b/src/tests/test_c25519.cpp
index 72d1b0961..bc68b27a8 100644
--- a/src/tests/test_c25519.cpp
+++ b/src/tests/test_c25519.cpp
@@ -88,7 +88,7 @@ class Curve25519_Roundtrip_Test final : public Test
 
             const std::string a_pass = "alice pass";
             const std::string b_pass = "bob pass";
-            const auto pbe_time = std::chrono::milliseconds(10);
+            const auto pbe_time = std::chrono::milliseconds(1);
             const std::string a_priv_pem = Botan::PKCS8::PEM_encode(a_priv_gen, Test::rng(), a_pass, pbe_time);
             const std::string b_priv_pem = Botan::PKCS8::PEM_encode(b_priv_gen, Test::rng(), b_pass, pbe_time);
 
diff --git a/src/tests/test_pbkdf.cpp b/src/tests/test_pbkdf.cpp
index 2e74b6098..990d45489 100644
--- a/src/tests/test_pbkdf.cpp
+++ b/src/tests/test_pbkdf.cpp
@@ -90,6 +90,10 @@ class Pwdhash_Tests : public Test
             "Bcrypt-PBKDF"
          };
 
+         const auto run_time = std::chrono::milliseconds(3);
+         const auto tune_time = std::chrono::milliseconds(1);
+         const size_t max_mem = 32;
+
          for(const std::string& pwdhash : all_pwdhash)
             {
             Test::Result result("Pwdhash " + pwdhash);
@@ -102,7 +106,7 @@ class Pwdhash_Tests : public Test
                const std::vector<uint8_t> salt(8);
                const std::string password = "test";
 
-               auto tuned_pwhash = pwdhash_fam->tune(32, std::chrono::milliseconds(10));
+               auto tuned_pwhash = pwdhash_fam->tune(32, run_time, max_mem, tune_time);
 
                std::vector<uint8_t> output1(32);
                tuned_pwhash->derive_key(output1.data(), output1.size(),
diff --git a/src/tests/test_pubkey.cpp b/src/tests/test_pubkey.cpp
index 9e8952906..025684fb5 100644
--- a/src/tests/test_pubkey.cpp
+++ b/src/tests/test_pubkey.cpp
@@ -656,7 +656,7 @@ void test_pbe_roundtrip(Test::Result& result,
       {
       Botan::DataSource_Memory data_src(
          Botan::PKCS8::PEM_encode(key, Test::rng(), passphrase,
-                                  std::chrono::milliseconds(10),
+                                  std::chrono::milliseconds(1),
                                   pbe_algo));
 
       auto loaded = Botan::PKCS8::load_key(data_src, passphrase);
@@ -674,7 +674,7 @@ void test_pbe_roundtrip(Test::Result& result,
       {
       Botan::DataSource_Memory data_src(
          Botan::PKCS8::BER_encode(key, Test::rng(), passphrase,
-                                  std::chrono::milliseconds(10),
+                                  std::chrono::milliseconds(1),
                                   pbe_algo));
 
       auto loaded = Botan::PKCS8::load_key(data_src, passphrase);