Cryptographic reasoning for double-hash?

bob123

legendary

Activity: 1624

Merit: 2481

Quote from: lichuan on March 31, 2018, 07:36:28 AM

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

lichuan

newbie

Activity: 148

Merit: 0

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.

hashcoin

full member

Activity: 372

Merit: 114

Quote from: maaku on September 26, 2011, 02:31:22 AM

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

iddo

sr. member

Activity: 360

Merit: 251

facepalm @ Hawkix

Hawkix

hero member

Activity: 531

Merit: 505

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

sr. member

Activity: 360

Merit: 251

Quote from: Shevek on September 26, 2011, 04:36:34 AM

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.

fivebells

sr. member

Activity: 462

Merit: 250

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.

Shevek

sr. member

Activity: 252

Merit: 250

Quote from: maaku on September 26, 2011, 03:15:32 AM

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?

maaku

legendary

Activity: 905

Merit: 1012

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

sr. member

Activity: 252

Merit: 250

Quote from: kjj on September 26, 2011, 01:45:40 AM

Quote from: Shevek on September 26, 2011, 01:29:45 AM

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

legendary

Activity: 905

Merit: 1012

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

kjj

legendary

Activity: 1302

Merit: 1026

Quote from: Shevek on September 26, 2011, 01:29:45 AM

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.

Shevek

sr. member

Activity: 252

Merit: 250

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.

iddo

sr. member

Activity: 360

Merit: 251

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

hashcoin

full member

Activity: 372

Merit: 114

Quote from: maaku on September 23, 2011, 05:53:47 PM

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.

maaku

legendary

Activity: 905

Merit: 1012

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.

iddo

sr. member

Activity: 360

Merit: 251

I'm saying that I fail to see why this 3AES should be more secure than 2AES(key,txt)=AES(key,AES(sha256(key),txt))
I think that if we assume that sha256 is (computationally) indistinguishable from a random function then both of these 3AES and 2AES wouldn't be less secure than AES itself, i.e. re-encrypting AES ciphertext with unrelated key is fine (the ciphertext is uniformly distributed because AES, or any other encryption algorithm, are permutations). So if sha256 doesn't have non-random quirks that can be exploited here (we cannot prove this), then it should be ok. But I don't have any idea how to estimate how much more secure this should be, under the assumption that sha256 is random. Like I mentioned there are diminishing returns when you use too many rounds with same key length. If you really care about increasing the security (I still have no idea why) then go for 3AES with independent keys.

maaku

legendary

Activity: 905

Merit: 1012

So to summarize, you're saying that the brute-force key-recovery attack against of 3AES is no different than against regular AES?

I don't get how you can call that "broken"--that's what I'm aiming for, security is not reduced, and it's what I assumed from the start. Obviously it won't have *more* security against a brute-force attack than vanilla AES, since all keys are derived from the original. The only thing I'm aiming for is slightly better protection against a mathematical attack on the AES cipher itself.

iddo

sr. member

Activity: 360

Merit: 251

Quote from: maaku on September 25, 2011, 01:08:33 PM

Under the theory that should a practical attack on AES be published, it's a reasonable bet that the attack will not extend to a strengthened AES right away, as-is (or at least not be practical). That gives extra time to find a suitable alternative and transition everyone to it (which will take time for something like the bitcoin network).

The approach I'm considering would be the following:

K1 = K
K2 = SHA-256(K).truncate() // for AES-128 or AES-192
K3 = K

3AES_Encrypt(K, x) = AES_Encrypt(K3, AES_Decrypt(K2, AES_Encrypt(K1, x)))
3AES_Decrypt(K, x) = AES_Decrypt(K1, AES_Encrypt(K2, AES_Decrypt(K3, x)))

This approach is very bad, it's broken using only one known plaintext (ptxt,ctxt) and even more easily than 2DES, by meet-in-the-middle with same time complexity as brute forcing single AES, and even same space complexity (unlike 2DES). Simply iterate over all possible K and compare AES_Decrypt(K2, AES_Encrypt(K, ptxt)) with AES_Decrypt(K, ctxt) until they match, and you found the secret key.

Edit: sorry, actually what I wrote is unnecessarily complicated, no need to mention MITM, simply iterate and compare 3AES_Encrypt(K, ptxt) with ctxt, i.e. brute forcing will work because you derive the keys from K, so I guess that there's no interesting reason to use 3AES instead of 2AES for example...

maaku

legendary

Activity: 905

Merit: 1012

Under the theory that should a practical attack on AES be published, it's a reasonable bet that the attack will not extend to a strengthened AES right away, as-is (or at least not be practical). That gives extra time to find a suitable alternative and transition everyone to it (which will take time for something like the bitcoin network).

The approach I'm considering would be the following:

K1 = K
K2 = SHA-256(K).truncate() // for AES-128 or AES-192
K3 = K

3AES_Encrypt(K, x) = AES_Encrypt(K3, AES_Decrypt(K2, AES_Encrypt(K1, x)))
3AES_Decrypt(K, x) = AES_Decrypt(K1, AES_Encrypt(K2, AES_Decrypt(K3, x)))

Topic: Cryptographic reasoning for double-hash? (Read 10764 times)