Move password hashing schemes to src/passhash

Set the upper limit on bcrypt hashing to workfactor 18, which takes
about 25 seconds to run on my desktop machine.

6 files changed, 407 insertions, 0 deletions

diff --git a/src/passhash/bcrypt/bcrypt.cpp b/src/passhash/bcrypt/bcrypt.cpp
new file mode 100644
index 000000000..e533c6081
--- /dev/null
+++ b/src/passhash/bcrypt/bcrypt.cpp
@@ -0,0 +1,154 @@
+/*
+* Bcrypt Password Hashing
+* (C) 2010 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/bcrypt.h>
+#include <botan/loadstor.h>
+#include <botan/libstate.h>
+#include <botan/blowfish.h>
+#include <botan/base64.h>
+
+#include <botan/pipe.h>
+#include <botan/b64_filt.h>
+#include <iostream>
+#include <stdio.h>
+
+namespace Botan {
+
+namespace {
+
+std::string bcrypt_base64_encode(const byte input[], size_t length)
+   {
+   // Bcrypt uses a non-standard base64 alphabet
+   const byte OPENBSD_BASE64_SUB[256] = {
+      0x00, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x38, 0x80, 0x80, 0x80, 0x39,
+      0x79, 0x7A, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x2E, 0x2F, 0x41, 0x42, 0x43, 0x44, 0x45,
+      0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51,
+      0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x59, 0x5A, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69,
+      0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75,
+      0x76, 0x77, 0x78, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80
+   };
+
+   std::string b64 = base64_encode(input, length);
+
+   while(b64.size() && b64[b64.size()-1] == '=')
+      b64 = b64.substr(0, b64.size() - 1);
+
+   for(size_t i = 0; i != b64.size(); ++i)
+      b64[i] = OPENBSD_BASE64_SUB[static_cast<byte>(b64[i])];
+
+   return b64;
+   }
+
+MemoryVector<byte> bcrypt_base64_decode(std::string input)
+   {
+   const byte OPENBSD_BASE64_SUB[256] = {
+      0x00, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x41, 0x42,
+      0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x2B, 0x2F, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49,
+      0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55,
+      0x56, 0x57, 0x58, 0x59, 0x5A, 0x61, 0x62, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D,
+      0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79,
+      0x7A, 0x30, 0x31, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
+      0x80, 0x80, 0x80, 0x80
+   };
+
+   for(size_t i = 0; i != input.size(); ++i)
+      input[i] = OPENBSD_BASE64_SUB[static_cast<byte>(input[i])];
+
+   //return base64_decode(input);
+   Pipe pipe(new Base64_Decoder);
+   pipe.process_msg(input);
+   return pipe.read_all();
+   }
+
+std::string make_bcrypt(const std::string& pass,
+                        const MemoryRegion<byte>& salt,
+                        u16bit work_factor)
+   {
+   const byte magic[24] = {
+      0x4F, 0x72, 0x70, 0x68, 0x65, 0x61, 0x6E, 0x42,
+      0x65, 0x68, 0x6F, 0x6C, 0x64, 0x65, 0x72, 0x53,
+      0x63, 0x72, 0x79, 0x44, 0x6F, 0x75, 0x62, 0x74
+   };
+
+   MemoryVector<byte> ctext(magic, 24);
+
+   Blowfish blowfish;
+
+   // Include the trailing NULL byte
+   blowfish.eks_key_schedule(reinterpret_cast<const byte*>(pass.c_str()),
+                             pass.length() + 1,
+                             salt,
+                             work_factor);
+
+   for(size_t i = 0; i != 64; ++i)
+      blowfish.encrypt_n(&ctext[0], &ctext[0], 3);
+
+   std::string salt_b64 = bcrypt_base64_encode(&salt[0], salt.size());
+
+   return "$2a$" + to_string(work_factor, 2) + "$" + salt_b64.substr(0, 22) +
+             bcrypt_base64_encode(&ctext[0], ctext.size() - 1);
+   }
+
+}
+
+std::string generate_bcrypt(const std::string& pass,
+                            RandomNumberGenerator& rng,
+                            u16bit work_factor)
+   {
+   return make_bcrypt(pass, rng.random_vec(16), work_factor);
+   }
+
+bool check_bcrypt(const std::string& pass, const std::string& hash)
+   {
+   if(hash.size() != 60 ||
+      hash[0] != '$' || hash[1] != '2' || hash[2] != 'a' ||
+      hash[3] != '$' || hash[6] != '$')
+      {
+      return false;
+      }
+
+   const u16bit workfactor = to_u32bit(hash.substr(4, 2));
+
+   MemoryVector<byte> salt = bcrypt_base64_decode(hash.substr(7, 22));
+
+   const std::string compare = make_bcrypt(pass, salt, workfactor);
+
+   return (hash == compare);
+   }
+
+}
diff --git a/src/passhash/bcrypt/bcrypt.h b/src/passhash/bcrypt/bcrypt.h
new file mode 100644
index 000000000..8a6ab58ea
--- /dev/null
+++ b/src/passhash/bcrypt/bcrypt.h
@@ -0,0 +1,37 @@
+/*
+* Bcrypt Password Hashing
+* (C) 2011 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_BCRYPT_H__
+#define BOTAN_BCRYPT_H__
+
+#include <botan/rng.h>
+
+namespace Botan {
+
+/**
+* Create a password hash using Bcrypt
+* @param password the password
+* @param rng a random number generator
+* @param work_factor how much work to do to slow down guessing attacks
+*
+* @see http://www.usenix.org/events/usenix99/provos/provos_html/
+*/
+std::string BOTAN_DLL generate_bcrypt(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 check_bcrypt(const std::string& password,
+                            const std::string& hash);
+
+}
+
+#endif
diff --git a/src/passhash/bcrypt/info.txt b/src/passhash/bcrypt/info.txt
new file mode 100644
index 000000000..91ab92e88
--- /dev/null
+++ b/src/passhash/bcrypt/info.txt
@@ -0,0 +1,9 @@
+define BCRYPT
+
+<requires>
+libstate
+blowfish
+rng
+base64
+</requires>
+
diff --git a/src/passhash/passhash9/info.txt b/src/passhash/passhash9/info.txt
new file mode 100644
index 000000000..f96809f29
--- /dev/null
+++ b/src/passhash/passhash9/info.txt
@@ -0,0 +1,9 @@
+define PASSHASH9
+
+<requires>
+libstate
+pbkdf2
+rng
+base64
+</requires>
+
diff --git a/src/passhash/passhash9/passhash9.cpp b/src/passhash/passhash9/passhash9.cpp
new file mode 100644
index 000000000..e5f379052
--- /dev/null
+++ b/src/passhash/passhash9/passhash9.cpp
@@ -0,0 +1,147 @@
+/*
+* 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/b64_filt.h>
+#include <botan/pipe.h>
+
+namespace Botan {
+
+namespace {
+
+const std::string MAGIC_PREFIX = "$9$";
+
+const size_t WORKFACTOR_BYTES = 2;
+const size_t ALGID_BYTES = 1;
+const size_t SALT_BYTES = 12; // 96 bits of salt
+const size_t PASSHASH9_PBKDF_OUTPUT_LEN = 24; // 192 bits output
+
+const byte PASSHASH9_DEFAULT_ALGO = 0; // HMAC(SHA-1)
+
+const size_t WORK_FACTOR_SCALE = 10000;
+
+MessageAuthenticationCode* get_pbkdf_prf(byte alg_id)
+   {
+   Algorithm_Factory& af = global_state().algorithm_factory();
+
+   try
+      {
+      if(alg_id == 0)
+         return af.make_mac("HMAC(SHA-1)");
+      else if(alg_id == 1)
+         return af.make_mac("HMAC(SHA-256)");
+      else if(alg_id == 2)
+         return af.make_mac("CMAC(Blowfish)");
+      }
+   catch(Algorithm_Not_Found) {}
+
+   return 0;
+   }
+
+}
+
+std::string generate_passhash9(const std::string& pass,
+                               RandomNumberGenerator& rng,
+                               u16bit work_factor)
+   {
+   return generate_passhash9(pass, PASSHASH9_DEFAULT_ALGO, rng, work_factor);
+   }
+
+std::string generate_passhash9(const std::string& pass,
+                               byte alg_id,
+                               RandomNumberGenerator& rng,
+                               u16bit work_factor)
+   {
+   MessageAuthenticationCode* prf = get_pbkdf_prf(alg_id);
+
+   if(!prf)
+      throw Invalid_Argument("Passhash9: Algorithm id " + to_string(alg_id) +
+                             " is not defined");
+
+   PKCS5_PBKDF2 kdf(prf); // takes ownership of pointer
+
+   SecureVector<byte> salt(SALT_BYTES);
+   rng.randomize(&salt[0], salt.size());
+
+   const size_t kdf_iterations = WORK_FACTOR_SCALE * work_factor;
+
+   SecureVector<byte> pbkdf2_output =
+      kdf.derive_key(PASSHASH9_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 size_t BINARY_LENGTH =
+     ALGID_BYTES +
+     WORKFACTOR_BYTES +
+     PASSHASH9_PBKDF_OUTPUT_LEN +
+     SALT_BYTES;
+
+   const size_t 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];
+
+   const size_t 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(
+      PASSHASH9_PBKDF_OUTPUT_LEN,
+      pass,
+      &bin[ALGID_BYTES + WORKFACTOR_BYTES], SALT_BYTES,
+      kdf_iterations).bits_of();
+
+   return same_mem(&cmp[0],
+                   &bin[ALGID_BYTES + WORKFACTOR_BYTES + SALT_BYTES],
+                   PASSHASH9_PBKDF_OUTPUT_LEN);
+   }
+
+}
diff --git a/src/passhash/passhash9/passhash9.h b/src/passhash/passhash9/passhash9.h
new file mode 100644
index 000000000..92cc391dc
--- /dev/null
+++ b/src/passhash/passhash9/passhash9.h
@@ -0,0 +1,51 @@
+/*
+* Passhash9 Password Hashing
+* (C) 2010 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_PASSHASH9_H__
+#define BOTAN_PASSHASH9_H__
+
+#include <botan/rng.h>
+
+namespace Botan {
+
+/**
+* Create a password hash using PBKDF2
+* @param password the password
+* @param rng a random number generator
+* @param work_factor how much work to do to slow down guessing attacks
+*/
+std::string BOTAN_DLL generate_passhash9(const std::string& password,
+                                         RandomNumberGenerator& rng,
+                                         u16bit work_factor = 10);
+
+/**
+* Create a password hash using PBKDF2
+* @param password the password
+* @param alg_id specifies which PRF to use with PBKDF2
+*        0 is HMAC(SHA-1)
+*        1 is HMAC(SHA-256)
+*        2 is CMAC(Blowfish)
+*        all other values are currently undefined
+* @param rng a random number generator
+* @param work_factor how much work to do to slow down guessing attacks
+*/
+std::string BOTAN_DLL generate_passhash9(const std::string& password,
+                                         byte alg_id,
+                                         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 check_passhash9(const std::string& password,
+                               const std::string& hash);
+
+}
+
+#endif