{"type":"rich","version":"1.0","author_name":"npub17rld56k4365lfphyd8u8kwuejey5xcazdxptserx03wc4jc9g24stx9l2h","author_url":"https://nostr.ae/npub17rld56k4365lfphyd8u8kwuejey5xcazdxptserx03wc4jc9g24stx9l2h","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-01-08\n📝 Original message:On Fri, Jan 08, 2016 at 07:38:50AM -0500, Gavin Andresen via bitcoin-dev wrote:\n\u003e Lets see if I've followed the specifics of the collision attack correctly,\n\u003e Ethan (or somebody) please let me know if I'm missing something:\n\u003e \n\u003e So attacker is in the middle of establishing a payment channel with\n\u003e somebody. Victim gives their public key, attacker creates the innocent\n\u003e fund-locking script  '2 V A 2 CHECKMULTISIG' (V is victim's public key, A\n\u003e is attacker's) but doesn't give it to the victim yet.\n\nUsing Ethan Heilman's procedure, the attacker can create two scripts:\n\n  2 V __A1__ 2 CHECKMULTISIG\n\n  2 V __A2__ 2 CHECKMULTISIG\n\nand find values A1 and A2 which hash the scripts to the same result\nwith under 3*2**80 work. I think you can do that by setting the next\nprivate key as the result of RIPEMD(SHA256(script with pubkey)), so you\ncould still spend either. But it doesn't change the script, so it's not\n*that* helpful -- you've just got two different keys you can use.\n\nAh, but you can make the form of the script be a function of your key, so:\n\n  if privkey % 2 == 0:\n    script = \"2 V %s 2 CHECKMULTISIG\" % (pubkey)\n  else:\n    script = \"%s CHECKSIG\" % (pubkey)\n  hash = ripemd160(sha256(script))\n\n  nextprivkey = hash\n\nThen you have a 50% chance of your cycle giving you a matching hash for\none script with A1 and the other script with A2, and you can find the\ncycle with under 3*2**80 work. Doing five attempts should give you ~96%\nchance of hitting a usable pair, and should take under 15*2**80 work ~=\n2**84 work, with trivial memory use.\n\nTrying that in python with a vastly weakened hash function (namely,\nthe first five bytes of ripemd160(sha256()), with 40 bits of security\nand 3*2**20 work) works as expected -- I got a \"useful\" collision on my\nsecond try in about 7 seconds, seeding with \"grumpycat3\" (\"grumpycat2\"\ndidn't work) with the result being:\n\n hexlify(ripemd160(sha256(\"foo%sbar\"%unhexlify(\"86f9fbac1a\")))[:5])\n 'ae94d9f908'\n\n hexlify(ripemd160(sha256(\"baz%squux\"%unhexlify(\"104fc5093f\")))[:5])\n 'ae94d9f908'\n\nCheers,\naj"}