Anonymous Atomic Swaps Using Homomorphic Hashing

[empty[g]]

Hi

Just thought I might share this. It is a simple attack, that the following proof shows will not work

h = sⁿ mod p

Assume an attacker want to find a power m such that

h^m mod p = s

=> s = s^(n.m) mod p

=> s^(n.m) - s = 0 (mod p)

The attacker would have to solve the above congruence.

Using the theorem from my previous post, this implies that the congruence can be factorized to yield

s.(s^(n.m-1) - 1)

This yields roots s = 0, s = 1 and possibly s = -1 for all values of n and m

Therefore for s > 1 there are no values of m that can be used to determine the pre-image s from the hash h.

i think your answer to this attack is right, maybe not complete but right.
it is not possible to determine a 'm' that works regardless of 's' with only having h(s)
i don't see how collisions effect this.

-----------

also don't be disappointed with collisions problem, i have found 46337 as a prime number without collisions for n=3 with brute force
i suggest that if you can find a way to determine if a prime number has collisions or not WITHOUT brute force the problem is solved.(as we need a large number that denies the possibility of brute force and it is not wise to determine itself with brute force  )

[1713975194]

1713975194

[1713975194]

1713975194

[1713975194]

1713975194

[1713975194]

1713975194

[johank]

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]

@johank
I think we are not done with your proposal yet, despite your suggested inverse attack which is based on finding at least one pair of (t,m) such that (p-1)*t+1=n.m or m = ((p-1)*t + 1)/n and using m to find s=h(s)^m mod p.

You can note that the equation has no integer roots if p-1 mod n = 0  or (p-1)/n = k
((p-1)*t+1)/n = m    ==>   (p-1)*t/n + 1/n = m    ==>   m= kt+1/n
so if we choose p and n such that n divides p-1 the hash function h(s) = sⁿ mod p is irreversible.

Now here is another interesting  problem:
For a prime number p and an odd number n, when such a number m can not be found to commit an inverse attack on h it seems that we have a hash function with collision! For example with n= 3 and p = 13 there is no m and inverse function but we have collision!

I suggest that analysing the collision rate may still imply good enough security for large prime numbers.

[johank]

@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]

@johank

If you are right about the number of collisions having an upper bound of n, choosing n slightly bigger is more appropriate to have more discontinuities and jumps hence more resistance to heuristic attacks  like what I suggested primarily up-thread.

For example putting n = 6 with a search space of 2²⁵⁵/3 height, is practically the same as ²⁵⁵ for n=2, both being computationally hard and won't be broken in real time.

I think it is time for you (or @empty[g]) to put everything together once again and give a solid mathematical presentation and proof of the homomorphic hash function:   h(s)=sⁿ mod p

I'm not convinced about the collision rate to be n by the way.

[johank]

@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:

The presence of collisions has implications for the homomorphic feature of the proposed hash function. Specifically a hash can have more than one secret. This implies that equation 7 can have multiple solutions.
If Alice is able to determine two secrets that have the same hash, she can use the one to generate hashes and sums to send to Bob, but use the other secret to unlock the coins Bob sent to her. This will stop Bob from being able to solve equation 5 correctly and unable to claim his coins. After a time delay Alice will then claim the coins.
This increases the requirement for a large search space. An attacker must not be able to determine any of the secrets that generate the same hash except using brute force.

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.

[aliashraf]

@johank
From my side, all the credits go to you though @empty[g]'s contribution was very helpful  , thanks anyway. 

And you are right Lagrange's theorem definitively proves the rate of collisions being bounded by n and choosing a properly small n (I suggest 6) with a large prime p will make it computationally infeasible to find a collision.

I have to emphasis on using n>>2 to mitigate heuristic attacks. Once you have finished  the final version, please keep me informed, we should take care of implementation issues next.

[empty[g]]

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

[johank]

@aliashraf

The paper is ready with the updates. I have uploaded it to SSRN, but the review can take anything from 1 to 14 days. If you require a copy sooner, please contact myself on the email on the original paper or empty[g] on the email provided above. I have sent him a copy of the paper that I have uploaded.