Japanese researchers break 41 out of 64 steps of SHA256 with preimage attack.

[fghj]

Yawn. I've had the pdf of that paper on my laptop for a couple of years now. Keep rereading, trying to figure out what it's actually saying, every so often. Fascinating stuff but it's hardly 'breaking' SHA256, or even 41 out of 64 rounds of it.

If I understand correctly, they show how collisions can be found on their 'reduced' form of SHA256, in an amount of time that's only a fraction of brute-force time - they shave off a few powers of two, but still a huuuuuuge amount of time. There's an extension of this technique by Jian Guo and Krystian Matusiewicz, which must be downloadable from somewhere as I've got that on my HD too.

No u didn't this 24 rounds paper they reference is from 2012.

Don't tell me you're drawing conclusions from an article just by reading it's title and abstract.  That's an absolute scientific no-no.

Link to full article: http://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.215.5017

This
attack requires 2²⁴⁹ SHA-256 computation and 2¹⁶ · 10 words of memory

That's like 128 times better than brute force. Still billions of times longer than till heat death of universe.
Note that if they refine attack to something usable for type 0 Kardashev civilization we will have to change hash used in building Merkle tree, not POW so ASICs can stay as they are (at least until hashes get reaaaly low). Also I think that all altcoins use SHA256 for transactions.

[1715071292]

1715071292

[1715071292]

1715071292

[spooderman]

pmg!!1 sell att teh bticoines

[DeathAndTaxes]

When the title reads "break 64 out of 64 steps" we need to be upgrade. 41 just isn't relevant.

This = the simple version.

If SHA-256 used 41 rounds then it would technically be broken.   I say technically because the attack requires an asinine amount of computing power and energy.  Granted it is less than brute force but it is kinda like saying you are 35 and I have 85 then I am closer to living to be a thousand years old.  The amount of computing power and time required for this attack means that it would have essentially no useful value although better attacks could be built off this in the future which reduce the time and computing requirements. 

Still SHA-256 doesn't use 41 rounds it uses 64 rounds so there is no vulnerability at this time.

There have been similar "breaks" on reduced round versions of SHA-256 in the past although this one involves the largest number of rounds.

[empoweoqwj]

Who wants to bet NSA already holds this card close and is waiting to spring it once crypto gets out of control?

You probably. Anyone else. I'm not sure.

[Lauda]

Yet another thread to spread FUD.
The exponential function is there for a reason. Good luck with steps 50 and above.

[Buffer Overflow]

Quark promoting FUD thread.
Nothing to see here.

[DeathAndTaxes]

I would also point out this "news" is from 2010.

Still even if this attack worked on the full SHA-2 algorithm the OP conclusion that one could create blocks infinitely fast isn't even close to accurate.

Still lets assume this attack worked on the full version of SHA-2 (64 rounds).  It doesn't so none of this is possible at any amount of time or energy but to illustrate how silly the OP "conclusions" are lets assume this attack does work on the full SHA-2.

Today mining has a difficulty of ~900 million.  That means it takes 3.86547E+12 (900 million * 2^32) hashes on average to solve a block.  To put it into cryptographic terms that is a complexity of 2^72.
Attempting a preimage attack of an existing SHA-256 hash by brute force has a complexity of 2^256.  So if you wanted to replace a block in the middle of the blockchain by brute force would require 2^256 attempts.  That is why we consider blocks deep in the blockchain "safe" because it is infeasible to replace a block by preimage.  Now an attacker can always build a longer chain to replace a block but that the deeper the block is the less probable that becomes (without 51% of hashrate).

