maaku


September 26, 2011, 12:27:25 AM 

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.

I'm an independent developer working on bitcoincore, making my living off community donations. If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP







Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.




hashcoin


September 26, 2011, 01:06:35 AM 

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


September 26, 2011, 02:28:40 AM 

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




Shevek


September 26, 2011, 06: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.

Proposals for improving bitcoin are like asses: everybody has one 1SheveKuPHpzpLqSvPSavik9wnC51voBa



kjj
Legendary
Offline
Activity: 1302


September 26, 2011, 06:45:40 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.




maaku


September 26, 2011, 07:31:22 AM 

@hashcoin: that's the case for a secondpreimage attack, but I believe my statement holds for a firstpreimage 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.

I'm an independent developer working on bitcoincore, making my living off community donations. If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP



Shevek


September 26, 2011, 07:57:02 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"

Proposals for improving bitcoin are like asses: everybody has one 1SheveKuPHpzpLqSvPSavik9wnC51voBa



maaku


September 26, 2011, 08:15:32 AM 

You are either ignorant, or tinfoil paranoid.
EDIT: That came off as mean, which was completely not my intention. Attacking SHA256 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 personyears of researcher time were spent demonstrating that, among other things, SHA256 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 tinfoil paranoid.

I'm an independent developer working on bitcoincore, making my living off community donations. If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP



Shevek


September 26, 2011, 09:36:34 AM 

EDIT: That came off as mean, which was completely not my intention. Attacking SHA256 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 personyears of researcher time were spent demonstrating that, among other things, SHA256 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 onetoone function y= SHA256(x') where x' is a 256bit 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 (yx') 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 (yx'), 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?

Proposals for improving bitcoin are like asses: everybody has one 1SheveKuPHpzpLqSvPSavik9wnC51voBa



fivebells


September 26, 2011, 10:25:00 AM 

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 precomputed 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


September 26, 2011, 10:31:12 AM 

I'm talking about the onetoone function y= SHA256(x') where x' is a 256bit number.
It is extremely unlikely that this function is onetoone, due to the birthday paradox.




Hawkix


September 26, 2011, 06:18:30 PM 

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


September 26, 2011, 06:55:26 PM 

facepalm @ Hawkix




hashcoin


September 27, 2011, 07:14:46 AM 

@hashcoin: that's the case for a secondpreimage attack, but I believe my statement holds for a firstpreimage 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 firstpreimage 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 preimage attack means finding any x' s.t. H(x') = H(x), not finding the original x.




