{"type":"rich","version":"1.0","author_name":"npub1gaszwl7qd0tjmnwcaamgzzgsmzzjlvle6kz0td66pwa8z69vsxsqxgac47","author_url":"https://nostr.ae/npub1gaszwl7qd0tjmnwcaamgzzgsmzzjlvle6kz0td66pwa8z69vsxsqxgac47","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-01-07\n📝 Original message:\u003eEthan:  your algorithm will find two arbitrary values that collide. That isn't useful as an attack in the context we're talking about here (both of those values will be useless as coin destinations with overwhelming probability).\n\nI'm not sure exactly the properties you want here and determining\nthese properties is not an easy task, but the case is far worse than\njust two random values. For instance: (a). with a small modification\nmy algorithm can also find collisions containing targeted substrings,\n(b). length extension attacks are possible with RIPEMD160.\n\n(a). targeted cycles:\n\ntarget1 = \"str to prepend\"\ntarget2 = \"str to end with\"\n\nseed = {0,1}^160\nx = hash(seed)\n\nfor i in 2^80:\n....x = hash(target1||x||target2)\nx_final = x\n\ny = hash(tartget1||x_final||target2)\n\nfor j in 2^80:\n....if y == x_final:\n........print \"cycle len: \"+j\n........break\n....y = hash(target1||y||target2)\n\nIf a collision is found, the two colliding inputs must both start with\n\"str to prepend\" and end with the phrase \"str to end with\". As before\nthis only requires 2^81.5 computations and no real memory. For an\nadditional 2**80 an adversary has an good change of finding two\ndifferent targeted substrings which collide. Consider the case where\nthe attacker mixes the targeted strings with the hash output:\n\nhash(\"my name is=0x329482039483204324423\"+x[1]+\", my favorite number\nis=\"+x) where x[1] is the first bit of x.\n\n(b). length extension attacks\n\nEven if all the adversary can do is create two random values that\ncollide, you can append substrings to the input and get collisions.\nOnce you find two random values hash(x) = hash(y), you could use a\nlength extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).\n\nNow the bitcoin wiki says:\n\"The padding scheme is identical to MD4 using Merkle–Damgård\nstrengthening to prevent length extension attacks.\"[1]\n\nWhich is confusing to me because:\n\n1. MD4 is vulnerable to length extension attacks\n2. Merkle–Damgård strengthening does not protect against length\nextension: \"Indeed, we already pointed out that none of the 64\nvariants above can withstand the 'extension' attack on the MAC\napplication, even with the Merkle-Damgard strengthening\" [2]\n3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin\nusing a non-standard version of RIPEMD-160.\n\nRIPEMD160(SHA256()) does not protect against length extension attacks\non SHA256, but should protect RIPEMD-160 against length extension\nattacks as RIPEMD-160 uses 512-bit message blocks. That being said we\nshould be very careful here. Research has been done that shows that\ncascading the same hash function twice is weaker than using HMAC[3]. I\ncan't find results on cascading RIPEMD160(SHA256()).\n\nRIPEMD160(SHA256()) seems better than RIPEMD160() though, but security\nshould not rest on the notion that an attacker requires 2**80 memory,\nmany targeted collision attacks can work without much memory.\n\n[1]: https://en.bitcoin.it/wiki/RIPEMD-160\n[2]: \"Merkle-Damgard Revisited: How to Construct a Hash Function\"\nhttps://www.cs.nyu.edu/~puniya/papers/merkle.pdf\n[3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf\n\nOn Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev\n\u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e Maybe I'm asking this question on the wrong mailing list:\n\u003e\n\u003e Matt/Adam: do you have some reason to think that RIPEMD160 will be broken\n\u003e before SHA256?\n\u003e And do you have some reason to think that they will be so broken that the\n\u003e nested hash construction RIPEMD160(SHA256()) will be vulnerable?\n\u003e\n\u003e Adam: re: \"where to stop\"  :  I'm suggesting we stop exactly at the current\n\u003e status quo, where we use RIPEMD160 for P2SH and P2PKH.\n\u003e\n\u003e Ethan:  your algorithm will find two arbitrary values that collide. That\n\u003e isn't useful as an attack in the context we're talking about here (both of\n\u003e those values will be useless as coin destinations with overwhelming\n\u003e probability).\n\u003e\n\u003e Dave: you described a first preimage attack, which is 2**160 cpu time and no\n\u003e storage.\n\u003e\n\u003e\n\u003e --\n\u003e --\n\u003e Gavin Andresen\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e"}