phpass/phpbb3 hashing algorithm detail

The fear of every surveillance society: citizens protecting their own privacy with strong cryptography

phpass/phpbb3 hashing algorithm detail

Post by WallShadow on Tue Dec 23, 2014 9:28 pm
([msg=86023]see phpass/phpbb3 hashing algorithm detail[/msg])

I couldn't find any complete resources on this out there, so i decided to write up a detail on the phpass/phpbb3 hashing algorithm here so that other people don't have to collect the information bit by bit like i did. enjoy!

PHPBB3 hashes are hashes used to store user passwords in phpbb3 forum databases. They are actually phpass hashes, just using a '$H$' identifier instead of '$P$' (actually, phpass 0.3 recognizes both) They look something like this:

$H$9XcmlsyEgtMOKxU/TH53bkOv637O9c/

They are always 34 characters long and start with "$H$" to show that it's a phpbb3 hash. here's a break down of the rest:

the first character, '9', is a setting which indicates how many md5 passes to perform. it is decoded via phpass's own base64 encoding:
'./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
'9' is the 11th character, so that means that there will be 2^11 md5 operations.

The next 8 characters, 'XcmlsyEg', is the hash salt. this is used once as plain text.

The next 22 characters, 'tMOKxU/TH53bkOv637O9c/', is the actual binary hash encoded in phpass's own base64 encoding.



To compute the actual hash:
First, the salt is prepended to the password and md5'd (using binary output mode):

$hash = md5($salt . $password, true);

next, the hash is prepended to the password and md5'd, repeatedly, for count number of times (where count is determined by the first character after $H$):

do
{
$hash = md5($hash . $password, true);
}
while (--$count);

