Convert PGP-S2K

This is a contribution by Ribose Inc (@riboseinc)

2 files changed, 225 insertions, 63 deletions

diff --git a/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp b/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
index df659de3c..65e4e72c0 100644
--- a/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
+++ b/src/lib/pbkdf/pgp_s2k/pgp_s2k.cpp
@@ -1,64 +1,26 @@
 /*
 * OpenPGP S2K
 * (C) 1999-2007,2017 Jack Lloyd
+* (C) 2018 Ribose Inc
 *
 * Distributed under the terms of the Botan license
 */
 
 #include <botan/pgp_s2k.h>
 #include <botan/exceptn.h>
+#include <botan/internal/timer.h>
 
 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 };
-
-//static
-uint8_t OpenPGP_S2K::encode_count(size_t desired_iterations)
+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)
       {
-      const uint32_t decoded_iter = OPENPGP_S2K_ITERS[c];
+      // TODO could binary search
+      const uint32_t decoded_iter = RFC4880_decode_count(c);
       if(decoded_iter >= desired_iterations)
          return static_cast<uint8_t>(c);
       }
@@ -66,37 +28,75 @@ uint8_t OpenPGP_S2K::encode_count(size_t desired_iterations)
    return 255;
    }
 
-//static
-size_t OpenPGP_S2K::decode_count(uint8_t iter)
+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];
    }
 
-size_t OpenPGP_S2K::pbkdf(uint8_t output_buf[], size_t output_len,
-                          const std::string& passphrase,
-                          const uint8_t salt[], size_t salt_len,
-                          size_t iterations,
-                          std::chrono::milliseconds msec) const
-   {
-   if(iterations == 0 && msec.count() > 0) // FIXME
-      throw Not_Implemented("OpenPGP_S2K does not implemented timed KDF");
+namespace {
 
+void pgp_s2k(HashFunction& hash,
+             uint8_t output_buf[], size_t output_len,
+             const char* password, const size_t password_size,
+             const uint8_t salt[], size_t salt_len,
+             size_t iterations)
+   {
    if(iterations > 1 && salt_len == 0)
       throw Invalid_Argument("OpenPGP_S2K requires a salt in iterated mode");
 
-   secure_vector<uint8_t> input_buf(salt_len + passphrase.size());
+   secure_vector<uint8_t> input_buf(salt_len + password_size);
    if(salt_len > 0)
       {
       copy_mem(&input_buf[0], salt, salt_len);
       }
-   if(passphrase.empty() == false)
+   if(password_size > 0)
       {
       copy_mem(&input_buf[salt_len],
-               cast_char_ptr_to_uint8(passphrase.data()),
-               passphrase.size());
+               cast_char_ptr_to_uint8(password),
+               password_size);
       }
 
-   secure_vector<uint8_t> hash_buf(m_hash->output_length());
+   secure_vector<uint8_t> hash_buf(hash.output_length());
 
    size_t pass = 0;
    size_t generated = 0;
@@ -108,7 +108,7 @@ size_t OpenPGP_S2K::pbkdf(uint8_t output_buf[], size_t output_len,
 
       // Preload some number of zero bytes (empty first iteration)
       std::vector<uint8_t> zero_padding(pass);
-      m_hash->update(zero_padding);
+      hash.update(zero_padding);
 
       // The input is always fully processed even if iterations is very small
       if(input_buf.empty() == false)
@@ -117,18 +117,96 @@ size_t OpenPGP_S2K::pbkdf(uint8_t output_buf[], size_t output_len,
          while(left > 0)
             {
             const size_t input_to_take = std::min(left, input_buf.size());
-            m_hash->update(input_buf.data(), input_to_take);
+            hash.update(input_buf.data(), input_to_take);
             left -= input_to_take;
             }
          }
 
-      m_hash->final(hash_buf.data());
+      hash.final(hash_buf.data());
       copy_mem(output_buf + generated, hash_buf.data(), output_this_pass);
       generated += output_this_pass;
       ++pass;
       }
+   }
+
+}
+
+size_t OpenPGP_S2K::pbkdf(uint8_t output_buf[], size_t output_len,
+                          const std::string& password,
+                          const uint8_t salt[], size_t salt_len,
+                          size_t iterations,
+                          std::chrono::milliseconds msec) const
+   {
+   if(iterations == 0 && msec.count() > 0) // FIXME
+      throw Not_Implemented("OpenPGP_S2K does not implemented timed KDF");
+
+   pgp_s2k(*m_hash, output_buf, output_len,
+           password.c_str(), password.size(),
+           salt, salt_len,
+           iterations);
 
    return iterations;
    }
 
