Composing hashes and/or MACs

Question

Suppose I have n hash/MAC functions, of which n-1 are extremely insecure, leaving only one that is in fact cryptographically secure. If I use all of them on a message and the XOR them together the result will be cryptographically secure or not? I believe it would, because if 1 is secure than it's output is undistinguishable from random, and will act as a one time pad for the insecure ones. Is this reasoning sound?

Answer 1

It is safe, in the case that you have MACs which are independently keyed (or at the very least, the cryptographically secure MAC is independently keyed from all the other ones). This can be seen not by an argument from randomness, but from a simple observation that it were not true, then an attacker could attack the secure MAC by generating the insecure MACs on his own, exclusive-or those MACs into the MAC he did observe, and then attack the combined MAC; any weakness there could be translated into a weakness in the original secure MAC.

If you have MACs which are not independently keyed, or you have hashes, you can construct cases where the XOR is not secure. Here is one such example:

• Our secure hash is SHA256 (which for the purposes of this example we will assume is secure).

• We have 256 insecure hashes, $X_0$ through $X_{255}$. $X_i$ is defined this way; all bits of $X_i(M)$ are 0, except for bit $i$; bit $i$ will be the same as bit $i$ of $SHA256(M)$.

We can see that every $X_i$ is extremely insecure (as each "hash" has only two possible values).

And, we can trivially see that the exclusive or $SHA256(M) \oplus X_0(M) \oplus X_1(M) \oplus ... \oplus X_{255}(M)$ is also insecure (because it is always zero).