Hi everyone! I wan't to share some interesting fact about how we're going to challenge almost every solution, that uses polynomial hashes modulo 2^64. We'll hack any solution, regardless of it's base (!), the only thing we need, that it's using int64 with overflows — like many coders write hashing.

Keywords: Only today, only for you, ladies and gentlemen: we're gonna challenge Petr's solution in problem 7D - Palindrome Degree from Codeforces Beta Round #7!

Is it interesting? Welcome reading after the cut. Firstly, for the most impatient of you. Here's the source of the generator:

```
const int Q = 11;
const int N = 1 << Q;
char S[N];
for (int i = 0; i < N; i++)
S[i] = 'A' + __builtin_popcount(i) % 2;
// this function in g++ returns
// number of ones in binary representation of number i
```

Let's try solutions of two CFBR #7 winners on this test: Petr Mitrichev's and Vlad Epifanov's. vepifanov solution doesn't contain hashing and so, it works correct: the answer is 6. But Petr's solution returns 8. After a little bit thinking it becomes clear, that the answer on such test for this problem is always (N + 1) / 2 — Vlad is 100% correct.

Moreover, if we take Q = 20, then Vlad's solution returns correct answer 11, but Petr's one returns 2055, what is obliviously wrong :-)

I'll prove, that starting from Q = 11, there are lots of collisions in this string.

Let's look on that string. How was it formed? It's beggining like that:

```
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBA...
```

It's true, that it can be formed by recurrent rule `S -> S + (not S)`

, starting from с `S = "A"`

, where (`not S`

) means string after changing `A`

на `B`

and vice versa. Let's denote *S* for fixed *Q* like *S*_{Q}.

Let's remember, what polynomial has is. It's function of string *S* of length *l*, equal to , where *P* is some odd number.

I claim that *hash*(*S*[0... (2^{k} - 1)]) for some sufficiently small k *k* will be equal to *hash*(*S*[(2^{k})... (2^{k + 1} - 1)]).

That means, that for *Q* = 10, *hash*(*S*_{Q}) = *hash*(*not* *S*_{Q}). That's very cool, because it *S*_{Q} and *not* *S*_{Q} will appear in bigger order strings many-many times because of reccurent condition.

Let's see what does condition *hash*(*S*_{Q}) = *hash*(*not* *S*_{Q}) mean.First, we can take zeros and ones in coefficients instead of `ord('A')`

and `ord('B')`

— we can just take off the both parts of the equation.

What is *hash*(*not* *S*_{Q}) — *hash*(*S*_{Q})? It's simple to understand, that it's

*T*=

*P*

^{0}—

*P*

^{1}—

*P*

^{2}+

*P*

^{3}—

*P*

^{4}+

*P*

^{5}+

*P*

^{6}—

*P*

^{7}... ±

*P*

^{2Q — 1}

--- it's just sign-alternating sum of *P* powers, where signs change by similar `ABBABAAB...`

-rule.

Let's consequentially take factors in this expression off the brackets:

*T*= (

*P*

^{1}- 1)( -

*P*

^{0}+

*P*

^{2}+

*P*

^{4}-

*P*

^{6}+

*P*

^{8}-

*P*

^{10}-

*P*

^{12}+

*P*

^{14}...) =

*P*

^{1}- 1)(

*P*

^{2}- 1)( -

*P*

^{4}+

*P*

^{8}+

*P*

^{12}-

*P*

^{16}...) = ... = (

*P*

^{1}- 1)(

*P*

^{2}- 1)(

*P*

^{4}- 1)... (

*P*

^{2Q - 1}- 1).

(maybe, it's multiplied on (-1), but there is no matter for it.)

Now the main thing — this value modulo 2^64 will become zero very-very fast!

Let's understand, what's the maximal power of 2 this value is divisable. Let's look on each of *Q* - 1 factors. (*i* + 1)-st factor *P*^{2i + 1} - 1 = (*P*^{2i} - 1)(*P*^{2i} + 1) is divisible by *i*-th and by some even number *P*^{2i} + 1. That means that if *i*-th bracket is divisible by 2^{r}, then (*i* + 1)-st is divisible at least on 2^{r + 1}.

So that means that (*P*^{1} - 1)(*P*^{2} - 1)(*P*^{4} - 1)...(*P*^{2Q - 1} - 1) is divisible at least by 2·2^{2}·2^{3}·... = 2^{Q(Q — 1) / 2}. That means, that it's enough to take Q >= 12. Congratulations, this is anti-hash test!

So because of that we have such small test length in comparsion with the modulo size 2^64. So antitest size is something of order , if we use x-bit data type.

Main idea: don't use overflowing when counting hashes unless you are confident that there is no test, consisting of this ABBABAABBAABABBA... string.

How did I get that? First using of that test was in 2003 on St. Petersburg school programming contest in problem cubes (russian statements here). This problem was used in SIS) problemset. Many generations of students got WA27 on that problem, submitting hash solution. One of them was I — nobody could explain me, why is there WA for any hash base. burunduk1 looked a bit on that test, but couldn't explain me either. Since that moment I remembered about that problem.