+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) const
+   {
+   const std::chrono::milliseconds tune_time = std::chrono::milliseconds(30);
+
+   const size_t buf_size = 1024;
+   Botan::secure_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 uint64_t desired_nsec = msec.count() * 1000000;
+
+   const size_t hash_size = m_hash->output_length();
+   const size_t blocks_required = (output_len <= hash_size ? 1 : (output_len + hash_size - 1) / hash_size);
+
+   const double bytes_to_be_hashed = (hash_bytes_per_second * (desired_nsec / 1000000000.0)) / blocks_required;
+   const size_t iterations = RFC4880_round_iterations(bytes_to_be_hashed);
+
+   return std::unique_ptr<PasswordHash>(new RFC4880_S2K(m_hash->clone(), iterations));
+   }
+
+std::unique_ptr<PasswordHash> RFC4880_S2K_Family::from_params(size_t iter, size_t, size_t) const
+   {
+   return std::unique_ptr<PasswordHash>(new RFC4880_S2K(m_hash->clone(), iter));
+   }
+
+std::unique_ptr<PasswordHash> RFC4880_S2K_Family::default_params() const
+   {
+   return std::unique_ptr<PasswordHash>(new RFC4880_S2K(m_hash->clone(), 50331648));
+   }
+
+RFC4880_S2K::RFC4880_S2K(HashFunction* hash, size_t iterations) :
+   m_hash(hash),
+   m_iterations(iterations)
+   {
+   }
+
+std::string RFC4880_S2K::to_string() const
+   {
+   return "OpenPGP-S2K(" + m_hash->name() + "," + std::to_string(m_iterations) + ")";
+   }
+
+void RFC4880_S2K::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
+   {
+   pgp_s2k(*m_hash, out, out_len,
+           password, password_len,
+           salt, salt_len,
+           m_iterations);
+   }
+
 }
diff --git a/src/lib/pbkdf/pgp_s2k/pgp_s2k.h b/src/lib/pbkdf/pgp_s2k/pgp_s2k.h
index 02b228258..b2c16d9ed 100644
--- a/src/lib/pbkdf/pgp_s2k/pgp_s2k.h
+++ b/src/lib/pbkdf/pgp_s2k/pgp_s2k.h
@@ -1,6 +1,7 @@
 /*
 * OpenPGP PBKDF
 * (C) 1999-2007,2017 Jack Lloyd
+* (C) 2018 Ribose Inc
 *
 * Distributed under the terms of the Botan license
 */
@@ -9,11 +10,31 @@
 #define BOTAN_OPENPGP_S2K_H_
 
 #include <botan/pbkdf.h>
+#include <botan/pwdhash.h>
 #include <botan/hash.h>
 
 namespace Botan {
 
 /**
+* RFC 4880 encodes the iteration count to a single-byte value
+*/
+uint8_t BOTAN_PUBLIC_API(2,8) RFC4880_encode_count(size_t iterations);
+
+/**
+* Decode the iteration count from RFC 4880 encoding
+*/
+size_t BOTAN_PUBLIC_API(2,8) RFC4880_decode_count(uint8_t encoded_iter);
+
+/**
+* Round an arbitrary iteration count to next largest iteration count
+* supported by RFC4880 encoding.
+*/
+inline size_t RFC4880_round_iterations(size_t iterations)
+   {
+   return RFC4880_decode_count(RFC4880_encode_count(iterations));
+   }
+
+/**
 * OpenPGP's S2K
 *
 * See RFC 4880 sections 3.7.1.1, 3.7.1.2, and 3.7.1.3
@@ -57,10 +78,73 @@ class BOTAN_PUBLIC_API(2,2) OpenPGP_S2K final : public PBKDF
       /**
       * RFC 4880 encodes the iteration count to a single-byte value
       */
-      static uint8_t encode_count(size_t iterations);
+      static uint8_t encode_count(size_t iterations)
+         {
+         return RFC4880_encode_count(iterations);
+         }
+
+      static size_t decode_count(uint8_t encoded_iter)
+         {
+         return RFC4880_decode_count(encoded_iter);
+         }
+
+   private:
+      std::unique_ptr<HashFunction> m_hash;
+   };
+
+/**
+* OpenPGP's S2K
+*
+* See RFC 4880 sections 3.7.1.1, 3.7.1.2, and 3.7.1.3
+* If the salt is empty and iterations == 1, "simple" S2K is used
+* If the salt is non-empty and iterations == 1, "salted" S2K is used
+* If the salt is non-empty and iterations > 1, "iterated" S2K is used
+*
+* Note that unlike PBKDF2, OpenPGP S2K's "iterations" are defined as
+* the number of bytes hashed.
+*/
+class BOTAN_PUBLIC_API(2,8) RFC4880_S2K final : public PasswordHash
+   {
+   public:
+      /**
+      * @param hash the hash function to use
+      * @param the iterations to use (this is rounded due to PGP formatting)
+      */
+      RFC4880_S2K(HashFunction* hash, size_t iterations);
+
+      std::string to_string() const override;
+
+      size_t iterations() const override { return m_iterations; }
 
-      static size_t decode_count(uint8_t encoded_iter);
+      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;
+
+   private:
+      std::unique_ptr<HashFunction> m_hash;
+      size_t m_iterations;
+   };
+
+class BOTAN_PUBLIC_API(2,8) RFC4880_S2K_Family final : public PasswordHashFamily
+   {
+   public:
+      RFC4880_S2K_Family(HashFunction* hash) : m_hash(hash) {}
+
+      std::string name() const override;
+
+      std::unique_ptr<PasswordHash> tune(size_t output_len,
+                                         std::chrono::milliseconds msec,
+                                         size_t max_mem) const override;
+
+      /**
+      * Return some default parameter set for this PBKDF that should be good
+      * enough for most users. The value returned may change over time as
+      * processing power and attacks improve.
+      */
+      std::unique_ptr<PasswordHash> default_params() const override;
 
+      std::unique_ptr<PasswordHash> from_params(
+         size_t iter, size_t, size_t) const override;
    private:
       std::unique_ptr<HashFunction> m_hash;
    };