The Sha256 Algorithm | Bitcointalksearch.org

AliceWonder

full member

Activity: 168

Merit: 100

Quote from: kokjo on June 26, 2013, 02:04:07 PM

So the question is if that sha256 is a bijective map between the set of numbers under 2^256 to itself?

i don't know, but my guess would be that its not.

I would guess not, that some valid numbers can not be obtained by hashing valid numbers while others have collissions.
But I don't know.

kokjo

legendary

Activity: 1050

Merit: 1000

You are WRONG!

So the question is if that sha256 is a bijective map between the set of numbers under 2^256 to itself?

i don't know, but my guess would be that its not.

stelmoi

newbie

Activity: 14

Merit: 0

Quote from: sliding scale on June 26, 2013, 01:58:28 PM

So we just switch over to a new crypto and everything is OK? We don't loose any coins?

It would be a hard fork, and those are not easy. But possible if the majority of miners agree.

sliding scale

newbie

Activity: 14

Merit: 0

Quote from: r3wt on June 25, 2013, 12:34:53 PM

Quote from: ARGpentem on June 25, 2013, 12:32:46 PM

wait so what happens when it is cracked Huh

we start using sha 512, Whirlpool-T or my personal favorite, Gost

So we just switch over to a new crypto and everything is OK? We don't loose any coins?

stelmoi

newbie

Activity: 14

Merit: 0

Quote from: r3wt on June 25, 2013, 12:34:53 PM

Quote from: ARGpentem on June 25, 2013, 12:32:46 PM

wait so what happens when it is cracked Huh

we start using sha 512, Whirlpool-T or my personal favorite, Gost

Maybe someone will start testing these with Whirlpoolcoin and Gostcoin ? Roll Eyes

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: qplayer on June 25, 2013, 03:42:13 PM

Quote from: erasmas on June 25, 2013, 12:00:43 PM

Quote from: DannyHamilton on June 25, 2013, 11:36:25 AM

Quote from: zemario on June 25, 2013, 11:24:47 AM

Quote from: DannyHamilton on June 25, 2013, 11:10:36 AM

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:
- snip -

Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.

Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.

hash(100) results in a value of 200
hash(400) results in a value of 200

This would mean there is a collision i.e hash(100) = hash(400)

Obviously. Given an infinite source, collisions will have to occur eventually in the solution. It can't be avoided.

Quote from: qplayer on June 25, 2013, 03:42:13 PM

I think either the loop would terminate for some value of C less than 2^256 or it would not terminate, meaning there was a collison in the sha256

Agreed, either:

sha256(y) would collide with an earlier iteration of sha256(y) creating a loop that would never terminate
sha256(y) would collide with sha256("abc") creating a loop that would terminate before C = 2²⁵⁶+1

I suppose it is possible that you could encounter every possible value between 0 and 2²⁵⁶-1. If that were to happen, then at C = 2²⁵⁶+1 you would either have to collide with an earlier value (since there are no values left that haven't been generated), or with sha256("abc"). I doubt the result set is that perfectly distributed, but I've not seen anything that says it can't be.

qplayer

newbie

Activity: 5

Merit: 0

Quote from: erasmas on June 25, 2013, 12:00:43 PM

Quote from: DannyHamilton on June 25, 2013, 11:36:25 AM

Quote from: zemario on June 25, 2013, 11:24:47 AM

Quote from: DannyHamilton on June 25, 2013, 11:10:36 AM

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999. Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function. Now imagine that he function results in the following particular results:

hash('abc') results in a value of 100
hash(100) results in a value of 200
hash(200) results in a value of 300
hash(300) results in a value of 400
hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit. It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc. It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.

Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.

hash(100) results in a value of 200
hash(400) results in a value of 200

This would mean there is a collision i.e hash(100) = hash(400)

I think either the loop would terminate for some value of C less than 2^256 or it would not terminate, meaning there was a collison in the sha256

zemario

full member

Activity: 194

Merit: 100

Quote from: DannyHamilton on June 25, 2013, 11:36:25 AM

Quote from: zemario on June 25, 2013, 11:24:47 AM

Quote from: DannyHamilton on June 25, 2013, 11:10:36 AM

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999. Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function. Now imagine that he function results in the following particular results:

hash('abc') results in a value of 100
hash(100) results in a value of 200
hash(200) results in a value of 300
hash(300) results in a value of 400
hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit. It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc. It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

You are right, I overlooked the code and assumed it was a trivial brute-forcer.
One thing we know, by hashing the output of an hash we are limiting the the input to a finite set, this, in theory, a brute force would require less iterations.

r3wt

hero member

Activity: 686

Merit: 504

always the student, never the master.

Quote from: ARGpentem on June 25, 2013, 12:32:46 PM

wait so what happens when it is cracked Huh

we start using sha 512, Whirlpool-T or my personal favorite, Gost

ARGpentem

full member

Activity: 154

Merit: 100

wait so what happens when it is cracked Huh

erasmas

newbie

Activity: 1

Merit: 0

Quote from: DannyHamilton on June 25, 2013, 11:36:25 AM

Quote from: zemario on June 25, 2013, 11:24:47 AM

Quote from: DannyHamilton on June 25, 2013, 11:10:36 AM

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999. Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function. Now imagine that he function results in the following particular results:

hash('abc') results in a value of 100
hash(100) results in a value of 200
hash(200) results in a value of 300
hash(300) results in a value of 400
hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit. It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc. It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.

Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: zemario on June 25, 2013, 11:24:47 AM

Quote from: DannyHamilton on June 25, 2013, 11:10:36 AM

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999. Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function. Now imagine that he function results in the following particular results:

hash('abc') results in a value of 100
hash(100) results in a value of 200
hash(200) results in a value of 300
hash(300) results in a value of 400
hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit. It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc. It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

zemario

full member

Activity: 194

Merit: 100

Quote from: DannyHamilton on June 25, 2013, 11:10:36 AM

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite. 'Finite' doesn't mean that is ridiculously large, which it is.

If the computing power is infinite than that program would terminate immediately. But there is no such thing as 'infinite computing power'.
In practice that method is won't get you anywhere. The technology is nowhere near to break that.

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: qplayer on June 25, 2013, 06:09:32 AM

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: jackthebeanstalk on June 25, 2013, 06:23:17 AM

I don't see how it is not safe, it is not supposed to be cracked for another 30 years.

There is a schedule for cracking SHA-256?
Huh

jackthebeanstalk

newbie

Activity: 52

Merit: 0

I don't see how it is not safe, it is not supposed to be cracked for another 30 years.

qplayer

newbie

Activity: 5

Merit: 0

I was wondering why bitcoin uses Sha256(Sha256()) instead of sha256() . Is it because the hashing algorithm is not considered safe?

If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?

y = "abc"
C = 0
y = sha256(y)
y = sha256(y)

do loop until y = sha256("abc")
{
y = sha256(y)
C = C + 1
}

Print c

Topic: The Sha256 Algorithm (Read 973 times)