Feature Request #3163

random salt injection

Added by Tomek Rychlik almost 4 years ago. Updated over 3 years ago.

Status:ClosedStart date:08/11/2010
Priority:UrgentDue date:
Assignee:Woody Gilk% Done:

0%

Category:Core
Target version:v3.1.0
Resolution:fixed Points:

Description

I guess salt injection in hash is to prevent brute force attack. It works fine but i think random injection make finding salt harder.

this salt pattern length for instance (1,5,7,10,20) with sha1, and current method, needs to perform (40!)/((40!-5!)5!) = 658008 combinations

random injection pattern: (20,1,7,5,10) needs to perform (40!)/(40!-5!) = 78960960 combinations!

Sorry for my english!
Regards!

not-cert.gif (1.22 KB) Steven G., 08/13/2010 02:09 PM

Associated revisions

Revision 1b600927
Added by Jeremy Bush almost 4 years ago

Changing hash method to hash_hmac, fixes #3163

History

#1 Updated by Steven G. almost 4 years ago

Tomek Rychlik wrote:

I guess salt injection in hash is to prevent brute force attack. It works fine but i think random injection make finding salt harder.

this salt pattern length for instance (1,5,7,10,20) with sha1, and current method, needs to perform (40!)/((40!-5!)5!) = 658008 combinations

random injection pattern: (20,1,7,5,10) needs to perform (40!)/(40!-5!) = 78960960 combinations!

Sorry for my english!
Regards!

Any link to specification for this "salt injection" pattern? Google has nothing on it.

#2 Updated by Tomek Rychlik almost 4 years ago

It is my idea :) Everything what you need to know is in my post. It is easy to implement and dramatically increases number of required combinations to find salt in passwords.

#3 Updated by Steven G. almost 4 years ago

Tomek Rychlik wrote:

It is my idea :) Everything what you need to know is in my post. It is easy to implement and dramatically increases number of required combinations to find salt in passwords.

Salt is not there to prevent brute force, it's there to prevent data from one brute force attack being used in another. In other words it's purpose to is to force the attacker to use a different brute force attack for each user.

If I have a password "password1" then applying a salt (of any size), or multiple salts (which I think is your case) does not change the number of combination! The hash functions always gives a result of the same bitlength so there are always the same number of combination. The intruder can simply use a tunneling technique to find a collision, and even if the string he finds is something like "42" then as long as that gives the same result as "password1" mission successful.

If you want to make it more secure I think simply using something like sha512 and so on, instead of sha1 is more productive.

The algorithm has some potential flaws as well:

  • normally the salt is kept next to the password verify-hash, how is this random number injection suppose to work? How do you verify a user if you just throw random numbers each time?
  • isn't using that many salts over and over (assuming that's what you mean) potentially creating more collisions making the hash function weaker and brute force easier?
  • a system is secure or it is not; there's no such as thing as "more secure" or "less secure," so really how is this better then just a normal salt? If you think the salt is weak simply make it bigger, you'll accomplish the same thing really; because of how a lot of hash functions work, but avoid inserting collisions in the hashing algorythm.

#4 Updated by Tomek Rychlik almost 4 years ago

You didnt understand me. I dont want use many salts. I just want defined in auth config something like that:

'salt_pattern' => '20, 5, 1, 32, 8'; // unordered offsets! <-- not ordered like current!


I know that many peoples keep salt next to the password. It protects against using rainbow tables. But doesnt protect against brute force attacks.

I thought hiding salt in hashed password prevent brute force becouse hacker doesnt have salt! So, i suggested better method to hide salt. The only difference is in use unordered offsets. Then hacker must carry out much more tests to extract salt from hash!
By bad was that i called it 'random injection' i should call it 'unordered injection'!

#5 Updated by Steven G. almost 4 years ago

Tomek Rychlik wrote:

I thought hiding salt in hashed password prevent brute force becouse hacker doesnt have salt! So, i suggested better method to hide salt. The only difference is in use unordered offsets. Then hacker must carry out much more tests to extract salt from hash!

What? But, hacker does have salt, salt is not a secret. :)

#6 Updated by Tomek Rychlik almost 4 years ago

Ah, ok. I hide salt in hash (hacker then dont know the salt) and I make it difficult to carry out brute force attack. If salt is not a secret, why use this code:

public function hash_password($password, $salt = FALSE)
{
(...)
$password = '';
// Used to calculate the length of splits
$last_offset = 0;
foreach ($this->_config['salt_pattern'] as $offset) {
// Split a new part of the hash off
$part = substr($hash, 0, $offset - $last_offset);
// Cut the current part out of the hash
$hash = substr($hash, $offset - $last_offset);
// Add the part to the password, appending the salt character
$password .= $part.array_shift($salt);
// Set the last offset to the current offset
$last_offset = $offset;
}
// Return the password, with the remaining hash appended
return $password.$hash;
}

and:

public function find_salt($password)
{
$salt = '';
foreach ($this->_config['salt_pattern'] as $i => $offset) {
// Find salt characters, take a good long look...
$salt .= substr($password, $offset + $i, 1);
}
return $salt;
}

