rich1.0npub1gaszwl7qd0tjmnwcaamgzzgsmzzjlvle6kz0td66pwa8z69vsxsqxgac47https://nostr.ae/npub1gaszwl7qd0tjmnwcaamgzzgsmzzjlvle6kz0td66pwa8z69vsxsqxgac47njumphttps://nostr.ae📅 Original date posted:2016-01-07 📝 Original message:Based on current GH/s count of 775,464,121 Bitcoin tests 2^80 every 19 days. log2(775464121*(1000*1000*1000*60*60*24*19)) = ~80.07 I don't fully understand the security model of segwit, so my analysis will assume that any collision is bad. >But it also requires O(2^80) storage, which is utterly infeasible You don't store all 2^80 previous hashes, instead you just hash a seed value 2^80 times, then look for a cycle. seed = {0,1}^160 x = hash(seed) for i in 2^80: ....x = hash(x) x_final = x y = hash(x_final) for j in 2^80: ....if y == x_final: ........print "cycle len: "+j ........break ....y = hash(y) If at any point x collides with a prior value of x it will form a cycle. Thus y will also cycle and collide with x_final. j gives you the cycle length, which allows you find the collision: hash^(2^80-j)(seed) == hash^(j)(hash^(2^80-j)(seed)). Worst case: First loop costs 2**80, second loop costs 2**80=j, finding the colliding value is 2**80. Total cost 2**80+2**80+2**80 = 2**81.5 and requires storing less than a kilobyte. This is a toy example, does not exploit parallelism, time memory trade offs, can be easily made better, etc... On Thu, Jan 7, 2016 at 2:02 PM, Gavin Andresen via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote: > I'm hoisting this from some private feedback I sent on the segregated > witness BIP: > > I said: > > "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12 > bytes-- a successful preimage attack against that ain't gonna happen before > we're all dead. I'm probably being dense, but I just don't see how a > collision attack is relevant here." > > Pieter responded: > > "The problem case is where someone in a contract setup shows you a script, > which you accept as being a payment to yourself. An attacker could use a > collision attack to construct scripts with identical hashes, only one of > which does have the property you want, and steal coins. > > So you really want collision security, and I don't think 80 bits is > something we should encourage for that. Normal pubkey hashes don't have that > problem, as they can't be constructed to pay to you." > > ... but I'm unconvinced: > > "But it is trivial for contract wallets to protect against collision > attacks-- if you give me a script that is "gavin_pubkey CHECKSIG > arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just > ignore that arbitrary data" a wallet can just refuse. Even more likely, a > contract wallet won't even recognize that as a pay-to-gavin transaction. > > I suppose it could be looking for some form of "gavin_pubkey > somebody_else_pubkey CHECKMULTISIG ... with the attacker using > somebody_else_pubkey to force the collision, but, again, trivial contract > protocol tweaks ("send along a proof you have the private key corresponding > to the public key" or "everybody pre-commits pubkeys they'll use at protocol > start") would protect against that. > > Adding an extra 12 bytes to every segwit to prevent an attack that takes > 2^80 computation and 2^80 storage, is unlikely to be a problem in practice, > and is trivial to protect against is the wrong tradeoff to make." > > 20 bytes instead of 32 bytes is a savings of almost 40%, which is > significant. > > The general question I'd like to raise on this list is: > > Should we be worried, today, about collision attacks against RIPEMD160 (our > 160-bit hash)? > > Mounting a successful brute-force collision attack would require at least > O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin > POW has computed more SHA256 hashes than that). But it also requires O(2^80) > storage, which is utterly infeasible (there is something on the order of > 2^35 bytes of storage in the entire world). Even assuming doubling every > single year (faster than Moore's Law), we're four decades away from an > attacker with THE ENTIRE WORLD's storage capacity being able to mount a > collision attack. > > > References: > > https://en.wikipedia.org/wiki/Collision_attack > > https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/ > > > -- > -- > Gavin Andresen > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >