CubeHash as a SHA alternative

[neptop]

First of all I am not saying you should switch to anything. I am just curious what other think about it. Maybe it's also interesting for people who want to create another FooCoin currency.

I have been following the SHA3 challenge since it started and always liked CubeHash, because it's simplicity. It's heavily optimized for both security and simplicity. However, it didn't receive too much love, because it was slow. Since this isn't really a huge problem for Bitcoin or similar currencies I think it would make an awesome algorithm. Security isn't a problem and it's simplicity makes it easy to create a good implementation. This would probably make it harder for a very experienced person (or any kind of organization with enough money, power and know-how) to create a custom implementation that outperforms everyone else.

http://cubehash.cr.yp.to/

[o]

Out of topic, is combinations of different hashing algorithm harder to break?

For example, is using SHA1 and then SHA256 harder to break in comparison with only SHA1? Or it depends on the weakest hashing (say md5), or the strongest hashing, or it depends on the order of the hashing?

[Meni Rosenfeld]

Out of topic, is combinations of different hashing algorithm harder to break?

For example, is using SHA1 and then SHA256 harder to break in comparison with only SHA1? Or it depends on the weakest hashing (say md5), or the strongest hashing, or it depends on the order of the hashing?

If you use the different hash functions separately and then XOR the results, you get a hash function which should be stronger than any single one of the original functions used (Edit: With caveats).

[ByteCoin]

If you use the different hash functions separately and then XOR the results, you get a hash function which should be stronger than any single one of the original functions used.

Oh really? So if I use SHA256 as one of the hashes and the other hash is just reversing the bits then the XOR of the two is stronger than SHA256?

ByteCoin

[notme]

That would make it awfully hard to find a nonce.

[Meni Rosenfeld]

If you use the different hash functions separately and then XOR the results, you get a hash function which should be stronger than any single one of the original functions used.

Oh really? So if I use SHA256 as one of the hashes and the other hash is just reversing the bits then the XOR of the two is stronger than SHA256?

Yeah, well, except for that

Is this a problem in practice? Is it conceivable that such dependencies exist between the named hash functions?

Is there a different way to aggregate several hash functions so that the resulting function is assured to be safer than any single one?

That would make it awfully hard to find a nonce.

This isn't a problem, it just means the numerical value of the difficulty will be lower. The cost of computing a hash can be thousands of times more than SHA-256 without having any consequence.

[theymos]

Specialized hardware can always beat consumer hardware, so CubeHash isn't going to be any better than SHA-256 in that area. That CubeHash is slow does affect verification speed, which should be fast.

Is there a different way to aggregate several hash functions so that the resulting function is assured to be safer than any single one?

Concatenate them (or parts of them).

[notme]

Sorry, I was referring to !a XOR a.  Unless your difficulty allows allows every nonce, no nonce is possible.

[gmaxwell]

I have been following the SHA3 challenge since it started and always liked CubeHash, because it's simplicity. It's heavily optimized for both security and simplicity. However, it didn't receive too much love, because it was slow.

No, it didn't meet much love because it failed to meet the explicit security requirements for the SHA3 process.  DJB had a variant which was slower and did meet the requirements, but he was unwilling to make it his primary recommendation. (He thought the particular security requirement was stupid)

See the NIST report from the end of the second round right before cubehash was removed from consideration: http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Round2_Report_NISTIR_7764.pdf

The document asserts the following, with supporting arguments:

“For all real-world cryptographic applications, ‘formal’ versions here can be ignored, and
this document amounts to a proposal of CubeHash16/32 as SHA-3.”

Therefore, NIST evaluated the “normal” versions when determining whether CubeHash would
advance to the next round of the competition.

[...]

Moreover, no single variant for the 512-bit
digest size achieves the required theoretical security with acceptable performance. Another
disadvantage of the design is the existence of the symmetric properties that are arguably a
potential avenue for future attacks. NIST felt that an additional year of study would not be
enough to determine whether or not the symmetric properties pose a threat. Therefore, NIST felt
that CubeHash could not be chosen as SHA-3 with confidence, and thus should not be selected as
a finalist.

This would probably make it harder for a very experienced person (or any kind of organization with enough money, power and know-how) to create a custom implementation that outperforms everyone else

This is nonsense. Efficient hardware designs for all the later round sha3 candidates we're presented as part of the process. One of cubehash's advantages is that it lends itself to particular compact ASIC implementations.

The poor density/performance of SHA2 in ASIC is one of the motivating factors for the SHA3 contest.

[Meni Rosenfeld]

Is there a different way to aggregate several hash functions so that the resulting function is assured to be safer than any single one?

Concatenate them (or parts of them).

If you concatenate parts of them you don't get the same security. If you have 8 functions of which 1 strong and the others are weak, and you take 32 bits from each, I think this can be weaker than just the strong function.

