Page 1 of 1

Forging SHA1 now down to O(2^52)

Posted: Fri Jun 12, 2009 3:14 am
by Apollo
Just came accross this document explaining a method with complexity O(2^52) to generate SHA1 collisions.

Still far from trivial to crack, but nonetheless, time to step up to SHA512 I guess :)

Re: Forging SHA1 now down to O(2^52)

Posted: Fri Jun 12, 2009 6:02 am
by kaisellgren
I just read it, too. :P

2^52 is low. Remember, MD5 was supposed to withstand 2^64, but this 2^52 figure is a lot lower than what MD5 (and counterparts) were supposed to withstand.

Definitely time to worry if you rely on SHA-1 unless it's irrelevant for your situation.

Re: Forging SHA1 now down to O(2^52)

Posted: Fri Jun 19, 2009 4:00 pm
by Darhazer
You should never use plain hash algorithm, no matter if it md5, sha1 or anything else. The reasons are simple:
* rainbow crack (lookup for the cache in a huge database of already generated hashes)
* even if we cannot crack, if we can get the md5 hash and we eventually can use it to login, we can use the same hash to login on another sites (because most probably the user will use the same password, hence the same hash)
You should use HMAC or something similar, for example IPB uses:
md5( md5(password) . salt )

Re: Forging SHA1 now down to O(2^52)

Posted: Sat Jun 20, 2009 5:57 am
by kaisellgren
Darhazer wrote:You should never use plain hash algorithm, no matter if it md5, sha1 or anything else.
That depends. There are situations where all you need is a simple HMAC of a message.
Darhazer wrote:* even if we cannot crack, if we can get the md5 hash and we eventually can use it to login, we can use the same hash to login on another sites
Hash is a cryptographic algorithm that accepts an arbitrary length input and turns it into a fixed-length output and due to its nature there are many uses for it - not just password hashing.
Darhazer wrote:You should use HMAC or something similar, for example IPB uses:
md5( md5(password) . salt )
I don't agree with "should". It's relative to the situation and the provided code is not "HMAC or something similar", it is no where near the HMAC structure.

Re: Forging SHA1 now down to O(2^52)

Posted: Sat Jun 20, 2009 6:31 am
by Darhazer
Wow, sorry, I meant exactly for storing passwords :oops:

Re: Forging SHA1 now down to O(2^52)

Posted: Sun Jun 21, 2009 6:52 am
by Apollo
Darhazer wrote:You should never use plain hash algorithm, no matter if it md5, sha1 or anything else. The reasons are simple:
* rainbow crack (lookup for the cache in a huge database of already generated hashes)
As you suggested in your next point, you should use salt, not hash(password) directly. Rainbow table attacks are very easy to prevent.
* even if we cannot crack, if we can get the md5 hash and we eventually can use it to login, we can use the same hash to login on another sites (because most probably the user will use the same password, hence the same hash)
You should use HMAC or something similar, for example IPB uses:
md5( md5(password) . salt )
There has been another discussion here a while ago. You cannot guarantee that md5(md5(password).salt) (or even more levels of nested hashes) is not significantly weaker than md5(password.salt). And it certainly isn't significantly stronger. Not just with md5, same goes for any hashing. The salt string is of course unique for your site, so same password on different sites = different hash.

There's really no point in double hashing, hash(password.salt) with long enough salt is the safest way to go (where, if applicable, salt is ideally salt.pepper with pepper being a 'using specific salt').

I personally use SHA512 anywhere I can, with good salts (e.g. 100+ random characters).

Re: Forging SHA1 now down to O(2^52)

