Hi

For those following this thread, here is a proof that this hash can be broken

Using Eulers totient function it is known that

s^phi(p) = 1 (mod p)

Raising to a power t using modular arithmetic yields

s^phi(p).t = 1 (mod p)

Multiplying by s

s^{(phi(p).t + 1)} = s (mod p)

Therefore if a secret s was raised to a power n to hash, then the hash can be undone by raising to such a power m so that

phi(p).t + 1 = n.m

(phi(p).t + 1)/n = m

Examples:

p = 11
n = 3

phi(p) = 10
t = 2

phi(p).t + 1 = 21

m = 7

s²¹ mod 11 = s mod 11 (you can easily verify this numerically)

for example

s = 9

s³ mod 11 = 3 = h

h⁷ mod 11 = 9 = s

This proof is holds for s < p. If s > p then it does not hold, but then collisions become unavoidable as k.p + 1 and (k+1).p + 1 will result in the same hash.

At this point one probably will have to change the hash function to h = g^s mod p ( where g is some fixed generator number)

(The problem with this hash function is that it can be computationally intensive)

This would change this attack to a brute force attack that has to solve

h^m = 1 (mod p)

which would mean

g^s.m = 1 (mod p)

And then they would have to use brute force to solve

s = phi(p).t/m

with no remainder

ie phi(p).t mod m = 0

I am not sure how hard this would be

@aliashraf

I agree with what you said. Yes, if (p-1) mod n = 0, it will not be reversible, and I agree that it seems if it is not reversible there are collisions.
We therefore want something with collisions, but as little as possible. This also means that n can be even.

It terms of the collision rate, I think I can help with that.

For h₁ = h₂

s₁ⁿ - s₂ⁿ mod p = 0

If p is prime then it has at most n roots

=> for a hash h, there are at most n secrets that create that hash.

=> brute force search space is reduced to 1/n of its original size

for n = 2

all primes will yield (p-1) mod 2 = 0, it will be reversible and I suspect have collisions (at most 2 per hash)

and the search space will only halve.

@aliashraf

I have updated the paper that I wrote with all the details we have discussed. It summarizes it all together. I will be uploading it soon. As you and empty[g] have provided valuable insights I wish to add you as authors. If you wish to allow this please email me your names and the email I should include and I will update the paper to reflect this.

Regarding the impact of collisions on the homomorphic hashing I included the following in the paper to discuss this:


A large search space is required, but also when choosing n and p to have collisions there should be no obvious double roots to a collision, e.g n = 2, p = 13, s₁ = 4, h₁ = 3, s₂ = 9, h₂ = 3 where -4 mod 13 = 9 => -s₁ mod p = s₂ when n = 2

If you want to find out more about the upper bound of the collisions, please look at Lagrange's Theorem on congruence of polynomials under modulo a prime. I also discuss this in the paper.

nice,
we are almost there...

if xⁿ=P (x is not integer)
i suggest to put x < S < P-x to be sure about the unpredictability of the hash function

also i have read and investigated the subjects have been said in last posts from @johank and @aliashraf , i'm very excited about them and agree with the solution that have been proposed.

johank , you may want choose a 512 bits prime number as p instead of 256 bits for making sure that the reduction of search space needed for brute force attack due the collisions is not that important, but i think even a 256 bits would do for this date we are in.

i also like to hear from you about the operation stage and if you are gonna code the program and etc. i would love to help the coding as much as i can.

about your honorable offer, unlike aliashraf i am new and searching for a name and i would be glad to be mentioned on the paper but i think the credit mainly is for you.
you can contact me at hamun.davarpanah@gmail.com