Title: The Sha256 Algorithm Post by: qplayer on June 25, 2013, 11:09:32 AM 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 Title: Re: The Sha256 Algorithm Post by: jackthebeanstalk on June 25, 2013, 11:23:17 AM I don't see how it is not safe, it is not supposed to be cracked for another 30 years.
Title: Re: The Sha256 Algorithm Post by: DannyHamilton on June 25, 2013, 04:07:11 PM 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? ??? Title: Re: The Sha256 Algorithm Post by: DannyHamilton on June 25, 2013, 04:10:36 PM - 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. Title: Re: The Sha256 Algorithm Post by: zemario on June 25, 2013, 04:24:47 PM - 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. Title: Re: The Sha256 Algorithm Post by: DannyHamilton on June 25, 2013, 04:36:25 PM - 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.If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? - snip - 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:
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. Title: Re: The Sha256 Algorithm Post by: erasmas on June 25, 2013, 05:00:43 PM - 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.If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? - snip - 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:
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. Title: Re: The Sha256 Algorithm Post by: ARGpentem on June 25, 2013, 05:32:46 PM wait so what happens when it is cracked ???
Title: Re: The Sha256 Algorithm Post by: r3wt on June 25, 2013, 05:34:53 PM wait so what happens when it is cracked ??? we start using sha 512, Whirlpool-T or my personal favorite, Gost Title: Re: The Sha256 Algorithm Post by: zemario on June 25, 2013, 07:50:52 PM - 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.If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? - snip - 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:
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. Title: Re: The Sha256 Algorithm Post by: qplayer on June 25, 2013, 08:42:13 PM - 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.If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? - snip - 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:
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.
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 Title: Re: The Sha256 Algorithm Post by: DannyHamilton on June 25, 2013, 11:58:16 PM - 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.If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? - snip - 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 - Here's an extreme example: - snip - 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.
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. 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:
I suppose it is possible that you could encounter every possible value between 0 and 2256-1. If that were to happen, then at C = 2256+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. Title: Re: The Sha256 Algorithm Post by: stelmoi on June 26, 2013, 06:55:20 PM wait so what happens when it is cracked ??? we start using sha 512, Whirlpool-T or my personal favorite, GostMaybe someone will start testing these with Whirlpoolcoin and Gostcoin ? ::) Title: Re: The Sha256 Algorithm Post by: sliding scale on June 26, 2013, 06:58:28 PM wait so what happens when it is cracked ??? 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? Title: Re: The Sha256 Algorithm Post by: stelmoi on June 26, 2013, 07:00:32 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. Title: Re: The Sha256 Algorithm Post by: kokjo on June 26, 2013, 07: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. Title: Re: The Sha256 Algorithm Post by: AliceWonder on June 26, 2013, 07:07:22 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. |