Suppose A is some arbitrary hash function, for example BCrypt or MD5. And B be some other arbitrary hash function, maybe SHA256 or SCrypt.
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
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.