Optimal Block Header hashing algorithm

[nlovric]

I have not had computer / Internet time to examine Bitcoin in depth, yet, but it has occurred to me that the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256) is not the optimal algorithm if the message is always of the same size. The optimum algorithm would be one designed to hash messages specifically of that size and possibly of that specific structure. This would provide a higher level of computational resistance and reduce computation overhead.

After a short examination of "Satoshi Nakamotos'" A Peer-to-Peer Digital Cash System, I have determined that the Block Header is one such message. Is the Block Header not always of the same size?

[gmaxwell]

Outside of a few very simply or highly abstract subjects when someone says "optimum" without defining it it usually means they have adopted a confused or very narrow minded view of what they are talking about.

There are many properties we need in Bitcoin which SHA256 is good for.  Foremost being a _very_ trustworthy and well studied cryptographic structure as a primary concern is that it be free of trapdoors.  Matching a cryptographic hash algorithm to the size has little value except for performance, and we already use double-sha256— performance is not a primary consideration (in fact, in the search its intentionally _slow_ and thats the basis of its usefulness as a computational proof of work), and on the validation side sha256 is already enormously fast especially considering that in steady state we only need to process one per ten minutes. Likewise, structure respecting hashes are only relevant when there is a lot of fixed structure, but our headers do not have a lot of fixed structure, they are generally pretty efficiently encoded.

So please, feel free to elaborate on your thoughts but take care to actually define "optimum" and concretely relate how that definition applies to the Bitcoin system in a manner which would improve its trustworthyness or scale in a meaningful way.

[nlovric]

…

What I pointed out is a matter of general theory as I do not yet have time to analyze the operation of Bitcoin in depth nor start searching for practical attack vectors. If the Block Header truly has no fixed structure nor frequent structure, it may not apply to Bitcoin at all, then. However, if an algorithm is not specifically tailored for a specific structure i. e. minimized, a shorter path may exist to calculate the hash for that structure or it might be possible to construct rainbow tables specific for that structure, which may not apply to other structures or non-structures. Also note that this may apply to any case in which the specific structure – a frequent structure – arises, so that the shortcut or rainbow table applies to such cases, only. In a general sense, it might be possible to construct a shortcut or rainbow table for such cases, in which cases only some Block Headers may be susceptible to such an attack.

[BombaUcigasa]

…

What I pointed out is a matter of general theory as I do not yet have time to analyze the operation of Bitcoin in depth nor start searching for practical attack vectors. If the Block Header truly has no fixed structure nor frequent structure, it may not apply to Bitcoin at all, then. However, if an algorithm is not specifically tailored for a specific structure i. e. minimized, a shorter path may exist to calculate the hash for that structure or it might be possible to construct rainbow tables specific for that structure, which may not apply to other structures or non-structures. Also note that this may apply to any case in which the specific structure – a frequent structure – arises, so that the shortcut or rainbow table applies to such cases, only. In a general sense, it might be possible to construct a shortcut or rainbow table for such cases, in which cases only some Block Headers may be susceptible to such an attack.

Perhaps one would identify and propose improvements upon the work of others after a coarse... examination ... of the basic models and usage scenarios, as to not appear arrogant and ignorant at the same time. May I offer a simple example, here is block 250458:

http://blockexplorer.com/block/0000000000000023d60ece1fd23ce92570f873c23f3ad86109ad0f52f4bff1ba -- structured human friendly output
http://blockexplorer.com/rawblock/0000000000000023d60ece1fd23ce92570f873c23f3ad86109ad0f52f4bff1ba -- raw data

You may notice that to obtain the maximum benefits of this block (0.12 BTC in fees, one must include the whole 95kb worth of transaction data. The high entropy of this data, as well as the low ratio of fixed components in the header makes an "attack vector" on the efficiency of work to be minimal. This is also of little worry as the hashing is done twice and it involves tens of thousands of individual bit operations making a partial "optimization" valid for only 10 minutes at a time.

Also considering your general scenario, of a very cyclic or repeated message: SHA-256 will still produce pseudo-random high entropy outputs and differential data for any individual bit flip in the original data. It contains a padding mechanism and sufficient computing rounds to affect all the output bits for any of the input bits irregardless of message size.

As such, you should explain how it occurred to you that this hashing algorithm designed and studied by the best mathematicians and computer scientists has the opposite functionality which it intended to perform, we are quite curious...

[gmaxwell]

http://blockexplorer.com/rawblock/0000000000000023d60ece1fd23ce92570f873c23f3ad86109ad0f52f4bff1ba -- raw data

A pedantic aside: That is not the raw data, it's a pretty printed form in human/machine readable json. The actual block data is a compact binary serialization.  No disagreement with your comments on SHA256, though.

[nlovric]

As such, you should explain how it occurred to you that this hashing algorithm designed and studied by the best mathematicians and computer scientists has the opposite functionality which it intended to perform, we are quite curious...

I have not examined the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256), either, as I do not have enough computer / Internet time, but the Vigenère cipher – "le chiffre indéchiffrable" – was also designed and studied by the best mathematicians and… well… scientists – as there were no computers at the time – for about 3 centuries before it was broken. If the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256) is secure for all eternity, then why do we need the Secure Hash Algorithm version 3 (SHA-3) etc.?

