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

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: empoweoqwj on December 17, 2013, 04:57:02 AM

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.

spooderman

legendary

Activity: 1652

Merit: 1029

pmg!!1 sell att teh bticoines

fghj

member

Activity: 65

Merit: 10

Quote from: Nancarrow on December 17, 2013, 01:22:30 AM

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.

Quote from: coastermonger link=topic=https://bitcointalk.org/index.php?topic=373959.msg4002732#msg4002732

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

Quote

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.

jarhed

sr. member

Activity: 672

Merit: 254

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

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

Edit:

Quote from: LAMarcellus on December 16, 2013, 09:23:38 PM

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.

Gabi

legendary

Activity: 1148

Merit: 1008

If you want to walk on water, get out of the boat

Quote

SHA3

Do you guys trust it?

Kazimir

legendary

Activity: 1176

Merit: 1011

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.

Kazimir

legendary

Activity: 1176

Merit: 1011

Quote from: Come-from-Beyond on December 17, 2013, 05:26:47 AM

Quote from: prezbo on December 17, 2013, 05:05:32 AM

Quote from: TheoryOfBitcoin on December 16, 2013, 09:06:13 PM

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

darlings

full member

Activity: 134

Merit: 100

so mean they can cheat with bitcoin ?

Honeypot

sr. member

Activity: 420

Merit: 250

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

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: prezbo on December 17, 2013, 05:05:32 AM

Quote from: TheoryOfBitcoin on December 16, 2013, 09:06:13 PM

they will be able to double spend transactions

No, they won't.

Yes, they will.

BitThink

legendary

Activity: 882

Merit: 1000

Quote from: TheoryOfBitcoin on December 16, 2013, 09:06:13 PM

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.

prezbo

sr. member

Activity: 430

Merit: 250

Quote from: TheoryOfBitcoin on December 16, 2013, 09:06:13 PM

they will be able to double spend transactions

No, they won't.

Quote from: Nancarrow on December 17, 2013, 01:22:30 AM

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.

empoweoqwj

hero member

Activity: 518

Merit: 500

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

Nancarrow

hero member

Activity: 492

Merit: 503

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.

pand70

sr. member

Activity: 476

Merit: 250

Quote from: TheoryOfBitcoin on December 16, 2013, 09:11:47 PM

Quote from: grue on December 16, 2013, 09:08:44 PM

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

r3wt

hero member

Activity: 686

Merit: 504

always the student, never the master.

Quote from: Piper67 on December 16, 2013, 09:28:33 PM

Quote from: LAMarcellus on December 16, 2013, 09:23:38 PM

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? Grin

exactly why its there.

Piper67

legendary

Activity: 1106

Merit: 1001

Quote from: LAMarcellus on December 16, 2013, 09:23:38 PM

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? Grin

LAMarcellus

full member

Activity: 180

Merit: 100

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.

coastermonger

sr. member

Activity: 367

Merit: 250

Find me at Bitrated

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

TheoryOfBitcoin

newbie

Activity: 38

Merit: 0

Quote from: grue on December 16, 2013, 09:08:44 PM

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"

Topic: Japanese researchers break 41 out of 64 steps of SHA256 with preimage attack. - page 3. (Read 8602 times)