0
$\begingroup$

A polynomial hash defines a hash as $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, all modulo $2^n$ (that is, in $GF(2^n)$).

For brevity, let $c$ be a $k$ dimensional vector (encapsulating all the individual $c_n$ values).

Are there particular values for $c$ that make the probability of collisions between two randomly chosen $a$ greater than $k/2^n$?

I would argue that there are not. For $H(c, a)$ equals evaluating a polynomial (of degree at most $k$) at $a$. Thus, $H_c(x)$ defines a polynomial with degree at most $k$. Let $H_{c,a}(x) = H_c(x) - H_c(a)$; the zeroes of $H_{c,a}$ are precisely the points where $H_c(x) = H_c(a)$, and there can be no more than $k$ such zeroes. Thus, for any non-zero $c$, two randomly chosen $a,a'$ have $H(a) = H(a')$ with probability $\le k/2^n $.

However, this crypto CTF challenge seems to argue certain $c$ do produce collisions, and this solution explains and demonstrates it (unfortunately most of the explanation is in Chinese). Where is my mistake?

$\endgroup$
1
  • 1
    $\begingroup$ Modulo $2^n$ is operations in the ring $\mathbb{Z}_{2^n}$ which is NOT the same as $GF(2^n)$. $\endgroup$
    – kodlu
    Feb 20 at 23:06

1 Answer 1

2
$\begingroup$

This ring has zero divisors so the answer is different than over fields.

Let $H(a)-H(a')=c_1 a^{k-1}+c_2 a^{k-2}+\cdots+c_k,$ and let $j$ be the largest nonnegative integer such that $2^j$ divides $gcd(c_1,\ldots,c_k).$

Claim: Let $j$ be as above, then the polynomial $H(a)-H(a')$ can have $k\times 2^{j}$ roots, leading to a collision probability of $$\frac{k}{2^{n-j}}.$$

Proof: If the coefficients of the difference polynomial have a gcd divisible by $2^j$ then all values of the polynomial are in the subset (which is an ideal) $$2^j \mathbb{Z}_{2^n}=\{2^j u: u \in \mathbb{Z}_{2^n}\}.$$ This means that the difference polynomial is of the form $2^j g(a)$ for some polynomial with gcd equal to 1. Therefore, it is enough for $g(a)$ to take values in $2^{n-j}\mathbb{Z}_{2^n}$ for $2^j g(a)$ to take on the value zero. This means that each zero of $g(a)$ is duplicated $2^j$ times to be a zero of the difference polynomial so the probability that the difference polynomial takes on the value zero is now $$ \frac{k 2^j}{2^n}=\frac{k}{2^{n-j}}. $$

Example from [Magma Calculator][1] of a degree $k=2$ polynomial, which has 2 roots and one where $j=2,$ which has $k 2^j=8$ roots.

code:

Z2to6:=IntegerRing(2^6); Z2to6;
R<a>:=PolynomialRing(Z2to6); R;
{* Z2to6!(a^2+63*a): a in Z2to6 *};
{* Z2to6!(4*(a^2+63*a)): a in Z2to6 *};}

output:

Univariate Polynomial Ring in a over IntegerRing(64)
{* 0^^2, 2^^2, 4^^2, 6^^2, 8^^2, 10^^2, 12^^2, 14^^2, 16^^2, 18^^2, 20^^2,
22^^2, 24^^2, 26^^2, 28^^2, 30^^2, 32^^2, 34^^2, 36^^2, 38^^2, 40^^2, 42^^2,
44^^2, 46^^2, 48^^2, 50^^2, 52^^2, 54^^2, 56^^2, 58^^2, 60^^2, 62^^2 *}`
{* 0^^8, 8^^8, 16^^8, 24^^8, 32^^8, 40^^8, 48^^8, 56^^8 *}```

The second polynomial $4(a^2+63a)$ has a gcd of 4 thus it has 8 roots not 2.

The magma list notation 0^^8 means the element 0 appears 8 times in the list.




  [1]: http://magma.maths.usyd.edu.au/calc/
$\endgroup$
1
  • $\begingroup$ Fascinating. Can you explain the math a bit more. It seems my mistake was confusing the Zn ring for the GF field, and, since the Zn ring has zero divisors, polynomials can have greater degree than I expected. Your equations remind me of gcd / Euclidean algorithm, but it would be very helpful if you could elaborate. $\endgroup$ Feb 21 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.