Add new PBKDF interface that takes a std::chrono::milliseconds and

runs the KDF until at least that much time has passed, then returns
the number of interations used.

New parameter to the PKCS8 encryption routines which tells how long to
run the PBKDF. Defaults to 200 milliseconds, which is short enough
that it is unlikely to bother anyone but long enough to provide quite
reasonable security against cracking attacks.  On a Core i7-860, 200
ms with PBKDF2/SHA-1 runs about 180K to 220K iterations (compare with
previous default of 10K).

New PBE interface, remove new_params/set_key and require all inputs
including the passphrase to be passed to the constructor.

Drop the PGP S2K as it is pretty weird and not really useful outside
of a full PGP implementation.

Drop the deprecated PKCS8::encrypt_key and PKCS8::encode functions.

8 files changed, 137 insertions, 149 deletions

diff --git a/src/pbkdf/pbkdf.h b/src/pbkdf/pbkdf.h
index e951b5673..176ed0302 100644
--- a/src/pbkdf/pbkdf.h
+++ b/src/pbkdf/pbkdf.h
@@ -1,6 +1,6 @@
 /*
 * PBKDF
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2012 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -10,6 +10,7 @@
 
 #include <botan/algo_base.h>
 #include <botan/symkey.h>
+#include <chrono>
 
 namespace Botan {
 
@@ -37,10 +38,43 @@ class BOTAN_DLL PBKDF : public Algorithm
       * @param salt_len length of salt in bytes
       * @param iterations the number of iterations to use (use 10K or more)
       */
-      virtual OctetString derive_key(size_t output_len,
-                                     const std::string& passphrase,
-                                     const byte salt[], size_t salt_len,
-                                     size_t iterations) const = 0;
+      OctetString derive_key(size_t output_len,
+                             const std::string& passphrase,
+                             const byte salt[], size_t salt_len,
+                             size_t iterations) const;
+
+      /**
+      * Derive a key from a passphrase
+      * @param output_len the desired length of the key to produce
+      * @param passphrase the password to derive the key from
+      * @param salt a randomly chosen salt
+      * @param salt_len length of salt in bytes
+      * @param msec is how long to run the PBKDF
+      * @param iterations is set to the number of iterations used
+      */
+      OctetString derive_key(size_t output_len,
+                             const std::string& passphrase,
+                             const byte salt[], size_t salt_len,
+                             std::chrono::milliseconds msec,
+                             size_t& iterations) const;
+
+      /**
+      * Derive a key from a passphrase for a number of iterations
+      * specified by either iterations or if iterations == 0 then
+      * running until seconds time has elapsed.
+      *
+      * @param output_len the desired length of the key to produce
+      * @param passphrase the password to derive the key from
+      * @param salt a randomly chosen salt
+      * @param salt_len length of salt in bytes
+      * @param iterations the number of iterations to use (use 10K or more)
+      */
+      virtual std::pair<size_t, OctetString>
+         key_derivation(size_t output_len,
+                        const std::string& passphrase,
+                        const byte salt[], size_t salt_len,
+                        size_t iterations,
+                        std::chrono::milliseconds msec) const = 0;
    };
 
 /**
diff --git a/src/pbkdf/pbkdf1/pbkdf1.cpp b/src/pbkdf/pbkdf1/pbkdf1.cpp
index 7f0939b8f..d51cbdc18 100644
--- a/src/pbkdf/pbkdf1/pbkdf1.cpp
+++ b/src/pbkdf/pbkdf1/pbkdf1.cpp
@@ -13,28 +13,46 @@ namespace Botan {
 /*
 * Return a PKCS#5 PBKDF1 derived key
 */
-OctetString PKCS5_PBKDF1::derive_key(size_t key_len,
-                                     const std::string& passphrase,
-                                     const byte salt[], size_t salt_size,
-                                     size_t iterations) const
+std::pair<size_t, OctetString>
+PKCS5_PBKDF1::key_derivation(size_t key_len,
+                             const std::string& passphrase,
+                             const byte salt[], size_t salt_len,
+                             size_t iterations,
+                             std::chrono::milliseconds msec) const
    {
-   if(iterations == 0)
-      throw Invalid_Argument("PKCS5_PBKDF1: Invalid iteration count");
-
    if(key_len > hash->output_length())
       throw Invalid_Argument("PKCS5_PBKDF1: Requested output length too long");
 
    hash->update(passphrase);
-   hash->update(salt, salt_size);
+   hash->update(salt, salt_len);
    secure_vector<byte> key = hash->final();
 
-   for(size_t j = 1; j != iterations; ++j)
+   const auto start = std::chrono::high_resolution_clock::now();
+   size_t iterations_performed = 1;
+
+   while(true)
       {
+      if(iterations == 0)
+         {
+         if(iterations_performed % 8192 == 0)
+            {
+            auto time_taken = std::chrono::high_resolution_clock::now() - start;
+            auto msec_taken = std::chrono::duration_cast<std::chrono::milliseconds>(time_taken);
+            if(msec_taken > msec)
+               break;
+            }
+         }
+      else if(iterations_performed == iterations)
+         break;
+
       hash->update(key);
       hash->final(&key[0]);
+
+      ++iterations_performed;
       }
 
-   return OctetString(&key[0], std::min<size_t>(key_len, key.size()));
+   return std::make_pair(iterations_performed,
+                         OctetString(&key[0], std::min(key_len, key.size())));
    }
 
 }
