Cryptographic reasoning for double-hash?

[maaku]

I'm *not* trying to increase the bit strength of the encryption (the sort of security that increasing the keysize would give), but given that I've reapeated that three times now, it's probably not worth our time to get that point across.

[hashcoin]

I understand the point of "address = RIPEMD160(SHA256(key))"--it combines the security of RIPEMD160 and SHA256, so both hash functions would have to be broken to undo the hash. But what cryptographic reason would there be for "SHA256(SHA256(data))"?

No, infact, taking H(key) =  RIPEMD160(SHA256(key)) makes the security of your hash the worst of the two, in that a collision for EITHER will yield a collision for your hash.

If you have pubkey K and publish your fingerprint as f(g(K)), then clearly, if I can generate a key K' s.t. g(K) = g(K'), we'll have f(g(K)) = f(g(K')).  So in your example, clearly if I can collide with SHA256(key), I am also colliding with any further function of that you take.

Similarly if f is weak, I might be able to collide with your fingerprint without actually colliding for g.

Composing hashes gives you security parameter the minimum of the two.  For security parameter the maximum of the two, you concatenate them, not compose.  So you write h(x) = f(x)g(x), not f(g(x)).

edit: to be clear, in the last statement I mean all one can prove is that the security of the construction is at least as good as the minimum of the two.  Specific functions might do better -- e.g. if you compose with the identity function, clearly the security parameter doesn't change.

[iddo]

Right, and what about h(x) = f(x) xor g(x)  ?

[Shevek]

I thought about this. It has the side effect, that one can analyse 256 bit -> 256 bit function SHA256(x) (x: 256 bit) in order to find correlations between input and output bits.

If somebody cared, the amount of computed hash is so big that it should be give some statistical correlations at this time. Who owns this information can take advantage on mining, because after the first x = SHA256(block) calculus, may be she can decide to perform or not the next step SHA256(x) depending on statistical probability to get a share.

[kjj]

I thought about this. It has the side effect, that one can analyse 256 bit -> 256 bit function SHA256(x) (x: 256 bit) in order to find correlations between input and output bits.

If somebody cared, the amount of computed hash is so big that it should be give some statistical correlations at this time. Who owns this information can take advantage on mining, because after the first x = SHA256(block) calculus, may be she can decide to perform or not the next step SHA256(x) depending on statistical probability to get a share.

We believe no such statistical correlation to exist.

[maaku]

@hashcoin: that's the case for a second-preimage attack, but I believe my statement holds for a first-preimage attack, no? The importance of that distinction depends on the application of course, but to use your own example it wouldn't much matter if you could find a different key that maps to the public hash of my secret/private key. Regardless of its hash, if it's not the same key you can't use it to decrypt my messages or impersonate me.

[Shevek]

I thought about this. It has the side effect, that one can analyse 256 bit -> 256 bit function SHA256(x) (x: 256 bit) in order to find correlations between input and output bits.

If somebody cared, the amount of computed hash is so big that it should be give some statistical correlations at this time. Who owns this information can take advantage on mining, because after the first x = SHA256(block) calculus, may be she can decide to perform or not the next step SHA256(x) depending on statistical probability to get a share.

We believe no such statistical correlation to exist.

You are too "naïve"

[maaku]

You are either ignorant, or tin-foil paranoid.


EDIT: That came off as mean, which was completely not my intention. Attacking SHA-256 in the mannor you describe would require either a) a computer larger than the known universe, or b) entirely new mathematics. During it's development, millions of dollars and many person-years of researcher time were spent demonstrating that, among other things, SHA-256 output exhibits no statistical correlations of any kind, exploitable or benign. Since then, it has been the target of continued cryptanalysis by some of the best and brightest minds around the world, and every crypto grad student that wants to make a name for themselves.

So again, if you think believing that no such statistical correlations exist is "naïve"... you are eiher ignorant of what I just described, or tin-foil paranoid.

[Shevek]

