Further passhash changes before release and things have to be

finalized.

Move header to passhash9.h and rename the functions to be passhash9
specific ({generator,check}_passhash9)

Add an algorithm identifer field. Currently only id 0 is defined, for
HMAC(SHA-1), but this opens up for using HMAC(SHA-512) or HMAC(SHA-3)
or CMAC(Blowfish) or whatever in the future if necessary. Increase the
salt size to 96 bits and the PRF output size to 192 bits.

Document in api.tex

7 files changed, 219 insertions, 110 deletions

diff --git a/doc/api.tex b/doc/api.tex
index 20177a9f8..dc920d07b 100644
--- a/doc/api.tex
+++ b/doc/api.tex
@@ -12,7 +12,7 @@
 
 \title{\textbf{Botan API Reference}}
 \author{}
-\date{2009/2/19}
+\date{2010/02/05}
 
 \newcommand{\filename}[1]{\texttt{#1}}
 \newcommand{\manpage}[2]{\texttt{#1}(#2)}
@@ -2662,6 +2662,84 @@ be about right). Using both a reasonably sized salt and a large
 iteration count is highly recommended to prevent password guessing
 attempts.
 
+\subsection{Password Hashing}
+
+Storing passwords for user authentication purposes in plaintext is the
+simplest but least secure method; when an attacker compromises the
+database in which the passwords are stored, they immediately gain
+access to all of them. Often passwords are reused among multiple
+services or machines, meaning once a password to a single service is
+known an attacker has a substantial head start on attacking other
+machines.
+
+The general approach is to store, instead of the password, the output
+of a one way function of the password. Upon receiving an
+authentication request, the authenticator can recompute the one way
+function and compare the value just computed with the one that was
+stored. If they match, then the authentication request succeeds. But
+when an attacker gains access to the database, they only have the
+output of the one way function, not the original password.
+
+Common hash functions such as SHA-256 are one way, but used alone they
+have problems for this purpose. What an attacker can do, upon gaining
+access to such a stored password database, is hash common dictionary
+words and other possible passwords, storing them in a list. Then he
+can search through his list; if a stored hash and an entry in his list
+match, then he has found the password. Even worse, this can happen
+\emph{offline}: an attacker can begin hashing common passwords days,
+months, or years before ever gaining access to the database. In
+addition, if two users choose the same password, the one way function
+output will be the same for both of them, which will be visible upon
+inspection of the database.
+
+There are two solutions to these problems: salting and
+iteration. Salting refers to including, along with the password, a
+randomly chosen value which perturbs the one way function. Salting can
+reduce the effectivness of offline dictionary generation (because for
+each potential password, an attacker would have to compute the one way
+function output for all possible salts - with a large enough salt,
+this can make the problem quite difficult). It also prevents the same
+password from producing the same output, as long as the salts do not
+collide. With a large salt (say 80 to 128 bits) this will be quite
+unlikely. Iteration refers to the general technique of forcing
+multiple one way function evaluations when computing the output, to
+slow down the operation. For instance if hashing a single password
+requires running SHA-256 100,000 times instead of just once, that will
+slow down user authentication by a factor of 100,000, but user
+authentication happens quite rarely, and usually there are more
+expensive operations that need to occur anyway (network and database
+I/O, etc). On the other hand, an attacker who is attempting to break a
+database full of stolen password hashes will be seriously
+inconvenienced by a factor of 100,000 slowdown; they will be able to
+only test at a rate of .0001\% of what they would without iterations
+(or, equivalently, will require 100,000 times as many zombie botnet
+hosts).
+
+There are many different ways of doing this password hashing
+operation, with common ones including Unix's crypt (which is based on
+DES) and OpenBSD's bcrypt (based on Blowfish). Other variants using
+MD5 or SHA-256 are also in use on various systems.
+
+Botan provides a technique called passhash9, in
+\filename{passhash9.h}, which is based on PBKDF2. Two functions are
+provided in this header, \function{generate\_passhash9} and
+\function{check\_passhash9}.  The generate function takes the password
+to hash, a \type{RandomNumberGenerator}, and a work factor, which
+tells how many iterations to compute. The default work factor is 10
+(which means 100,000 iterations), but any non-zero value is accepted.
+The check function takes a password and a passhash9 output and checks
+if the password is the same as the one that was used to generate the
+passhash9 output, returning a boolean true (same) or false (not same).
+An example can be found in \filename{doc/examples/passhash.cpp}.
+
+Passhash9 currently uses HMAC(SHA-1) for the underlying PBKDF2
+psuedo-random function, but can be extended to use different
+algorithms in the future if necessary. For instance using a PRF based
+on Blowfish (a block cipher that requires 4 KiB of RAM for efficient
+execution) could be used to make hardware-based password cracking more
+expensive (this was one motivation for Blowfish's use in the bcrypt
+hashing scheme, in fact).
+
 \subsection{Checksums}
 
 Checksums are very similar to hash functions, and in fact share the same
diff --git a/doc/examples/passhash.cpp b/doc/examples/passhash.cpp
index 1e4c8c505..586c28c3f 100644
--- a/doc/examples/passhash.cpp
+++ b/doc/examples/passhash.cpp
@@ -5,7 +5,7 @@
 */
 
 #include <botan/botan.h>
-#include <botan/passhash.h>
+#include <botan/passhash9.h>
 #include <iostream>
 #include <memory>
 
@@ -30,11 +30,11 @@ int main(int argc, char* argv[])
          Botan::AutoSeeded_RNG rng;
 
          std::cout << "H('" << argv[1] << "') = "
-                   << Botan::password_hash(argv[1], rng) << '\n';
+                   << Botan::generate_passhash9(argv[1], rng) << '\n';
          }
       else
          {
-         bool ok = Botan::password_hash_ok(argv[1], argv[2]);
+         bool ok = Botan::check_passhash9(argv[1], argv[2]);
          if(ok)
             std::cout << "Password and hash match\n";
          else
diff --git a/doc/log.txt b/doc/log.txt
index 3367337eb..847bf8596 100644
--- a/doc/log.txt
+++ b/doc/log.txt
@@ -6,7 +6,7 @@
  - Perform CBC decryption in parallel where possible
  - Add SQLite3 db encryption codec, contributed by Olivier de Gaalon
  - Add a block cipher cascade construction
- - Add support for password hashing for authentication (passhash.h)
+ - Add support for password hashing for authentication (passhash9.h)
  - Add support for Win32 high resolution system timers
  - Changed S2K interface: derive_key now takes salt, iteration count
  - Fix crash in GMP_Engine if library is shutdown and reinitialized
diff --git a/src/constructs/passhash/info.txt b/src/constructs/passhash/info.txt
index fdc68deac..f96809f29 100644
--- a/src/constructs/passhash/info.txt
+++ b/src/constructs/passhash/info.txt
@@ -1,4 +1,4 @@
-define PASSHASH
+define PASSHASH9
 
 <requires>
 libstate
diff --git a/src/constructs/passhash/passhash.cpp b/src/constructs/passhash/passhash.cpp
deleted file mode 100644
index d3571808d..000000000
--- a/src/constructs/passhash/passhash.cpp
+++ /dev/null
@@ -1,96 +0,0 @@
-/*
-* Password Hashing
-* (C) 2010 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/passhash.h>
-#include <botan/loadstor.h>
-#include <botan/libstate.h>
-#include <botan/pbkdf2.h>
-#include <botan/base64.h>
-#include <botan/pipe.h>
-
-namespace Botan {
-
-namespace {
-
-const std::string MAGIC_PREFIX = "$9$";
-const u32bit SALT_BYTES = 10; // 80 bits of salt
-const u32bit PBKDF_OUTPUT_LEN = 15; // 112 bits output
-const u32bit WORK_FACTOR_SCALE = 10000;
-const std::string PBKDF_MAC = "HMAC(SHA-1)";
-
-}
-
-std::string password_hash(const std::string& pass,
-                          RandomNumberGenerator& rng,
-                          u16bit work_factor)
-   {
-   PKCS5_PBKDF2 kdf(
-      global_state().algorithm_factory().make_mac(PBKDF_MAC)
-      );
-
-   SecureVector<byte> salt(SALT_BYTES);
-   rng.randomize(&salt[0], salt.size());
-
-   u32bit kdf_iterations = WORK_FACTOR_SCALE * work_factor;
-
-   SecureVector<byte> pbkdf2_output =
-      kdf.derive_key(PBKDF_OUTPUT_LEN, pass,
-                     &salt[0], salt.size(),
-                     kdf_iterations).bits_of();
-
-   Pipe pipe(new Base64_Encoder);
-   pipe.start_msg();
-   pipe.write(get_byte(0, work_factor));
-   pipe.write(get_byte(1, work_factor));
-   pipe.write(salt);
-   pipe.write(pbkdf2_output);
-   pipe.end_msg();
-
-   return MAGIC_PREFIX + pipe.read_all_as_string();
-   }
-
-bool password_hash_ok(const std::string& pass, const std::string& hash)
-   {
-   if(hash.size() != (36 + MAGIC_PREFIX.size()))
-      return false;
-
-   for(size_t i = 0; i != MAGIC_PREFIX.size(); ++i)
-      if(hash[i] != MAGIC_PREFIX[i])
-         return false;
-
-   Pipe pipe(new Base64_Decoder);
-   pipe.start_msg();
-   pipe.write(hash.c_str() + MAGIC_PREFIX.size());
-   pipe.end_msg();
-
-   SecureVector<byte> bin = pipe.read_all();
-
-   const u32bit WORKFACTOR_BYTES = 2;
-
-   if(bin.size() != (WORKFACTOR_BYTES + PBKDF_OUTPUT_LEN + SALT_BYTES))
-      return false;
-
-   u32bit kdf_iterations = WORK_FACTOR_SCALE * load_be<u16bit>(bin, 0);
-
-   if(kdf_iterations == 0)
-      return false;
-
-   PKCS5_PBKDF2 kdf(
-      global_state().algorithm_factory().make_mac(PBKDF_MAC)
-      );
-
-   SecureVector<byte> cmp = kdf.derive_key(
-      PBKDF_OUTPUT_LEN, pass,
-      &bin[WORKFACTOR_BYTES], SALT_BYTES,
-      kdf_iterations).bits_of();
-
-   return same_mem(cmp.begin(),
-                   bin.begin() + WORKFACTOR_BYTES + SALT_BYTES,
-                   PBKDF_OUTPUT_LEN);
-   }
-
-}
diff --git a/src/constructs/passhash/passhash9.cpp b/src/constructs/passhash/passhash9.cpp
new file mode 100644
index 000000000..9e5ff3257
--- /dev/null
+++ b/src/constructs/passhash/passhash9.cpp
@@ -0,0 +1,127 @@
+/*
+* Passhash9 Password Hashing
+* (C) 2010 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/passhash9.h>
+#include <botan/loadstor.h>
+#include <botan/libstate.h>
+#include <botan/pbkdf2.h>
+#include <botan/base64.h>
+#include <botan/pipe.h>
+
+namespace Botan {
+
+namespace {
+
+const std::string MAGIC_PREFIX = "$9$";
+
+const u32bit WORKFACTOR_BYTES = 2;
+const u32bit ALGID_BYTES = 1;
+const u32bit SALT_BYTES = 12; // 96 bits of salt
+const u32bit PBKDF_OUTPUT_LEN = 24; // 192 bits output
+
+const u32bit WORK_FACTOR_SCALE = 10000;
+
+MessageAuthenticationCode* get_pbkdf_prf(byte alg_id)
+   {
+   Algorithm_Factory& af = global_state().algorithm_factory();
+
+   if(alg_id == 0)
+      return af.make_mac("HMAC(SHA-1)");
+
+   return 0;
+   }
+
+std::pair<byte, MessageAuthenticationCode*> choose_pbkdf_prf()
+   {
+   byte alg_id = 0;
+   return std::make_pair(alg_id, get_pbkdf_prf(alg_id));
+   }
+
+}
+
+std::string generate_passhash9(const std::string& pass,
+                               RandomNumberGenerator& rng,
+                               u16bit work_factor)
+   {
+   std::pair<byte, MessageAuthenticationCode*> prf = choose_pbkdf_prf();
+   byte alg_id = prf.first;
+
+   PKCS5_PBKDF2 kdf(prf.second); // takes ownership of pointer
+
+   SecureVector<byte> salt(SALT_BYTES);
+   rng.randomize(&salt[0], salt.size());
+
+   u32bit kdf_iterations = WORK_FACTOR_SCALE * work_factor;
+
+   SecureVector<byte> pbkdf2_output =
+      kdf.derive_key(PBKDF_OUTPUT_LEN, pass,
+                     &salt[0], salt.size(),
+                     kdf_iterations).bits_of();
+
+   Pipe pipe(new Base64_Encoder);
+   pipe.start_msg();
+   pipe.write(alg_id);
+   pipe.write(get_byte(0, work_factor));
+   pipe.write(get_byte(1, work_factor));
+   pipe.write(salt);
+   pipe.write(pbkdf2_output);
+   pipe.end_msg();
+
+   return MAGIC_PREFIX + pipe.read_all_as_string();
+   }
+
+bool check_passhash9(const std::string& pass, const std::string& hash)
+   {
+   const u32bit BINARY_LENGTH =
+      (ALGID_BYTES + WORKFACTOR_BYTES + PBKDF_OUTPUT_LEN + SALT_BYTES);
+
+   const u32bit BASE64_LENGTH =
+      MAGIC_PREFIX.size() + (BINARY_LENGTH * 8) / 6;
+
+   if(hash.size() != BASE64_LENGTH)
+      return false;
+
+   for(size_t i = 0; i != MAGIC_PREFIX.size(); ++i)
+      if(hash[i] != MAGIC_PREFIX[i])
+         return false;
+
+   Pipe pipe(new Base64_Decoder);
+   pipe.start_msg();
+   pipe.write(hash.c_str() + MAGIC_PREFIX.size());
+   pipe.end_msg();
+
+   SecureVector<byte> bin = pipe.read_all();
+
+   if(bin.size() != BINARY_LENGTH)
+      return false;
+
+   byte alg_id = bin[0];
+
+   u32bit kdf_iterations =
+      WORK_FACTOR_SCALE * load_be<u16bit>(bin + ALGID_BYTES, 0);
+
+   if(kdf_iterations == 0)
+      return false;
+
+   MessageAuthenticationCode* pbkdf_prf = get_pbkdf_prf(alg_id);
+
+   if(pbkdf_prf == 0)
+      return false; // unknown algorithm, reject
+
+   PKCS5_PBKDF2 kdf(pbkdf_prf); // takes ownership of pointer
+
+   SecureVector<byte> cmp = kdf.derive_key(
+      PBKDF_OUTPUT_LEN, pass,
+      &bin[ALGID_BYTES + WORKFACTOR_BYTES], SALT_BYTES,
+      kdf_iterations).bits_of();
+
+   return same_mem(cmp.begin(),
+                   bin.begin() + ALGID_BYTES + WORKFACTOR_BYTES + SALT_BYTES,
+                   PBKDF_OUTPUT_LEN);
+   }
+
+}
diff --git a/src/constructs/passhash/passhash.h b/src/constructs/passhash/passhash9.h
index 9676ff85e..6020dce42 100644
--- a/src/constructs/passhash/passhash.h
+++ b/src/constructs/passhash/passhash9.h
@@ -1,12 +1,12 @@
 /*
-* Password Hashing
+* Passhash9 Password Hashing
 * (C) 2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
 
-#ifndef BOTAN_PASSHASH_H__
-#define BOTAN_PASSHASH_H__
+#ifndef BOTAN_PASSHASH9_H__
+#define BOTAN_PASSHASH9_H__
 
 #include <botan/rng.h>
 
@@ -18,17 +18,17 @@ namespace Botan {
 * @param rng a random number generator
 * @Param work_factor how much work to do to slow down guessing attacks
 */
-std::string BOTAN_DLL password_hash(const std::string& password,
-                                    RandomNumberGenerator& rng,
-                                    u16bit work_factor = 10);
+std::string BOTAN_DLL generate_passhash9(const std::string& password,
+                                         RandomNumberGenerator& rng,
+                                         u16bit work_factor = 10);
 
 /**
 * Check a previously created password hash
 * @param password the password to check against
 * @param hash the stored hash to check against
 */
-bool BOTAN_DLL password_hash_ok(const std::string& password,
-                                const std::string& hash);
+bool BOTAN_DLL check_passhash9(const std::string& password,
+                               const std::string& hash);
 
 }