And now I've decided to think a bit and understand, what's happening in that test. burunduk1 offered to post it on CF, so here it is :-)

I tried to found any information about anti-hash in web, googled a lot, but couldn't find anything. Does anybody know anything else, maybe, any papers? Maybe I'm not so good in googling?

In POI19 http://main.edu.pl/en/archive/oi/19/pre ... It also contain such a case ...

We found that case by accident during that POI :) We actually submitted a short paper about this to the next IOI journal.

Sorry to revive this, but I use a lot of hashing technique for online contests and have some questions :).

In short, the solution to not be targeted by this anti-hash test is to use a different mod (not power of 2)? For instance using mod 10^9+7. But that mod is kind of small, and with around 50k random strings it is really easy to get a collision. Using a larger mod will require to implement a function to multiply longs, and that function adds an unwanted overhead to the solution that might make it time out easily on some problems (does knows an efficient way of doing it? I can only think of a O(bits) way, where bits is the number of bits of our mod, something like this: http://pastebin.com/r5Af5zfp).

One other possibility is using two mods (that fit in an int type), and creating a pair of hash values. My question is, is that enough? I mean, enough for online contests where there won't be more than 10^8 string hashes. Through some empirical results, I couldn't find a hash collision for that, my bruteforce test code is here: http://pastebin.com/iaVp6ypH (be careful running it, it can consume pretty fast your computer memory, adjust the LIMIT variable for your purposes). Thanks!

You are talking right things. Hash value of order 10^9 + 7 can really cause collisions. But it's useful to understand why exactly collision can happen.

Imagine the problem, where you are asked to check 10

^{5}pairs of substrings of big string to be equal. Suppose that answers for each query are in fact "NO". Let's assume that due to big length hash of each substring is random uniformly distributed value over segment [0..10^{9}+ 6]not depending from hashes of other strings. Then the probability that the check suddenly gives us answer "YES" instead of "NO" is almost same with the probability of two uniformly distributed values from that segment to be equal. This probability is 10^{ - 9}. The probability that no one of the 10^{5}checks will fail due to collision is (1 - 10^{ - 9})^{105}≈ 1 - 10^{ - 4}, that is really close to 1. One the testset consisting of 100 tests the probability that you'll recieve "Accepted" is (1 - 10^{ - 4})^{100}≈ 99%. That's pretty big probability to write such solution, so using single hash modulo 10^{9}+ 7 is ok for that type of problems.Other type of problems involve checks like "check that hashes of 10

^{5}substrings are pairwise different". For example if we calculate number of different substrings of length 5·10^{4}in string of length 10^{5}and they all are in fact different. Once again, we can assume that each hash of that substrings is random uniformly distributed value from segment [0..10^{9}+ 7],that are independent one for each other. So now we need to calculate another probability: that from 10^{5}random integers from range of length 10^{9}no two will suddenly coincide, giving as less answer then expected an verdict "Wrong Answer".But here appears the effect known as Birthday problem: surprisingly, but for different independent randomly distributed values probability for some pair of the to be equal is about . So for 10

^{5}probes our probability to fail on one test will be even greater than 50%!Here is one note: we take hash over prime modulo because for prime

pZ_{p}is a field, and for finite fields it can be proven, that all values above (that are values of random polynomials in fixed point) are very close to be really uniformly distributed over the whole field. If we take composite number, there will appear special effects like zero divisors and other, so there is needed additional analysis of probability for that cases, it can easily happen that all such calculations for them will be wrong. The main idea of my topic is exactly about surprising property ofZ_{264}, that one can easily build a polynomial of small degree (~2048), whose value is zero in any point, so it isn't suitable for solving problems with hashes.So as you correctly said, we need to increase the hash-value space size. One way is to look on one hash modulo prime of greater size. But there is indeed a problem with their multiplication. You can multiply them with binary multiplication (such as binary exponentiation, but with adding and doubling on each step), or you can use some hacks like this (examples of code in Russian interface).

Other idea is two use a pair of hashes by two different prime modulo of order 10

^{9}, let's say,pandq. Then we once again can assume that two components of that hash will be independent of each other random uniformly distributed over theZ_{p}andZ_{q}respectively, so in fact we have a point in 2d-space that is randomly uniformly distributed over thep·q≈ 10^{18}possible values. Then in every calculation above we can replace 10^{9}with 10^{18}and probability for us to fail becomes insignificant. From my experience this way is faster then previous two.I hope this will help in understanding, when hashes can cause a collision, and why we can submit correctly proved hash solution and be sure, that it will be Accepted.

Wow, very complete response :). Thank you for the help, It definitely helped in understanding!! We should learn Russian, we miss so much interesting information only available at CF.ru posts :|

