Rabin-Karp hash collisions: random bases, root counting, and the Thue-Morse attack on 64-bit hashing

A plagiarism checker compares documents by fingerprints. A string $s$ of length $L$ gets $F (s) = (s_{0} r^{L - 1} + s_{1} r^{L - 2} + \dots + s_{L - 1}) mod M,$ where $s_{i}$ is the code of the $i$ -th character, $r$ is the base and $M$ the modulus. Rabin and Karp's matcher slides a window along the text and compares fingerprints, and it only compares characters when two fingerprints agree. Two different strings with the same fingerprint are a collision. Too many collisions make the matcher slow, or make a checker that trusts fingerprints wrong.

A window of 3 slides along the text; each position gets a fingerprint.

How hard is it to make collisions? It depends on what the checker keeps secret.

In parts A and B the letters a to z have codes 1 to 26, and $M = 101$ .
In part C the codes are ord(c), and $M = 2^{b i t s}$ : the arithmetic of a machine word that simply wraps around, which is how many programs compute fingerprints.

Background: Fingerprinting and String Matching.

Part B: a random base is a random point of a polynomial

The difference of two fingerprints is a polynomial in the base:

F (s) - F (t) = (s_{0} - t_{0}) r^{2} + (s_{1} - t_{1}) r + (s_{2} - t_{2}) (\mod 101)

. The letter differences lie between

- 25

and

25

, so for two different words this polynomial is not zero mod 101, and a nonzero polynomial of degree at most 2 has at most 2 roots mod a prime. So no pair collides for more than 2 of the 101 bases. To reach 2, choose the roots first:

(r - 1) (r - 2) = r^{2} - 3 r + 2

, so the letter differences are

1, - 3, 2

, for example bac and ada.

That is the whole case for Rabin–Karp with a random base: two strings of length

L

collide with probability at most

(L - 1) / M

, so with a large prime

M

a collision is rare whatever strings the adversary writes.

Part C: without a prime, the roots come back

Mod

2^{64}

the argument fails, because

2^{64}

is not prime and a polynomial can vanish at every odd point. Take the Thue–Morse strings:

t_{0}

is a, and

t_{k + 1}

t_{k}

followed by

t_{k}

with a and b swapped. The difference between

t_{n}

and its complement is, up to sign,

\prod_{i = 0}^{n - 1} (x^{2^{i}} - 1)

. For odd

x

, the factor

x - 1

is even, and

x^{2^{i}} - 1

for

i \geq 1

is divisible by

2^{i + 2}

(since

x^{2} - 1

is divisible by 8). So the product is divisible by

2^{1 + \sum_{i = 1}^{n - 1} (i + 2)}

, which reaches

2^{16}

n = 5

(32 letters),

2^{32}

n = 7

(128 letters) and

2^{64}

n = 10

(1024 letters). The bound is exact for a base that is 3 more than a multiple of 8, so a shorter Thue–Morse string does not work.

So a fingerprint computed with plain 64-bit arithmetic is broken for every base at once by two strings of 1024 letters. Programming contests use this as a standard "anti-hash" test.

Going further

Use a prime modulus and a random base. Then part B's bound holds: collisions have probability at most

(L - 1) / M

. A common choice is

M = 2^{61} - 1

, which has fast reduction.

A fixed, known base can still be attacked. A birthday search over about

2^{30}

strings finds a collision mod

2^{61} - 1

, and lattice reduction (LLL) finds collisions far shorter than either. A secret random base defeats both.

The same polynomial argument powers Polynomials in Algorithm Design: a nonzero polynomial rarely vanishes at a random point.

Matching Fingerprints

Try your rule first

Part A: a small modulus has few values

Part B: a random base is a random point of a polynomial

Part C: without a prime, the roots come back

Going further

References

Two words, one fingerprint