[TheMaster]

Sephern, Daniel15, and ianonavy, thank you very much!

All your replies much appreciated. I'm finally beginning to understand the wonderful word of cryptography alot better!

[Sephern]

ianonavy, on 22 May 2012 - 08:56 AM, said:

No, it would just take a marginally longer time to calculate the password. Common hash functions like SHA1 and MD5 are ridiculously fast for any modern computer to calculate. Security comes not from how long it takes for someone to brute force a password, but rather how unlikely it would be that they would randomly guess it. If you feed a hash back into a hash, you still get another hash of the same length with the same amount of entropy. Hash functions work by taking any size input and turning it into a very very highly likely unique set of bits with a fixed length (usually 128 or 160 depending on the algorithm). However, because the number of hashes an algorithm can produce is finite, it is mathematically possible (but extremely unlikely) for two passwords to produce the same hash. By running the hash algorithm multiple times, you effectively reduce the number of "possible hashes" that the algorithm can use for hashes, and that makes collisions exponentially more likely, which is bad bad BAD for password hashing.


This. SHA1 and MD5 are secure because of the immense amount of possible hashes they can produce. By running them multiple times, you're reducing their security (by slightly decreasing the entropy) in exchange for a few more microseconds of calculation.


Let me illustrate this with an example. Let's say that a password-obfuscating algorithm does this by counting the number of vowels, then the number of consonants and storing it as a concatenated string and fitting a bunch of zeros to make it a fixed-length. "Iamyourcatoverlord" corresponds to "00000710". Now a computer that wants to reverse this algorithm is going to have a difficult time because the output string "00000710" could be interpreted as 71 vowels, 0 consonants OR 7 vowels and 10 consonants. For each situation, they have to iterate through the 21 possible consonants and 5 possible vowels (I did not count y in this case). This algorithm's security comes from making it difficult to guess a password that would produce the same hash that the original password produces.

What a cracker could do, however, is reverse the algorithm and try every possible combination of letters and vowels that fit with either 71 vowels, 0 consonants or 7 vowels and 10 consonants. Considering you can get any computer that can calculate 10 GigaFLOPS (that is, 10 billion floating-point operations in a second) for relatively cheap, any password protected by this algorithm would be guessed practically instantly. The major drawback is that passwords like "cat" and "dog" produce the same hash: "00000021". That means that a cracker can guess the word "dog", even though the user normally enters "cat", and the server will hash both passwords to mean the same "0000021", and "dog" will give the cracker access.

MD5, which is often mistaken to be insecure for passwords, produces a 128-bit hash value. That means that there are 2^128 or 3.40 × 10^38 possible hashes that can be produced by MD5. At an average speed of 10 GFLOPS, a desktop PC would take 3.40 × 10^28 seconds or 1.08 × 10^21 years to go through every possible hash! Now that's an average desktop PC. More than likely, your cracker will be using some sort of distributed system to achieve more FLOPS, or much more powerful hardware. It's still going to take them a long time, especially if you salt the password first. Every time you run MD5 more than once, you reduce the number of possible hashes that can be produced while only marginally increasing how long it takes for the computer to calculate it. Considering that MD5 takes only around 624 operations to calculate, you'd have to run it 16,025,641 times to make it take a second longer for a cracker to calculate a password for a hash, while giving them exponentially more passwords that could possibly produce the same stored hash value. This is why running secure hash algorithms more than once is generally frowned upon by security experts.

Edit: I can spell "overlord".

