Could code be changed quickly if vulnerability found?

[eatingthenight]

From what I have read so far I don't see how this can have an effect on the network. This may make it possible for GPU's to mine much faster but even a 10x increase does not make them anywhere close to profitable.   I assume they would also shortly implement this for asics as well although it would take a bit more work. Pretty even if this would actual work all that would happen is the old 5GH would now be 50GH but doing the exact same thing. The network difficulty would adjust accordingly and it would be like nothing ever happened assuming that you could actually statistically filter out nonces.

[chaintest]

I'm talking about determining that a nonce has little chance of producing a successful hash, and therefore not needing to make the calculation at all.

Yes, that makes sense. No, Satoshi already took care about it. Guess why single SHA-256 is not enough for Bitcoin?

Let's say the hashing algorithm is this:  Add up all the data bytes, take the lowest 8 bits (0 through 255), and multiply by 256.  In this case, the hash is 16 bits, with the lower 8 bits always zero.

Do a double hash of this poor hashing algorithm, and you aren't any better off than just hashing once.

Worse, take a hashing algorithm that takes each bit of the data and xor's it with 1.  So binary 10011 becomes 01100.  If you double *that* really poor hashing algorithm, the results are even worse:  you get the original data!

So a double-hash with SHA256 will *presumably* increase security, but has anyone gone through and tried to prove that it actually does?

From my perspective, I do not consider what hashing algorithm is used, or what variations there may be.  You could do SHA256(MD5(CRC32(SHA256()))), and I would approach it the same way.  Now if it can be mathematically proven that the variation of the algorithm (in this case, doing it twice) makes it much harder to crack, then it would not make sense for me to continue looking into this.  But without such proof, believing that the variation is definitely better is dangerous (as proven above, where doubling other algorithms can generate no improvement, or make it easier to crack).

[chaintest]

From what I have read so far I don't see how this can have an effect on the network. This may make it possible for GPU's to mine much faster but even a 10x increase does not make them anywhere close to profitable.   I assume they would also shortly implement this for asics as well although it would take a bit more work. Pretty even if this would actual work all that would happen is the old 5GH would now be 50GH but doing the exact same thing. The network difficulty would adjust accordingly and it would be like nothing ever happened assuming that you could actually statistically filter out nonces.

Exactly.  At a 10x increase that would require new ASICs (or using existing CPUs/GPUs), the existing network should be able to handle it (a slight increase in hashrate very quickly, but staggered a bit; followed by a much larger increase as new ASICs came online).  It would upset those that paid for ASICs, but that's one of the risks.

At a 100x increase or 1000x increase, however, the picture would change.  If that were to occur, the cost per GH/s for GPUs might become much, much lower than current ASICs.  Dust off all those old GPUs and get them working within a couple of weeks, and it could strain the network.  Add a 100x to 1000x increase to ASICs within months to a year, and it could spell trouble.

And there could be new bottlenecks that appear.  The nonce is only 32 bits; it takes just 4GH/s to go through those in one second, at which point a new block header needs to be created.  For a 400GH/s ASIC, that's a new block header every 1/100 second.  At 1,000x increase, you're dealing with a new block header every 1/100,000 second, which could introduce new bottlenecks (e.g. calculating the Merkle tree).  Of course, such bottlenecks would reduce the stress on the system, which would be good.

But would about a 1,000,000x increase?  That would be a game changer.  If that was discovered and exploited to its full potential immediately, you've got a problem:  you could hit a new difficulty level very quickly, which would slow down the person discovering this to generating new blocks every 10 minutes or so, and giving everyone else nearly no chance of solving a block.  If the super-miner quits when the difficulty changes (after having made $50M or so of BTC), it could be days or longer before a single new block is solved.  And then you're dealing with blocks too big to be accepted, requiring a patch to allow Bitcoin to survive.  And what about the difficulty?  You could lower it with a patch, but then if the super-miner comes back online, it jumps again.

So at 10x, little concern.  1,000,000x, potential disaster.

[toast]

Yes.  One of the design features is that given a hash, it is extremely difficult to create data that would generate that hash.

And furthermore, there is total information loss. Any distribution you know over outputs does not help you determine distribution over inputs. All you've said is, "if we know the distribution over outputs, we could maybe turn that into knowledge about distribution over inputs".  You are saying SHA256 is an ineffective cryptographic hashing function. The DoD will make you very rich if you can show that this is the case.

AFACT (can tell), both of those threads refer to possible shortcuts to the SHA256 hashing algorithm (in other words, testing the same number of nonces, just doing so faster).

Yes, the shortcut involves trying to use knowledge about distribution of outputs to solve the problem faster. That's why it's relevant. But they aren't using techniques that rely on statistical analysis that SHA256 was designed to resist.

Let's say the hashing algorithm is this:  Add up all the data bytes, take the lowest 8 bits (0 through 255), and multiply by 256.  In this case, the hash is 16 bits, with the lower 8 bits always zero.

Worse, take a hashing algorithm that takes each bit of the data and xor's it with 1.

Neither of those are cryptographic hashing algorithms. Do you see why?

[toast]

Actually nevermind, don't let naysayers like me slow you down. Your turing award awaits.

PM me if you find something and I'll help you get rich.

[chaintest]

Let's say the hashing algorithm is this:  Add up all the data bytes, take the lowest 8 bits (0 through 255), and multiply by 256.  In this case, the hash is 16 bits, with the lower 8 bits always zero.

Worse, take a hashing algorithm that takes each bit of the data and xor's it with 1.

