Skip to main content
1 of 4
poncho
  • 150.6k
  • 11
  • 230
  • 369

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

poncho
  • 150.6k
  • 11
  • 230
  • 369