# Commutativity of keyed hashes

Definition

${H_1}^{K_1}(X)$ means data $X$ hashed by keyed hashing algorithm $H_1$ with key $K_1$.

Short question

Is $H_1^{K_1}(H_2^{K_2}(X))$ equal to $H_2^{K_2}(H_1^{K_1}(X))$?
Is $H_1^{K_1}(H_1^{K_2}(X))$ equal to $H_1^{K_2}(H_1^{K_1}(X))$?

Long question

My web application is storing a hashed password in a database. A web service requests for authentication that the user types a password, which is hashed with a random key and then sent to the server. The server thus only sees $H_1^{K_1}(X)$ where $X$ is the password, not the password itself.

I have to compare the client-side hash with the original password. How can I do that?

-
You are rolling your own crypto. Please stop. Use a purpose-designed password hashing algorithm like bcrypt. –  Stephen Touset Feb 2 '13 at 5:50
OK, I will, thanks for advice. –  TIKSN Feb 2 '13 at 8:02
Normal hash functions don't have this property, though there are some constructions which might have them intentionally. (Note that you should use the password in the key position and hash random data with it, not the other way around.) But as said, use an existing password authentication protocol. –  Paŭlo Ebermann Feb 2 '13 at 12:42
I guess I done something wrong. –  TIKSN Feb 4 '13 at 5:48

For H1=H2 there are one-way functions with that property: $y = g^x \mod p$.

$(g^{k_1})^{k_2} = g^{k_1 \cdot k_2} = (g^{k_2})^{k_1}$

This property is exploited by the Diffie-Hellman key exchange. One variation of DH used for password based authentication is SRP.

I strongly recommend to use an existing protocol, and not write your own. Implementing SRP is quite easy to get wrong. I'd just use SSL, either with a normal suite (such as ECDHE_RSA) sending the password in plain over that connection, or using a SRP suite(only supported by a few libs, such as GnuTLS).

-
Thanks a lot. This is what I was seeking for. –  TIKSN Feb 2 '13 at 9:50

No, I don't know of any hash functions that maintain that property. The defacto way to securely store user's passwords is to use adaptive hash algorithms like bcrypt. Take a look at this question for more details.

-