Do you mean this is only for store salt in hash and can be replaced by adding one more field ('salt') in user table? If its true how hacker knows salt if he doesnt know salt pattern:

'salt_pattern' => '1, 5, 7, 10, 15, 22, 23, 26, 30, 34';

???

#7 Updated by Jeremy Bush almost 4 years ago

Steven G. wrote:

What? But, hacker does have salt, salt is not a secret. :)

The salt is a secret. What would be the point if it was public? ;)

In auth's case, each hash has a unique random salt.

#8 Updated by Tomek Rychlik almost 4 years ago

'The salt is a secret. What would be the point if it was public? ;)' I know that! You said 'salt is not a secret', but i guess it was a mistake.

When i say 'public salt' i think salt is placed in the database, and it is not encrypted. Salt is then 'public' for hacker who has our database tables.

In auth module (i talk only about auth module) salt is not 'public' - this is good. Hacker (with our database) first (before brute force attack) have to get salts for all passwords. Becouse salt was injected in hash using one pattern (for example 'salt_pattern' => '1, 5, 7, 10, 15, 22, 23, 26, 30, 34';) breaking this pattern allow him to get salts from all passwords. So it is important to create difficult salt_pattern.

I just suggest new, better, salt pattern method, thats all!

#9 Updated by Steven G. almost 4 years ago

Jeremy Bush wrote:

Steven G. wrote:

What? But, hacker does have salt, salt is not a secret. :)

The salt is a secret. What would be the point if it was public? ;)

In auth's case, each hash has a unique random salt.

Let's assume your user table contains the (computed) hashed password and salt in one column called "verify", and salt in another called "salt". All communication is done though TSL or SSL. If you don't have the option you are doomed. We'll assume that Alice is the user, Bob is the server, and Eve (Evesdroper) is the intruder. So A, B, and E. As with modeling of a typical security system we'll assume the salt is fresh on registration and that E knows everything including implementation and anything he can deduce from the environment. The only thing E can not do is break cryptographically strong algorithms.

I'll use the simple modeling pattern for the algorithm; you might or might not have seen this before so I'll explain it briefly: "A!B:" = A sends B, "B?A:" = B receives from A, also this:

...means I've used A's public key (asymmetric cryptosystem) to encrypt A's identity, B's identity (ie. nonces), a symmetric key between A and B, and I provided a timestamp (fresh() = its guaranteed to be unique/new). Disclaimer: don't look at that as a certificate.

Assuming TSL

If you didn't have TSL
- at step 1 Eve can intercept the password
- if you did something like send the salt, then Eve would just intercept both

In both cases Eve doesn't have to compute nothing, here's a example of the salt version:

So why use salts? The general good practice is to store your users passwords as hashes. This both makes managing them easier; no more password length problems, particularly now when when people are finally learning (finally) special characters don't make your passwords stronger, length does! This used to be fine, for a while. However modern storage has exploded. While computationally it's hard to compute all the hashes it's easier if you store them. So as I mention in another thread things like rainbow tables have emerged that can just break them instantly. To solve this you use a "salt" which basically randomizes the result. So it's still the same amount of computations, same collision, just that now someone can't just look the hash:

07e547d9 586f6a73 f73fbac0 435ed769 51218fb7 d0c8d788 a309d785 436bbb64
2e93a252 a954f239 12547d1e 8a3b5ed6 e1bfd709 7821233f a0538f3d b854fee6 

...and say: oh that's "The quick brown fox jumps over the lazy dog".

As anticlimactic as it sounds: yes, that's all they are good for. But you should of course definitely use them; database backups do get stolen pretty often.

So anyway, in conclusion the salt is not a secret, at most it's a nonce. Unless you have some secure alternative communication algorithm in mind that uses the same terminology there intruder will definitely know your salts when he steals your database/backup.

#10 Updated by Jeremy Bush almost 4 years ago

So anyway, in conclusion the salt is not a secret

Again, the salt is a secret. Just because it's placed in the hash doesn't mean it's not secret. The secret positions make the salt a secret.

I just suggest new, better, salt pattern method, thats all!

If someone wants to suggest a better salting algorithm, please provide a new algorithm on github ;)

#11 Updated by Steven G. almost 4 years ago

Jeremy Bush wrote:

So anyway, in conclusion the salt is not a secret

Again, the salt is a secret. Just because it's placed in the hash doesn't mean it's not secret. The secret positions make the salt a secret.

