Topic: Could code be changed quickly if vulnerability found? (Read 3174 times)

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.

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

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.


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.

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!

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.

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.

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.

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.

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.

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.

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.


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.


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

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.

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

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.

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

Yes.  One of the design features is that given a hash, it is extremely difficult to create data that would generate that hash.  But we have septendecillions of hashes to pick from, exponentially increasing our chances of getting one that works (either via brute force, or otherwise).


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

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.

So:

Case #1 [normal]:  You go through 2^32 nonces, calculate the hash for each, ending if you get a successful hash.
Case #2 [those 2 threads]:  You go through 2^32 nonces, calculate the hash for each using a faster method, ending if you get a successful hash.
Case #3 [my post]:  You go through perhaps 2^24 nonces, calculate the hash for each using a faster method, ending if you get a successful hash.

#2 and #3 both have the potential to be faster than what is traditionally used, but go about doing so in very different ways.  Case #3 treats the SHA256 algorithm as a black box, not caring what the algorithm does.  Case #2 looks at how the SHA256 algorithm works and tries to find ways to duplicate it faster.

I believe that double SHA-256 is and for a long time will be immune to such kind of attacks, but blake hash as used in Blakecoin may be vulnerable to 'statistical mining'.

Question, have you read those two threads, and do you understand how they relate to what you're talking about?

What a brilliantly helpful post!  :)


I figure it is safe to go into some more details now.

I am still processing the data; I haven't figured out yet for certain if there is indeed an advantage to be gained, or what it would be.  My hunch is that I am on to something, but that it would not provide enough of an advantage at this point (and like typical hash vulnerabilities, would come a bit at a time, which would be advantageous to Bitcoin, as that would provide the least volatility).  My hunch is that current ASICs would not be able to take advantage of this, but that GPUs would -- so you would need a big advantage for it to be worthwhile.

My concern is that there may be ways to eliminate certain nonces without having to calculate the hash for them.  As a simple (but made up) example, if you knew that the last nibble of the nonce had to be a 0 in order to solve the block, you would only have to check every 16th nonce, cutting your work by over 90% (or multiplying your hash rate by about 10x).  If you knew that the last 2 nibbles had to be 00, your hashrate would increase about 250x (256x minus any calculations you have to perform).  Of course, these are simplistic and unrealistic examples.

As for where I believe the vulnerability lies, it boils down to the hash needed to solve to block, and the leading zero bits.  Right now, the latest successful hash (0000000000000000f7d7b35dbc3d750166fe3b9c45e24a25dbed93fb4a28bf2f) has 256 bits (as all do), with the first 64 bits set to 0.  That's 25% of the bits set to 0, in a row.  Because of that, the hash ends up with about 25% less 1's than average.  Between having less 1's than average, and the order of the 0's, I believe it is possible to predict (given the block header data) whether certain nonces could solve the block.

Adding to this is that we now have a great data source to assist:  over 250,000 80-byte blocks of data, along with their 32-byte "winning" hash.

A typical use of hashes involves using the hash to verify that data has not changed; in this case, an attacker would have to change data in a way that the hash would come out to one specific value (the hash of the original data).  However, with Bitcoin, the attacker (miner) needs to change the data in such a way that any that the hash matches one of massive amounts of potential hashes (somewhere in the order of a septendecillion acceptable hashes -- now there's a word I don't see every day!).  So you've got a much, much better chance of finding a way of altering the data to "win."

One other thing worth mentioning -- like most (I would guess) data, the header block is skewed towards zeroes (I.E. 80 bytes of random data would have 320 0 bits on average; this data normally has more).

In any case, I haven't come up with anything conclusive, and from a purely statistical view (e.g. based on the expected numbers of people who have tried and failed), it is unlikely that I will.  However, my gut still feels that there is something here.

The fix would be to prevent the leading zeroes required in the hash.  For example, requiring that they be set to the first X bits of the Merkle tree would likely do the trick.

I'm pretty sure he hasn't