How's this for a hashing algorithm?

cachepl0x · 10-16-2009, 11:30 AM

I was wondering. In terms of security, how is this for a hashing algorithm?

PHP Code:


			
$salt = sha1('Hash');
$pass = sha1('My Password');
$hash = $pass . $salt;

for ($i = 0; $i < 10000; $i++) {
    $hash = sha1($hash);
    $hash = substr($hash, 5, 15);
}

Good, or bad? Improvements?

Salathe · 10-16-2009, 12:14 PM

I'm no cryptography expert by any stretch of the imagination! However, I think it is bad for two main reasons. Firstly, the end result will be a 10 character hexadecimal string which is much (much!) easier to collide with than say a full SHA-1 hash (40 hexadecimal characters). Secondly, rehashing 10,000 times and slicing that hash into a quarter is a complete waste of time and effort.

For what reasons do you think it an improvement (if you think that) over much more simple uses of hashing (like $hash = sha1($salt.$password);)?

Village Idiot · 10-16-2009, 03:11 PM

I know a little about cryptography, and the first rule we were taught was that "if you came up with it yourself, it is insecure." Mixing hashes often makes collision rates higher and adds more of a footprint than it takes away. Basic hashing with a salt is quite secure. If you want more security go for a low-collision algorithm that the Department of Defense says is still good (MD5 and SHA1 were ruled insecure years ago). Although a hash with an unknown salt is for all intents and purposes unreleasable (although collisions would still apply).

edit:
After actually reading your algorithm, it is not safe. Reducing it to a base-16 number, trimming it, reducing it again and repeating it 10,000 times will likely make collisions extremely high. Even doing it once will have the same effect since your end result will always be the product of a ten digit base-16 number.

ryanmr · 10-16-2009, 05:53 PM

So something better might be something like this.

PHP Code:


			
$data = 'my very secret password';

$salt = 'QX;2t9`l}O^fE71AVueo5NLW7;fCI5[])=v/8Ju+?HEsxMqbtgeK@L7eVb[DH|]|'; // from wordpress, http://api.wordpress.org/secret-key/1.1/

$str = $salt . $data;

$hash = hash('sha256', $str);

Which returns this masterpiece, 1c5759b53c6b6c017f548087774cf9ab69da7dd77609cd5606 512e0cab6b52eb. Yours would return, with the same data and hash, 6e6455d40c33712.

Village Idiot · 10-16-2009, 07:40 PM

Quote:

Originally Posted by ryanmr

So something better might be something like this.

PHP Code:


			
$data = 'my very secret password';
$salt = 'QX;2t9`l}O^fE71AVueo5NLW7;fCI5[])=v/8Ju+?HEsxMqbtgeK@L7eVb[DH|]|'; // from wordpress, http://api.wordpress.org/secret-key/1.1/
$str = $salt . $data;
$hash = hash('sha256', $str);

Which returns this masterpiece, 1c5759b53c6b6c017f548087774cf9ab69da7dd77609cd5606 512e0cab6b52eb. Yours would return, with the same data and hash, 6e6455d40c33712.

Long salts don't really make anything more secure. Since similar inputs do not yield similar outputs, a short but unknown salt is just as effective as a long one. A long salt does not hurt though, it just doesn't help.

bucabay · 10-19-2009, 03:48 PM

Quote:

Originally Posted by Village Idiot

Long salts don't really make anything more secure. Since similar inputs do not yield similar outputs, a short but unknown salt is just as effective as a long one. A long salt does not hurt though, it just doesn't help.

I think it should be stated as a random salt or a hard to guess salt and not as long and short. Of course a long salt like "try and guess me if you can" would not be a good choice.

If the salt can be isolated, say for a password+salt where the user knows the password, or time()+salt for a session where time() can be guessed you'd have just the salt to figure out.

It would thus be useful to have a salt that is as hard to guess as the actual hashes. You'll notice the salts generated by http://api.wordpress.org/secret-key/1.1/ are 64 chars and so are sha256 hashes. I'm assuming this is not a coincidence but actually making sure the salt is even harder to guess then the hashes (256^64 possible salts compared to 16^64 hashes).

I'm mostly guessing here from the little I've read on the topic.

Village Idiot · 10-19-2009, 04:04 PM

Quote:

Originally Posted by bucabay

It would thus be useful to have a salt that is as hard to guess as the actual hashes. You'll notice the salts generated by http://api.wordpress.org/secret-key/1.1/ are 64 chars and so are sha256 hashes. I'm assuming this is not a coincidence but actually making sure the salt is even harder to guess then the hashes (256^64 possible salts compared to 16^64 hashes).

Those are not sha256 hashes because they are not base-16 numbers. Those are simply random strings.

Bear in mind that SHA1 is still yet to be reverse engineered even without a salt in the way. Since an infinite amount of inputs go to a finite number of outputs, each SHA1 value potentially has infinite input values. This makes these algorithms extremely hard to reverse, especially if you are not working with real words.