Sorry, I was referring to !a XOR a.  Unless your difficulty allows allows every nonce, no nonce is possible.

You should always quote the comment you're replying to. Unquoted comments should be assumed to be replying to the original post.

[neptop]

I have been following the SHA3 challenge since it started and always liked CubeHash, because it's simplicity. It's heavily optimized for both security and simplicity. However, it didn't receive too much love, because it was slow.

No, it didn't meet much love because it failed to meet the explicit security requirements for the SHA3 process.  DJB had a variant which was slower and did meet the requirements, but he was unwilling to make it his primary recommendation. (He thought the particular security requirement was stupid)

I was referring to that variant. He had to choose between them, but I don't think any of them would have won or even reached the final round, because of being either slow or insecure.

This is nonsense. Efficient hardware designs for all the later round sha3 candidates we're presented as part of the process. One of cubehash's advantages is that it lends itself to particular compact ASIC implementations.

That's nonsense but then you say I am right? I am confused.

A compact implementation would mean that it is easier to get to an optimal implementation and so it is easier to get a very efficient hardware. This means it is harder for a small group to outperform the rest. Or did I miss something?

Btw. CubeHash is just an example. The scrypt based currencies made me think about benefits that certain algorithms could have. As I mentioned at the beginning of this thread I am not saying anything should be replaced, it's just about thought experiments.

Oh and while thinking about that I have become a bit worried about Bitcoins future. If an attacker would begin to mine Bitcoins in a very sophisticated, optimized and efficient way (I am not talking about breaking SHA or anything) and sell them cheaply, probably even at a minor loss this would at a certain point make it unprofitable for others to mine. This would be way below 50% of the network's hashrate, but would cause people to stop mining, because of being inefficient. I know there are people who have interest in Bitcoin and would still mine, but with a big bunch of people leaving an attacker would be able to create even more Bitcoins making his attack even more efficient would have it much easier to get past the 50% to mess the network up. So an attacker doesn't have to get to the 50% right away. It would probably be way easier to start a a lower rate and cut out the others.

An attacker whose aim isn't really making money in first place, but to destroy Bitcoin could do such a thing and therefor wouldn't really require the 50% right away, correct?

[Meni Rosenfeld]

Oh and while thinking about that I have become a bit worried about Bitcoins future. If an attacker would begin to mine Bitcoins in a very sophisticated, optimized and efficient way (I am not talking about breaking SHA or anything) and sell them cheaply, probably even at a minor loss this would at a certain point make it unprofitable for others to mine. This would be way below 50% of the network's hashrate, but would cause people to stop mining, because of being inefficient. I know there are people who have interest in Bitcoin and would still mine, but with a big bunch of people leaving an attacker would be able to create even more Bitcoins making his attack even more efficient would have it much easier to get past the 50% to mess the network up. So an attacker doesn't have to get to the 50% right away. It would probably be way easier to start a a lower rate and cut out the others.

An attacker whose aim isn't really making money in first place, but to destroy Bitcoin could do such a thing and therefor wouldn't really require the 50% right away, correct?

That's correct. I don't think it will give the attacker that much of an advantage though, most miners should have a sizable operating profit so will continue to mine even with this reduction in profitability. If the attacker waits too long he risks Bitcoin increasing in popularity (and price) and attracting more miners than before.

[mndrix]

If an attacker would begin to mine Bitcoins in a very sophisticated, optimized and efficient way

I think most mining is already "very sophisticated, optimized and efficient."  Perusing the discussions and mining rig photos in the mining subforums, makes me think an attacker already faces stiff competition.  There's still some room for improved efficiency from custom hardware (FPGA, ASIC, etc) and vertical integration (buying a local electric utility, building a custom coal-fired power plant, etc), but I'm not sure those efficiencies will dramatically change the economics of mining.

[gmaxwell]

I was referring to that variant. He had to choose between them, but I don't think any of them would have won or even reached the final round, because of being either slow or insecure.

Or both— NIST's concern's with respect to symmetric states apply to all variants.

That's nonsense but then you say I am right? I am confused.
A compact implementation would mean that it is easier to get to an optimal implementation and so it is easier to get a very efficient hardware. This means it is harder for a small group to outperform the rest. Or did I miss something?

Ah—— What you were suggesting didn't make sense to me, so the interpretation I picked didn't match the one you were suggesting.

I believed you were suggesting the cubehash would be more difficult to get an ASIC implementation which would be orders of magnitude faster than the GPU/FPGA things most bitcoin users are currently using. This is not the case: Cubehash would be agreeable to even greater speedups from GPU to ASIC.

