Bitcoin Forum
June 20, 2021, 10:45:38 PM
 News: Latest Bitcoin Core release: 0.21.1 [Torrent]
 Home Help Search Login Register More
 Pages: 1 [2]  All
 Author Topic: Anonymous Atomic Swaps Using Homomorphic Hashing  (Read 1042 times)
empty[g]
Newbie

Offline

Activity: 7
Merit: 11

 September 06, 2018, 09:50:52 AM

Hi

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

h = sn mod p

Assume an attacker want to find a power m such that

hm 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  )
1624229138
Hero Member

Offline

Posts: 1624229138

Ignore
 1624229138

1624229138
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
johank
Newbie

Offline

Activity: 14
Merit: 148

 September 06, 2018, 11:34:29 AMLast edit: September 06, 2018, 12:14:42 PM by 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

sphi(p) = 1 (mod p)

Raising to a power t using modular arithmetic yields

sphi(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

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

for example

s = 9

s3 mod 11 = 3 = h

h7 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 = gs 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

hm = 1 (mod p)

which would mean

gs.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
Legendary

Offline

Activity: 1344
Merit: 1025

Always remember the cause!

 September 06, 2018, 10:05:36 PMLast edit: September 06, 2018, 10:17:27 PM by aliashrafMerited by ETFbitcoin (1), empty[g] (1)

@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) = sn 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.

 ▄██▄   ▄██▄      ▀█▀▀     ▄██▄   ▀██▀▄  ▄▄█████▄▄  ▐███▀       ███████████████      ████████▀▄▄▄▀████ ▄▄  ▐███▀▄▀██▄▀▀▀▄█████  ▄▄████▀█████▄███▀▀█████ ██▀████ ▀▀  ▐███▄███ ██ ████ █▌  ▀▀      ▀████▄██▄▄███▀▄█▀    ▄▄ █▀██████▀▄▄▄█▀█ ▄▄   ████▀   ▀▀▀█▀▀▀   ▐████    ▀▀       ▄██▄      ▀▀             ▀██▀ ..P R O J E C T........Covid-19...... ⟩ ⟩ ⟩ ▄▄▄  ▄▄▄▄▄▄▄▄▄▄█   █▄ █           ▀▀▀  █ ▀▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▀▄▀▀ ▄▄▄▄▄▄▄▄▄▄▄▄ ▀▀▄█ ▄▀ ▄▄▄▄▄▄▄    ▀█ ██ █ █       █    █ ▄█ █ ▄▀▀▀▀▀▀▄▄    █ ██ █ ▀▄▄▄▄▀▀▄▄▀▀▄ █ ██ █ █   █  ██  █ █ ██ █ ▄▀▀▀▀▄▄▀▀▄▄▀ █ ██ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ █ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ A FINANCIAL AID ────███████  Only for Bitcointalk Users! ⟩ ⟩ ⟩ ▄████▄  ▄████▄      ████████████████      ████████████████       ██████████████        ▀██████████▀██        ▀██████▀        ████▌   ▄      ▀▀      ▄   ▐█████  ███▄          ▄███  ███▀███▄ ▀███▄      ▄███▀ ▄███▀  ▀████████      ████████▀     ▀████▀      ▀████▀     ▄   ▄▄      ▄▄   ▄     ▀█████      █████▀ You AreNot Alone
johank
Newbie

Offline

Activity: 14
Merit: 148

 September 07, 2018, 08:36:57 AMMerited by ETFbitcoin (1), empty[g] (1)

@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 h1 = h2

s1n - s2n 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
Legendary

Offline

Activity: 1344
Merit: 1025

