Improve PBKDF self-tuning

Make the tune interval a build-time configurable instead of hardcoding
it in each source file.

Also use binary search in RFC4880_encode_count instead of linear search.

Fix a bug in Timer

4 files changed, 66 insertions, 65 deletions

diff --git a/src/lib/pbkdf/pbkdf2/pbkdf2.cpp b/src/lib/pbkdf/pbkdf2/pbkdf2.cpp
index 9d0be3a58..6b036f6e0 100644
--- a/src/lib/pbkdf/pbkdf2/pbkdf2.cpp
+++ b/src/lib/pbkdf/pbkdf2/pbkdf2.cpp
@@ -64,19 +64,19 @@ size_t tune_pbkdf2(MessageAuthenticationCode& prf,
    BOTAN_ASSERT_NOMSG(prf_sz > 0);
    secure_vector<uint8_t> U(prf_sz);
 
-   const size_t trial_iterations = 10000;
+   const size_t trial_iterations = 2000;
 
    // Short output ensures we only need a single PBKDF2 block
 
    Timer timer("PBKDF2");
 
-   const std::chrono::milliseconds tune_msec(30);
+   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
 
    prf.set_key(nullptr, 0);
 
-   timer.run_until_elapsed(tune_msec, [&]() {
-      uint8_t out[16] = { 0 };
-      uint8_t salt[16] = { 0 };
+   timer.run_until_elapsed(tune_time, [&]() {
+      uint8_t out[12] = { 0 };
+      uint8_t salt[12] = { 0 };
       pbkdf2(prf, out, sizeof(out), salt, sizeof(salt), trial_iterations);
       });
 
diff --git a/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp b/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
index 1cd07c490..6555183d1 100644
--- a/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
+++ b/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
@@ -9,67 +9,65 @@
 #include <botan/pgp_s2k.h>
 #include <botan/exceptn.h>
 #include <botan/internal/timer.h>
+#include <algorithm>
 
 namespace Botan {
 
+/*
+PGP stores the iteration count as a single byte
+Thus it can only actually take on one of 256 values, based on the
+formula in RFC 4880 section 3.6.1.3
+*/
+static const uint32_t OPENPGP_S2K_ITERS[256] = {
+   1024, 1088, 1152, 1216, 1280, 1344, 1408, 1472, 1536, 1600,
+   1664, 1728, 1792, 1856, 1920, 1984, 2048, 2176, 2304, 2432,
+   2560, 2688, 2816, 2944, 3072, 3200, 3328, 3456, 3584, 3712,
+   3840, 3968, 4096, 4352, 4608, 4864, 5120, 5376, 5632, 5888,
+   6144, 6400, 6656, 6912, 7168, 7424, 7680, 7936, 8192, 8704,
+   9216, 9728, 10240, 10752, 11264, 11776, 12288, 12800, 13312,
+   13824, 14336, 14848, 15360, 15872, 16384, 17408, 18432, 19456,
+   20480, 21504, 22528, 23552, 24576, 25600, 26624, 27648, 28672,
+   29696, 30720, 31744, 32768, 34816, 36864, 38912, 40960, 43008,
+   45056, 47104, 49152, 51200, 53248, 55296, 57344, 59392, 61440,
+   63488, 65536, 69632, 73728, 77824, 81920, 86016, 90112, 94208,
+   98304, 102400, 106496, 110592, 114688, 118784, 122880, 126976,
+   131072, 139264, 147456, 155648, 163840, 172032, 180224, 188416,
+   196608, 204800, 212992, 221184, 229376, 237568, 245760, 253952,
+   262144, 278528, 294912, 311296, 327680, 344064, 360448, 376832,
+   393216, 409600, 425984, 442368, 458752, 475136, 491520, 507904,
+   524288, 557056, 589824, 622592, 655360, 688128, 720896, 753664,
+   786432, 819200, 851968, 884736, 917504, 950272, 983040, 1015808,
+   1048576, 1114112, 1179648, 1245184, 1310720, 1376256, 1441792,
+   1507328, 1572864, 1638400, 1703936, 1769472, 1835008, 1900544,
+   1966080, 2031616, 2097152, 2228224, 2359296, 2490368, 2621440,
+   2752512, 2883584, 3014656, 3145728, 3276800, 3407872, 3538944,
+   3670016, 3801088, 3932160, 4063232, 4194304, 4456448, 4718592,
+   4980736, 5242880, 5505024, 5767168, 6029312, 6291456, 6553600,
+   6815744, 7077888, 7340032, 7602176, 7864320, 8126464, 8388608,
+   8912896, 9437184, 9961472, 10485760, 11010048, 11534336,
+   12058624, 12582912, 13107200, 13631488, 14155776, 14680064,
+   15204352, 15728640, 16252928, 16777216, 17825792, 18874368,
+   19922944, 20971520, 22020096, 23068672, 24117248, 25165824,
+   26214400, 27262976, 28311552, 29360128, 30408704, 31457280,
+   32505856, 33554432, 35651584, 37748736, 39845888, 41943040,
+   44040192, 46137344, 48234496, 50331648, 52428800, 54525952,
+   56623104, 58720256, 60817408, 62914560, 65011712 };
+
 uint8_t RFC4880_encode_count(size_t desired_iterations)
    {
-   /*
-   Only 256 different iterations are actually representable in OpenPGP format ...
-   */
-   for(size_t c = 0; c < 256; ++c)
-      {
-      // TODO could binary search
-      const size_t decoded_iter = RFC4880_decode_count(static_cast<uint8_t>(c));
-      if(decoded_iter >= desired_iterations)
-         return static_cast<uint8_t>(c);
-      }
+   if(desired_iterations <= OPENPGP_S2K_ITERS[0])
+      return 0;
+
+   if(desired_iterations >= OPENPGP_S2K_ITERS[255])
+      return 255;
 
-   return 255;
+   auto i = std::upper_bound(OPENPGP_S2K_ITERS, OPENPGP_S2K_ITERS + 256, desired_iterations);
+
+   return (i - OPENPGP_S2K_ITERS);
    }
 
 size_t RFC4880_decode_count(uint8_t iter)
    {
-   /*
-   PGP stores the iteration count as a single byte
-   Thus it can only actually take on one of 256 values, based on the
-   formula in RFC 4880 section 3.6.1.3
-   */
-   static const uint32_t OPENPGP_S2K_ITERS[256] = {
-      1024, 1088, 1152, 1216, 1280, 1344, 1408, 1472, 1536, 1600,
-      1664, 1728, 1792, 1856, 1920, 1984, 2048, 2176, 2304, 2432,
-      2560, 2688, 2816, 2944, 3072, 3200, 3328, 3456, 3584, 3712,
-      3840, 3968, 4096, 4352, 4608, 4864, 5120, 5376, 5632, 5888,
-      6144, 6400, 6656, 6912, 7168, 7424, 7680, 7936, 8192, 8704,
-      9216, 9728, 10240, 10752, 11264, 11776, 12288, 12800, 13312,
-      13824, 14336, 14848, 15360, 15872, 16384, 17408, 18432, 19456,
-      20480, 21504, 22528, 23552, 24576, 25600, 26624, 27648, 28672,
-      29696, 30720, 31744, 32768, 34816, 36864, 38912, 40960, 43008,
-      45056, 47104, 49152, 51200, 53248, 55296, 57344, 59392, 61440,
-      63488, 65536, 69632, 73728, 77824, 81920, 86016, 90112, 94208,
-      98304, 102400, 106496, 110592, 114688, 118784, 122880, 126976,
-      131072, 139264, 147456, 155648, 163840, 172032, 180224, 188416,
-      196608, 204800, 212992, 221184, 229376, 237568, 245760, 253952,
-      262144, 278528, 294912, 311296, 327680, 344064, 360448, 376832,
-      393216, 409600, 425984, 442368, 458752, 475136, 491520, 507904,
-      524288, 557056, 589824, 622592, 655360, 688128, 720896, 753664,
-      786432, 819200, 851968, 884736, 917504, 950272, 983040, 1015808,
-      1048576, 1114112, 1179648, 1245184, 1310720, 1376256, 1441792,
-      1507328, 1572864, 1638400, 1703936, 1769472, 1835008, 1900544,
-      1966080, 2031616, 2097152, 2228224, 2359296, 2490368, 2621440,
-      2752512, 2883584, 3014656, 3145728, 3276800, 3407872, 3538944,
-      3670016, 3801088, 3932160, 4063232, 4194304, 4456448, 4718592,
-      4980736, 5242880, 5505024, 5767168, 6029312, 6291456, 6553600,
-      6815744, 7077888, 7340032, 7602176, 7864320, 8126464, 8388608,
-      8912896, 9437184, 9961472, 10485760, 11010048, 11534336,
-      12058624, 12582912, 13107200, 13631488, 14155776, 14680064,
-      15204352, 15728640, 16252928, 16777216, 17825792, 18874368,
-      19922944, 20971520, 22020096, 23068672, 24117248, 25165824,
-      26214400, 27262976, 28311552, 29360128, 30408704, 31457280,
-      32505856, 33554432, 35651584, 37748736, 39845888, 41943040,
-      44040192, 46137344, 48234496, 50331648, 52428800, 54525952,
-      56623104, 58720256, 60817408, 62914560, 65011712 };
-
    return OPENPGP_S2K_ITERS[iter];
    }
 
@@ -160,18 +158,17 @@ std::string RFC4880_S2K_Family::name() const
 
 std::unique_ptr<PasswordHash> RFC4880_S2K_Family::tune(size_t output_len, std::chrono::milliseconds msec, size_t) const
    {
-   const std::chrono::milliseconds tune_time = std::chrono::milliseconds(30);
+   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
 
    const size_t buf_size = 1024;
-   Botan::secure_vector<uint8_t> buffer(buf_size);
+   std::vector<uint8_t> buffer(buf_size);
 
    Timer timer("RFC4880_S2K", buf_size);
    timer.run_until_elapsed(tune_time, [&]() {
       m_hash->update(buffer);
       });
 
-   // bug in Timer::bytes_per_second?
-   const double hash_bytes_per_second = buf_size * timer.bytes_per_second();
+   const double hash_bytes_per_second = timer.bytes_per_second();
    const uint64_t desired_nsec = msec.count() * 1000000;
 
    const size_t hash_size = m_hash->output_length();
diff --git a/src/lib/pbkdf/scrypt/scrypt.cpp b/src/lib/pbkdf/scrypt/scrypt.cpp
index c20225734..e50073669 100644
--- a/src/lib/pbkdf/scrypt/scrypt.cpp
+++ b/src/lib/pbkdf/scrypt/scrypt.cpp
@@ -50,10 +50,10 @@ std::unique_ptr<PasswordHash> Scrypt_Family::tune(size_t output_length,
    size_t r = 1;
    size_t p = 1;
 
-   Timer timer("Scrypt", 0);
-   const std::chrono::milliseconds tune_msec(30);
+   Timer timer("Scrypt");
+   const auto tune_time = BOTAN_PBKDF_TUNING_TIME;
 
-   timer.run_until_elapsed(tune_msec, [&]() {
+   timer.run_until_elapsed(tune_time, [&]() {
       uint8_t output[32] = { 0 };
       scrypt(output, sizeof(output), "test", 4, nullptr, 0, N, r, p);
       });
diff --git a/src/lib/utils/timer.h b/src/lib/utils/timer.h
index 3240b5c85..5182aa2eb 100644
--- a/src/lib/utils/timer.h
+++ b/src/lib/utils/timer.h
@@ -31,8 +31,12 @@ class BOTAN_TEST_API Timer final
          , m_clock_speed(clock_speed)
          {}
 
-      Timer(const std::string& name, size_t buf_size = 0) :
-         Timer(name, "", "", 1, buf_size, 0.0, 0)
+      Timer(const std::string& name) :
+         Timer(name, "", "", 1, 0, 0.0, 0)
+         {}
+
+      Timer(const std::string& name, size_t buf_size) :
+         Timer(name, "", "", buf_size, buf_size, 0.0, 0)
          {}
 
       Timer(const Timer& other) = default;