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

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.

-
"but split the key into several parts and hash each of these parts" that'd be much easier to crack. Read a bit about LANMAN hashes. –  CodesInChaos Nov 26 '12 at 20:55

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)$.

-
Thanks for that clear answer. –  Simon Rühle Nov 26 '12 at 21:21