Page 1 of 3

Advanced Hashing

Posted: Tue Feb 03, 2009 9:04 am
by exesteam
hi all

im new to this security area so i wanted to ask here first before applying the changes to my website.

so the thing is that i am using hashing for passwords. instead of simply hashing typically, i decided to make it even better and use this:

Code: Select all

sha1($msg).md5($msg);
this way I get longer hash and better security.

just wanted to share my method.

Re: Advanced Hashing

Posted: Tue Feb 03, 2009 12:46 pm
by Hannes2k
Hi,
yeah you get a longer hash, but you do net get better security. Why should this be better? The attacker just have to read the last 32 hexchars and then try to break the md5 hash of your hash.

To increase the security of the hash, you should write:
sha1(sha1($pw).md5($pw));

Or use the Improved Hash Algorithm Class, so you get an easy to use salt and key strengthening method.

Re: Advanced Hashing

Posted: Tue Feb 03, 2009 1:05 pm
by kaisellgren
Hannes2k wrote:Hi,
yeah you get a longer hash, but you do net get better security. Why should this be better? The attacker just have to read the last 32 hexchars and then try to break the md5 hash of your hash.

To increase the security of the hash, you should write:
sha1(sha1($pw).md5($pw));

Or use the Improved Hash Algorithm Class, so you get an easy to use salt and key strengthening method.
You definetly should not mess with hashing algorithms. Whether you use multiple hashes, or alter the hash value (output), it is rarely a good idea (rare = if you happen to be an expert).

Re: Advanced Hashing

Posted: Tue Feb 03, 2009 1:32 pm
by Apollo
exesteam, you're creating a false sense of security.

You are really a lot better off by using

Code: Select all

hash( 'sha512' , $msg.'RandomSalt_bK3R4Nz1dQse25fmTyB9MeQn5L4vPz' );

Re: Advanced Hashing

Posted: Fri Feb 13, 2009 12:10 pm
by josh
Messing with hashes increases the probability a cracker will find a collision

Re: Advanced Hashing

Posted: Fri Feb 13, 2009 12:30 pm
by kaisellgren
josh wrote:Messing with hashes increases the probability a cracker will find a collision
Indeed. The hashing functions have been created and designed to prevent attacks. When you are messing with them, you very easily break these built-in protections.

Re: Advanced Hashing

Posted: Fri Feb 13, 2009 1:25 pm
by Mordred
With web apps the treat model is hardly collisions. They, even for "broken" hashes require quite significant firepower.

If we're to find problems with hash misuse it would be in improperly storing them in databases (which, when stolen, could be subject to offline attacks - see my old hashing article) and (to a much lesser degree) misusing them as a MAC (in short - use HMAC, not your own scheme)

Re: Advanced Hashing

Posted: Fri Feb 13, 2009 2:06 pm
by josh
I was referring to offline attacks, but as far as webapps being immune to network brute forcing either I don't know about that, a lot of data centers offer unlimited usage of gigabit backbones between their customers, that's why you need to lock an account / IP after repeated failures, but you still shouldn't screw with the hash other then to add a salt _before_ you pass it to a hash function, and pass it to exactly 1 hash function, no more no less.

Re: Advanced Hashing

Posted: Fri Feb 13, 2009 2:14 pm
by kaisellgren
SHA-2 among with other *newer* and stronger hash families are enough to prevent any attacks. There is zero need to complicate hashing by altering it or running it through series of string and data manipulations. Many people are still using SHA-1, however, so they think they are safer by manipulating their hashes (may it be concatenating something, double hashing, whatever). Due to birthday paradox, one can expect your SHA-1'ed data to be broken after 2^80 evaluations. However, recent researches clearly state that it is possible to break by running the compressor only 2^35 times (http://www.iaik.tugraz.at/content/resea ... iption.php). If you are to manipulate your hashes, it will be even faster to crack your hashes.

For these reasons, I would say that it does matter how you use your hashes. You do not need that much firepower after all, because if you have got a full database access, for instance, or even a read-only one, you can pretty quickly offline crack the hash with a CUDA enabled GPU just like what I did with my friend's hash.

In spite of everything, we are after security and strength, aren't we?

Re: Advanced Hashing

Posted: Fri Feb 13, 2009 2:23 pm
by kaisellgren
josh wrote:but you still shouldn't screw with the hash other then to add a salt _before_ you pass it to a hash function, and pass it to exactly 1 hash function, no more no less.
Indeed. This is the right way to use hashes for passwords. To correct your sentence, you are not screwing with a hash if you are passing data into it. You are screwing with the hash if you are doing anything with the hash value. Hash value is the output of the hash. A proper way to hash passwords is to type HASH(DATA) and that's it. You can do whatever you want to do with DATA, but under any circumstances are you not allowed to alter the hash value. You can not double hash, you can not use PHP's string functions on it, and so forth. Well, basically you could use strrev(), for instance, because it does not alter the hash value, but the contextual presentation of it, which can be restored back into the original form.