A very good post. The only thing is that Salts don't really protect against traditional brute-force attacks. The reason that you have a salt is because otherwise somebody could simply have a lookup table of every single MD5 for common passwords (or even dictionary words, or whatever) and just look it up. Salting your passwords means that obviously, this doesn't work (if I have a record for 'Password', then it naturally wouldn't match 'e3423lm_Password' for example).

The reason you should use different salts for every user is that otherwise an attacker could simply generate one of those lookup tables for every password using your particular salt. If you have different salts for every user, somebody would have to make a lookup table of every dictionary word for every user. It also means that if 2 users have the same password they wouldn't have the same hash. That means that the most efficient way of breaking passwords ceases to be generating lookup tables, and starts being bruteforce. If they're bruteforcing every password and they know the salt (which they do since they're stored in plaintext) then essentially instead of trying every word, you just try every word with the salt in front of it (or behind it. Or whatever).

[Comkid]

<?php

define('VERSION', '0.2f');

/* --- Changelog ---
* Version: 0.2f
  - Changed changelog and comments styling
* Version: 0.2e
  - Fixed up a bug in the check part for intense, always making it say it is false
* Version: 0.2d
  - Added a simple intensive mode (advanced to come)
* Version: 0.2c
  - Changed the hash to md5 (specifically)
* Version: 0.2b
  - Changed the crypt to using hash
* Version: 0.2a
  - Commented everything
* Version: 0.1c
  - Cleaned up the code
* Version: 0.1b
  - Integrated both functions into one
* Version: 0.1a
  - Base code coded
  --- Changelog --- */

function C4H2()
{
//  Make sure that this script can run forever, until it finishes
	set_time_limit(0);

//  Get all args passed to the function
	$args = func_get_args();

//  Make sure not too many args passed to the function
	if (count($args) > 5)
	{
	//  Return the error message
		return 'Too Many Arugments Defined';
	}

//  Set mode as the first arg passed
	$mode = $args[0];

//  Validate mode, make sure it is not empty and it is one of the two, hash or check
	if (empty($mode) || !in_array($mode, array('hash', 'check')))
	{
	//  Return the error message
		return (empty($mode)) ? 'Mode Not Defined' : 'Inexistant Mode Defined';
	}

//  If mode is hash then make arg equal to four, if not make it equal to three
	$arg = ($mode == 'hash') ? 4 : 3;

//  If the amount of args passed to the function is smaller than the arg (the amount it should be)
	if (count($args) < $arg)
	{
	//  Return the error message
		return 'Not All Arguments Defined';
	}

//  Make input and original equal the second arg passed to the function
	$input = $original = $args[1];

//  Validate input, make sure it is not empty
	if (empty($input))
	{
	//  Return the error message
		return 'Input Not Defined';
	}

//  If mode is hash, then arg is key, if not then it is hash
	$arg = ($mode == 'hash') ? 'key' : 'hash';	
//  $arg (look above) ^^ is equal to the third arg passed to the function
	$$arg = $args[2];
//  If mode is hash, then arg is hash, if not then it is key
	$arg = ($mode == 'hash') ? 'hash' : 'key';
//  $arg (look above) ^^ is equal to nothing
	$$arg = '';

//  Switch between the cases depending on the value of mode
	switch ($mode)
	{
	//  If mode is hash run this code block
		case 'hash':
		//  Make key equal to the third arg passed to the function (turned into an int)
			$key = intval($key);
		//  Make runs equal to the fourth arg passed to the function (turned into an int)
			$runs = (isset($args[3]) && !empty($args[3]) && is_int($args[3]) && strlen($args[3])) ? intval($args[3]) : rand(10, 99);
		//  Intense is true if it was passed correctly to the function, if not then it is false
			$intense = (isset($args[4]) && is_bool($args[4])) ? $args[4] : false;
		break;

	//  If mode is check run this code block
		case 'check':
		//  Validate hash, make sure it is the right length, and the hash checks out compared to a default regex which all hashes generated should
			if (strlen($hash) != 50 || !preg_match('/[0-9]{1,9}[$]{0,1}[a-zA-Z0-9]{35}[a-zA-Z0-9]{2,11}[0-9]{3}/', $hash))
			{
			//  Return the error message
				return 'Not a C4H2 hash';
			}

		//  Runs is equal to the forty-eighth character and forty-nineth character of the hash
			$runs = $hash[47] . $hash[48];

		//  For loop which continues running until $r is equal to the fiftieth
			for ($r = 0; $r < $hash[49]; $r++)
			{
			//  Add the $r+1th character of the hash to the end of the key variable
				$key .= $hash[$r];
			}

		//  Make the key variable an integer
			$key = intval($key);

		//  Begin the regex variable with /(
			$regex = '/(';

		//  Intense is true if strlen(key)+1th character of hash is $, if not then intense is false
			$intense = ($hash[strlen($key)] == '$') ? true : false;
		break;
	}

//  Validate key, by making sure it isn't empty, it is an integer and it does fit the regex
	if (empty($key) || !is_int($key) || !preg_match('/^[0-9]{1,9}$/', $key))
	{
	//  If it doesn't, make key a random 9 digit number
		$key = rand(100000000, 999999999);
	}

//  Array is equal to all the hash algorithms supported by PHP
	$array = hash_algos();
//  Hash_algos is equal to an empty array
	$hash_algos = array();

//  For loop which continues running until the 35th run
	for ($i = 0, $s = $key % 35; $i < 35; $i++, $s++)
	{
	//  Check if s is bigger than 34
		if ($s > 34)
		{
		//  If s is bigger than 34, then make s equal to 0
			$s = 0;
		}

	//  Make hash_algos key i equal to array key s
		$hash_algos[$i] = $array[$s];
	}

//  Switch between the cases depending on the value of intense
	switch ($intense)
	{
	//  If intense is true, run this code block
		case true:
		//  For loop which runs until e is bigger than runs
			for ($e = 0; $e <= $runs; $e++)
			{
			//  On every run after the first run this code
				if ($e > 0)
				{
				//  Reset the input, by making it the previous hash/result
					$input = $hash;

				//  If mode is hash, then arg is hash, if not then it is regex
					$arg = ($mode == 'hash') ? 'hash' : 'regex';
				//  $arg (look above) ^^ is equal to key with $ after it if mode is hash, if not then it is equal to /( and ) around key with $ after it
					$$arg = ($mode == 'hash') ? "$key$" : "/($key\\$)";
				}

			//  Make hash run equal to the input
				$hash_run = $input;

			//  For loop which runs until i is equal to 35
				for ($i = 0; $i < 35; $i++)
				{
				//  Used is equal to nothing
					$used = '';

				//  If mode is check run the code block
					if ($mode == 'check')
					{
					//  Add to the end of regex [
						$regex .= '[';
					}

				//  For loop which runs until r is bigger than runs
					for ($r = 0; $r <= $runs; $r++)
					{
					//  hash_run is equal to the hash of the hash_run using the hash_algos key i
						$hash_run = hash($hash_algos[$i], $hash_run);

					//  For loop which runs until c is equal to the length of hash_run
						for ($c = 0; $c < strlen($hash_run); $c++)
						{
						//  If the c+1th character of hash_run is not found in used, then run the code block
							if (strpos($used, $hash_run[$c]) === false)
							{
							//  Add the c+1th character of hash_run to the end of used
								$used .= $hash_run[$c];

							//  If mode is check, then run the code block
								if ($mode == 'check')
								{
								//  Add the c+1th character of hash_run to the end of regex
									$regex .= $hash_run[$c];
								}
							}
						}
					}

				//  Switch between the cases depending on the value of mode
					switch ($mode)
					{
					//  If mode is hash run this code block
						case 'hash':
						//  Add a random character of used to the end of hash
							$hash .= $used[rand(0, strlen($used) - 1)];
						break;

					//  If mode is check run this code blcok
						case 'check':
						//  If i is 34 add to the end of regex, ](, if not then add ]
							$regex .= ($i == 34) ? '](' : ']';
						break;
					}
				}

			//  md5 is a md5 hash reversed of original if key is divisible by two, if not, then it is just a hash of the original
				$md5 = ($key % 2 == 0) ? strrev(md5($original)) : md5($original);
			//  If mode is hash, then length is the length of hash, if not then it is the length of key added with 35
				$length = ($mode == 'hash') ? strlen($hash) : strlen($key) + 36;
			//  Chars is the length subtracted from 47
				$chars = 47 - $length;

			//  For loop  which runs until r is bigger than chars
				for ($r = 0; $r < $chars; $r++)
				{
				//  If mode is hash, then arg is hash, if not then it is regex
					$arg = ($mode == 'hash') ? 'hash' : 'regex';
				//  $arg (look above) ^^ is equal to hash_run key r
					$$arg .= $md5[$r];
				}

			//  $arg (look above) ^^ is equal to runs with the length of key after it if mode is hash, if not then it is equal to that with )/ on the end
				$$arg .= ($mode == 'hash') ? $runs . strlen($key) : $runs . strlen($key) . ')/';
			}
		break;

	//  If intense is false, run this code block
		case false:
		//  If mode is hash, then arg is hash, if not then it is regex
			$arg = ($mode == 'hash') ? 'hash' : 'regex';
		//  $arg (look above) ^^ is equal to key if mode is hash, if not then it is equal to /( and ) around key
			$$arg = ($mode == 'hash') ? $key : "/($key)";

		//  Make hash run equal to the input
			$hash_run = $input;

		//  For loop which runs until i is equal to 35
			for ($i = 0; $i < 35; $i++)
			{
			//  Used is equal to nothing
				$used = '';

			//  If mode is check run the code block
				if ($mode == 'check')
				{
				//  Add to the end of regex [
					$regex .= '[';
				}

			//  For loop which runs until r is bigger than runs
				for ($r = 0; $r <= $runs; $r++)
				{
				//  hash_run is equal to the hash of the hash_run using the hash_algos key i
					$hash_run = hash($hash_algos[$i], $hash_run);

				//  For loop which runs until c is equal to the length of hash_run
					for ($c = 0; $c < strlen($hash_run); $c++)
					{
					//  If the c+1th character of hash_run is not found in used, then run the code block
						if (strpos($used, $hash_run[$c]) === false)
						{
						//  Add the c+1th character of hash_run to the end of used
							$used .= $hash_run[$c];

						//  If mode is check, then run the code block
							if ($mode == 'check')
							{
							//  Add the c+1th character of hash_run to the end of regex
								$regex .= $hash_run[$c];
							}
						}
					}
				}

			//  Switch between the cases depending on the value of mode
				switch ($mode)
				{
				//  If mode is hash run this code blcok
					case 'hash':
					//  Add a random character of used to the end of hash
						$hash .= $used[rand(0, strlen($used) - 1)];
					break;

				//  If mode is check run this code blcok
					case 'check':
					//  If i is 34 add to the end of regex, ](, if not then add ]
						$regex .= ($i == 34) ? '](' : ']';
					break;
				}
			}

		//  md5 is a md5 hash reversed of original if key is divisible by two, if not, then it is just a hash of the original
			$md5 = ($key % 2 == 0) ? strrev(md5($original)) : md5($original);
		//  If mode is hash, then length is the length of hash, if not then it is the length of key added with 35
			$length = ($mode == 'hash') ? strlen($hash) : strlen($key) + 35;
		//  chars is the length subtracted from 47
			$chars = 47 - $length;

		//  For loop  which runs until r is bigger than chars
			for ($r = 0; $r < $chars; $r++)
			{
			//  If mode is hash, then arg is hash, if not then it is regex
				$arg = ($mode == 'hash') ? 'hash' : 'regex';
			//  $arg (look above) ^^ is equal to hash_run key r
				$$arg .= $md5[$r];
			}

		//  $arg (look above) ^^ is equal to hash then add at the end runs and the length of key, if not add to the end the runs, the length of key and )/
			$$arg .= ($mode == 'hash') ? $runs . strlen($key) : $runs . strlen($key) . ')/';
		break;
	}

//  If mode is check, then run this code block
	if ($mode == 'check')
	{
	//  boolean is equal to true if the preg_match returns 1, if not then it is false
		$boolean = (preg_match($regex, $hash) == 1) ? true : false;
	}

//  If mode is hash, then return is hash, if not then it is boolean
	$return = ($mode == 'hash') ? $hash : $boolean;
//  If mode is hash, then return is hash, if not then it is regex
//  $return = ($mode == 'hash') ? $hash : $regex;
//   Uncomment return (look above) ^^ to make return equal to hash if mode is hash, if not then it is regex

//  Return the result of the function
	return $return;
}

This is what I use, I practically commented every line because I was bored, this is actually quite old, I think I wrote this over a year ago