The implementation is not secret. Thus, the position is not secret. The intruder will only ever steal your database (the other scenarios imply you're doing something else really wrong). The database contains the salt and user verify hash in plain view, how does that make the salt secret? :)

Also, just use a keyed hash function with the salt as key, that's what they are for.

#12 Updated by Isaiah DeRose-Wilson almost 4 years ago

Steven G. wrote:

The implementation is not secret. Thus, the position is not secret. The intruder will only ever steal your database (the other scenarios imply you're doing something else really wrong). The database contains the salt and user verify hash in plain view, how does that make the salt secret? :)

But it doesn't contain the salt in plain view, you have no idea where the salt is stored in the hash. With just the database you won't be able to find the salt value (or the real hash value). You need to know what offsets the salt is stored at to find the these values, so knowing the salt offsets stored in your auth config is required to figure out the salt value. Knowing the implementation doesn't make any difference...

#13 Updated by Steven G. almost 4 years ago

Isaiah DeRose-Wilson wrote:

Steven G. wrote:

The implementation is not secret. Thus, the position is not secret. The intruder will only ever steal your database (the other scenarios imply you're doing something else really wrong). The database contains the salt and user verify hash in plain view, how does that make the salt secret? :)

But it doesn't contain the salt in plain view, you have no idea where the salt is stored in the hash. With just the database you won't be able to find the salt value (or the real hash value). You need to know what offsets the salt is stored at to find the these values, so knowing the salt offsets stored in your auth config is required to figure out the salt value. Knowing the implementation doesn't make any difference...

The salt is in plain view. The application has to re-hash your password with your salt to confirm it's equal to the value it has stored. What you're referring to is not password salt, but a extra secret in the code. That is irrelevant, the salt is still not secret because of it. That technique is only useful for when "you know" you're database was stolen; there's no such gurantee.

If you dispose of the salt after use, you can't verify your users.

If you are simply generating a salt one-time, or have it in your config file then that's worse! Each user needs to have their own personal salt, otherwise there's no point. You are are a little safer but still vulnerable to a rainbow table attack.
  • if they have to do it per user then the process involved is finding the actual password of that user (needle in a haystack problem),
  • if they can do it on mass then they will likely end up with at the least some of your users passwords (white and black grain sorting problem).

#14 Updated by Woody Gilk almost 4 years ago

OP: How could you possibly have salt injection? You would have to store the injected offsets somewhere in plaintext.

Each user needs to have their own personal salt, otherwise there's no point.

This is how it works currently, except that the salts can be regenerated when the hashing is done, if plaintext is available.

It is true that the salt is "visible but hidden", hidden in plain view. What makes this implementation secure is the secret of what offsets the salt exists at. Without knowing the offsets, you cannot crack a hashed password. This method is also immune to rainbow table attacks because every salt is unique per user.

This issue has a lot of FUD and random thoughts all over it, but I don't see any real security issues here.

#15 Updated by Tomek Rychlik almost 4 years ago

Let's summary:

1) I full agree with Jeremy, Isaiah and Woody. I think Steven dont understand us.

2) I think current salt system with offset is VERY GOOD! It protects against:
- rainbow tables attack (random salt for every password)
- brute and dictionary attack (salt is secret becouse we use offsets)

3) I just suggest to improve offset idea algorithm.
Its important becouse hacker to get salt from stolen hash needs to perform all possibilities to extract salt from the hash (same way like find_salt() method do, but he have to check all offset posibilites). In current !!!ORDERED!!! offset, he has to perform:

(n!)/((n-k!)(k!)) checks. Where n = length of hash (in sha1 = 40), k = length od salt (offsets)

For example, using sha1, and 5 offset length : (40!)/((40!-5!)5!) = 658008 combinations

If we improve offset to be !!!NOT ORDERED AND REPEAT ARE ALLOWDED!!! the same example, hacker needs to perform 40^5 = 102400000 combinations!

Why? Becouse offset could be even this: 'salt_pattern' => '20, 20, 5, 1, 4'; !!!NOT ORDERED!!! EVEN REPEAT ARE ALLOWDED!!!

If we use offset length equal 10 (default) then in my new offset method hacker have to check all 40^10 = 10485760000000000 combinations

I think its much more secure, dont you think?

To be clearly understood:

NOW:
'salt_pattern' => '1,3,5,7,9,20';
salt = SECRET (offcourse its random for all passwords)
hash = sha1(salt.hash) = 9e9203d3e345b469ed688a995e58be6a
hash + salt = 9 'S' e9 'E' 20 ' C' 3d 'R' 3e 'E' 345b469ed 'T' 688a995e58be6a

FUTURE :)
'salt_pattern' => '5,5,1,1,9,20';
salt = SECRET (offcourse its random for all passwords)
hash = sha1(salt.hash) = 9e9203d3e345b469ed688a995e58be6a
hash + salt = 9 'CR' e920 'SE' 3d3e 'E' 345b469ed68 'T' 8a995e58be6a

I implement this algoritm and show here, soon...

Sory for my english, regards!

#16 Updated by Steven G. almost 4 years ago

Woody Gilk wrote:

OP: How could you possibly have salt injection? You would have to store the injected offsets somewhere in plaintext.

Each user needs to have their own personal salt, otherwise there's no point.

This is how it works currently, except that the salts can be regenerated when the hashing is done, if plaintext is available.

