Return to Answer

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 same approach would allow computing preimages, should the attacker find that useful.

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.

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.

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 same approach would allow computing preimages, should the attacker find that useful.

This was designed to get simple collision resistance with incremental checksumming.

Here's good news and bad news.

First the good news: your mapping from $[v_0, v_1, ...]$ to $C$ is an "almost universal hash function", that is, for any two distinct messages, the probability of them hashing to the same value is provably tiny (assuming $R$ is chosen uniformly random). In particular, if the degree of the polynomials is $n$, then the probability is at most $n / p$ (where $p$ is your 256 bit prime) [1].

One cavaet: it is important that distinct inputs map to different polynomials; for example, if you allow varying input lengths, then $[1, 1]$ will obviously collide with $[1, 1, 0]$ with the simple mapping function you have. This can be addressed by using a slightly more complex mapping function, or just insisting that the inputs must be a fixed length.

Now, the bad news: if the attacker can see the value $C$ of a known input, he can recover $R$ efficiently (actually, generate a small set of values that contains the correct $R$ value), and from there, he can easily generate collisions (or preimages, should he so desire).

Hence, if you are using this function in a way where the attacker can observe the outputs, it's not at all secure.

[1]: Note: it is important that $p$ be prime; your notation of $\mathbb{F}_p$ indicates that it is, however to be clear, it must be

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.