Posted: Sun Jun 21, 2009 9:14 am
by kaisellgren
A month ago I spent two days finding out valid reasons to hash multiple times in a row. I came up with the fact that it only helps in client side security, not server side. That is, if your site is cracked, someone might be interested in a user's password to get into other websites (or he never intended to crack your site, but that was the only way to get a user's password). For example, Bob slept with Eva, who is Mallory's girl friend and then Mallory wants a revenge. Mallory found out that Bob has registered into a site that is vulnerable to an attack, so, Mallory cracks into the site and breaks it completely to steal the hash - and continues offline cracking Bob's password hash until the process completes. At this point iterative hashing will make Mallory's offline cracking harder or impossible. This is client side security and does not help in PHP web application security. Some people think that web application security includes client side security, but that's another topic.

Re: Forging SHA1 now down to O(2^52)

Posted: Sun Jun 21, 2009 12:59 pm
by Apollo
kaisellgren wrote:For example, Bob slept with Eva, who is Mallory's girl friend and then Mallory wants a revenge.
Wait a minute - Eva is Mallory's girlfriend, but she also slept with Bob? So, I reckon Eva is bisexual then? Or was this sudden swing in sexual orientation just an incident, all due to a moment of drunkenness or excessive drug abuse? 8O
Mallory cracks into the site and breaks it completely to steal the hash - and continues offline cracking Bob's password hash until the process completes. At this point iterative hashing will make Mallory's offline cracking harder or impossible.
Why, because of the increased computation time? Also for that purpose, I'd say just using a longer salt is better*. With every nested hash, you lose "some" entropy, and how much may currently not be known yet.

(*) This reminds me - a while ago I figured out why it's better to put the salt after the password, instead of before, i.e. hash(password.salt) vs hash(salt.password), but I couldn't remember why.
Now I remember: when you're bruteforcing a hash(salt.unknownpassword) checksum, you can pre-compute the hash(salt.) part once, storing the hashing algorithm's state, and initiate the hash computation for each brute force attempt from that point. So the salt, no matter how long, does not help increasing the computational time. This is not possible if you put the salt at the end. :)

Re: Forging SHA1 now down to O(2^52)

Posted: Sun Jun 21, 2009 3:02 pm
by kaisellgren
Whooooops... I had some sort of a blackout and I thought Mallory is a name for a man, because there's a similar name in Finnish, which is only used for men. :lol:

Anyway, Eva could be bisexual, too, which would just make the situation a lot more interesting. :)
Apollo wrote:Why, because of the increased computation time? Also for that purpose, I'd say just using a longer salt is better*. With every nested hash, you lose "some" entropy, and how much may currently not be known yet.
I was talking about iterative hashing, which is:

Code: Select all

$h = H($pass . $salt);
for (...)
 $h = H($h);
which will slow down brute forcing attacks. If you keep using the salt, then you do lose a very little amount of entropy. Using a longer salt helps nothing though.
Apollo wrote:(*) This reminds me - a while ago I figured out why it's better to put the salt after the password, instead of before, i.e. hash(password.salt) vs hash(salt.password), but I couldn't remember why.
Now I remember: when you're bruteforcing a hash(salt.unknownpassword) checksum, you can pre-compute the hash(salt.) part once, storing the hashing algorithm's state, and initiate the hash computation for each brute force attempt from that point. So the salt, no matter how long, does not help increasing the computational time. This is not possible if you put the salt at the end. :)
If you hash iteratively, how would you go for saving the state and gaining some use of it? No way. It only helps when you are cracking several passwords which all have the same salt (and salts are not the same for each passwords :P).

Edit: I think you were only referring to a situation where you do something like H(Salt + Pass), then yes, you can pre-compute the salt part (why couldn't you?) and just calculate the end of it, but this is usually not needed as a dictionary attack would bite anyway.

Re: Forging SHA1 now down to O(2^52)

Posted: Sun Jun 21, 2009 3:26 pm
by Apollo
Ah OK, happy we cleared that up, I was kinda worried about the whole Bob/Eva/Mallory situation :)

Now, as for the less important matters:
kaisellgren wrote:I was talking about iterative hashing, which is:

Code: Select all

$h = H($pass . $salt);
for (...)
 $h = H($h);