Re: Advanced Hashing

Posted: Sat Feb 14, 2009 5:51 am
by Mordred
That's a whole lot of misconceptions here.
Josh wrote:I was referring to offline attacks
Offline attacks do not aim for generating collisions as well. Collisions matter when you use hashes for MAC/signatures.
Josh wrote:...but as far as webapps being immune to network brute forcing either..
I haven't said webapps are immune to online attacks (it's very much quite the opposite, heh)
The thing is, online attacks are not related to password storage at all. They are application-level attacks that work (or don't work) irregardless of whether you hash passwords on the backend or not, whether you use salts or not, and whether you actually hardcode them in your code or not.

Here's the point, distilled from all refutals above:
Hashing passwords is a mitigation measure against offline attacks.
kaisellgren wrote:For these reasons, I would say that it does matter how you use your hashes. You do not need that much firepower after all, because if you have got a full database access, for instance, or even a read-only one, you can pretty quickly offline crack the hash with a CUDA enabled GPU just like what I did with my friend's hash.
Well done, but what you did was not finding a collision, but a bruteforce attack against a known value, a so-called preimage attack. Also, against strong passwords, the preimage attacks do require lots of firepower. CUDA reduces your time by a linear factor of N. Long password increase the time by a power of N.
kaisellgren wrote:SHA-2 among with other *newer* and stronger hash families are enough to prevent any attacks. There is zero need to complicate hashing by altering it or running it through series of string and data manipulations.
On the contrary, all iterative hash functions cannot be used as MAC out-of-the-box, that's why HMAC exists.
josh wrote:but you still shouldn't screw with the hash other then to add a salt _before_ you pass it to a hash function, and pass it to exactly 1 hash function, no more no less.
kaisellgren wrote:You can not double hash
There are valid reasons to hash twice or to concat two hashes. Also, the notion that double-hashing reduces hash strength is only a theoretical one (I've fallen to that once as well). In practice, the reducement of strength is by a tiny fraction of a bit, it doesn't matter (nearly) at all.

Re: Advanced Hashing

Posted: Sat Feb 14, 2009 7:30 am
by Apollo
Mordred wrote:There are valid reasons to hash twice or to concat two hashes. Also, the notion that double-hashing reduces hash strength is only a theoretical one (I've fallen to that once as well). In practice, the reducement of strength is by a tiny fraction of a bit, it doesn't matter (nearly) at all.
For two random strings s1 and s2, the probability that hash(hash(s1))==hash(hash(s2) is higher than the probability of hash(s1)==hash(s2).
Even though the difference may be small, it's generally NOT a good idea to use more than just one hash.

That being said, I don't deny that there could be valid reasons to hash twice, although I can't think of any. Out of curiousity, what would be a valid reason, other than increasing brute force time? (in which case you're MUCH better off by just using a longer hash, e.g. sha512 instead of sha256).
Mordred wrote:Offline attacks do not aim for generating collisions as well. Collisions matter when you use hashes for MAC/signatures.
:?:

Hashes are commonly used for password verification. By creating a collision, you can get a password that (regardless of whether the password is really correct) gives you unauthorized access. What's that got to do with (H)MAC/signatures?

Re: Advanced Hashing

Posted: Sat Feb 14, 2009 7:43 am
by Mordred
How much higher?

In your setup for two random values with an N bit hash, the probability for a collision between h(s1) and h(s2) is 1 / 2^(N/2). Please make a guesstimate what will be the collision probability between h(h(s1)) and h(h(s2))

Yes, there is a theoretical reducement.
No, it's not significant in any practical way.

Re: Advanced Hashing

Posted: Sat Feb 14, 2009 8:22 am
by Hannes2k
Hi,
For two random strings s1 and s2, the probability that hash(hash(s1))==hash(hash(s2) is higher than the probability of hash(s1)==hash(s2).
Thats right, that the probability for hash(hash(s1)) == hash(hash(s2)) is higher, but you need the same time to find a collosion for hash(hash()) as for a single hash()-call (when you uses a secure hash algorithm).

To calculate this is easy. Guess hash() is a realy good hash function.
The probability of hash(s1) == hash(s2) with s1 != s2 is 1 to 2^n, where n is the length of the hash.

The probability of hash(hash(s1)) == hash(hash(s2)) is 1/2^n (if hash(s1) == hash (s2)) plus (1-2^n)*1/2^n (if hash(s1) != hash(s2) but hash(hash(s1)) == hash(hash(s2))), so the probability is ~ 1 to 2^(n-1).
But you need the double time to calculate hash(hash()) than to calculate hash().


it's generally NOT a good idea to use more than just one hash.
That's wrong!
If you wanna find a string s so that hash(s) == hash(password), it's much harder to find such a string if you have called the hash function multiple times ( hash(hash(hash(...(pw)...) ), because in the most cases a bad password was selected (who uses a password with 20 random chars? No one, most users uses a password with a length of 8 and just a-z0-9) .

The reason is, that the attacker have to calculate the hash multiple times to test one possible password, so if you call the hash function e.g. 2^16 times, the attack would be slowed down by the factor of ~65 000. Instead of 1 day the attacker than needs 65 000 days.
So you add 15/16 bit extra stength to the password.

To crack a 40 bit password with a key strengthing methode (e.g. with the 2^16-th iterate of hash) is as hard to crack a 55/56 bit password which was hashed just with a single call of hash().

I can recommend this paper:
Secure Applications of Low-Entropy Keys - J. Kelsey, B. Schneier, C. Hall, and D. Wagner
see especial ยง4:
Let H() be a secure, collision-resistant one-way hash function [...]

The basic scheme works as follows:
X0 = H(Kshort; S).
For i = 1 to 2^t:
Xi = H(Xi-1).

Klong = X2^t .

We are computing the 2^t-th iterate of H().
[...]
Considering each of our design criteria in turn, we can make the following
statements of security:

Time to Compute: One crucial requirement is that naive iteration must be
the fastest way to compute X2^t (x) for random inputs x. In other words,
there must be no shortcuts available to implement H2^t (). Fortunately, we
have some theoretical results which assure us that such shortcuts can't exist,
if H has sufficient resistance to collision attacks

[...]
Theorem 1. If H() is a strongly collision-resistant hash function that admits
a naive birthday attack, then computing the i-th iterate of H requires
time at least i=2.

the theorem says that iterating the hash function 2^t times adds
at least t - 1 bits of extra "strength" to the key.

[...]

7.
The hash-based construction was shown to have the property that
a method for speeding up the exhaustive search of the low-entropy variable
translates into a significant weakness in the underlying hash function.
Of course, key stretching is no substitute for long keys. Key stretching only
reduces a short key's resistance to certain attacks.
So if you use a secure hash algorithm, this methode could be used to increase the strength of the user passwords.
If your users do not use weak passwords, a key strengthing methode is senseless, but if not...


Please see also RFC 2898 - Password-Based Cryptography Specification
5.1 PBKDF1
PBKDF1 applies a hash function, which shall be MD2 [6], MD5 [19] or
SHA-1 [18], to derive keys. The length of the derived key is bounded
by the length of the hash function output, which is 16 octets for MD2
and MD5 and 20 octets for SHA-1. PBKDF1 is compatible with the key
derivation process in PKCS #5 v1.5.

PBKDF1 is recommended only for compatibility with existing
applications since the keys it produces may not be large enough for
some applications.

PBKDF1 (P, S, c, dkLen)

Options: Hash underlying hash function

Input: P password, an octet string
S salt, an eight-octet string
c iteration count, a positive integer
dkLen intended length in octets of derived key,
a positive integer, at most 16 for MD2 or
MD5 and 20 for SHA-1

Output: DK derived key, a dkLen-octet string

Steps:

1. If dkLen > 16 for MD2 and MD5, or dkLen > 20 for SHA-1, output
"derived key too long" and stop.

2. Apply the underlying hash function Hash for c iterations to the
concatenation of the password P and the salt S, then extract
the first dkLen octets to produce a derived key DK:

T_1 = Hash (P || S) ,
T_2 = Hash (T_1) ,
...
T_c = Hash (T_{c-1}) ,
DK = Tc<0..dkLen-1>

3. Output the derived key DK.
PBKDF1
PBKDF2 is the replacement for PBKDF1, but the schema is nearly the same: PBKDF2

Re: Advanced Hashing

Posted: Sat Feb 14, 2009 9:14 am
by josh
Mordred wrote:
Josh wrote:I was referring to offline attacks
Offline attacks do not aim for generating collisions as well. Collisions matter when you use hashes for MAC/signatures.
I guess the more accurate word would have been preimage like you said, but what about http://en.wikipedia.org/wiki/Birthday_attack
"Optimally, a preimage attack on an n-bit hash function will take an order of 2n operations to be successful. On the other hand, due to the birthday attack, one can expect to find a collision between two arbitrary messages in an order of 2n/2 operations."
Hannes2k wrote: The reason is, that the attacker have to calculate the hash multiple times to test one possible password, so if you call the hash function e.g. 2^16 times, the attack would be slowed down by the factor of ~65 000. Instead of 1 day the attacker than needs 65 000 days.
So you add 15/16 bit extra stength to the password.
By re-hashing the values all you're doing is introducing more collisions. The author you linked specifically said hes using a reversible permutation ( not double hashing! ) and states he cannot make any significant claims.