Add support for bcrypt, the Blowfish-based password hashing scheme

used in OpenBSD. Tested as compatible with a common Java
implementation (http://www.mindrot.org/projects/jBCrypt/)

5 files changed, 264 insertions, 7 deletions

diff --git a/src/block/blowfish/blowfish.cpp b/src/block/blowfish/blowfish.cpp
index ea227e93e..6610decd8 100644
--- a/src/block/blowfish/blowfish.cpp
+++ b/src/block/blowfish/blowfish.cpp
@@ -1,6 +1,6 @@
 /*
 * Blowfish
-* (C) 1999-2009 Jack Lloyd
+* (C) 1999-2011 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -87,20 +87,61 @@ void Blowfish::key_schedule(const byte key[], size_t length)
    {
    clear();
 
+   const byte null_salt[16] = { 0 };
+
+   key_expansion(key, length, null_salt);
+   }
+
+void Blowfish::key_expansion(const byte key[],
+                             size_t length,
+                             const byte salt[16])
+   {
    for(size_t i = 0, j = 0; i != 18; ++i, j += 4)
       P[i] ^= make_u32bit(key[(j  ) % length], key[(j+1) % length],
                           key[(j+2) % length], key[(j+3) % length]);
 
    u32bit L = 0, R = 0;
-   generate_sbox(P, L, R);
-   generate_sbox(S, L, R);
+   generate_sbox(P, L, R, salt, 0);
+   generate_sbox(S, L, R, salt, 2);
+   }
+
+/*
+* Modified key schedule used for bcrypt password hashing
+*/
+void Blowfish::eks_key_schedule(const byte key[], size_t length,
+                                const byte salt[16], size_t workfactor)
+   {
+   if(length == 0 || length >= 56)
+      throw Invalid_Key_Length("EKSBlowfish", length);
+
+   if(workfactor == 0)
+      throw std::invalid_argument("Bcrypt work factor must be at least 1");
+
+   if(workfactor > 24) // ok?
+      throw std::invalid_argument("Requested Bcrypt work factor too large");
+
+   clear();
+
+   const byte null_salt[16] = { 0 };
+
+   key_expansion(key, length, salt);
+
+   const size_t rounds = 1 << workfactor;
+
+   for(size_t r = 0; r != rounds; ++r)
+      {
+      key_expansion(key, length, null_salt);
+      key_expansion(salt, 16, null_salt);
+      }
    }
 
 /*
 * Generate one of the Sboxes
 */
 void Blowfish::generate_sbox(MemoryRegion<u32bit>& box,
-                             u32bit& L, u32bit& R) const
+                             u32bit& L, u32bit& R,
+                             const byte salt[16],
+                             size_t salt_off) const
    {
    const u32bit* S1 = &S[0];
    const u32bit* S2 = &S[256];
@@ -109,6 +150,9 @@ void Blowfish::generate_sbox(MemoryRegion<u32bit>& box,
 
    for(size_t i = 0; i != box.size(); i += 2)
       {
+      L ^= load_be<u32bit>(salt, (i + salt_off) % 4);
+      R ^= load_be<u32bit>(salt, (i + salt_off + 1) % 4);
+
       for(size_t j = 0; j != 16; j += 2)
          {
          L ^= P[j];
diff --git a/src/block/blowfish/blowfish.h b/src/block/blowfish/blowfish.h
index b89ffcaaa..13706d21e 100644
--- a/src/block/blowfish/blowfish.h
+++ b/src/block/blowfish/blowfish.h
@@ -1,6 +1,6 @@
 /*
 * Blowfish
-* (C) 1999-2009 Jack Lloyd
+* (C) 1999-2011 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -21,15 +21,28 @@ class BOTAN_DLL Blowfish : public Block_Cipher_Fixed_Params<8, 1, 56>
       void encrypt_n(const byte in[], byte out[], size_t blocks) const;
       void decrypt_n(const byte in[], byte out[], size_t blocks) const;
 
+      /**
+      * Modified EKSBlowfish key schedule, used for bcrypt password hashing
+      */
+      void eks_key_schedule(const byte key[], size_t key_length,
+                            const byte salt[16], size_t workfactor);
+
       void clear();
       std::string name() const { return "Blowfish"; }
       BlockCipher* clone() const { return new Blowfish; }
 
       Blowfish() : S(1024), P(18) {}
    private:
-      void key_schedule(const byte[], size_t);
+      void key_schedule(const byte key[], size_t length);
+
+      void key_expansion(const byte key[],
+                         size_t key_length,
+                         const byte salt[16]);
+
       void generate_sbox(MemoryRegion<u32bit>& box,
-                         u32bit& L, u32bit& R) const;
+                         u32bit& L, u32bit& R,
+                         const byte salt[16],
+                         size_t salt_off) const;
 
       static const u32bit P_INIT[18];
       static const u32bit S_INIT[1024];
diff --git a/src/constructs/bcrypt/bcrypt.cpp b/src/constructs/bcrypt/bcrypt.cpp
new file mode 100644
index 000000000..b2152a0a7
--- /dev/null
+++ b/src/constructs/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 size_t 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/constructs/bcrypt/bcrypt.h b/src/constructs/bcrypt/bcrypt.h
new file mode 100644
index 000000000..8a6ab58ea
--- /dev/null
+++ b/src/constructs/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/constructs/bcrypt/info.txt b/src/constructs/bcrypt/info.txt
new file mode 100644
index 000000000..91ab92e88
--- /dev/null
+++ b/src/constructs/bcrypt/info.txt
@@ -0,0 +1,9 @@
+define BCRYPT
+
+<requires>
+libstate
+blowfish
+rng
+base64
+</requires>
+