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

[TheoryOfBitcoin]

This affects Bitcoin massively because bitcoin uses SHA256 hashes for transaction IDs and blocks. A preimage attack is when you can find a value that has a specific hash value. For example, when researchers break the full 64 steps of SHA256, they will be able to double spend transactions and mine blocks near infinitely fast.

Here is the paper http://www.scholr.ly/paper/2078146/preimage-attacks-on-41-step-sha-256-and-46-step-sha-512

[grue]

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

[betyourbits]

Kind of interesting even if it is sensationalist.  Something like this might happen at some point and ruin bitcoin in the future.  Maybe we should update to sha512 or 1024 bits or something.

[TheoryOfBitcoin]

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"

[coastermonger]

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

[LAMarcellus]

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.

[Piper67]

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.

The exponential function is a bitch,misn't it? 

[r3wt]

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.

The exponential function is a bitch,misn't it? 

exactly why its there.

[pand70]

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

[Nancarrow]

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.

[empoweoqwj]

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

[prezbo]

they will be able to double spend transactions

No, they won't.

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.

Exactly.

[BitThink]

This affects Bitcoin massively because bitcoin uses SHA256 hashes for transaction IDs and blocks. A preimage attack is when you can find a value that has a specific hash value. For example, when researchers break the full 64 steps of SHA256, they will be able to double spend transactions and mine blocks near infinitely fast.

Here is the paper http://www.scholr.ly/paper/2078146/preimage-attacks-on-41-step-sha-256-and-46-step-sha-512

First, the distance between 41 steps to 64 steps are huge enough to say its useless to break the first 41 steps.

Second, mining is not to find an arbitrary input value to satisfy a specific hash value. In mining, some parts of the input value are determined and the hash value is not determined (it just needs to be smaller than a certain value). The probability for the value you found happens to include the correct block header is almost zero. Therefore, I don't think preimage attack will affect mining speed that much.

[Come-from-Beyond]

they will be able to double spend transactions

No, they won't.

Yes, they will.

[Honeypot]

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

[darlings]

so mean they can cheat with bitcoin ?

[Kazimir]

they will be able to double spend transactions

No, they won't.

Yes, they will.

No, they won't. If you think otherwise, please elaborate (because it's false).

[Kazimir]

1. This does NOT imply SHA256 is broken or less secure in any way.
2. Luckily, Bitcoin uses Double SHA256. No problem whatsoever.

If somebody would break all 64 rounds of SHA256 (which is still lightyears away) we'll still have plenty of time to switch Bitcoin to SHA3.

Oh, and
3. If SHA256 would be broken, unlike Bitcoin most security protocols for other financial ecosystems will be in serious trouble. So this purely theoretical scenario would actually be reason to heavily switch towards Bitcoin, rather than away.

[Gabi]

SHA3

Do you guys trust it?

[jarhed]

Guys, way off topic here.......

So far an interesting read....the thread that is. That vanity-gen post was an eye opener.


Edit:

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.