It just sunk in you were actually doing something similar to what he's suggested... damn should have looked closer in that modules/ folder. In the light of this "revelation" I think what he's asking for is each time someone downloads Kohana it should come with a random value there not '1, 3, 5, 9, 14, 15, 20, 21, 28, 30'... personally, I would just make it NULL and have the system fail with critical exception if anyone tries to use it with NULL :) ie. doesn't customize the configuration. This is also work if people just copy paste Kohana around, since setting it is forced on you each time.

It is true that the salt is "visible but hidden", hidden in plain view. What makes this implementation secure is the secret of what offsets the salt exists at. Without knowing the offsets, you cannot crack a hashed password. This method is also immune to rainbow table attacks because every salt is unique per user.

If I understand this correctly... you are doing this: hash_part123 .. salt .. hash_part456 .. salt .. hash789 etc. I've already mentioned in my first post how I've never heard of any official documents of a system like this. As far as I know from implementing hash algorythms, because of the steps envolved, a simple thing like this: hash(salt+hash(pass)) is pretty much equivalent in security to any other combination. If anything any combination that doesn't start with the salt is likely less secure.

But, like usual I'm not good with words:
  • consider a system where the configuration has been altered, so it's not '1,3,5,7,9,20'
  • intruder Eve registers in the system
  • Eve then steals the database
  • Eve now has a plain text version of the password, the salt of "her" password, and of course the resulting hash stored next to the salt.
  • Eve downloads a version of Kohana (just in case anyone was fooling themselves with implementation secrecy)
  • Given we're dealing with at most a few numbers, hence a few bits, Eve simply does a simple brute force attack on all the possible combinations
  • Eve now knows the offsets

I don't have a exact number to give you on how much that brute force attack would take, but it's pretty obvious it's nowhere near secure. If instead you were using a system where the key was a actual secret (hashed), then cracking her own password would be just as hard as that of any other user.

Also, there's no such thing as "unbreakable system" it's all in computing power and for how much time the data needs to stay secure. :)

Anyway I've said enough, and I think my presence here is simply preventing code from being written (if anything) so I'll leave this as my last comment to the issue. The module in question (now that I know we're talking about it) is also of little interest to me; so it wouldn't be fair for me to drag the topic any further.

#17 Updated by Matt Button almost 4 years ago

It just sunk in you were actually doing something similar to what he's suggested... damn should have looked closer in that modules/ folder. In the light of this "revelation" I think what he's asking for is each time someone downloads Kohana it should come with a random value there not '1, 3, 5, 9, 14, 15, 20, 21, 28, 30'... personally, I would just make it NULL and have the system fail with critical exception if anyone tries to use it with NULL :) ie. doesn't customize the configuration. This is also work if people just copy paste Kohana around, since setting it is forced on you each time.

At the moment if I have a hash asdfghjkl, salt 12345 and an offset pattern of 1,3,5,8,10 then the result will be:

a1s2df3gh4j5

The current implementation requires that the salt offsets be placed in ascending order, I believe Tomek's asking if they can be placed in a random order e.g. 1,5,3,15,9

If I understand this correctly... you are doing this: hash_part123 .. salt .. hash_part456 .. salt .. hash789 etc.

No, we hashing password + salt, then hiding the salt at specific points within the generated hash.

But, like usual I'm not good with words:
  • consider a system where the configuration has been altered, so it's not '1,3,5,7,9,20'
  • intruder Eve registers in the system
  • Eve then steals the database
  • Eve now has a plain text version of the password, the salt of "her" password, and of course the resulting hash stored next to the salt.
  • Eve downloads a version of Kohana (just in case anyone was fooling themselves with implementation secrecy)
  • Given we're dealing with at most a few numbers, hence a few bits, Eve simply does a simple brute force attack on all the possible combinations
  • Eve now knows the offsets

Considering that every character in the resultant hash could be either part of the sha hash or the salt, you'd have to try multiple combinations (worst case approximately 658,000 according to tomek's math) in order to find the salt offset.

Tomek's suggestion would require them to spend more time finding the salt.

If instead you were using a system where the key was a actual secret (hashed), then cracking her own password would be just as hard as that of any other user.

I'm not quite sure how what you're talking about would work, care to elaborate?

#18 Updated by Woody Gilk almost 4 years ago

each time someone downloads Kohana it should come with a random value

How exactly would that be possible? The download is not generated for every download.

#19 Updated by Steven G. almost 4 years ago

@ Woody Gilk: Put a comment then have a script look for the line where that comment is. After finding the line, the script would take it and do a replace on the secret. After the script is done the framework is archived and sent to the user.

Like I said I think just forcing them to set it by defaulting to NULL and breaking on NULL is probably better since it works even if they get it from the trunk.

Matt Button wrote:

It just sunk in you were actually doing something similar to what he's suggested... damn should have looked closer in that modules/ folder. In the light of this "revelation" I think what he's asking for is each time someone downloads Kohana it should come with a random value there not '1, 3, 5, 9, 14, 15, 20, 21, 28, 30'... personally, I would just make it NULL and have the system fail with critical exception if anyone tries to use it with NULL :) ie. doesn't customize the configuration. This is also work if people just copy paste Kohana around, since setting it is forced on you each time.

