Bitcoin Forum
December 05, 2016, 06:51:37 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2]  All
  Print  
Author Topic: Cryptographic reasoning for double-hash?  (Read 7086 times)
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
September 26, 2011, 12:27:25 AM
 #21

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 bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
1480963897
Hero Member
*
Offline Offline

Posts: 1480963897

View Profile Personal Message (Offline)

Ignore
1480963897
Reply with quote  #2

1480963897
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480963897
Hero Member
*
Offline Offline

Posts: 1480963897

View Profile Personal Message (Offline)

Ignore
1480963897
Reply with quote  #2

1480963897
Report to moderator
1480963897
Hero Member
*
Offline Offline

Posts: 1480963897

View Profile Personal Message (Offline)

Ignore
1480963897
Reply with quote  #2

1480963897
Report to moderator
1480963897
Hero Member
*
Offline Offline

Posts: 1480963897

View Profile Personal Message (Offline)

Ignore
1480963897
Reply with quote  #2

1480963897
Report to moderator
hashcoin
Full Member
***
Offline Offline

Activity: 122


View Profile
September 26, 2011, 01:06:35 AM
 #22

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
Sr. Member
****
Offline Offline

Activity: 360


View Profile
September 26, 2011, 02:28:40 AM
 #23

Right, and what about h(x) = f(x) xor g(x)  ?
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
September 26, 2011, 06:29:45 AM
 #24

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 Offline

Activity: 1302



View Profile
September 26, 2011, 06:45:40 AM
 #25

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
September 26, 2011, 07:31:22 AM
 #26

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

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
September 26, 2011, 07:57:02 AM
 #27

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
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
September 26, 2011, 08:15:32 AM
 #28

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
September 26, 2011, 09:36:34 AM
 #29

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?

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
fivebells
Sr. Member
****
Offline Offline

Activity: 462


View Profile
September 26, 2011, 10:25:00 AM
 #30

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
Sr. Member
****
Offline Offline

Activity: 360


View Profile
September 26, 2011, 10:31:12 AM
 #31

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
Hero Member
*****
Offline Offline

Activity: 517



View Profile WWW
September 26, 2011, 06:18:30 PM
 #32

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.

Donations: 1Hawkix7GHym6SM98ii5vSHHShA3FUgpV6
http://btcportal.net/ - All about Bitcoin - coming soon!
iddo
Sr. Member
****
Offline Offline

Activity: 360


View Profile
September 26, 2011, 06:55:26 PM
 #33

facepalm @ Hawkix
hashcoin
Full Member
***
Offline Offline

Activity: 122


View Profile
September 27, 2011, 07:14:46 AM
 #34

@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.
Pages: « 1 [2]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!