2

Specific example of mine concerns the probability of collision, where I have two plain texts A and B that I want to hash using MD5.

Given the cryptographic hash function H and the following:

A' = H(A)
B' = H(B)
A'' = H(H(A))
B'' = H(H(B))

is the probability of A'' and B'' colliding higher than that of A' and B'?

  • MD5 is not considered a secure hashing algorithm. – Gumbo Mar 4 '15 at 6:15
  • Whoops, I meant cryptographic hashing algorithm. Let me update the post (I assume you mean it's not part of the SHA family of crypto hash algos and not the fact that it's been proven insecure). – Mansour Mar 4 '15 at 6:17
  • @Mansour Actually MD5 HAS been proven to be insecure under many use cases – Richie Frame Mar 4 '15 at 10:08
  • @RichieFrame Oh ye, I'm quite aware of that, I was just asking to clarify which one Gumbo meant. – Mansour Mar 4 '15 at 11:26
1

It would need to be researched as to whether or not such an action would produce a collision in practice, but you can consider that a recursive MD5 hash is still only 1 MD5 hash at the end. You are only running the hash on 32 bits of data (the output of your n - 1) instead of on n bits of data. So, considering that the hash algorithm is pseudo-random, you might instead ask whether collisions are more or less likely on 32 bits of data vs on a variable size.

The collisions should be equally unlikely in either case, due to the fact that they are always unlikely with a good algorithm. As to the ability to force a collision, you might defeat known methods, but in principle it should be the same, if your new algorithm was researched.

Finally, you must consider what is the significance of your fear of collisions. As I understand it, collisions allow one to enter instead of the password hashed, another password and it will hash the same. In certificates, it means the ability to generate a new private key for encrypting data (ie. the password of your certificate). So if your login hashes have been compromised, collisions might allow them to enter your site, but not to know the user's passwords exactly. And that will be mainly the cryptographic use of a has algorithm - to hide the password or other source data. In this case, you are better hashing multiple times because it will increase needed CPU to guess the plaintext hashes. You may assume that one your site has been hacked, that all your information is also divulged, and so no great need remains for an attacker to login again to your site with a collided password.

The ability to authenticate a password or other data is reduced by collisions, but again is unlikely in general and so also recursively unlikely as each has as many collisions as on the nth hash only, which is the same as one hash. The subset of data (the result of the n - 1th hash) should not increase the risk of collisions with a pseudo-random hash function. If it is not truely random, the collisions definitely increase, but that does not necessarily make them easier to find or create, though you will loose some iniqueness. With a good hash, this should be minimal and not of any concern over the computational difficulty obtained by recursion.

-1

By doing number of times the hashing gives you more randomness and entropy.

The primary reason is protection against brute force attacks. You're adding a work factor to slow down trials of possible keys. Take a 4 digit passcode - there are 10,000 possible passwords, and you can get all of them by incrementing 0 through 9999 by 1. If you use a key derivation function like PBKDF2, you need to additionally hash the passcode X number of times (generally 2,000 to 50,000), increase the amount of work you need to do to derive the key.

Another reason is key stretching. Instead of using a 4 digit key, you're using a longer key for encryption (though you get that with a single hash as well).

Lastly, consider the case where the hash is revealed for some reason. In a single hash operation, you could potentially look up the passcode corresponding to the hash for a single hash operation. Doing that multiple times prevents easy lookup of original passcode. This is useful when users use the same passcode in multiple places.

  • 1
    You're right that it adds to the work required to prove the hash, but it doesn't add to the entropy or randomness - a proper hash algorithm does not produce random data, it is pseudorandom, and shouldn't have any more or less entropy in the resultant hash if you repeat the hashing process. – StampyCode Mar 7 '15 at 20:41
  • For Randomness and entrpy, I mean in a way that for each time u can add time or salt to prove the hash and its difficult for the attacker to get the number of hash times as the output always look the same byte for 'n' times. – user45475 Mar 10 '15 at 1:00
  • @user45475 That still just means you increase work, but you increase neither randomness nor entropy. – Philipp Mar 29 '15 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.