At the moment if I have a hash asdfghjkl, salt 12345 and an offset pattern of 1,3,5,8,10 then the result will be:

a1s2df3gh4j5

The current implementation requires that the salt offsets be placed in ascending order, I believe Tomek's asking if they can be placed in a random order e.g. 1,5,3,15,9

If I understand this correctly... you are doing this: hash_part123 .. salt .. hash_part456 .. salt .. hash789 etc.

No, we hashing password + salt, then hiding the salt at specific points within the generated hash.

But, like usual I'm not good with words:
  • consider a system where the configuration has been altered, so it's not '1,3,5,7,9,20'
  • intruder Eve registers in the system
  • Eve then steals the database
  • Eve now has a plain text version of the password, the salt of "her" password, and of course the resulting hash stored next to the salt.
  • Eve downloads a version of Kohana (just in case anyone was fooling themselves with implementation secrecy)
  • Given we're dealing with at most a few numbers, hence a few bits, Eve simply does a simple brute force attack on all the possible combinations
  • Eve now knows the offsets

Considering that every character in the resultant hash could be either part of the sha hash or the salt, you'd have to try multiple combinations (worst case approximately 658,000 according to tomek's math) in order to find the salt offset.

Tomek's suggestion would require them to spend more time finding the salt.

I've gone though the code and dumped it all into a function (replaced method calls with actual code). After a little more cryptanalysis I found it doesn't even take brute force to break this: http://pastie.org/1093540 Simple output:

