Find some hash function with deliberate collisions

Question

I guess this should be well known (or trivially desperate), but I couldn't find any reference.

I have a small number (say $k=15$) of messages $m_i$ ,$i=1\cdots k$ (they are fixed length and short, but I think this should be irrelevant).

I'd like to find some hash function such that $h(m_i)=h(m_j)$ (deliberate universal collision, they all give the same hash), but such that the chance of a random collision is reasonably small. I'm not concerned about cryptographic attacks.

The brute force approach (append some random bytes to all messages, hash, retain some bits and hope that the universal collision happens) doesn't look practical. Too many tries, too high probability of random collisions.

Is there some other way?

Answer 1

If you just want to prescribe up front that a set of messages $m_1, m_2, \ldots, m_k$ will collide in an otherwise innocuous hash function, without regard for any cryptographic security properties…

…then the question is off-topic for crypto.SE, but you can just pick a hash function $H\colon \{0,1\}^* \to \{0,1\}^\ell$, pick your favorite hash value $h$ for the messages $\{m_i\}$, and define $$H'(m) = \begin{cases} h, & \text{if $m \in \{m_i\}$;} \\ H(m), & \text{otherwise.} \end{cases}$$ In this case, $H'(m_i) = H'(m_j)$, but $H'$ otherwise behaves like whatever kind of hash function $H$ is. It is unlikely that you can compress the description of $H'$ more than this without additional structure to the fixed messages $m_i$.

Another approach would be to define $\hat H(m) = f(H(m))$ where the polynomial $f \in \operatorname{GF}(2^\ell)[x]$ is the Lagrange interpolation of of the function $H(m_i) \mapsto h$: $$f(x) = \sum_i h\cdot\prod_j \frac{x - H(m_j)}{H(m_i) - H(m_j)}.$$ If the $m_i$ are larger than the $\ell$-bit hash values, this has a substantially shorter description: it is a degree-$k$ polynomial with hash-value-sized coefficients. (Caveat: If $H(m_i) = H(m_j)$ for any $i \ne j$, this formula doesn't work as written—the denominator $H(m_i) - H(m_j)$ is zero. In that case, just discard that term.)

Note that unlike $H'(m)$, $\hat H(m)$ does not coincide with $H(m)$ when $m \notin \{m_i\}$. Whether $\hat H(m)$ has any properties one might expect of the kind of hash function you mean, I leave as an exercise for the reader to ascertain.

(Original answer) If you were concerned about cryptographic attacks…

You can make a public-key collision-resistant hash function. Anyone can evaluate the hash function; knowledge of a secret key enables finding collisions; without knowledge of the secret key, finding collisions is conjectured to be difficult.

One example is $x \mapsto y^x \bmod n$ for random $y$, where $n = pq$ is an RSA modulus. If you know the factors $p$ and $q$ of the modulus, then it is easy to find a collision; if you don't, then it's probably not. Specifically: any algorithm that can compute a collision with nonnegligible probability can be used as a subroutine to solve the RSA problem, computing roots modulo a large semiprime of secret factorization, without much additional effort. Under certain additional conditions, finding a collision can't be much easier than factoring for an analogous reason.

VSH is a somewhat more well-known example, defined on arbitrary bit string messages.

These don't allow you to prescribe collisions, however: you get no choice in the messages that collide, only the ability to find them. Actually you even get the ability to find preimages and second preimages, but again, no control over which sets of messages collide.

Answer 2

You could define a new hash algorithm which just outputs the SHA-256 hash of the input, except for the given inputs $m_i$ where the function always outputs the fixed result $x$. This algorithm has collisions for these special inputs but is for all other inputs as secure as SHA-256.

Answer 3

You might want to look at using a Cyclic redundancy check. These are good at detecting random errors, but a malicious person (you) can easily calculate how to modify a message to produce a chosen CRC. Here is a program to modify a message to get a particular CRC.

Answer 4

There is a proof of concept called Malicious SHA-1 which tweaks constants from nothing-up-my-sleeves numbers to something-up-my-sleeves numbers.

This is not an attack on SHA-1. It differs from SHA-1 by replacing constants with magic numbers. The values are chosen such that a person with knowledge of the backdoor can compute collisions much more efficiently than everyone else.

An interesting property is described in the FAQ:

To third party analysis, malicious SHA-1 remains as strong as the original SHA-1: the backdoor is “undiscoverable“, it can only be exploited by the designer.

---

Note of clarification not directed at the question poster:

This does not apply to the real SHA-1 function. It is a modified algorithm. This does not attack unmodified versions of SHA-2 or SHA-3 either. Nor is it a sign of weakness in either the SHA-2 or SHA-3 family of algorithms.

It's also important to note that normal SHA-1 is still broken (using a different method).

The proof of concept shows us what we already knew: magic numbers in algorithms are suspicious. Leaving yourself, as an algorithm designer, a high degree of freedom in choice of magic numbers (for algorithms in general!) could be used to hide known weaknesses in algorithms. Which may or may not get discovered.