Now I understand that you were actually suggesting is that there would be less difference between different ASIC implementations. This might be true— except the the upfront cost of spinning any ASIC on a state of the art process (E.g. millions) is going to dwarf the engineering resources required to drive an efficient sha256 design to its maximum. Both SHA256 and cubehash are exceptionally simple compared to most logic, and neither should have design work be a significant cost in manufacturing a chip.  The kinds of costs NIST was concerned with for SHA3 were the area required for a single instance to achieve a particular hashing rate— this isn't a relevant criteria for us. Also, the difference between a moderately well tuned implementation and an exceptionally well tuned one wouldn't be that gigantic... smaller than the difference between semiconductor generations.

If an attacker would begin to mine Bitcoins in a very sophisticated, optimized and efficient way (I am not talking about breaking SHA or anything) and sell them cheaply, probably even at a minor loss this would at a certain point make it unprofitable for others to mine.

His differential mining efficiency doesn't really matter much here, it would just be a small constant factor, the fact that he's willing to take a loss relative to the income he could receive selling them at market rate is the key point.  I don't see that there is much the hash function can do here. If someone wants to throw a lot of income away— they can make trouble for bitcoin in a great many different ways.

[neptop]

@gmaxwell: Thanks for your reply.

I don't see that there is much the hash function can do here. If someone wants to throw a lot of income away— they can make trouble for bitcoin in a great many different ways.

Really? The thing is that the example I gave actually destroys the system by reversing transactions and stuff. So I think this would be more like a technical attack and therefor would therefor actually destroy Bitcoin instead of just cause fluctuations in the market. Or did I miss something?

If an attacker would begin to mine Bitcoins in a very sophisticated, optimized and efficient way

I think most mining is already "very sophisticated, optimized and efficient."  Perusing the discussions and mining rig photos in the mining subforums, makes me think an attacker already faces stiff competition.  There's still some room for improved efficiency from custom hardware (FPGA, ASIC, etc) and vertical integration (buying a local electric utility, building a custom coal-fired power plant, etc), but I'm not sure those efficiencies will dramatically change the economics of mining.

You can optimize costs for example by buying a larger set of FPGAs, ASIC, get cheap energy. I know there are people getting basically energy for free, but these mostly seem to be very small scale setups in households or like a small server room. The reason for using so many adjectives was that I wanted to make clear that many smaller advantages in different areas could become very serious if you are doing this large scale.

It most likely isn't a serious problem right now, but should Bitcoin become more widespread and serious organizations like a company (especially something like a bank or something like Paypal) or a government would attack Bitcoin small advantages in hardware, energy cost, etc. could pose a serious threat. It's an investment like taking over an other company so it doesn't become a serious competition. Of course Paypal is not the only company that would may not be a friend of Bitcoin, so organization could even join up.

This is similar to the fear of the point where transaction fees are the only reason to mine. The question is whether Bitcoin will still be able to remain independent and not have a very dominant institutions that advance the blockchain allowing it to manipulate. I think the mining contractors are a very good way to prevent this, but currently (please don't consider that an offense) they are not really established or professional and one often asks how far you can trust those people. I know it will take a while. It's some for of evolution. The best will survive. It just hope that there will be a large group, so they don't have too much power - not because of reversing the block chain, but because they most likely will have a huge influence on how things will develop.

[gmaxwell]

@gmaxwell: Thanks for your reply.

So — perhaps I'm misunderstanding you again.

I think you're saying that a miner could get cost advantages which would then allow him to drive the price down to the exclusion of everyone else at very little cost to himself because his lower price comes from more efficient mining instead of raw loss taking.

I think you're making the wrong economic analysis here— When considering what the attacker is willing to lose the correct metric is not his sale price vs cost of production.  The correct metric is his sale price vs the sale price that he _could_ have taken (e.g. what the market would have supported).

If you're willing to lose money by selling at less than you could have sold at, lowing your production cost only changes how much trouble you can afford to make by small factors. Once you're at the point where multiple parties have ASICs, I don't see more than a factor of two in performance coming from more skillful implementation/better siting/etc. as the commercial miners also have access to these things.  And if you are to assume that the bad guy would make ASIC while the rest of us only have GPUs/FPGAS— thats a few million in spending which would far more effectively be spent on lobbying to outlaw bitcoin, then on an investment into technical attack which could be destroyed by a one line of code change in our GPU/FPGA miners (just add one 32 bit xor between the SHA256 stages.. and poof, asics go into the trash).

Moreover, we already have _drastically_ different costs in our mining operations— I know that my setup is substantially more efficient than many of the ones I hear discussed both in terms of operating and initial price (e.g. easily less than half on both vs the people running two 6990s per host).  I expect there are people more efficient than I... and yet everyone else isn't completely pushed out of the market— The people who are more profitable simply make more income (or horde more of the results).