The quick brown fox jumped over the lazy dog. (Eve's pass) 
492793507e (Eve's salt) 
8c81634b0ceecdc067558953f371ae64d7d15b65 (Eve's hash) 
84c8916234b07ceecd9c306755580953f3717aee64d7d15b65 (Eve's passhash) 

found : 1 3 5 9 14 15 20 21 28 30  
  was : 1 3 5 9 14 15 20 21 28 30 

You don't even need a algorythm for this, a 12-year-old given just the hash before and after your injection:

8c81634b0ceecdc067558953f371ae64d7d15b65 (Eve's hash) 
84c8916234b07ceecd9c306755580953f3717aee64d7d15b65 (Eve's passhash)

...could probably guess/deduce your salt and your injection pattern in 10min.

If I missed something please just correct me, but regarding the probabilities: 658,000 is aprox 2^19 which is very weak, from a cryptographic stand point. Consider how even md5 is 2^128.

If instead you were using a system where the key was a actual secret (hashed), then cracking her own password would be just as hard as that of any other user.

I'm not quite sure how what you're talking about would work, care to elaborate?

Break this:

hash_hmac('sha512', hash_hmac('sha512',$password,$salt), $api_secret);

1.34078079 × 10^154 possible values. :)

PHP docs: http://us2.php.net/manual/en/function.hash-hmac.php
IETF: http://www.ietf.org/rfc/rfc2104.txt
NIST: http://csrc.nist.gov/publications/fips/fips198/fips-198a.pdf

#20 Updated by Jeremy Bush almost 4 years ago

I'm not sure your example is completely accurate. You need to take a pre-existing hash (with a previously defined, unknown salt value), and try and find the salt positions from that. You can't generate the hash in the same cracking algorithm. In your case, you are storing the pre-injected hash, which the cracker will never have access to.

I attempted to do this by modifying your "Cracking" code, and failed to do so (since the "cracker" will never know the $hash_store value you use). I just woke up, so I'm not saying it's impossible, however ;)

Try this one: e6bc1d43a61b16082c2a622d77326295ab929e5b85c6db10c6

With that being said, I do think there is value in using hmac hashing functions as opposed to our homegrown method we use.

#21 Updated by Dos Moonen almost 4 years ago

Somehow I have this feeling I am going to make a fool out of myself, but who cares!

a 12-year-old given just the hash before and after your injection could probably guess/deduce your salt and your injection pattern in 10min.

Sure, but who solves the chicken or the egg kind of problem of finding the "hash before" for which you need to know the injection pattern, and how long would he/she/it take to find it?

Anyway, after Tomek Rychlik's last post I saw creating the same algorithm as a fun little challenge.
Here is what i came up with:
http://github.com/Darsstar/auth/commit/286e62cba3d96aa2657e9941ae8fa6ae80fd8a0d (ok, this is just a little improvement for the current system, shall I make a pull request?)
http://github.com/Darsstar/auth/commit/47b6306c2716a94b44f41b0ac2c2a4fae5b5aaba

It will generate the exact same hash (9CRe920SE3d3eE345b469ed68T8a995e58be6a) as he wanted.

I hope this somehow helps somebody.

#22 Updated by Steven G. almost 4 years ago

Jeremy Bush wrote:

I'm not sure your example is completely accurate. You need to take a pre-existing hash (with a previously defined, unknown salt value), and try and find the salt positions from that. You can't generate the hash in the same cracking algorithm. In your case, you are storing the pre-injected hash, which the cracker will never have access to.

I attempted to do this by modifying your "Cracking" code, and failed to do so (since the "cracker" will never know the $hash_store value you use). I just woke up, so I'm not saying it's impossible, however ;)

Try this one: e6bc1d43a61b16082c2a622d77326295ab929e5b85c6db10c6

Nope. Like I said it's Eves - the attackers - hash! She knows the hash because it's HER password, and it's her password because its HER account(s). A hash function is guaranteed to be the same every time, so no it's not like you're going to have "different" hash. :)

Or I might have missed something in what you're saying, if so simply point it out.

#23 Updated by Steven G. almost 4 years ago

Dos Moonen wrote:

a 12-year-old given just the hash before and after your injection could probably guess/deduce your salt and your injection pattern in 10min.

Sure, but who solves the chicken or the egg kind of problem of finding the "hash before" for which you need to know the injection pattern, and how long would he/she/it take to find it?

This is the example I gave above:

8c81634b0ceecdc067558953f371ae64d7d15b65 (Eve's hash) 
84c8916234b07ceecd9c306755580953f3717aee64d7d15b65 (Eve's passhash)

You solve it like this:

  • is 8 in the hash? yes, our string is 8
  • is 4 in the hash? no, our string is 8, salt is 4, offsets are 1
  • is c8 in the hash? yes, our string is 8c8, salt is 4, offsets are 1
  • is 9 in the hash? no, our string is 8c8, salt is 49, offsets are 1,3
  • is 16 in the hash? yes, our string is 8c816, salt is 49, offsets are 1,3
  • is 2 in the hash? no, our string is 8c816, salt is 492, offsets are 1,3,5
    etc.

Not so hard is it. :)

#24 Updated by Dos Moonen almost 4 years ago

Once you have the (uninjected) hash of the salt+pass, yes.
But that one will not get saved anywhere.
So to get the salt so you can create that uninjected hash you need the uninjected hash, and to get that you need to know the salt pattern, from which you can deduce the salt so you can remove it from the injected hash to get the uninjected hash so you can get the salt...
Does that sound a bit like the chicken or the egg problem?

#25 Updated by Jeremy Bush almost 4 years ago

Steven G. wrote:

A hash function is guaranteed to be the same every time, so no it's not like you're going to have "different" hash. :)

No, it's not. I still don't think you know how our hashing method works. Unless you provide the salt value, you will get a different hash every time (because the random salt will be different every time). It's basically impossible for an attacker to know their salt unless they know the salt pattern (which is secret [or they successfully break the hash by bruteforcing the salt positions]).

A user or attacker will never know their "pre-salt-injected" hash. This is all you know:

e6bc1d43a61b16082c2a622d77326295ab929e5b85c6db10c6

Where is the salt in that hash? If you can tell me that, I will concede this hash method is completely insecure.

And again, I'm conceding that we should use a hmac method instead of our method in 3.1.

#26 Updated by Steven G. almost 4 years ago

@ Dos Moonen: I don't know what you are trying to tell me with this "chiken or the egg problem". As far as I know the egg came before the chicken because the first chicken came from a egg. The egg with the first chicken was layed by what you want to consider different enough to be a non-chicken. As far as I know from biology and geography it should have been some relative of the junglefowl but you can think of dinosaurs if you really want it to be really different.

Jeremy Bush wrote:

And again, I'm conceding that we should use a hmac method instead of our method in 3.1.

I'm not debating; I've stopped debating over this a few posts back. I'm simply answering posts who are directly addressed to me. :) What you do with it is your business.

Steven G. wrote:

A hash function is guaranteed to be the same every time, so no it's not like you're going to have "different" hash. :)

No, it's not. I still don't think you know how our hashing method works. Unless you provide the salt value, you will get a different hash every time (because the random salt will be different every time). It's basically impossible for an attacker to know their salt unless they know the salt pattern (which is secret [or they successfully break the hash by bruteforcing the salt positions]).

Looking database sql file I think I understand now what you mean. Sorry, my bad. Indeed the previous algorithm would not work given this.

A user or attacker will never know their "pre-salt-injected" hash. This is all you know:

e6bc1d43a61b16082c2a622d77326295ab929e5b85c6db10c6

Where is the salt in that hash? If you can tell me that, I will concede this hash method is completely insecure.

The method I suggested to break it involves registering prior to the attack. So I do know a extra part of it: the plain text version of the password; since I will be attacking my own account in pursuit of finding your pattern.

Though, part of the reason why I can't deduce anything is also another small security liability you have. As far as I know salts are suppose to be used directly, not hashed. In your case you are generating a salt by hashing, and thus masking the salt inside the hash. Technically the salt (at worst) should have been encoded in base64 or something and should also be larger then it is now. You should also consider just using the hash directly and not the pretty hex version as it may be more efficient for both storage and speed. Of course at the moment the pretty hex version is required for injection to work. :)

Regardless, given the text version of the password and the final salted/injected hash, I can deduce your scheme though brute force fairly easily. I've created a simple brute force C++ console app (sha1: http://code.google.com/p/smallsha1/) to brute force your algorithm. Here's a copy of the commands used and result (type --help for descriptions):

g++ (tdm-1) 4.5.0

g++ -o ICE.exe -I. InjectionCrackerEve.cpp sha1.cpp -Wall

Command: ICE --verbosity 20000 --minstep 1 --maxstep 10 --textpass "The quick brown fox jumped over the lazy dog." --passhash ecb8c446769175432ca89a988644ec78b8ddd9a13b956ce5e7
 salt: cc67a94ed1
 pattern: 1, 3, 5, 9, 14, 15, 20, 21, 26, 30
 Time: 617.00 seconds

617 seconds is approximately 10 minutes.

I estimate (more like guess based on a few tests) that in the worst possible case it would take (on a average single core 32bit processor home computer) something along the lines of 2 days. Which from a security point of view is weak, very weak. Most cryptographic algorithms are considered secure when they take tens if not hundreds of years, and that's using super computers!

I should also note my algorithm simply uses backtracking (since it was the most straight forward) but you could probably use some iterative method derived from a sort of gray code algorithm and take advantage of extra manipulation. If you make it iterative you can set the start pattern. If if you do that then you can split the workload on different computers or simply different cores on a multi-core system. I should also note that the higher the values the faster the algorithm becomes since things like 5,6,1,2,3 are invalid. You can think of it as having fewer numbers to check the higher the leading ones are.

#27 Updated by Mathew Davies almost 4 years ago

This issue is not low priority!

I've been watching this issue for a number of days and Steven G is totally correct as far as I'm concerned.

The salt pattern is essentially useless; Take a day or two to crack the random salt pattern and then you can start attacking the passwords the traditional way (rainbow tables or brute-force). I propose Kohana release a security upgrade (they weren't too keen when I suggested it) where a new algorithm is put along side the old one. This way the developer can develop an upgrade process; Here's an example:

1. User logs on.
2. Hash the password with new algorithm and check it against the stored password.
3. If it doesn't match. Hash the password against the old algorithm, if it matches then upgrade it.
4. Fixed.

Transparent and easy to do.

What do you think? I can create a patch if the demand exists.

#28 Updated by Tomek Rychlik almost 4 years ago

Steven G you are RIGHT! Your post is important! Your program show us how current salt pattern is easy to break (with knowledge of plain text version of the password, i agree its is easy to make).

BUT we are talking in this post about NEW salt pattern! PLEASE TRY BREAK MY NEW SALT PATTERN! You used sha1 and 10 length salt pattern. Your program (in the worst case) had to perform (40!)/(10!*30!) = 847660528 tries. You said it could take 2 days.

Ok. But in my new pattern you need to perform (in the worst case) 40^10 = 10485760000000000 checks. It is 12370235 times MORE!!! 2 days * 12370235 = 67782 years.

If it is still not enough, whe can use sha-256 or sha-512 and 20 length salt pattern. Then it takes more than the age of the universe.

Why you dont listen to me?

#29 Updated by Steven G. almost 4 years ago

Tomek Rychlik wrote:

Steven G you are RIGHT! Your post is important! Your program show us how current salt pattern is easy to break (with knowledge of plain text version of the password, i agree its is easy to make).

BUT we are talking in this post about NEW salt pattern! PLEASE TRY BREAK MY NEW SALT PATTERN! You used sha1 and 10 length salt pattern. Your program (in the worst case) had to perform (40!)/(10!*30!) = 847660528 tries. You said it could take 2 days.

Ok. But in my new pattern you need to perform (in the worst case) 40^10 = 10485760000000000 checks. It is 12370235 times MORE!!! 2 days * 12370235 = 67782 years.

If it is still not enough, whe can use sha-256 or sha-512 and 20 length salt pattern. Then it takes more than the age of the universe.

Why you dont listen to me?

2 days = time on a consumer piece of junk; no distributed system no nothing. The algorythm I made also uses backtracking; which is slow and typically to be avoided.

10485760000000000 = 1.048576 × 10^16 = bubble gum for todays super computers sadly

Consider how md5 is 2^128 = 3.40282367 × 10^38 combination.
Do you think it took them thousand of years to generate Rainbow Tables ;)

I've also mentioned how there are (standardized, certified and verified) alternatives that even government agencies use for the secret and top secret documents. I gave the following as a simple example of using certified algorythms: hash_hmac('sha512', hash_hmac('sha512',$password,$salt), $api_secret); It has 1.34078079 × 10^154 possible combination. Why not use this?

A alternative might be to have many security variants coexist in it, and that might be the ideal compromise.

#30 Updated by Jeremy Bush almost 4 years ago

Steven G. wrote:

I gave the following as a simple example of using certified algorythms: hash_hmac('sha512', hash_hmac('sha512',$password,$salt), $api_secret); It has 1.34078079 × 10^154 possible combination. Why not use this?

This is about the only useful thing to come out of all of this ;)

http://github.com/kohana/auth/tree/feature/3163-hmac-auth

But again, something like this cannot be added to the core distro until 3.1. It's possible to combine the old method and provide some upgrade path to keep the api the same, but that's out of my scope right now.

If you have more to add, just fork the repo and do it :)

