3
$\begingroup$

This question already has an answer here:

Suppose A is some arbitrary hash function, for example BCrypt or MD5. And B be some other arbitrary hash function, maybe SHA256 or SCrypt.

Let passwordHashedWithA = A(password) and passwordHashedWithB = B(password).

If an attacker is given just passwordHashedWithA and finds a pA such that:

passwordHashedWithA == A(pA)

Then the attacker has performed a successful preimage attack on A.

I want to know if it is theoretically possible to construct a hash function C out of two arbitrary hash functions A and B, such that for any A and B, performing a successful preimage attack on C would require performing a preimage attack on both A and B. The question can be extended to build C from N arbitrary hash functions.

I strongly suspect that this is theoretically impossible; it seems like a free lunch. But I cannot begin to think how to prove it.

If such a thing does exist then it would be incredibly useful: we could combine old, proven hashes like BCrypt with slightly newer and fancier hashes like SCrypt, such that we have the best of both worlds. Like I said - sounds too much like a free lunch.

I am asking this from a theoretical perspective, I'm aware that BCrypt or SCrypt are probably good enough for most production systems.

I'm looking for a proof that this is impossible, or a construction of C that provides these properties.

Examples of C that don't work

Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.

The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking A or B.

If we try C(password) = A(B(password)), this initially looks stronger but you really can't say much about C without looking at the specifics of A and B. For example if A was a completely useless hash that always returned a constant string, the strengths in B would be irrelevant, and any string would be a preimage of C.

$\endgroup$

marked as duplicate by D.W., e-sushi May 4 '16 at 14:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What about C(password) = A(B(password) || password) where || is concatenation? I don't have time to prove it now but it appears to work around the issue you found with just composing the two hash functions. $\endgroup$ – Thomas Apr 29 '16 at 23:47
  • 2
    $\begingroup$ Is'nt the answer you want exactly the top answer to this question crypto.stackexchange.com/questions/270/… ? $\endgroup$ – Geoffroy Couteau Apr 30 '16 at 4:27
  • $\begingroup$ Thank you! Yes I hadn't seen that question - it is remarkably similar. Unfortunately the answers do not focus on preimage attacks and are not written in a formal manor. This question specifically asks for those things but does that constitute a significant enough difference? $\endgroup$ – George Powell Apr 30 '16 at 8:17
  • $\begingroup$ @Thomas if A gave constant output then all of B's strengths would be lost in C $\endgroup$ – George Powell Apr 30 '16 at 8:22
  • $\begingroup$ @Thomas : ​ A might leak a significant portion of its input. ​ ​ ​ ​ $\endgroup$ – user991 Apr 30 '16 at 11:50
3
$\begingroup$

Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.

The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking A or B.

This is incorrect with the standard notion of preimage resistance.

Because there are many more possible inputs to a hash function than outputs, there are necessarily collisions. Even if $A$ allows you to find a preimage, that is not necessarily a preimage for $B$. For random inputs and unrelated hashes, it very likely is not.

In practical applications this is quite a bit more messy. For example, if you take $A$ to be the truncate function (to e.g. 256 bits, zero-padded), it lets you find a preimage for the concatenated hash if the input is short enough. For the vast majority of possible inputs it does not directly give you a preimage, but that is cold comfort if hashing e.g. typical passwords.


If you want a provably robust combiner, you could look into the thesis linked from an answer to the previous question: Anja Lehmann: "On the security of hash function combiners" (pdf). It offers good combiners that are unfortunately rather complex.

For a simpler combiner, you could use XOR like TLS does. You do not get a nice proof from only the preimage resistance of the hash, but it is provably PRF if either of the two password hashes is PRF (and they are independent). That is a practical choice that is probably good enough if you take care to use different hashes.

$\endgroup$
  • $\begingroup$ Thanks, this is helpful - however I carefully worded my statement "we can preimage C by finding the original password by cracking A or B." which I believe is correct - if we find the original password by cracking A or B, then we have found a preimage of C. I did not say preimaging A or B was equivalent to preimaging C, finding the original input however would be. $\endgroup$ – George Powell May 4 '16 at 14:51
  • $\begingroup$ @GeorgePowell, yes, I addressed that in the third paragraph. However, in practice it seems rather unlikely that a password hash would have a preimage attack that allowed one to find that particular preimage quickly. $\endgroup$ – otus May 5 '16 at 7:36

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