SHA1 and MD5 both do not yield similar outputs to similar inputs, so a unknown SALT of any kind will completely throw anything off. The difference between "hello" and "hello1" is great, and the difference between the previous contrasted with "goodbye" and "goodbye1" will normally also great. This means that not only can you not trace a hash though the algorithm, you can't cross reference multiple ones to extract a salt.

bucabay · 10-19-2009, 09:04 PM

Quote:

Originally Posted by Village Idiot

Those are not sha256 hashes because they are not base-16 numbers. Those are simply random strings.

I was assuming the salts were ASCII strings, thus the 256^64 possible salts and 16^64 possible hashes.

Quote:

Originally Posted by Village Idiot

Bear in mind that SHA1 is still yet to be reverse engineered even without a salt in the way. Since an infinite amount of inputs go to a finite number of outputs, each SHA1 value potentially has infinite input values. This makes these algorithms extremely hard to reverse, especially if you are not working with real words.

SHA1 and MD5 both do not yield similar outputs to similar inputs, so a unknown SALT of any kind will completely throw anything off. The difference between "hello" and "hello1" is great, and the difference between the previous contrasted with "goodbye" and "goodbye1" will normally also great. This means that not only can you not trace a hash though the algorithm, you can't cross reference multiple ones to extract a salt.

I understand that you cannot easily reverse a hashing algorithm, and that two inputs do not have related results.

What I'm implying is the pure statistical possibility of guessing the salt knowing it's hash. If you're going to use a hashing algorithm that makes collision a 1 in 16^64 chance, why use a salt with a a high chance of being guessed? A pretty random salt is good enough, but one that also has a 16^64 chance of being guessed through direct brute force would be the most secure. Anything above that, won't be adding any more randomness.

bucabay · 10-20-2009, 07:09 PM

Quote:

Originally Posted by cachepl0x

I was wondering. In terms of security, how is this for a hashing algorithm?

PHP Code:


			
$salt = sha1('Hash');

$pass = sha1('My Password');

$hash = $pass . $salt;



for ($i = 0; $i < 10000; $i++) {

    $hash = sha1($hash);

    $hash = substr($hash, 5, 15);

}

Good, or bad? Improvements?

