# 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

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?

-
 The problem with the wrong key is, that I copy the encrpyted file and decrypt it in the original file, so that if the key was wrong, the data was lost, but your idea with testing if encryptions works with a short value. Is there any good suggestion what can be taken for such a thing (I mean what value, a dynamic and how to create it)? – Simon Rühle Dec 1 '12 at 18:08 It can't be dynamic, because you need to refer to it both at the time of encryption as well as decryption. Like I mentioned, a static value of "ABC123" provides a crib to an attacker: try a brute force approach and if any decrypts to the known value, you lose. I don't know of any asymmetric approach you could take here that wouldn't be easily bypassed. I think you'll just have to take the risk of the known plaintext attack. It's much safer than storing a hash of the key. – John Deters Dec 14 '12 at 14:35