Rolling Hash function over untrusted data: how to preserve statistical splitting properties? I would like to know if there is a construction for a Rolling Hash function to be used to split the received untrusted data in chunks.
The data is split whenever the hash function drops below a certain threshold and the splitted data is then used to build trees for efficient indexing of such data.
In my case the input data is however untrusted and I need a rolling hash construction that preserves the mean splitting size even under adversarial attacks on the data (which would otherwise make the trees highly unbalanced).
From what I have seen rolling hashes are mainly used in backup applications for deduplication purposes but they operate under the setting of non-adversary data.
Thank you in advance.
There are absolutely functions like this but no such function, regardless of its properties, can solve your problem. They depend on the adversary not knowing the secret value used for deciding where to mark the stream. For efficient rolling HMACs, the attacker has almost full control of the output if they know the key.
how to build a secure rolling HMAC
Performance is 1/16th that of AES encryption because one full block is encrypted for every input byte. The universal hash is trivial in comparison and not a bottleneck.
An attacker with the key can produce streams with arbitrary function outputs limited by the number of bits they are putting into the window. Putting in 16 bytes gives them (almost) full control of the output of the universal function and resulting AES encrypted output value.
This is true regardless of the function you use. If the attacker has the keys they can set the splitting properties of the stream arbitrarily. It's only a question of computing cost.
That's why most systems for chunking or otherwise marking locations in streams as interesting just use buzhash and friends with a secret tweak. The moment the attacker learns that F(x)&lt;threshold they can construct a stream x|x|x|x full of marked locations. Constructing a stream that contains no marks is similarly trivial. It becomes possible to construct streams with arbitrary marks from a library of strings with known mark properties.
There's no point in paying the computing cost to prevent key recovery if the adversary can break the system anyway which is why secure rolling hashes aren't in wider use.