#31 Updated by Woody Gilk almost 4 years ago

  • Category set to Core
  • Status changed from New to Review
  • Assignee set to Woody Gilk

The method I suggested to break it involves registering prior to the attack. So I do know a extra part of it: the plain text version of the password; since I will be attacking my own account in pursuit of finding your pattern.

This will not help anything. Here's why:

1. The plaintext password is hashed with hash($plaintext.$salt).
2. The salt is inserted into the password using the user-configured offsets.

Now tell me: when you have a plaintext password, how would you be able to find the salt?

Think about this. The salt is randomly generated every time the password is changed. Every single time, you have a random salt, which is being combined with the plaintext to generate a hash, then the salt is inserted into that hash at offsets that you do not know. The salt uses the same characters as the hash, so you cannot identify them. There are no constants from hash to hash, because salt is randomized.

Now, it do concur that this method does not provide the highest possible entropy, but it does provide an extremely secure method of hashing. Even if you could get all of the password hashes, breaking them without guessing, or stealing, the salt offset is near 100%. If someone gets login to your server, then you are screwed. But stealing the database will not break this security.

Unless you can tell me what the salt of the following hash is, or provide a step by step explanation for how to find it, I am going to close this issue as invalid:

7d8bd81ea9a35082e544095be10acabc6ad7412c0838cafac7

