Skip to main content
Added links on hash convergence
Source Link
marcelm
  • 596
  • 3
  • 6

You can see that the convergence effect is present in all three scenarios. As for uncut SHA-512, my computer isn't fast enough to compute this, I couldn't find any information on the strength and certainty of the effect, and I'm not smart enough to construct a proof (if a proof is even possible). But odds are you'll see the effect in full SHA-512 too. My instinct suspects that it reduces the hash space by its square root (halving the bit length), but I could be very wrong [update: see links provided in the comments: one, two, three]. 100k rounds probably limits the damage, probablytoo.

You can see that the convergence effect is present in all three scenarios. As for uncut SHA-512, my computer isn't fast enough to compute this, I couldn't find any information on the strength and certainty of the effect, and I'm not smart enough to construct a proof (if a proof is even possible). But odds are you'll see the effect in full SHA-512 too. My instinct suspects that it reduces the hash space by its square root (halving the bit length), but I could be very wrong. 100k rounds limits the damage, probably.

You can see that the convergence effect is present in all three scenarios. As for uncut SHA-512, my computer isn't fast enough to compute this, I couldn't find any information on the strength and certainty of the effect, and I'm not smart enough to construct a proof (if a proof is even possible). But odds are you'll see the effect in full SHA-512 too. My instinct suspects that it reduces the hash space by its square root (halving the bit length), but I could be very wrong [update: see links provided in the comments: one, two, three]. 100k rounds probably limits the damage, too.

Source Link
marcelm
  • 596
  • 3
  • 6

It's a bad idea to design your own password hash.

Making cryptographic functions is still very much a process of trial and error. Sure, over time we have stumbled on some things that are a good idea or even mandatory. And we certainly have learned a lot of things that don't work. But we don't know how to make things that are proven secure all the way. A very subtle small mistake can cause a cryptographic construct to fail catastrophically. And there are a lot of opportunities for such mistakes. I'll name some later.

The best we can do right now is that people with experience in this make a crypto thing, and then everyone tries and break that crypto thing. If everyone tries enough and doesn't succeed at that for a long time then we have something that's probably good enough. We still can't prove the absence of problems, but if thousands of cryptanalysists couldn't, then hopefully the next thousand also can't.

But even this fails from time to time. Sometimes after years, decades even, a critical problem is found in something that was scrutinized by the smartest people for ages. That is why MD5 is no longer considered OK, and why RC4 is considered problematic. Or the landscape changes, leading e.g. to the need for salts in password hashes, and intentionally slow hash functions.

By using the best known current cryptographic algorithms, we can leverage this collective experience, and probably avoid repeating past mistakes. New mistakes may be discovered, but that can't be helped. Someone who builds their own crypto functions though, is likely to repeat some of those mistakes, or create entirely new ones.

I know, I know, it's fun to design that stuff yourself. And it feels good to build something that feels secure. Stack Exchange is littered with questions about custom encryption and (particularly) password hashes. Problem is, it's easy to build something that you yourself cannot break. But that doesn't mean others can't. This adage is ancient, and comes up often enough that it's now known as Schneier's law.

What can go wrong?

So, there can be problems with the very core of a crypto algorithm. This is what broke MD5 and RC4.

Or the algorithm can be completely fine, but an implementation can be broken. This can be a simple bug, or it can be something more subtle like a side-channel attack (which are surprisingly tricky to avoid sometimes).

But it's also possible (easy, even) for secure cryptographic primitives with bug-free implementations to be used incorrectly, rendering the system insecure. For example, correctly using encryption and digital signatures, but making naive assumptions during a communication handshake (SSL had its share of issues with this). Another well-known example is AES-ECB, which uses the perfectly fine AES in a way that can leak significant information.

In your hash function?

Your own password hashing function also falls prey to something like this here:

repeat 100_000:
    hash = sha512(hash)

SHA-512 is perfectly fine (as far as we know). Using it like this is frowned upon.

SHA-512 generates an "indistinguishable from random" 512-bit output for every input. It may generate the same output for two distinct inputs, this is called a collision. The problem is that N-bit hash functions on N-bit inputs are generally not bijective. That means that when feeding a SHA-512 output to itself, some of the possible 512-bit values will collide with others, producing the same output. By necessity, this means also that some other hash values cannot be generated at all.

Let's look at how this works for SHA-512, truncated to 4 bits. Specifically, we take the first byte from the output, and zero out the high 4 bits in this byte. The resulting single byte is used as input to the next round. Different ways of selecting the bits gives different results, but the principle is the same.

Trying all 16 possible inputs for several rounds gives us these chains:

in      1.      2.      3.      4.      5.      6.      7.
00  ->  08  ->  06  ->  08  ->  06  ->  08  ->  06  ->  08
06  ->  08  /
07  ->  06  ->  08  ->  06  ->  08  ->  06  ->  08  ->  06
08  ->  06  /   
03  ->  04  ->  05  \\
13  ->  15  ->  05  ->  09  ->  02  ->  10  ->  14  ->  14
04  ->  05  ->  09  ->  02  ->  10  ->  14  ->  14  /
15  ->  05  ->  09  ->  02  ->  10  ->  14  /
05  ->  09  ->  02  ->  10  ->  14  ->  14  
01  ->  11  ->  02  ->  10  ->  14  /
09  ->  02  ->  10  ->  14  ->  14  
11  ->  02  ->  10  ->  14  /
02  ->  10  ->  14  ->  14  
12  ->  10  /       /
10  ->  14  ->  14   
14  ->  14  /

After just 6 rounds, the 16 possible outputs have been reduced to just 3. The same effect can be seen for larger truncations. I ran some simulations for SHA-512 truncated to the first 1 byte (2⁸), 2 bytes (2¹⁶), and 3 bytes (2²⁴):

                bytes:  1    2      3
          input space:  256  65536  16777216
converged to M values:  13   330    2765
       after N rounds:  31   518    7114

You can see that the convergence effect is present in all three scenarios. As for uncut SHA-512, my computer isn't fast enough to compute this, I couldn't find any information on the strength and certainty of the effect, and I'm not smart enough to construct a proof (if a proof is even possible). But odds are you'll see the effect in full SHA-512 too. My instinct suspects that it reduces the hash space by its square root (halving the bit length), but I could be very wrong. 100k rounds limits the damage, probably.

Now, does this really harm your hash? Probably not. But it is a weakness, one that real-world password hash functions take care to avoid (e.g. by ensuring the password and salt are mixed back in regularly).

I think this is a great example of the subtle traps in crypto design. It's so easy to miss something like this. That's why I recommend using a battle-tested algorithm. They're better than anything you or I can come up with.

The other answers already make some recommendations for what hashes to use; Okay: pbkdf2, bcrypt. Better: argon2, scrypt. I hear Balloon is a thing, but I don't know anything about it so I have no opinion on it.