From 2d9b4aaa8bc80dd2bbefabebd52826caac532f82 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Sat, 29 Dec 2018 09:17:48 -0500 Subject: 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 --- src/build-data/buildh.in | 6 +++ src/lib/pbkdf/pbkdf2/pbkdf2.cpp | 10 ++-- src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp | 107 ++++++++++++++++++-------------------- src/lib/pbkdf/scrypt/scrypt.cpp | 6 +-- src/lib/utils/timer.h | 8 ++- 5 files changed, 72 insertions(+), 65 deletions(-) diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in index 17df7791b..d37c183cf 100644 --- a/src/build-data/buildh.in +++ b/src/build-data/buildh.in @@ -213,6 +213,12 @@ Each read generates 32 bits of output */ #define BOTAN_ENTROPY_RDSEED_RETRIES 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/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 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 #include #include +#include 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(c)); - if(decoded_iter >= desired_iterations) - return static_cast(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 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 buffer(buf_size); + std::vector 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 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; -- cgit v1.2.3