Is there an advantage to storing keys split between several hashes?

Question

I have a question about the way to store a key or password that was used for encryption, so that the application can check if the user put in the right key for decryption. If I make a mistake, please advise me and I will try to avoid such a mistake in the future.

Normally, the key that was used for encryption is stored hashed on the system, so that the application can check if the user used the correct key.

Would it be better to store not the whole key hashed, but split the key into several parts and hash each of these parts? This should make cracking more difficult, because the attacker has to crack several hashes, with different salts (if used). Am I totally wrong with my line of thought?

If yes a little hint would be nice, so that I can investigate in that direction and avoid this mistake in future.

Answer 1

Lets take your idea to the extreme to see its weakness. For simplicity I'll scale things down. Let's assume an 8 bit key chosen randomly. Call this key $k$. If I break into your database and get $d=H(k,s)$ along with $s$ (where $H$ is a hash function and $s$ is the salt), it would take on average $2^{8-1}=2^7=128$ computations (or calls to $H$) to find $k$.

Now, using your idea, lets say the server instead splits $k$ into $(b_1,b_2,\cdots,b_8)$ (i.e., bits) and then computes $d_i=H(k_i,s_i)$ (so there is a different salt for each bit of the key). Now, the attacker who breaks into your database and steals the pairs $(d_i, s_i)$ needs to crack all $8$ hashes. More difficult? No.

The reason is, how much work does it take to break $d_1$? Well, the attacker only need compute $H(1,s_1)$ and $H(0,s_1)$ to find $b_1$. That is only two operations (one on average though since half of the time the attacker will get the right value on the first try). Do this for all $8$ bits and the attacker has to make a maximum of $16$ hash function calls to break the key $k$. The average number of hash function calls would be $12$. This is much, much less than in the normal case above.

Asymptotically speaking, the first system (which hashes the entire password) is something like $O(2^n)$ where $n$ is the number of bits in the key and the second system (your proposal) is $O(n)$.

Answer 2

Instead of storing a value based on the key, look at the problem you're trying to solve. You're not actually interested in the value of the key, you just need to ensure decryption works. If you feel you must test the user's input immediately, might I suggest instead storing a value that was encrypted with the key, and testing decryption directly?

The advantage is that security remains equal to the security of the encryption algorithm itself, as opposed to the less-understood (and therefore much more risky) security of a home-brewed hash mechanism.

The disadvantage is that your software would be holding both the challenge and response data, which might help enable a known plaintext attack.

However, rather than storing any test value whatsoever, I advise you take a step back and determine the overall risk to your system of attempting to decrypt with the "wrong" key. Your application should know as soon as any encrypted data arrives whether or not the key was correct, as the decrypted data will either be legible or it will be useless. What is the impact to your system if the entered key was wrong? Does it mean the user has to wait for encrypted data to arrive before he knows the inputted key was correct? Is that truly an intolerable situation for your system?