Always remember the cause!

 September 07, 2018, 10:10:08 AMLast edit: September 07, 2018, 12:29:38 PM by 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 2255/3 height, is practically the same as 255 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)=sn mod p

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

 ▄██▄   ▄██▄      ▀█▀▀     ▄██▄   ▀██▀▄  ▄▄█████▄▄  ▐███▀       ███████████████      ████████▀▄▄▄▀████ ▄▄  ▐███▀▄▀██▄▀▀▀▄█████  ▄▄████▀█████▄███▀▀█████ ██▀████ ▀▀  ▐███▄███ ██ ████ █▌  ▀▀      ▀████▄██▄▄███▀▄█▀    ▄▄ █▀██████▀▄▄▄█▀█ ▄▄   ████▀   ▀▀▀█▀▀▀   ▐████    ▀▀       ▄██▄      ▀▀             ▀██▀ ..P R O J E C T........Covid-19...... ⟩ ⟩ ⟩ ▄▄▄  ▄▄▄▄▄▄▄▄▄▄█   █▄ █           ▀▀▀  █ ▀▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▀▄▀▀ ▄▄▄▄▄▄▄▄▄▄▄▄ ▀▀▄█ ▄▀ ▄▄▄▄▄▄▄    ▀█ ██ █ █       █    █ ▄█ █ ▄▀▀▀▀▀▀▄▄    █ ██ █ ▀▄▄▄▄▀▀▄▄▀▀▄ █ ██ █ █   █  ██  █ █ ██ █ ▄▀▀▀▀▄▄▀▀▄▄▀ █ ██ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ █ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ A FINANCIAL AID ────███████  Only for Bitcointalk Users! ⟩ ⟩ ⟩ ▄████▄  ▄████▄      ████████████████      ████████████████       ██████████████        ▀██████████▀██        ▀██████▀        ████▌   ▄      ▀▀      ▄   ▐█████  ███▄          ▄███  ███▀███▄ ▀███▄      ▄███▀ ▄███▀  ▀████████      ████████▀     ▀████▀      ▀████▀     ▄   ▄▄      ▄▄   ▄     ▀█████      █████▀ You AreNot Alone
johank
Newbie

Offline

Activity: 14
Merit: 148

 September 07, 2018, 04:26:41 PMMerited by ETFbitcoin (1)

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

Quote
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, s1 = 4, h1 = 3, s2 = 9, h2 = 3 where -4 mod 13 = 9 => -s1 mod p = s2 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
Legendary

Offline

Activity: 1344
Merit: 1025

Always remember the cause!

 September 07, 2018, 07:22:21 PM

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

 ▄██▄   ▄██▄      ▀█▀▀     ▄██▄   ▀██▀▄  ▄▄█████▄▄  ▐███▀       ███████████████      ████████▀▄▄▄▀████ ▄▄  ▐███▀▄▀██▄▀▀▀▄█████  ▄▄████▀█████▄███▀▀█████ ██▀████ ▀▀  ▐███▄███ ██ ████ █▌  ▀▀      ▀████▄██▄▄███▀▄█▀    ▄▄ █▀██████▀▄▄▄█▀█ ▄▄   ████▀   ▀▀▀█▀▀▀   ▐████    ▀▀       ▄██▄      ▀▀             ▀██▀ ..P R O J E C T........Covid-19...... ⟩ ⟩ ⟩ ▄▄▄  ▄▄▄▄▄▄▄▄▄▄█   █▄ █           ▀▀▀  █ ▀▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▀▄▀▀ ▄▄▄▄▄▄▄▄▄▄▄▄ ▀▀▄█ ▄▀ ▄▄▄▄▄▄▄    ▀█ ██ █ █       █    █ ▄█ █ ▄▀▀▀▀▀▀▄▄    █ ██ █ ▀▄▄▄▄▀▀▄▄▀▀▄ █ ██ █ █   █  ██  █ █ ██ █ ▄▀▀▀▀▄▄▀▀▄▄▀ █ ██ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ █ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ A FINANCIAL AID ────███████  Only for Bitcointalk Users! ⟩ ⟩ ⟩ ▄████▄  ▄████▄      ████████████████      ████████████████       ██████████████        ▀██████████▀██        ▀██████▀        ████▌   ▄      ▀▀      ▄   ▐█████  ███▄          ▄███  ███▀███▄ ▀███▄      ▄███▀ ▄███▀  ▀████████      ████████▀     ▀████▀      ▀████▀     ▄   ▄▄      ▄▄   ▄     ▀█████      █████▀ You AreNot Alone
empty[g]
Newbie

Offline

Activity: 7
Merit: 11

 September 08, 2018, 06:26:43 AM

nice,
we are almost there...

if xn=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
Newbie

Offline

Activity: 14
Merit: 148

 September 09, 2018, 03:24:04 PM

@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.
 Pages: 1 [2]  All