diff --git a/src/pbkdf/pbkdf1/pbkdf1.h b/src/pbkdf/pbkdf1/pbkdf1.h
index f8e2dbe69..783b70ed9 100644
--- a/src/pbkdf/pbkdf1/pbkdf1.h
+++ b/src/pbkdf/pbkdf1/pbkdf1.h
@@ -46,10 +46,12 @@ class BOTAN_DLL PKCS5_PBKDF1 : public PBKDF
          return new PKCS5_PBKDF1(hash->clone());
          }
 
-      OctetString derive_key(size_t output_len,
-                             const std::string& passphrase,
-                             const byte salt[], size_t salt_len,
-                             size_t iterations) const;
+      std::pair<size_t, OctetString>
+         key_derivation(size_t output_len,
+                        const std::string& passphrase,
+                        const byte salt[], size_t salt_len,
+                        size_t iterations,
+                        std::chrono::milliseconds msec) const override;
    private:
       HashFunction* hash;
    };
diff --git a/src/pbkdf/pbkdf2/pbkdf2.cpp b/src/pbkdf/pbkdf2/pbkdf2.cpp
index 699ce7c6b..c116b10ab 100644
--- a/src/pbkdf/pbkdf2/pbkdf2.cpp
+++ b/src/pbkdf/pbkdf2/pbkdf2.cpp
@@ -8,19 +8,22 @@
 #include <botan/pbkdf2.h>
 #include <botan/get_byte.h>
 #include <botan/internal/xor_buf.h>