EDIT: That came off as mean, which was completely not my intention. Attacking SHA-256 in the mannor you describe would require either a) a computer larger than the known universe, or b) entirely new mathematics. During it's development, millions of dollars and many person-years of researcher time were spent demonstrating that, among other things, SHA-256 output exhibits no statistical correlations of any kind, exploitable or benign. Since then, it has been the target of continued cryptanalysis by some of the best and brightest minds around the world, and every crypto grad student that wants to make a name for themselves.

I'm talking about the one-to-one function y= SHA256(x') where x' is a 256-bit number. I'm NOT talking about general SHA256(x), which could be much more difficult to analyse.

I'm talking about that the effort obtaining systematically pairs (y|x') has never been done until bitcoin. So, it doesn't matter what say the millions of dollars invested because now, with bitcoin, there is a big chance to get deeper in old analysis.

So, if the owner of powerful pool cared analysing those pairs (y|x'), he/she may eventually discover some some (tiny) correlations between bits of y and x', (correlations that only the big computing network of bitcoin can reveal) and take some (tiny) advantage selecting the x' = SHA256(block) vectors that should be the target of second SHA256 round.

Do you understand now?

[fivebells]

Most of those hash computations haven't been recorded, though.  Only the ones meeting the difficulty requirement. 

Think about it.  A wimpy GPU can generate 100MH/s.  Do you really think it's going to be more efficient to pull pre-computed preimage/hash pairs over the network?

It is just possible that there are some interesting relationships in the preimages to the hashes which met the difficulty requirement, but they will probably be very hard to tease out.

[iddo]

I'm talking about the one-to-one function y= SHA256(x') where x' is a 256-bit number.

It is extremely unlikely that this function is one-to-one, due to the birthday paradox.

[Hawkix]

If we use only single SHA256(), it could be easier to "backtrace" the correct nonce with given difficulty. A lot of first bits of result needs to be ZERO to provide a proof of work. I can imagine that some really clever folks could find a way how to select nonces so that the chance after *single* SHA256() will have a lot of zero bits at start (you can "unwire" loops and construct nasty polynomials) will be better. Hashing again makes this approach impossible.

[iddo]

facepalm @ Hawkix

[hashcoin]

@hashcoin: that's the case for a second-preimage attack, but I believe my statement holds for a first-preimage attack, no? The importance of that distinction depends on the application of course, but to use your own example it wouldn't much matter if you could find a different key that maps to the public hash of my secret/private key. Regardless of its hash, if it's not the same key you can't use it to decrypt my messages or impersonate me.

Why would you ever hash a private key? A public key fingerprint in general (and in particular, a bitcoin address) is a hash of a public key.    So if you make addresses f(g(pubkey)), then a collision for either f or g suffices for an adversary to spend your coins.  They just claim your coins with their own pubkey that collides with your address.

I think perhaps you are mixing up a first-preimage attack with finding the input.  In general, it is clearly imformation theoretically impossible to compute x given H(x), if x is longer than H(x).  A first pre-image attack means finding any x' s.t. H(x') = H(x), not finding the original x.

[lichuan]

In my opinion, the reason for double sha256 is about fair, because the pow formula is:

sha265(sha256(data + nonce + pubkey)) -------> 0x0000000000aeff23232323 (example)

but one sha256() function is not equal distribution, for example, the following is possible: (whatever nonce and pubkey is)

sha256("aaaaaaaaaxxxxxxxxxx" + nonce + pubkey)------> 0xnnnnnnnnnfebbdd2af9892 (n means not zero, for example)

there may be some inherent compute process in one sha256 caused that if data be hashed is not equal distributed, the result of one sha256() may be not equal distributed too.

but double sha256() can reduce this.

[bob123]

there may be some inherent compute process in one sha256 caused that if data be hashed is not equal distributed, the result of one sha256() may be not equal distributed too.

Each hashfunction (which is considered to be 'safe') follows the avalanche effect [1].
This means: If you change 1 bit in your input to the hash function this will result in a probability of 50% for each bit to flip.
This makes it appear as it was a 'random' output when changing just one single bit.

And sha256 does utilize the avalanche effect.
There is no way to 'adjust' the input to 'modify' the probability of leading zero's in a sha256 hash.

I am not sure what the reason for double sha256 is, but im pretty sure its not this one.



[1] https://en.wikipedia.org/wiki/Avalanche_effect