Hardening a polynomial checksum scheme

Question

I have a checksum scheme that uses a simple polynomial summation as described here.

Basically I'll take a random value $R$ and a set of inputs $[v_0, v_1, v_2]$ and checksum it like $v_0*R + v_1*R^2 + v_2*R^3$. This was designed to get simple collision resistance with incremental checksumming.

I'm trying to change this algorithm to be resistant to chosen inputs. e.g. an adversary should be allowed to choose $V = [v_0, v_1, ...]$ without being able to break the checksum.

My current approach is to discard the incremental component and sample an $R$ value from the inputs. I define a constant $R_c$ and a set of inputs $V = [v_0, v_1, ...]$. I also define a hash function $H$ that is a random oracle. All of this is happening inside $\mathbb{F}_{p}$ where $p \approx 2^{256}$.

First I sample an $R$ value from the $V$ and $R_c$ by doing the following:

$R = H( \sum_{i=0}^{|V|} v_i * R_c^i)$

Then I use the originally strategy above with this $R$ value sampled from $V$.

$C = \sum_{i=0}^{|V|} v_i * R^i$

Now $C$ is the final checksum of the data.

Does this add security against chosen input attacks, and if so how much? I'm imagining the simple collision case for 1 element being (roughly)

$H(v) * v = H(v') * v'$ where $v \neq v'$

This seems awfully close to the security of $H$, is this accurate? Does this change significantly as $|V|$ gets larger?

Answer 1

Does this add security against chosen input attacks, and if so how much?

No, if $R_c$ is public, it is easy to find collisions. The idea is to find a simultaneous collision on both $R$ and $C$.

Here is one approach:

• Start with a provisional input $v_i$; set the lower three inputs $v_3, v_2, v_1$ to 0, and everything above that arbitrarily (we won't change those values)

• Compute the value $R = H( \sum_{i=0}^{|V|} v_i * R_c^i)$

• Now, for any arbitrary constant $c$, we can reset $v_2 = c$, $v_1 = -c(R + R_c)$, $v_0 = cRR_c$

For any such value of $c$, evaluating the function gives us the same value of $R$ (because $cR_c^2 - c(R + R_c)R_c + cRR_c = 0$, consistent with our initial test evaluation), and thus gives the same $H$ value (because $cR^2 - c(R + R_c)R + cRR_c = 0$ and all higher order terms are the same)

By choosing two different values of $c$, this gives us a collision. This approach can be adapted to compute preimages, should the attacker find that useful.