+#include <botan/internal/rounding.h>
 
 namespace Botan {
 
 /*
 * Return a PKCS #5 PBKDF2 derived key
 */
-OctetString PKCS5_PBKDF2::derive_key(size_t key_len,
-                                     const std::string& passphrase,
-                                     const byte salt[], size_t salt_size,
-                                     size_t iterations) const
+std::pair<size_t, OctetString>
+PKCS5_PBKDF2::key_derivation(size_t key_len,
+                             const std::string& passphrase,
+                             const byte salt[], size_t salt_len,
+                             size_t iterations,
+                             std::chrono::milliseconds msec) const
    {
-   if(iterations == 0)
-      throw Invalid_Argument("PKCS#5 PBKDF2: Invalid iteration count");
+   if(key_len == 0)
+      return std::make_pair(iterations, OctetString());
 
    try
       {
@@ -39,22 +42,62 @@ OctetString PKCS5_PBKDF2::derive_key(size_t key_len,
 
    secure_vector<byte> U(mac->output_length());
 
+   const size_t blocks_needed = round_up(key_len, mac->output_length()) / mac->output_length();
+
+   std::chrono::microseconds usec_per_block =
+      std::chrono::duration_cast<std::chrono::microseconds>(msec) / blocks_needed;
+
    u32bit counter = 1;
    while(key_len)
       {
       size_t T_size = std::min<size_t>(mac->output_length(), key_len);
 
-      mac->update(salt, salt_size);
+      mac->update(salt, salt_len);
       mac->update_be(counter);
       mac->final(&U[0]);
 
       xor_buf(T, &U[0], T_size);
 
-      for(size_t j = 1; j != iterations; ++j)
+      if(iterations == 0)
+         {
+         /*
+         If no iterations set, run the first block to calibrate based
+         on how long hashing takes on whatever machine we're running on.
+         */
+
+         const auto start = std::chrono::high_resolution_clock::now();
+
+         iterations = 1; // the first iteration we did above
+
+         while(true)
+            {
+            mac->update(U);
+            mac->final(&U[0]);
+            xor_buf(T, &U[0], T_size);
+            iterations++;
+
+            /*
+            Only break on relatively 'even' iterations. For one it
+            avoids confusion, and likely some broken implementations
+            break on getting completely randomly distributed values
+            */
+            if(iterations % 8192 == 0)
+               {
+               auto time_taken = std::chrono::high_resolution_clock::now() - start;
+               auto usec_taken = std::chrono::duration_cast<std::chrono::microseconds>(time_taken);
+               if(usec_taken > usec_per_block)
+                  break;
+               }
+            }
+         }
+      else
          {
-         mac->update(U);
-         mac->final(&U[0]);
-         xor_buf(T, &U[0], T_size);
+         for(size_t i = 1; i != iterations; ++i)
+            {
+            mac->update(U);
+            mac->final(&U[0]);
+            xor_buf(T, &U[0], T_size);
+            }
          }
 
       key_len -= T_size;
@@ -62,7 +105,7 @@ OctetString PKCS5_PBKDF2::derive_key(size_t key_len,
       ++counter;
       }
 
-   return key;
+   return std::make_pair(iterations, key);
    }
 
 }
diff --git a/src/pbkdf/pbkdf2/pbkdf2.h b/src/pbkdf/pbkdf2/pbkdf2.h
index 26392bdad..8bc271fcf 100644
--- a/src/pbkdf/pbkdf2/pbkdf2.h
+++ b/src/pbkdf/pbkdf2/pbkdf2.h
@@ -1,6 +1,6 @@
 /*
 * PBKDF2
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2012 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -19,20 +19,22 @@ namespace Botan {
 class BOTAN_DLL PKCS5_PBKDF2 : public PBKDF
    {
    public:
-      std::string name() const
+      std::string name() const override
          {
          return "PBKDF2(" + mac->name() + ")";
          }
 
-      PBKDF* clone() const
+      PBKDF* clone() const override
          {
          return new PKCS5_PBKDF2(mac->clone());
          }
 
-      OctetString derive_key(size_t output_len,
-                             const std::string& passphrase,
-                             const byte salt[], size_t salt_len,
-                             size_t iterations) const;
+      std::pair<size_t, OctetString>
+         key_derivation(size_t output_len,
+                        const std::string& passphrase,
+                        const byte salt[], size_t salt_len,
+                        size_t iterations,
+                        std::chrono::milliseconds msec) const override;
 
       /**
       * Create a PKCS #5 instance using the specified message auth code
diff --git a/src/pbkdf/pgps2k/info.txt b/src/pbkdf/pgps2k/info.txt
deleted file mode 100644
index 8be9c79f8..000000000
--- a/src/pbkdf/pgps2k/info.txt
+++ /dev/null
@@ -1,5 +0,0 @@
-define PGPS2K
-
-<requires>
-hash
-</requires>
diff --git a/src/pbkdf/pgps2k/pgp_s2k.cpp b/src/pbkdf/pgps2k/pgp_s2k.cpp
deleted file mode 100644
index 6f6de58e2..000000000
--- a/src/pbkdf/pgps2k/pgp_s2k.cpp
+++ /dev/null
@@ -1,57 +0,0 @@
-/*
-* OpenPGP S2K
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/pgp_s2k.h>
-
-namespace Botan {
-
-/*
-* Derive a key using the OpenPGP S2K algorithm
-*/
-OctetString OpenPGP_S2K::derive_key(size_t key_len,
-                                    const std::string& passphrase,
-                                    const byte salt_buf[], size_t salt_size,
-                                    size_t iterations) const
-   {
-   secure_vector<byte> key(key_len), hash_buf;
-
-   size_t pass = 0, generated = 0,
-          total_size = passphrase.size() + salt_size;
-   size_t to_hash = std::max(iterations, total_size);
-
-   hash->clear();
-   while(key_len > generated)
-      {
-      for(size_t j = 0; j != pass; ++j)
-         hash->update(0);
-
-      size_t left = to_hash;
-      while(left >= total_size)
-         {
-         hash->update(salt_buf, salt_size);
-         hash->update(passphrase);
-         left -= total_size;
-         }
-      if(left <= salt_size)
-         hash->update(salt_buf, left);
-      else
-         {
-         hash->update(salt_buf, salt_size);
-         left -= salt_size;
-         hash->update(reinterpret_cast<const byte*>(passphrase.data()), left);
-         }
-
-      hash_buf = hash->final();
-      buffer_insert(key, generated, &hash_buf[0], hash->output_length());
-      generated += hash->output_length();
-      ++pass;
-      }
-
-   return key;
-   }
-
-}
diff --git a/src/pbkdf/pgps2k/pgp_s2k.h b/src/pbkdf/pgps2k/pgp_s2k.h
deleted file mode 100644
index 7620a6c84..000000000
--- a/src/pbkdf/pgps2k/pgp_s2k.h
+++ /dev/null
@@ -1,49 +0,0 @@
-/*
-* OpenPGP PBKDF
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_OPENPGP_S2K_H__
-#define BOTAN_OPENPGP_S2K_H__
-
-#include <botan/pbkdf.h>
-#include <botan/hash.h>
-
-namespace Botan {
-
-/**
-* OpenPGP's S2K
-*/
-class BOTAN_DLL OpenPGP_S2K : public PBKDF
-   {
-   public:
-      /**
-      * @param hash_in the hash function to use
-      */
-      OpenPGP_S2K(HashFunction* hash_in) : hash(hash_in) {}
-
-      ~OpenPGP_S2K() { delete hash; }
-
-      std::string name() const
-         {
-         return "OpenPGP-S2K(" + hash->name() + ")";
-         }
-
-      PBKDF* clone() const
-         {
-         return new OpenPGP_S2K(hash->clone());
-         }
-
-      OctetString derive_key(size_t output_len,
-                             const std::string& passphrase,
-                             const byte salt[], size_t salt_len,
-                             size_t iterations) const;
-   private:
-      HashFunction* hash;
-   };
-
-}
-
-#endif