So as a theoretical concept you can already replace a block in the blockchain it just requires an amount of energy and time that is beyond the life of our star.  So how much does this attack improve that equation?
This attack has a complexity of 2^253.5.  That's right 2 raised to the 253 1/2 instead of 256.   So it is a staggering 5.6 times easier than a (for all practical purposes impossible) brute force attack  [ 2^(256 - 253.5) ]. It is still 4.33455E+54 (that is 4 followed by 53 zeros) times harder than solo mining a block at difficulty 900 million [ 2^(253.5 - 72) ].  If the entire blockchain from the genesis block till today was all difficulty 900 million then the complexity of replacing the entire blockchain with a new one would be 2^90.  So for any amount of computing power in the time it takes to preimage a single block or transaction (2^253.5) one could mine 16,535,003,495,550,700,000,000,000,000,000,000,000,000,000,000,000 complete unique alternate copies of the Bitcoin blockchain.

In mining terms for someone to preimage a block in 600 seconds would require 34,115,571,461,443,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 PH/s of computing power.

Summary:
This attack doesn't have any effect on the full (64 round) SHA-2 hash function.  Researchers work on reduced round versions of algorithms because they are easier to break and it allows learning and progress which in theory someday over the course of years and decades could lead to an attack on the full algorithm.  This isn't anything new or novel.  There are at least 8 papers outlining similar theoretical attacks on reduced round versions of SHA-2.  Also the OP is an idiot if he think "heat death of the universe" = "instantly mine blocks".

[empoweoqwj]

Also I would point out this "news" is from 2010.

So they are up to 42 now then

[DeathAndTaxes]

Also I would point out this "news" is from 2010.

So they are up to 42 now then

Something like that. 

Everyone panic, IIRC in some limited applications the highest attack is on a 45 or 46 rounds.   

Attacks like those (with complexity of 2^120 or higher) can be considered impossible to implement.  The attack with practical complexity (in theory could be built in our lifetime at insane cost) is 24 rounds.  I am away from my home computer which has a folder of research articles so I am going off memory on those two records.

[prezbo]

I would also point out this "news" is from 2010.

Still even if this attack worked on the full SHA-2 algorithm the OP conclusion that one could create blocks infinitely fast isn't even close to accurate.

Still lets assume this attack worked on the full version of SHA-2 (64 rounds).  It doesn't so none of this is possible at any amount of time or energy but to illustrate how silly the OP "conclusions" are lets assume this attack does work on the full SHA-2.

Today mining has a difficulty of ~900 million.  That means it takes 3.86547E+12 (900 million * 2^32) hashes on average to solve a block.  To put it into cryptographic that is a complexity of 2^72.
Attempting a preimage attack of an existing SHA-256 hash by brute force has a complexity of 2^256.  So if you wanted to replace a block in the middle of the blockchain by brute force would require 2^256 attempts.  That is why we consider blocks deep in the blockchain "safe" because you can't replace a block by preimage you have to solve an entire chain longer than the good one.

So how much does this attack improve that equation?
This attack has a complexity of 2^253.5 vs 2^256 by brute force.  So it is a staggering 5.6 times easier than a brute force attack  [ 2^(256 - 253.5) ].
However it is still 4.33455E+54 (thats 4 followed by 53 zeros) times harder than solving a block at difficulty 900 million [ 2^(253.5 - 72) ].

If the entire blockchain from the genesis block till today was difficulty 900 million then the complexity of replacing the entire blockchain with a new one would be 2^90.  

So for a given amount of computing power in the time it takes to preimage a single block or transaction (2^253.5) one could mine 16,535,003,495,550,700,000,000,000,000,000,000,000,000,000,000,000 unique alternate copies of the entire Bitcoin blockchain.

In mining terms that would be someone with 34,115,571,461,443,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 PH/s on computing power.

Summary:
This attack doesn't have any effect on the full (64 round) SHA-2 hash function.  Researchers work on reduced round versions of algorithms because they are easier to break and it allows learning and progress.  This isn't anything new or novel.  There are at least 8 papers outlining similar theoretical attacks on reduced round versions of SHA-2.  Also the OP is an idiot if he think "heat death of the universe" = "instantly mine blocks".

