Seeking special-use fingerprinting/hashing algorithm

Question

For a project I wonder if there exists some kind of fixed-size checksumming/fingerprinting function in which based on this fingerprint given data block 1, it is easy to generate more data blocks that share the same fingerprint/hash key.

Therefore this is unlike an MD5 sum. (In that I don't know how to easily go back from MD5 sum → new matching file.)

Basically, I am looking to generate the set of data blocks that hash to the same fingerprint of data block 1. Data blocks 2, 3, 4 etc... may be the same size or even smaller than 1 – ideally the less information entropy the better – but the series must be deterministic and finite, and computationally easy to find.

Comment#1 helps me tighten some properties. In particular, considering the mapping

hash[key][index] -> datablock

Given a 32-byte key for instance, index should be consecutive integers like you would expect in arrays, and a fixed index should map to a fixed datablock (for that key). Within that set of datablocks, each datablock should calculate to the same hash key, but when enumerated should maintain their relative index position (eg. datablockYYY should always and only be found at 15 index positions higher than datablockBBB).

The tricky part might be that the index range of hashes should not have to be so vast as to need as many bits of entropy as the data blocks themselves generally, but substantially less: limited to a 31bit unsigned integer for simpler testing, let's say. In fact, when I come to calculating the key1 given my starting datablock1, I hope to find a datablockN whose index in the hash is not too far from datablock1's index. The data blocks need not all be the same size, nor all possible blocks of a certain size be mappable by a particular key (pigeonhole principle in reverse). An onto function? Not sure about the terminology.

Hoping that a much reduced problem using familiar things will help shed some light, though there are significant differences here.

Answer 1

For cryptographic hash functions we usually want to avoid collisions as much as possible (and even more we want to avoid any way to get from the output back to the preimage).

So what you want certainly is not a cryptographic hash function, but something else.

On the first look, something like a CRC (cyclic redundancy check) could fit your bill. These have the property that they reduce arbitrary-length messages to fixed-length checksums ($n$ bit for a CRC-$n$), and given a $n$-bit checksum and a prefix of a string with only $n$ bits missing, it requires just some linear algebra to compute the exactly one postfix missing. (You can have other parts missing instead, but then the computation is a bit more complicated.)

So assuming your datablocks are $m$ bit, we have the functions $$\def\Z{\mathbb Z}\def\invC{\operatorname{inv}\!CRC} CRC : \Z_2^m \to \Z_2^n,$$ $$ \invC : \Z_2^{m-n} \times \Z_2^n \to \Z_2^m, $$ where $\invC(x,y)$ has $x$ as the first $m-n$ bits, and $CRC(\invC(x,y)) = y$.

I'm not sure if this fits your bill - you could have $y$ as key and $x$ as index, or the other way around.

Answer 2

You can use Rabin's fingerprints for your case