Neither of those are cryptographic hashing algorithms. Do you see why?

They are cryptographic hashing algorithms, just extremely poor ones, I stated, to get the point across.

I encourage you to provide an example with a more advanced cryptographic hashing algorithm.

[BurtW]

I encourage you to provide an example with a more advanced cryptographic hashing algorithm.

SHA 256, twice for good measure.

Advanced cryptographic hashing functions are designed so that if you change one single bit in the input a majority of the bits are changed in the output.  They are designed this way on purpose so that the attack you are proposing does not work.

[chaintest]

I encourage you to provide an example with a more advanced cryptographic hashing algorithm.

SHA 256

Sorry, that's "example with", not "example of."  Yes, SHA256 is infinitely more advanced than my simple examples, but SHA256 has not been proven to be equally or less secure when performed twice.  My examples were showing that performing hashing algorithms twice does not always increase security, in some cases providing equal or less security.

toast was saying that my examples were not good because they were not advanced cryptographic hashing algorithms, and I was encouraging him (or others) to provide an example with an advanced cryptographic hashing algorithm.  But in most cases, simplistic examples are better, as they are easier to understand, and get the point across with less work.

[smolen]

And furthermore, there is total information loss.

AFACT (can tell), both of those threads refer to possible shortcuts to the SHA256 hashing algorithm (in other words, testing the same number of nonces, just doing so faster).

Yes, the shortcut involves trying to use knowledge about distribution of outputs to solve the problem faster. That's why it's relevant. But they aren't using techniques that rely on statistical analysis that SHA256 was designed to resist.

The information is not lost momentarily, it's slow dissipates with each hash round, were it pass from down to top or in reverse. Those two threads describe two different approaches to morph the structure of hash function. I think that single SHA-256 is small enough to be vulnerable to statistical analysis after such liposuction, but (I'm pretty sure killerstorm gave exact numbers, cannot find it now) double SHA-256 is big enough to be safe.

[smolen]

SHA256 has not been proven to be equally or less secure when performed twice

Well, it's not a proof, but for sake of discussion... Let's imagine that I have a magic way to restore preimage from SHA-256 (or any other) hash. By applying this magic twice I can restore preimage of double hash. Were I in possession of magic method of reversing double hash, I could reverse single hash by reversing double one and then re-applying single hash if such preimage exists. So breaking single hash leads to breaking double one, but not vice verse.

[toast]

Well you're right in the sense that it is possible to prove that a hash is not cryptographic but so far not yet possible to prove that a hash is cryptographic (P vs NP and all). We rely on the crypto community to keep us up-to-date on potential attacks. If you're interested in pursuing this, great! Cryptanalysis is an exciting field. I found a paper that might be helpful as a starting point.

http://www.femto-second.com/papers/SHA256LimitedStatisticalAnalysis.pdf

Again, realize all you are saying is "I know double SHA256 is supposed to be a strong cryptographic hash and most prominent cryptographers seem to think so, but what if it's not?"

I suppose the next step is to run some statistical analysis!

[chaintest]

... If you're interested in pursuing this, great! Cryptanalysis is an exciting field. I found a paper that might be helpful as a starting point.

http://www.femto-second.com/papers/SHA256LimitedStatisticalAnalysis.pdf

Thanks for the link; glancing at it, it appears to be similar to what I am doing.  I'll need to read that one thoroughly.

Again, realize all you are saying is "I know double SHA256 is supposed to be a strong cryptographic hash and most prominent cryptographers seem to think so, but what if it's not?"

Remember, Bitcoin does something different than most.  It is possible for a cryptographic hash function to meet the criteria of a cryptographic hash function (going by the Wikipedia definition), while having vulnerabilities as used by Bitcoin.  Specifically, checking a single nonce to see if it is successful (has enough leading zeroes) has the same effect as testing septendecillions of variations to a message against its original hash.

So if using current computing power it would take 1,000,000 years to create an altered message with the same hash as the original, it could take less than a second to alter a message and get a hash that Bitcoin considers successful.  Such a hashing algorithm would like be considered highly secure for most purposes, just not Bitcoin.

In other words, all those prominent cryptographers think that SHA256 is very strong, but that does not mean that they think that it is strong as used by Bitcoin.

[empoweoqwj]

I'm talking about determining that a nonce has little chance of producing a successful hash, and therefore not needing to make the calculation at all.

Yes, that makes sense. No, Satoshi already took care about it. Guess why single SHA-256 is not enough for Bitcoin?

I wouldn't bother pointing out facts to him. He seems determined to carry on regardless ..... until he realizes he hasnt found a vulnerability

[gmaxwell]

Many people have spent large amounts of time looking at far more mining data than you have available. (e.g. hundreds of gigabytes of shares) and have not found anything terribly useful.

Because the distribution of input data is not believed to matter miners do all sorts of things which bias their inputs e.g. increment starting at zero or only sweep part of the nonce range, etc. which can serve to create apparent after the fact biases which aren't real and can be hard to sort out.

The fact early termination winnowing would be useful if available isn't lost on anyone— its an oft cited reason why $otherfunction wouldn't make a good POW. (E.g. you can rapidly tell trivial 3sat problems from potentially hard ones, so you grind the problem generator and then use a fast solver for trivial problems). Many (most?) miners make use of the fact that you can terminate sha256 a couple rounds early with the h==0 constraint.

If you've found something that lets you mine faster— congrats. I look forward to hearing about your major mining income or reading your paper.

Good luck.