If this were on reddit I'd give you gold It's funny how everyone thinks such attacks "break cryptography" but no one ever even checks the new (reduced) time complexities, they just somehow infer it's O(1).

[Piper67]

I would also point out this "news" is from 2010.

Still even if this attack worked on the full SHA-2 algorithm the OP conclusion that one could create blocks infinitely fast isn't even close to accurate.

Still lets assume this attack worked on the full version of SHA-2 (64 rounds).  It doesn't so none of this is possible at any amount of time or energy but to illustrate how silly the OP "conclusions" are lets assume this attack does work on the full SHA-2.

Today mining has a difficulty of ~900 million.  That means it takes 3.86547E+12 (900 million * 2^32) hashes on average to solve a block.  To put it into cryptographic that is a complexity of 2^72.
Attempting a preimage attack of an existing SHA-256 hash by brute force has a complexity of 2^256.  So if you wanted to replace a block in the middle of the blockchain by brute force would require 2^256 attempts.  That is why we consider blocks deep in the blockchain "safe" because you can't replace a block by preimage you have to solve an entire chain longer than the good one.

So how much does this attack improve that equation?
This attack has a complexity of 2^253.5 vs 2^256 by brute force.  So it is a staggering 5.6 times easier than a brute force attack  [ 2^(256 - 253.5) ].
However it is still 4.33455E+54 (thats 4 followed by 53 zeros) times harder than solving a block at difficulty 900 million [ 2^(253.5 - 72) ].

If the entire blockchain from the genesis block till today was difficulty 900 million then the complexity of replacing the entire blockchain with a new one would be 2^90.  

So for a given amount of computing power in the time it takes to preimage a single block or transaction (2^253.5) one could mine 16,535,003,495,550,700,000,000,000,000,000,000,000,000,000,000,000 unique alternate copies of the entire Bitcoin blockchain.

In mining terms that would be someone with 34,115,571,461,443,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 PH/s on computing power.

Summary:
This attack doesn't have any effect on the full (64 round) SHA-2 hash function.  Researchers work on reduced round versions of algorithms because they are easier to break and it allows learning and progress.  This isn't anything new or novel.  There are at least 8 papers outlining similar theoretical attacks on reduced round versions of SHA-2.  Also the OP is an idiot if he think "heat death of the universe" = "instantly mine blocks".

If this were on reddit I'd give you gold It's funny how everyone thinks such attacks "break cryptography" but no one ever even checks the new (reduced) time complexities, they just somehow infer it's O(1).

Also, if the cryptography was truly broken, the world of pain we'd find ourselves in would make any issues with Bitcoin a far distant memory...

[seriouscoin]

Only QRK gonna survive the crypto attacks

  really? noob?

[Tirapon]

Title: Japanese researchers break 41 out of 64 steps of SHA256 with preimage attack.
Abstract: In this paper, we propose preimage attacks [...]

sensationalist 6/10

Do you not understand all scientific papers use propose?

Propose as in "You can do it this way that we discovered"

Not propose as in "We think"

I think he means that you should evaluate the actual preimage attack that they propose before saying that they broke it.
I mean i can propose an attack: Search for all the possible keys one by one... This is a nice theoretical attack but has no value in the real world...

You could make a start on this attack by convincing people to pool their resources, perhaps by offering a financial incentive (maybe some bitcoins for contributing computing power)? People could even work on creating some sort of application specific hardware to efficiently search for SHA-256 hash values. You could structure it so that rewards are payed out proportionally to each persons contribution.

[DeathAndTaxes]

Title: Japanese researchers break 41 out of 64 steps of SHA256 with preimage attack.
Abstract: In this paper, we propose preimage attacks [...]

sensationalist 6/10

Do you not understand all scientific papers use propose?

Propose as in "You can do it this way that we discovered"

Not propose as in "We think"