Then, the settings (made up of '$H$', the count setting, and the salt) is prepended to a base64 encoding (phpass's own base64 encoding) of the binary hash and output:

$output = substr($setting, 0, 12);
$output .= _hash_encode64($hash, 16, $itoa64);

return $output;



Hence, md5 is computed 2049 times on each input password (513 times if the php version is less than 5). You can estimate your hashes/s by taking your md5s/s and dividing it by the count (2049 in most cases). I can get ~1.2k hashes/s on each core. The salt is too long to create rainbow tables for all inputs, but dictionary attacks are still possible, yet a little difficult on large numbers of hashes.

An interesting note is that if you can successfully reverse the last hash then it is very likely that you've obtained real password. Hence, a successful pre-image attack on a single md5 block will break the hash.


To crack a phpbb3 hash, you just have to take the count and salt, and keep hashing passwords until you find one that matches.



I borrowed the following php code from some other place to figure out how this all works:
Code: Select all
/**
*
* @version Version 0.1 / $Id: functions.php 8491 2008-04-04 11:41:58Z acydburn $
*
* Portable PHP password hashing framework.
*
* Written by Solar Designer <solar at openwall.com> in 2004-2006 and placed in
* the public domain.
*
* There's absolutely no warranty.
*
* The homepage URL for this framework is:
*
*   http://www.openwall.com/phpass/
*
* Please be sure to update the Version line if you edit this file in any way.
* It is suggested that you leave the main version number intact, but indicate
* your project name (after the slash) and add your own revision information.
*
* Please do not change the "private" password hashing method implemented in
* here, thereby making your hashes incompatible.  However, if you must, please
* change the hash type identifier (the "$P$") to something different.
*
* Obviously, since this code is in the public domain, the above are not
* requirements (there can be none), but merely suggestions.
*
*
* Hash the password
*/
function phpbb_hash($password)
{
   $itoa64 = './0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

   $random_state = unique_id();
   $random = '';
   $count = 6;

   if (($fh = @fopen('/dev/urandom', 'rb')))
   {
      $random = fread($fh, $count);
      fclose($fh);
   }

   if (strlen($random) < $count)
   {
      $random = '';

      for ($i = 0; $i < $count; $i += 16)
      {
         $random_state = md5(unique_id() . $random_state);
         $random .= pack('H*', md5($random_state));
      }
      $random = substr($random, 0, $count);
   }

   $hash = _hash_crypt_private($password, _hash_gensalt_private($random, $itoa64), $itoa64);

   if (strlen($hash) == 34)
   {
      return $hash;
   }

   return md5($password);
}

/**
* Check for correct password
*/
function phpbb_check_hash($password, $hash)
{
   $itoa64 = './0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
   if (strlen($hash) == 34)
   {
      return (_hash_crypt_private($password, $hash, $itoa64) === $hash) ? true : false;
   }

   return (md5($password) === $hash) ? true : false;
}

/**
* Generate salt for hash generation
*/
function _hash_gensalt_private($input, &$itoa64, $iteration_count_log2 = 6)
{
   if ($iteration_count_log2 < 4 || $iteration_count_log2 > 31)
   {
      $iteration_count_log2 = 8;
   }

   $output = '$H$';
   $output .= $itoa64[min($iteration_count_log2 + ((PHP_VERSION >= 5) ? 5 : 3), 30)];
   $output .= _hash_encode64($input, 6, $itoa64);

   return $output;
}

/**
* Encode hash
*/
function _hash_encode64($input, $count, &$itoa64)
{
   $output = '';
   $i = 0;

   do
   {
      $value = ord($input[$i++]);
      $output .= $itoa64[$value & 0x3f];

      if ($i < $count)
      {
         $value |= ord($input[$i]) << 8;
      }

      $output .= $itoa64[($value >> 6) & 0x3f];

      if ($i++ >= $count)
      {
         break;
      }

      if ($i < $count)
      {
         $value |= ord($input[$i]) << 16;
      }

      $output .= $itoa64[($value >> 12) & 0x3f];

      if ($i++ >= $count)
      {
         break;
      }

      $output .= $itoa64[($value >> 18) & 0x3f];
   }
   while ($i < $count);

   return $output;
}

/**
* The crypt function/replacement
*/
function _hash_crypt_private($password, $setting, &$itoa64)
{
   $output = '*';

   // Check for correct hash
   if (substr($setting, 0, 3) != '$H$')
   {
      return $output;
   }

   $count_log2 = strpos($itoa64, $setting[3]);

   if ($count_log2 < 7 || $count_log2 > 30)
   {
      return $output;
   }

   $count = 1 << $count_log2;
   $salt = substr($setting, 4, 8);

   if (strlen($salt) != 8)
   {
      return $output;
   }

   /**
   * We're kind of forced to use MD5 here since it's the only
   * cryptographic primitive available in all versions of PHP
   * currently in use.  To implement our own low-level crypto
   * in PHP would result in much worse performance and
   * consequently in lower iteration counts and hashes that are
   * quicker to crack (by non-PHP code).
   */
   if (PHP_VERSION >= 5)
   {
      $hash = md5($salt . $password, true);
      do
      {
         $hash = md5($hash . $password, true);
      }
      while (--$count);
   }
   else
   {
      $hash = pack('H*', md5($salt . $password));
      do
      {
         $hash = pack('H*', md5($hash . $password));
      }
      while (--$count);
   }

   $output = substr($setting, 0, 12);
   $output .= _hash_encode64($hash, 16, $itoa64);

   return $output;
}



Also, here's the more modern phpass 0.3 php code just for comparison, the essential hashing process is basically the same;
Code: Select all
<?php
#
# Portable PHP password hashing framework.
#
# Version 0.3 / genuine.
#
# Written by Solar Designer <solar at openwall.com> in 2004-2006 and placed in
# the public domain.  Revised in subsequent years, still public domain.
#
# There's absolutely no warranty.
#
# The homepage URL for this framework is:
#
#   http://www.openwall.com/phpass/
#
# Please be sure to update the Version line if you edit this file in any way.
# It is suggested that you leave the main version number intact, but indicate
# your project name (after the slash) and add your own revision information.
#
# Please do not change the "private" password hashing method implemented in
# here, thereby making your hashes incompatible.  However, if you must, please
# change the hash type identifier (the "$P$") to something different.
#
# Obviously, since this code is in the public domain, the above are not
# requirements (there can be none), but merely suggestions.
#
class PasswordHash {
   var $itoa64;
   var $iteration_count_log2;
   var $portable_hashes;
   var $random_state;

   function PasswordHash($iteration_count_log2, $portable_hashes)
   {
      $this->itoa64 = './0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

      if ($iteration_count_log2 < 4 || $iteration_count_log2 > 31)
         $iteration_count_log2 = 8;
      $this->iteration_count_log2 = $iteration_count_log2;

      $this->portable_hashes = $portable_hashes;

      $this->random_state = microtime();
      if (function_exists('getmypid'))
         $this->random_state .= getmypid();
   }

   function get_random_bytes($count)
   {
      $output = '';
      if (is_readable('/dev/urandom') &&
          ($fh = @fopen('/dev/urandom', 'rb'))) {
         $output = fread($fh, $count);
         fclose($fh);
      }

      if (strlen($output) < $count) {
         $output = '';
         for ($i = 0; $i < $count; $i += 16) {
            $this->random_state =
                md5(microtime() . $this->random_state);
            $output .=
                pack('H*', md5($this->random_state));
         }
         $output = substr($output, 0, $count);
      }

      return $output;
   }

   function encode64($input, $count)
   {
      $output = '';
      $i = 0;
      do {
         $value = ord($input[$i++]);
         $output .= $this->itoa64[$value & 0x3f];
         if ($i < $count)
            $value |= ord($input[$i]) << 8;
         $output .= $this->itoa64[($value >> 6) & 0x3f];
         if ($i++ >= $count)
            break;
         if ($i < $count)
            $value |= ord($input[$i]) << 16;
         $output .= $this->itoa64[($value >> 12) & 0x3f];
         if ($i++ >= $count)
            break;
         $output .= $this->itoa64[($value >> 18) & 0x3f];
      } while ($i < $count);

      return $output;
   }

   function gensalt_private($input)
   {
      $output = '$P$';
      $output .= $this->itoa64[min($this->iteration_count_log2 +
         ((PHP_VERSION >= '5') ? 5 : 3), 30)];
      $output .= $this->encode64($input, 6);

      return $output;
   }

   function crypt_private($password, $setting)
   {
      $output = '*0';
      if (substr($setting, 0, 2) == $output)
         $output = '*1';

      $id = substr($setting, 0, 3);
      # We use "$P$", phpBB3 uses "$H$" for the same thing
      if ($id != '$P$' && $id != '$H$')
         return $output;

      $count_log2 = strpos($this->itoa64, $setting[3]);
      if ($count_log2 < 7 || $count_log2 > 30)
         return $output;

      $count = 1 << $count_log2;

      $salt = substr($setting, 4, 8);
      if (strlen($salt) != 8)
         return $output;

      # We're kind of forced to use MD5 here since it's the only
      # cryptographic primitive available in all versions of PHP
      # currently in use.  To implement our own low-level crypto
      # in PHP would result in much worse performance and
      # consequently in lower iteration counts and hashes that are
      # quicker to crack (by non-PHP code).
      if (PHP_VERSION >= '5') {
         $hash = md5($salt . $password, TRUE);
         do {
            $hash = md5($hash . $password, TRUE);
         } while (--$count);
      } else {
         $hash = pack('H*', md5($salt . $password));
         do {
            $hash = pack('H*', md5($hash . $password));
         } while (--$count);
      }

      $output = substr($setting, 0, 12);
      $output .= $this->encode64($hash, 16);

      return $output;
   }

   function gensalt_extended($input)
   {
      $count_log2 = min($this->iteration_count_log2 + 8, 24);
      # This should be odd to not reveal weak DES keys, and the
      # maximum valid value is (2**24 - 1) which is odd anyway.
      $count = (1 << $count_log2) - 1;

      $output = '_';
      $output .= $this->itoa64[$count & 0x3f];
      $output .= $this->itoa64[($count >> 6) & 0x3f];
      $output .= $this->itoa64[($count >> 12) & 0x3f];
      $output .= $this->itoa64[($count >> 18) & 0x3f];

      $output .= $this->encode64($input, 3);

      return $output;
   }

   function gensalt_blowfish($input)
   {
      # This one needs to use a different order of characters and a
      # different encoding scheme from the one in encode64() above.
      # We care because the last character in our encoded string will
      # only represent 2 bits.  While two known implementations of
      # bcrypt will happily accept and correct a salt string which
      # has the 4 unused bits set to non-zero, we do not want to take
      # chances and we also do not want to waste an additional byte
      # of entropy.
      $itoa64 = './ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';

      $output = '$2a$';
      $output .= chr(ord('0') + $this->iteration_count_log2 / 10);
      $output .= chr(ord('0') + $this->iteration_count_log2 % 10);
      $output .= '$';

      $i = 0;
      do {
         $c1 = ord($input[$i++]);
         $output .= $itoa64[$c1 >> 2];
         $c1 = ($c1 & 0x03) << 4;
         if ($i >= 16) {
            $output .= $itoa64[$c1];
            break;
         }

         $c2 = ord($input[$i++]);
         $c1 |= $c2 >> 4;
         $output .= $itoa64[$c1];
         $c1 = ($c2 & 0x0f) << 2;

         $c2 = ord($input[$i++]);
         $c1 |= $c2 >> 6;
         $output .= $itoa64[$c1];
         $output .= $itoa64[$c2 & 0x3f];
      } while (1);

      return $output;
   }

   function HashPassword($password)
   {
      $random = '';

      if (CRYPT_BLOWFISH == 1 && !$this->portable_hashes) {
         $random = $this->get_random_bytes(16);
         $hash =
             crypt($password, $this->gensalt_blowfish($random));
         if (strlen($hash) == 60)
            return $hash;
      }

      if (CRYPT_EXT_DES == 1 && !$this->portable_hashes) {
         if (strlen($random) < 3)
            $random = $this->get_random_bytes(3);
         $hash =
             crypt($password, $this->gensalt_extended($random));
         if (strlen($hash) == 20)
            return $hash;
      }

      if (strlen($random) < 6)
         $random = $this->get_random_bytes(6);
      $hash =
          $this->crypt_private($password,
          $this->gensalt_private($random));
      if (strlen($hash) == 34)
         return $hash;

      # Returning '*' on error is safe here, but would _not_ be safe
      # in a crypt(3)-like function used _both_ for generating new
      # hashes and for validating passwords against existing hashes.
      return '*';
   }

   function CheckPassword($password, $stored_hash)
   {
      $hash = $this->crypt_private($password, $stored_hash);
      if ($hash[0] == '*')
         $hash = crypt($password, $stored_hash);

      return $hash == $stored_hash;
   }
}

?>


happy cracking <3
User avatar
WallShadow
Contributor
Contributor
 
Posts: 686
Joined: Tue Mar 06, 2012 9:37 pm
Blog: View Blog (0)


Re: phpass/phpbb3 hashing algorithm detail

Post by -Ninjex- on Tue Dec 23, 2014 11:31 pm
([msg=86025]see Re: phpass/phpbb3 hashing algorithm detail[/msg])

Thanks for the detailed information, Wall.
I enjoyed the read. I'm hoping to see more from you.
image
For those that know
K: 0x2CD8D4F9
User avatar
-Ninjex-
Moderator
Moderator
 
Posts: 1691
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)



Return to Crypto

Who is online

Users browsing this forum: No registered users and 0 guests