There is also a very interesting article here: http://www.mii.lt/olympiads_in_informatics/pdf/INFOL119.pdf A friend sent me, not sure if he found here on CF or somewhere else..

Look a few posts above and you will see one of the author of this article saying that they submitted a paper about this :D.

But note one other thing. Exactly as Zlobober said there are two types of problems where hashes are useful — comparing many pairs of strings and checking if all hashes are different. Note that when you just check if two hashes are equal or not, you probably won't have to check so many pairs that a probability of a collision will be high, because firstly it will rather exceed time limit than find a collision. In that case exponent in (1-p)^k (where p is a prob. of collision) grows linearly with time of execution. When you have 10^6 hashes generated modulo 10^9 number of colliding hashes will be pretty high but that doesn't change fact that if you won't do more than 10^6 queries of type "==" the probability of FINDING collision is really small (~0.999). This can be stated unless you won't do anything else than using operation "==" or "!=". But when you use other operations such as "<" the exponent and so the probability of collision may grow much faster! Best example is a simple example "are all of those hashes are different". You can sort them and check if every two consecutive values of hashes are different. But in this case you have used a specific values of hashes and that allowed you to obtain O(n^2) informations in O(n log n), so a probability of finding a collision in former example is very large.

So summing up:

I use only "==" and "!=" -> nothing to worry about

I use "<" (maybe hidden in sort or a set or a map or anything) -> use pair of hashes mod 10^9+7 and 10^9+13 or anything else.

The same in English: I came up with a workaround. Can someone break a Fibonacci hash modulo 2^32? zlobober?

a_0 (0; 1) + a_1 (0, 1; b, 1) (0; 1) + a_2 (0, 1; b, 1) ^ 2 (0; 1) + …

Where a_i — letters in a string, b — random odd constant, ';' — delimiter in a matrix. The resulting hash is a vector of two int32's. You can compute it for substrings analogically, but you need to work with two int32's instead of one int64. Why is it a Fibonacci hash? Because one can simplify matrixes multiplication: (0, 1; b, 1) (x; y) = (y; bx + y) — this trick is used for computing Fibonacci numbers and analogical sequences.

Thanks to everyone who will try to break it!

Strings "aab" and "bba" have the same hash value.

Thank you for your example, but I guess you didn't quite understand the idea. I'll try to explain in more details. The matrix notation (0, 1; b, 1) means two by two matrix:

a_0 (0; 1) + a_1 (0, 1; b, 1) (0; 1) + a_2 (0, 1; b, 1) ^ 2 (0; 1) = a_0 (0; 1) + a_1 (1; 1) + a_2 (1; b + 1)

We can assume that char 'a' code is zero and char 'b' code is one. Then hash("aab") = (1, b + 1) and hash("bba") = (1, 2). These hash codes are obviously unequal. I guess you thought that b = 1 because of the name 'Fibonacci'. But I meant extended Fibonacci sequence when x_n = x_(n-1) * b + x_(n-2)

You are right, I misread your comment, sorry :) This approach should work, given that b > max char value.

BTW, if we consider eigenvalues of (0, 1; b, 1) it seems that your hash is equivalent to the polynomial hash with base (1+sqrt(4*b+1))/2 in the ring of numbers of the form x+y*sqrt(4*b+1) (x, y taken modulo 2^32) when 4*b+1 is non-residue modulo 2^32 (which is the case iff b is odd).

Hmm, eigenvalues interpretation is interesting.

Sorry for necroposting, but this is possible to break as well.

I will consider slightly more general construction. Let