which will slow down brute forcing attacks. If you keep using the salt, then you do lose a very little amount of entropy. Using a longer salt helps nothing though.
I understand, this does indeed slow down brute forcing attacks, and it also loses an unknown amount of entropy. Probably a little, maybe some Chinese freak invents a vulnerability in 3 year from now by abusing some unforeseen bit correlation occurring from repeatedly feeding H's output to itself. We really can't tell.

By using a longer salt (e.g. several KBs, or even MBs if you want) you can slow down just as much (computational time of H linearly depends on length of salt) without losing any entropy for sure.
Apollo wrote:If you hash iteratively, how would you go for saving the state and gaining some use of it? No way. It only helps when you are cracking several passwords which all have the same salt (and salts are not the same for each passwords :P).
I was referring here to brute forcing H(salt.unknownpassword), i.e. one specific password. Or, actually, one specific hash value for which we're trying to find a matching password string. Without salt, you could use rainbow tables. With salt, you can't, and brute forcing becomes longer depending on salt's length. So you'd have to calculate H(salt.bruteforceattemptX) every time. But since the salt is always the first part, you can partially perform the hash algorithm up to the salt once, and just calculate the rest for every brute force attempt. As opposed to H(unknownpassword.salt), where this is not possible.

Let me put it this way: suppose my salt string is "i3P!tD_9C%7v2.mU;h6/4ft5m73P,bH8k#zO*nT+U9", now which hash would be faster to brute force, as in which allows more attempts per second: H(salt.BobsPassword) or H(BobsPassword.salt) ? ;)

Re: Forging SHA1 now down to O(2^52)

Posted: Sun Jun 21, 2009 4:04 pm
by kaisellgren
Apollo wrote:maybe some Chinese freak invents a vulnerability in 3 year from now by abusing some unforeseen bit correlation occurring from repeatedly feeding H's output to itself. We really can't tell.
The thing is, you don't need to worry about that if the underlying hash algorithm is collision resistant, but how do you know it is? You don't. So, yes, I could agree to certain extent, but if I am to discover a collision nonresistance of a hash function, I would no longer use the hash function. :P
Apollo wrote:By using a longer salt (e.g. several KBs, or even MBs if you want) you can slow down just as much (computational time of H linearly depends on length of salt) without losing any entropy for sure.
I agree, although that is a bit pointless. If you want to slow down a brute force attack, hash iteratively. If you do not care about client side security that much, hash once. Iterative hashing will slow down attacks more than lengthy salts, which also make your hash generation slower especially because the generation of KBs (not to mention MBs) of random data is very, very inefficient...
Apollo wrote:I was referring here to brute forcing H(salt.unknownpassword), i.e. one specific password. Or, actually, one specific hash value for which we're trying to find a matching password string. Without salt, you could use rainbow tables. With salt, you can't, and brute forcing becomes longer depending on salt's length. So you'd have to calculate H(salt.bruteforceattemptX) every time. But since the salt is always the first part, you can partially perform the hash algorithm up to the salt once, and just calculate the rest for every brute force attempt. As opposed to H(unknownpassword.salt), where this is not possible.
I know what you are saying, but I think it's just a side effect. I would not worry about having my salt in the start of the mix, because I use the salt to prevent rainbow table attacks and same passwords becoming the same hash value. If I am to slow down brute force attacks (for the sake of client side security), I would hash iteratively, which makes a lot more sense.

The same thing can be seen in the HMAC standard. You can precompute the ipad and the opad if you want, but that (slowing down cracking) is not the purpose of them.

If I want to slow down brute force attacks, I would probably iteratively hash 10 000 times. The question is, how large salt is needed to achieve the same effect? The answer is 2 MB in the case of SHA-256. Now imagine a site of 100 000 users, that would be 200 GB of database storage just for the salts and imagine the amount of bandwidth it consumes, the execution time it eats not to mention the heck a lot of time it takes to generate that much of random data. By the way, have you ever tried generating 200 GB of random data? You are lucky if you can do that within your life time...