I think he means that you should evaluate the actual preimage attack that they propose before saying that they broke it.
I mean i can propose an attack: Search for all the possible keys one by one... This is a nice theoretical attack but has no value in the real world...

You could make a start on this attack by convincing people to pool their resources, perhaps by offering a financial incentive (maybe some bitcoins for contributing computing power)? People could even work on creating some sort of application specific hardware to efficiently search for SHA-256 hash values. You could structure it so that rewards are payed out proportionally to each persons contribution.

You "could" if you made computers out of something other than matter and they occupied something other than space.

[empoweoqwj]

Title: Japanese researchers break 41 out of 64 steps of SHA256 with preimage attack.
Abstract: In this paper, we propose preimage attacks [...]

sensationalist 6/10

Do you not understand all scientific papers use propose?

Propose as in "You can do it this way that we discovered"

Not propose as in "We think"

I think he means that you should evaluate the actual preimage attack that they propose before saying that they broke it.
I mean i can propose an attack: Search for all the possible keys one by one... This is a nice theoretical attack but has no value in the real world...

You could make a start on this attack by convincing people to pool their resources, perhaps by offering a financial incentive (maybe some bitcoins for contributing computing power)? People could even work on creating some sort of application specific hardware to efficiently search for SHA-256 hash values. You could structure it so that rewards are payed out proportionally to each persons contribution.

You make this stuff up as you type right?

[Dabs]

You could make a start on this attack by convincing people to pool their resources, perhaps by offering a financial incentive (maybe some bitcoins for contributing computing power)? People could even work on creating some sort of application specific hardware to efficiently search for SHA-256 hash values. You could structure it so that rewards are payed out proportionally to each persons contribution.

Hahahahahaahah... mining.

Let's pretend it's 3 steps additional per year.

2010 = 41
2011 = 44
2012 = 47
2013 = 50
2014 = 53
2015 = 56
2016 = 59
2017 = 62
2018 = 65 (cracked, broken, whatever.)

We have several years to do something about it.

But, this isn't going to happen.

[BittBurger]

I can use Vanity Gen to match 8 out of 32 letters in under 12 hours. 9 letters takes 2 days.  10 letters takes 4 months. 11 letters takes 2 years. 12 letters takes 10 years. 13 letters takes.....
Steps 1-41 is not 2/3rds.  Steps 1-41 are the easiest. They can't get past 42. And 43 will be doubly difficult as 42 was.   Step 42-64 take orders of magnitude longer to crack than 1-41 did.  They got the first 10 years worth done. Now the nheed to get the next 2 billion worth done, in steps 42-64.

Repeating this.

Thread can be closed now.  This responds to the original post.  And newbies need not fret.

-Burger-

[empoweoqwj]

You could make a start on this attack by convincing people to pool their resources, perhaps by offering a financial incentive (maybe some bitcoins for contributing computing power)? People could even work on creating some sort of application specific hardware to efficiently search for SHA-256 hash values. You could structure it so that rewards are payed out proportionally to each persons contribution.

Hahahahahaahah... mining.

Let's pretend it's 3 steps additional per year.

2010 = 41
2011 = 44
2012 = 47
2013 = 50
2014 = 53
2015 = 56
2016 = 59
2017 = 62
2018 = 65 (cracked, broken, whatever.)

We have several years to do something about it.

But, this isn't going to happen.

That's not how it works .... its an elliptical curve ............ its not incremental steps.

[Soros Shorts]

A lot of other things in the world would be more critically impacted than Bitcoin if SHA-256 were broken. Finding some random preimage of a SHA-256 hash is just one of the many steps needed in order to do a double spend. However, it is probably the only step needed to break into bank accounts if you already had a DB dump of userids and hashed passwords. Guess which one a crook would rather do?

[Dabs]

That's not how it works .... its an elliptical curve ............ its not incremental steps.

I know, right? So my "forecast" is too good to be true. Reality is worse. Don't worry about your 0.01 bitcoins, no one is going to take them.