# Can there be two hash functions without common collisions?

Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision? I mean, like provable in way that someone who took one cryptography class in university can prove.

For example, I want hash functions $A$ and $B$ such that if hash function $A$ collides on $X$ and $Y$, then $B$ will not collide on these $X$ and $Y$:

$$A(X) = A(Y) \quad \Rightarrow \quad B(X) \neq B(Y)$$

• Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. – Paŭlo Ebermann Nov 8 '12 at 23:05

No, in general, there will always be a pair of inputs that will collide for both hash functions. Specifically, if the hash functions have fixed sized outputs, and both take an arbitrary input which is at least as long as the sum of their outputs, then there will be bitstrings $$X$$ and $$Y$$ with $$X \neq Y$$, $$A(X) = A(Y)$$ and $$B(X) = B(Y)$$

Here is a simple demonstration that such a pair must exist: let us assume that $$A$$ generates an output which is $$n$$ bits long, while $$B$$ generates an output which is $$m$$ bits long, and further assume that $$n, m > 0$$.

Now, consider the set of all possible bitstrings of length $$n+m$$, along with the empty bitstring (or, if you don't like that, pick any bitstring shorter than $$n+m$$). This set has size $$2^{n+m}+1$$. If we apply the hash function $$A$$ to each member of the set, there are $$2^n$$ possible outputs, and hence (by the pigeon-hole principle), there must be some output with at least $$2^m+1$$ preimages. Let us pick such an output, and call the subset when generates that output subset $$W$$.

Now, let us consider applying the hash function $$B$$ to each member of $$W$$; $$W$$ has size at least $$2^m+1$$, and $$B$$ has $$2^m$$ possible outputs; hence there must be two elements $$X$$ and $$Y$$ of $$W$$ with the output.

This pair $$X$$ and $$Y$$ is a common colliding pair for $$A$$ and $$B$$.

• The proof works for $m=0$ or $n=0$ (or both), too, it is just a not such interesting case. – Paŭlo Ebermann Nov 8 '12 at 23:10
• The answer to "what do I do about it" is simple: Since you get to choose the hash algorithms, just choose algorithms such that the probability of such a collision is low enough that you can ignore it. (Say, less than one hundredth the probability that you'll fail by your most likely failure mechanism with comparable failure consequences.) – David Schwartz Nov 10 '12 at 0:56

The combined output of the two hash functions must be at least as large as the input*. This follows trivially from the Pidgeonhole Principle.

The general way to construct this is using a permutation and partitioning the output into two parts that together make up the whole thing.

If you use hash-function as something that takes (almost) unlimited length inputs and produces a short constant length output, then it's impossible.

But in practice you shouldn't care. If you have a secure 256 bit hash function, collisions will never happen in practice.

* With size I mean the number of possible values the input/output can have

[Poncho's answer is correct and is probably the answer you are looking for, but I won't delete my answer as I believe there are cases where the construction has merit.]

It seems like you could construct this. Let $\oplus$ denote xor, with suitable length extension of the operands. Given any hash function $F$, define $G(x) := F(x) \oplus x$. If $x \neq y$ and $F(x) = F(y)$, then $G(x) = F(x) \oplus x = F(y) \oplus x \neq F(y) \oplus y = G(y)$.

You could use this construction to make the hash function $B$ from your given hash function $A$.

• It's important to note that in this new scheme, F(x) and G(x) both have collisions, they are just guaranteed not to be the same collisions. – Stephen Touset Nov 8 '12 at 19:34
• Stephen, that actually depends. If the pigeon hole argument applies, then of course any hash has a collision. If we can restrict the input space to be not bigger than the output space then this is not true: consider the function F(x) = 0 which makes G(x) = x. – bmm6o Nov 8 '12 at 20:03
• This only works when the input length is restricted to be smaller (or equal) than the output length of $F$, otherwise either $G$'s output grows with the input length or there is a collision where $x$ and $y$ differ only beyond the length of $G$'s output. – Paŭlo Ebermann Nov 8 '12 at 23:01