I agree with you in theory, but in practice it is unusable to use salts to slow down anything. You can place the salt in the beginning if you want, that's not a problem.

Re: Forging SHA1 now down to O(2^52)

Posted: Mon Jun 22, 2009 4:33 am
by Darhazer
kaisellgren wrote:There's really no point in double hashing, hash(password.salt) with long enough salt is the safest way to go (where, if applicable, salt is ideally salt.pepper with pepper being a 'using specific salt')
What about this:
* If we can found the hash, probably we can found the salt as well. It is often stored in the same database, so SQL injection that give us the hash, can give us the salt as well. Or if it is in the source code, what is the source code leaked.
If you have just md5( password . salt ) and you have the salt, it's just the same as md5(password).
But if it is md5 (md5(password) . salt ) ...
* You are forcing the first part to be 32 characters
* and even if you decrypt this, you still have a md5 hash (which obviously you will decrypt, since you've already broke one 32 characters long 'password'

Re: Forging SHA1 now down to O(2^52)

Posted: Mon Jun 22, 2009 5:43 am
by kaisellgren
Wtf... I never said that, it was Apollo... please don't modify the quoted name...
Darhazer wrote:* If we can found the hash, probably we can found the salt as well. It is often stored in the same database, so SQL injection that give us the hash, can give us the salt as well. Or if it is in the source code, what is the source code leaked.
Usually Salt is expected to be known by an attacker. You should assume that it is known. Referring to a value that is not known by an attacker would be a "key" or a "secret".
Darhazer wrote:If you have just md5( password . salt ) and you have the salt, it's just the same as md5(password).
Not at all. The salt prevents rainbow table attacks and two or more passwords becoming the same hash and that is exactly why we are salting in the first place...
Darhazer wrote:But if it is md5 (md5(password) . salt ) ...
* You are forcing the first part to be 32 characters
* and even if you decrypt this, you still have a md5 hash (which obviously you will decrypt, since you've already broke one 32 characters long 'password'
I don't get what you are trying to say, but it's definitely not 32 characters, the output of a hash function is (most likely) a sequence of numbers, which is exactly what each PHP hash function return.

Re: Forging SHA1 now down to O(2^52)

Posted: Tue Jun 23, 2009 1:45 pm
by Darhazer
kaisellgren, I'm sorry for mistyping the username in the quote above. It was not my intension :oops:
Although md5 is a number, the PHP function returns 32 hex characters, and also we are forcing it to cast to string since we are using a string operator ('.')

kaisellgren, of course you are right for the table attacks, but if we are bruteforcing, and we know the salt, and there is no second hashing, than md5( password . salt ) becomes exactly the same as md5( password )

Re: Forging SHA1 now down to O(2^52)

Posted: Tue Jun 23, 2009 2:27 pm
by kaisellgren
Hex stands for Hexadecimal and the word decimal implies that it is about numbers.
http://en.wikipedia.org/wiki/Hexadecimal wrote:In mathematics and computer science, hexadecimal is a numeral system
Characters, on the other hand, are a lot more than just numbers:
http://en.wikipedia.org/wiki/Character_%28computing%29 wrote:An example of a character is a letter, numerical digit, or punctuation mark. The concept also includes control characters, which do not correspond to symbols in a particular natural language, but rather to other bits of information used to process text in one or more languages. Examples of control characters include carriage return or tab, as well as instructions to printers or other devices that display or otherwise process text.
Most characters do not exist within the hash values.

Anyway,
Darhazer wrote:if we are bruteforcing, and we know the salt, and there is no second hashing, than md5( password . salt ) becomes exactly the same as md5( password )
Salts are irrelevant in context of brute forcing, they add no strength to our hashing scheme. Well, in theory they can slow down the brute force process by an insignificant figure, but in practice, as you said, salts matter nothing when it comes to brute forcing and they never intended to do anything about it - that's not their job.