Mbe some 2 × 2 matrix with integer coefficients then hash of strings_{0}s_{1}...s_{n}is modulo 2^{w}(w= 32 orw= 64) — also 2 × 2 matrix.In your case, for some odd

b. One can verify thatM^{2}=M+b(bis a shorthand forbE, whereEis the identity matrix) holds even in integers, let alone modulo any number (math remark: becauseM's characteristic polynomial isx^{2}-x-b). One can say that in the following sense ifA-Bhas only even entries. Therefore .Now we can substitute

M^{3}instead ofPin the (P- 1)(P^{2}- 1)... (P^{2Q - 1}- 1) expression from the post. One can see that only important quality ofPwas thatP- 1 andP+ 1 are both divisible by 2. As shown above, in a sense this still holds forM^{3}. Therefore (M^{3}- 1)(M^{6}- 1)... (M^{2Q - 1·3}- 1) is a polynomial ofMwith small degree, coefficients in range [ - 1, 1] and is zero on any matrix of form.Even more, suppose that

Mis any 2 × 2 integer matrix with odd determinant (basically, nondegenerate when considered modulo 2). Then . One can verify this by brut force, but probably easier way to see this is (warning: math ahead) is noticing that nondegenerate matrices modulo 2 form a finite group of order 6 and apply [Lagrange's theorem, link is not clickable for some reason](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)#Applications ).Considering matrices

Mthat are degenerate modulo 2 may complicate things a bit, but this is not the best idea for the same reason as using evenPis a really bad idea when using simple polynomial hashes modulo 2^{w}.Warning: more math ahead.

One can also ask what will happen if we use 3 × 3, 4 × 4 matrices, et cetera. Well, for 3 × 3 matrices and

w= 64 the degree of the resulting polynomial will be 2^{11}·|GL(3, 2)| = 2^{11}·(8 - 1)·(8 - 2)·(8 - 4) = 344064 (you can read aboutGL(n,p) here), what is slightly more than usual constraints in string problems, but I believe that this can be hacked with more careful consideration of the same idea. And I am not sure that using 4 × 4 matrices will be faster than usual double hashing approach (did not test it though) and it doesn't sound safe either.TL;DR: strings

sandtgenerated by the following code should have equal Fibonacci hashes modulo 2^{64}:This is very nice. Good observations!

In fact has no element of order 8 — either by bruteforce, or rational canonical form, or the observation that the (Heisenberg) subgroup of upper triangular matrices is a non-cyclic Sylow 2-subgroup, or (insert simple argument here) — so you can reduce the degree of your polynomial to 172032. I can't see how to reduce it further, since there are matrices of order 3, 4, and 7.

Actually the decision to use matrices seems a bit arbitrary, since multiplication is slow, and you're really only using powers of a single matrix.

We could instead use a ring of the form , where

pis an arbitrary monic integer polynomial of degreed, say, with , so thatxis invertible inR, and then let the hash ofabe , evaluated inR. (Elements of R can be represented uniquely as , where eachb_{i}is a long long.)This is essentially equivalent to using

d×dmatrices, since any such matrix is a root of a polynomial of degreed(Cayley-Hamilton), and the minimal polynomial could be any polynomial of degreed(e.g. consider the matrix representing multiplication byxwith regard to the basis 1,x, ...,x^{d - 1}ofR).However, each multiplication in

Rrequires 'only'O(d^{2}) long long operations, and each addition requires onlyO(d) long long additions, which is slightly better than theO(d^{3}),O(d^{2}) required ford×d-matrices.For

d= 4, according to my calculations the order ofxmodulo 2, i.e. in , is either 15, 7, 12, 8, or a divisor of one of them, so your hack would require a string of length 2^{11}·5·3·7·8 = 1720320, assuming you don't knowp.If the hacker knows the order

mofxmod 2, however, they will only need length 2^{11}m. The fact thatmseems to inevatibly be fairly small suggests that this approach is essentially no better than say choosing a small numbermat random, dividing the string into chunks of sizem, and treating each chunk as one character somehow.Tl;dr: Just use one or more large primes.

By the way, order of any element of

GL(d, 2) does not exceed 2^{d}- 1 (simple proof here). Thereforem≤ 2^{d}- 1 always holds andmalways is quite small.UPD. So hacker can just generate a pair of strings with same hash for every possible "maximal"

m≤ 2^{d}- 1 (i. e.mis a divisor of |GL(d, 2)| and does not have multiples less than 2^{d}other than itself). Their total length won't be very big even ford= 4 and their concatenation would work as countertest in most problems.