What I have pointed out is an area of application in which cryptologic "mauvering space" may exist.

[nlovric]

Perhaps one would identify and propose improvements upon the work of others after a coarse... examination ... of the basic models and usage scenarios, as to not appear arrogant and ignorant at the same time. May I offer a simple example, here is block 250458:

As I said, my observation is theoretical at present. If all theory required practice, then most theory would never be published, preventing the rise of practice by a party other than the theorist themselves.

[nlovric]

http://blockexplorer.com/block/0000000000000023d60ece1fd23ce92570f873c23f3ad86109ad0f52f4bff1ba -- structured human friendly output

Indeed, the application of this theory in such cases seems to be next to, but not, non-existent.

[nlovric]

I also do not have enough computer / Internet time to read it, but Yu Sasaki <sasaki.yu@lab.ntt.co.jp> and Kazumaro Aoki introduced the initial structure concept in Finding Preimages in Full MD5 Faster than Exhaustive Search, which is also being applied to attacks on the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256).

Note that the work popped up as a reference in an article found in a Startpage search; it may or may not be related to my observation.

[Jan]

I have not had computer / Internet time to examine Bitcoin in depth, yet, but it has occurred to me that ....

... as I do not yet have time to analyze the operation of Bitcoin in depth nor start searching for practical attack vectors...

... I have not examined the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256), either, as I do not have enough computer / Internet time, ...

I also do not have enough computer / Internet time to read it, but Yu Sasaki ...

I suggest you find yourself some more computer / Internet time.

[BombaUcigasa]

As such, you should explain how it occurred to you that this hashing algorithm designed and studied by the best mathematicians and computer scientists has the opposite functionality which it intended to perform, we are quite curious...

I have not examined the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256), either, as I do not have enough computer / Internet time, but the Vigenère cipher – "le chiffre indéchiffrable" – was also designed and studied by the best mathematicians and… well… scientists – as there were no computers at the time – for about 3 centuries before it was broken. If the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256) is secure for all eternity, then why do we need the Secure Hash Algorithm version 3 (SHA-3) etc.?

What I have pointed out is an area of application in which cryptologic "mauvering space" may exist.

Yes, it is possible to render SHA256 useless. With the current technology and knowledge, it is not yet something that can be done. Bitcoin requires 10 times more compute power every year, that's like 2^3.3, or 3.3 bits less trusted, you can see where this is going.

[BombaUcigasa]

I also do not have enough computer / Internet time to read it, but Yu Sasaki <sasaki.yu@lab.ntt.co.jp> and Kazumaro Aoki introduced the initial structure concept in Finding Preimages in Full MD5 Faster than Exhaustive Search, which is also being applied to attacks on the 256-binary-digit-(bit) Secure Hash Algorithm version 2 (SHA-2-256).

Note that the work popped up as a reference in an article found in a Startpage search; it may or may not be related to my observation.

Pre-imaging on SHA256 is very costly and with regular architecture, the costs of the pre-image and the rest of the hashing will equal the cost of the whole hashing pass, more or less. You have to consider that the SHA alogorithms were improved constantly to resist new computational theories and applications that could lower their strength.

Right now, partial boolean satisfiability (SAT) could be a weakness for bitcoin: http://eprints.soton.ac.uk/265340/1/jpms-wodes08.pdf

But you also have to remember, Bitcoin's core idea is the blockchain. Every 10 minutes, your preimage or any other pre-work done is rendered useless, and it might take you a bit of effort to prepare them again before the next block. With added computing power every block, an attack becomes harder and harder to perform, regardless of methodology.

My suggestion to you is to research more papers on the subject (see what people post around here, cross-check references) and possibly contact researchers that work in this area, some new developments only reach the public after 4-5 years.