This was a very interesting discussion, thanks. :) And using hmac_sha1 for should be a separate issue, this is a little bit much to wade through.

#32 Updated by Mathew Davies almost 4 years ago

Now tell me: when you have a plaintext password, how would you be able to find the salt?

Woody

He's registering on the website prior to stealing your database. He's going to have the plain text password (which he signed up with!) and the hash that has been stored in the database. Since the salt pattern in Kohana can be cracked quite quickly (as proven), it wont take long for him to use brute force to find out what that is.

Once he has the pattern, it's a case of running a dictionary through the same code found in Kohana.

I hope you understand that.

PS: Issue is certainly not invalid!

#33 Updated by Woody Gilk almost 4 years ago

  • Status changed from Review to Assigned
  • Priority changed from Low to Urgent
  • Target version set to v3.0.8

Upon more careful reading, I see you talk about registering first. Now this makes a lot more sense.

So, this needs to be a security fix, which entails breaking the API. I have no issue with that.

#34 Updated by Yahasana . almost 4 years ago

Why not this phpass ?

#35 Updated by Woody Gilk almost 4 years ago

  • Target version changed from v3.0.8 to v3.0.9

#36 Updated by Kevin D almost 4 years ago

Maybe i'm missing something, but since when is it a problem when someone trying to find out the passwords knows the salt?

The main purpose of a salt is to lengthen the password string, making it harder to use rainbow tables, because the hashes in the rainbow table are made up of shorter strings. The bigger the string, the lesser the chance the string is in a rainbow table.

Or is the salt not included in the hash, but only injected afterwards? Then this is indeed a security failure.

#37 Updated by Mathew Davies almost 4 years ago

Kevin

You're right about the rainbow tables, those are still useless. The problem is it's still vulnerable to brute force/dictionary attacks, which it shouldn't be. They'll run the dictionary word or w/e through Kohana's salting algorithm with the stolen salt and do a comparison. This will make cracking the passwords take longer than using a rainbow table, but Kohana's Auth module needs renovating.

Or is the salt not included in the hash, but only injected afterwards?

The salt is in the hash.

#38 Updated by Isaiah DeRose-Wilson almost 4 years ago

Kevin Daudt wrote:

Maybe i'm missing something, but since when is it a problem when someone trying to find out the passwords knows the salt?

It's not a huge problem. It just makes the putting the salt at random offsets in the hash pointless and using something like hash_hmac() would probably be a better way to handle this.

The main purpose of a salt is to lengthen the password string, making it harder to use rainbow tables, because the hashes in the rainbow table are made up of shorter strings. The bigger the string, the lesser the chance the string is in a rainbow table.

Salting and password stretching are really two different things. Using custom salt values just makes sure nobody can use an existing rainbow table to easily figure out your passwords. Password stretching is normally used in addition to salting to make brute force attempts take longer.

#39 Updated by Jeremy Bush almost 4 years ago

I've implemented this change in my fork: http://github.com/zombor/auth/commit/1b600927e8c6d81903fffe57fcea655a75253e32

I've not merged it to the mainline branch, because it's a backwards incompatible change.

#40 Updated by Jeremy Bush almost 4 years ago

  • Status changed from Assigned to Closed
  • Resolution set to fixed

This is fixed in the 3.1 branch: http://github.com/kohana/auth/tree/3.1.x

#41 Updated by Jeremy Bush over 3 years ago

  • Target version changed from v3.0.9 to v3.1.0

Also available in: Atom PDF