I had an idea. Could anyone tell me if this is a thing, if they see any problems with it, and if they know of a commutative hash function that would make it work?

Suppose you had a pair of cryptographic hash functions, one of which could take an a key in addition to its regular input, and that these functions were commutative. So:

hash1(hash2(key, input)) = hash2(key, hash1(input))

I think this could be used to implement a very effective challenge-response password system:

  1. Server stores storedHash = hash1(password)
  2. User requests login
  3. Server generates random key, sends to user. (Alternatively: User and hub use trust-less protocol to agree on random key.)
  4. User returns sentHash = hash2(key, password)
  5. Server compares hash1(sentHash) == hash2(key, storedHash)

The upside to this system is that even if the communications are intercepted, the users password remains safe, even for future use on the same server. Even if the user were tricked into trying to log in to a malicious fake server, the credentials they sent would be useless for impersonating them to the true server.

So... anyone see a problem with this? Anyone know a hash function that would make it work? (Or is there a reason any hash functions that's key-able and commutative would not be secure?)

  • $\begingroup$ I'm not understanding what it provides beyond what vanilla challenge-response password authentication already provides. Please explain why the server must hash the response. $\endgroup$
    – MickLH
    Jun 30, 2016 at 20:44
  • $\begingroup$ @MickLH Because the server does not have hash2(key, password), nor any way to acquire it. $\endgroup$ Jun 30, 2016 at 20:55
  • $\begingroup$ I don't mean that in the shallow sense, I am asking; what can this pair of functions achieve that a simple salted hash challenge response can not? $\endgroup$
    – MickLH
    Jun 30, 2016 at 20:58
  • $\begingroup$ @MickLH I'm not sure of exactly what process you're describing; the "Simple" challenge response examples I've found assume the user and the server share a secret. In this, the server could have all of its stored information stolen, and still remain secure. $\endgroup$ Jun 30, 2016 at 21:02
  • $\begingroup$ The client and server apparently do share a secret... storedHash = hash1(password) but that does not necessarily have to be secret! So the advantage of this scheme is to mitigate a "pass-the-hash" attack. $\endgroup$
    – MickLH
    Jun 30, 2016 at 21:40

1 Answer 1


If you are storing $h_1(password)$ and I break into your database, I will simply sort all the hashes I find. The one that appears most often will be $h_1($"123456"$)$, closely followed by $h_1($"password"$)$. In other words: you're storing unsalted hashes.

This is why you use special key derivation functions like scrypt and not plain cryptographic hashes on passwords.

If you are doing a man-in-the-middle attack, you generate your own key $k$ and send it to the user, who replies with $h_2(k, password)$. You know $k$ (this is still the case if you use a "trust-less protocol" to agree on $k$) so you can now try $h_2(k, x)$ for all $x$ in the 10 million most common passwords list at your leisure - even without breaking into the server.

If we're talking about key-based authentication, where collisions are unlikely to be a problem, there is an authentication protocol that uses a commutativity property a bit like you mentioned: Schnorr ZK proofs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.