Guy on twitter claims he is working on hash method without brute force.

[zby]

relatively little research has been done on the subproblem of sha256 compromise on which bitcoin's security depends. it is not the same problem as one-to-one collisions (i.e., an outright compromise of the function). in the general case, it cannot be determined whether finding a result that corresponds to a pattern that matches x out of 2^256 hashes is indeed no more than x times easier than forcing a one-to-one collision. there are reasons to think that in bitcoin's particular case, it is just about that easy and thus that bitcoin's use of sha256 in mining is secure - but to my knowledge that hasn't been proven.

I would be surprised if there were no results showing how to mine faster.  The statement that the current algorithm is the fastest one of all possible is rather strong.

[1713870668]

1713870668

[1713870668]

1713870668

[1713870668]

1713870668

[grue]

this is going to turn out just like the may doomsday. once it flops, the guy is just going to vanish.

[Quantumplation]

this is going to turn out just like the may doomsday. once it flops, the guy is just going to vanish.

BitRapture.

[Mike Hearn]

Yes, I asked Yu Sasaki specifically about the problem of finding a partial pre-image rather than a full pre-image. She didn't seem to think it would make things any easier. I don't think we can do better than this for now. If there's a weakness in (double) SHA256 that would make it easier to solve the problem Bitcoin uses I guess there will be an academic paper on it eventually.

[FreeMoney]

Yes, I asked Yu Sasaki specifically about the problem of finding a partial pre-image rather than a full pre-image. She didn't seem to think it would make things any easier. I don't think we can do better than this for now. If there's a weakness in (double) SHA256 that would make it easier to solve the problem Bitcoin uses I guess there will be an academic paper on it eventually.

Is it right that it won't be a problem if it becomes a thousand or a million times easier to solve? People will just switch to the better algo and difficulty will increase like when we moved to GPUs.

[cloud9]

As soon as it can be done, and everybody knows it can be done, and everybody want to do that, some other people will also find a way to do that and if it becomes open source (just like the gpu miner) - everybody will be doing that and the network hash rate will just supercharge as it did when graphics card mining were introduce - and the system will balance itself around the new competition factor - even securing the system even more against an attacker not using such a hash algorithm (if it exists!!!  )

[FreeMoney]

That's what I thought, so SHA256 needs to completely break to be a problem for Bitcoin?

[gigitrix]

Yeah, because hacking billions from banks and pretty much every website using SHA256 wasn't enough incentive, clearly it takes bitcoin to get SHA256 attacking investigated 

[unk]

i'm curious what you think you could do to most 'banks' with a compromise of sha-2. more readily mount a phishing attack by spoofing an ssl certificate? sneak into their datacenter, figure out how they handle internal integrity checks, and then spoof those checks after injecting your own data?

[bittrader]

If I'm not mistaken, most effort has gone into "single" SHA256, and though the composition of SHA256 operations would seem harder to crack, one never knows.

SHA256 allows an attacker to create a hash that corresponds to [your message w/padding] + [his own message] without having to know what [your message] was. This could be a serious vulnerability for some (incorrect) applications of SHA256. Double hashing prevents this attack.

[Quantumplation]

If I'm not mistaken, most effort has gone into "single" SHA256, and though the composition of SHA256 operations would seem harder to crack, one never knows.

SHA256 allows an attacker to create a hash that corresponds to [your message w/padding] + [his own message] without having to know what [your message] was. This could be a serious vulnerability for some (incorrect) applications of SHA256. Double hashing prevents this attack.

Really?  I thought that was only on SHA1 or MD5...

[wumpus]

If I'm not mistaken, most effort has gone into "single" SHA256, and though the composition of SHA256 operations would seem harder to crack, one never knows.

SHA256 allows an attacker to create a hash that corresponds to [your message w/padding] + [his own message] without having to know what [your message] was. This could be a serious vulnerability for some (incorrect) applications of SHA256. Double hashing prevents this attack.

Really?  I thought that was only on SHA1 or MD5...

Also for SHA256, see the algorithm:
https://secure.wikimedia.org/wikipedia/en/wiki/SHA-2#SHA-256_.28a_SHA-2_variant.29_pseudocode

a-h represent the hasher state, and they're all concatenated to form the hash. So someone with the hash can continue the hashing with his own data. One of the requirements for the recent NIST competition was AFAIK that this was not possible (hasher has hidden state).

In the case of bitcoin this is not a problem though. This doesn't simplify finding a hash value within a certain range.

this is going to turn out just like the may doomsday. once it flops, the guy is just going to vanish.

Indeed, he wouldn't exactly be the first guy making a bold claim on the internet.

[Gareth Nelson]

this is going to turn out just like the may doomsday. once it flops, the guy is just going to vanish.

Well this is embarrassing...........

I didn't vanish

Long story short is this: I looked at how much hardware this would take to precalculate the branches and found it'd be cheaper to just buy BTC or mine the old-fashioned way.

People on this thread are forgetting something very important - in bitcoin, we map a block hash to a nonce. This MASSIVELY reduces the search space, otherwise miners would not be feasible at all. My (now abandoned) work was about further reducing the search space by removing binary branches (i.e each bit of the nonce splits it into a new branch) that will never result in a valid hash as output. Each time you do this you divide the time taken to mine a valid block by 2. That's the theory anyway.

When I started to get into the details and try to build the thing I discovered that although theoretically possible it'd take so much resources it's not worth it.

[ElectricMucus]

I can imagine it is possible to use known cryptoanalysis of sha-2 to write software which is 50-90% more efficient of what we have now, though I doubt it.

[Gareth Nelson]

I can imagine it is possible to use known cryptoanalysis of sha-2 to write software which is 50-90% more efficient of what we have now, though I doubt it.

From the time I put into this thing, it's possible - definitely possible - but you're better off using traditional methods because of the resources needed either in pregeneration using my approach or in development time.

[Gabi]

So, we have a guy claiming to revolutionize the whole thing

+

aspiesforfreedom

aspie...


=

Yeeeaahhh sure....  should i link the aspie article on encyclopedia dramatica?

[Gareth Nelson]

The more relevant tweets that were missed off from the first post:
http://twitter.com/#!/garethnelson/status/75236526593810432
http://twitter.com/#!/garethnelson/status/75236664062132224
http://twitter.com/#!/garethnelson/status/75236789480210432

As for Gabi's comments, well - i'm just going to ignore the nastiness as ED is known for having nothing nice to say on any subject.
Example - http://encyclopediadramatica.ch/Bitcoin

[ElectricMucus]

If you complain about how ED is written it probably isn't for you 

[Gareth Nelson]

If you complain about how ED is written it probably isn't for you 

Some stuff on there is mildly amusing, sometimes even in a self-depreciating way, but generally it's just nasty for the sake of being nasty.

[error]

If you complain about how ED is written it probably isn't for you 

Some stuff on there is mildly amusing, sometimes even in a self-depreciating way, but generally it's just nasty for the sake of being nasty.

I'm only going to suggest that you know what you're talking about before opening your mouth on the Internet, or people who DO know what they're talking about will call you out.