It appears that rehashing (http://en.wikipedia.org/wiki/Key_strengthening) is a defense against precomputation attacks such as rainbow tables.
http://en.wikipedia.org/wiki/Rainbow...rainbow_tables

You'd have to rehash with the hash and password included:

PHP Code:


			
$salt = 'QX;2t9`l}O^fE71AVueo5NLW7;fCI5[])=v/8Ju+?HEsxMqbtgeK@L7eVb[DH|]|';

$pass = 'My Password';

$hash = '';



for ($i = 0; $i < 10000; $i++) {

    $hash = sha1($hash.$pass.$salt);

}

Quote:

Originally Posted by Village Idiot

Mixing hashes often makes collision rates higher and adds more of a footprint than it takes away.

I'm assuming adding the pass and salt to each iteration is to prevent the footprint and collision rate form increasing?

adamdecaf · 10-21-2009, 12:07 AM

I wonder if this will help.

Take one letter or number, you can have 62 possible symbols for that ([a-zA-Z0-9]). Now you take and form a single character hash of that, you've now just simplified that to a base (16/32/64/...). The values can now be [0-9a-f], or 16 characters.

If we take a sample string of "62-symbol possible characters" and try to predict a pattern in that you would agree that it will take a lot more time/effort than a string with "16-symbol possible characters". You're doing the same thing with re-hashing a hash over and over again, now we're talking about (sha-1) 2**52 <> 2**80, but still a considerable decomposition in security.

Your best bet is to create a fairly random string (8-16 characters) and hash that alongside with the password. The position for the salt and hash doesn't make a difference.

PHP Code:


			
// A simple and very trivial random string generator.
// You can/should always seed the random number generator with something.
function rand_string($length = 8) {
   switch(rand(0,2)) {
       case 0:
          return chr(rand(65, 90));
       break;

       case 1:
          return chr(rand(97, 122));
       break;

       case 2:
          return chr(rand(33, 64));
       break;
   }
}

$salt = rand_string(rand(8,16));
$password = $_POST['password'];

$hash = sha1($salt . $password);

That has been tried, tested, and very true for almost all web applications. (More advanced systems use far more complicated methods, which you should not need.)

*EDIT* - Put $salt and $hash in wrong places, fixed.

Rhinos · 11-01-2009, 07:20 PM

@Adamdecaf: Your function does not use the $length variable, I'm guessing you wanted to have a loop in there to make the salt whatever length is given in the arguments. Also you will never be able to compare the hash again the next time a user logs in because the salt would be different each time and therefore the hash would be different to the one stored in the database even if the entered passwords match.

The salt can be a static string, just make sure no one gets access to the place it is stored and don't make it too short.

Here's a quick example of basic password storing security:

PHP Code:


			
// some config file
$salt = 'go_on_guess'; // use letters, numbers and symbols


// registration
$userpass = sha1($salt . $password); // where $password is from $_POST['password']
// Then you save $userpass when creating the user


// login
// select user based on email/username given
if ($user['password'] === sha1($salt . $_POST['password'])) {
    // right password, create session
}

adamdecaf · 11-01-2009, 07:43 PM

Whoops, that code was not made correctly. I was going for something similar to the following.

PHP Code:


			
function rand_string($length = 8) {

// Store the random string.
$str = '';

    for ($n = 0; $n < $length; $n++) {
         switch(rand(0,2)) {
           case 0:
              $str .= chr(rand(65, 90));
           break;

           case 1:
              $str .= chr(rand(97, 122));
           break;

           case 2:
              $str .= chr(rand(33, 64));
           break;
       }
    }

return $str;
}

// Now when a new user is created we should 
// give them a hash alongside the password.
$pass = $_POST['password'];
$salt = rand_string(rand(8,16));

$hash = sha265($salt . $pass);

// Now store it in the database.
// This is a dummy function that would store
// the value in the correct field/row.
// Note: The $user_id would be generated from 
// another part of the script.
$mysql->insert(array('id','password'), array($user_id, $hash));

Now, we would create another unique random string and assign/store it in the database that could be used in a cookie. That would associate the cookie with the correct user account.

Rhinos · 11-01-2009, 08:10 PM

So each user will have their own salt stored in the database?

I'm still unconvinced by your use of a random string generator for the salt.

Surely ryanmr's method as well as mine would be better?

adamdecaf · 11-01-2009, 08:38 PM

Quote:

Originally Posted by Rhinos

So each user will have their own salt stored in the database?

Yes, you should store the clear-text version of the salt and a hashed version of the salt + password.

You then grab the incoming data $_GET/$_POST and hash it (with the given salt) and compare the newly hashed data against the string stored in the database. If they match then you have a successful login, else you need to send an error.

Quote:

Originally Posted by Rhinos

I'm still unconvinced by your use of a random string generator for the salt.

Surely ryanmr's method as well as mine would be better?

The length of a salt doesn't matter a great deal, the idea is to combine the password with any length of unknown characters. This way a brute force attack would have to contemplate more data than just a simple password. If a hackers gains access to your database then they still have to check the possibilities.

Salts are just used to increase security for resistance against brute force attacks, the unknown variable is a great asset for securing user accounts.

Rhinos · 11-01-2009, 09:05 PM

I understand the need for a salt but your method seems redundant. If a hacker could get into the database then they are given the salt, which they can then use to bruteforce a single users password. It's not much different than using the same password all that would happen in the brute force script is the changing of the salt on a per user basis.

SQL Injection seems far more likely in web apps than remote file inclusion and therefore storing a salt in a php file that is outside of the web root seems like a safer option as anyone who does get the hash's from the database will still need to try and brute force the salt that is an unknown number of characters to them.

I'm aware that you can show files using mysql but you have to know the directory structure and name of the file which I am not sure how easy that would be but this article touchs upon file inclusion with mysql: http://ferruh.mavituna.com/sql-injec...gwithoutQuotes

I have no proof that what I am suggesting is better but I just thought that your method was overly complicated. I'm open to hearing why you think a unique salt per user would be just as good/better though.

Regards,
David

adamdecaf · 11-01-2009, 09:53 PM

Quote:

Originally Posted by Rhinos

I have no proof that what I am suggesting is better but I just thought that your method was overly complicated. I'm open to hearing why you think a unique salt per user would be just as good/better though.

With using one salt if the salt is guessed then you have to count all of your accounts as compromised, if you use multiple salts and one is guessed then you just reset the salt for that account and notify the user.

Also, you should always clean (mysql_real_escape_string() at bare minimum) any input that you're placing into a DB, otherwise, you're just asking for trouble.

bucabay · 11-01-2009, 10:17 PM

A visible salt does not decrease the effectiveness of a brute force.
http://en.wikipedia.org/wiki/Brute_force_attack

Quoting the wikipedia article:

Quote:

For symmetric-key ciphers, a brute force attack typically means a brute-force search of the key space; that is, testing all possible keys in order to recover the plaintext used to produce a particular ciphertext.

For hashes, the only unknown would be the password. Thus only the length of the password would affect the time taken for the brute force.

The visible salt would however make a current rainbow table infeasible ONLY IF the salt is random (large) enough.

The current posts that are stating that the size of the salt does not matter is only correct for unknown salts. If the salt is visible, you need a salt that is longer then what current rainbow tables can crack.
http://www.codinghorror.com/blog/archives/000949.html
See the length of passwords the rainbow table supports in the above article. It seems 14 characters are about the limit but I'm sure there are larger tables out there.

I would not solely trust a hidden salt, since having database access usually means the attacker can gain access to the file system. So I think having a large visible salt is the best bet against rainbow tables.

Then having a hidden salt to make brute force harder. More importantly have key strengthening (http://en.wikipedia.org/wiki/Key_strengthening) or a computationally intensive hashing algorithm to make brute force ineffective such as mentioned here:
http://chargen.matasano.com/chargen/...w-about-s.html