{"type":"rich","version":"1.0","author_name":"npub1s4lj77xuzcu7wy04afcr487f0r3za0f8n2775xrpkld2sv639mjqsd44kw","author_url":"https://nostr.ae/npub1s4lj77xuzcu7wy04afcr487f0r3za0f8n2775xrpkld2sv639mjqsd44kw","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-01-07\n📝 Original message:Thanks, Ethan, that's helpful and I'll stop thinking that collision attacks\nrequire 2^(n/2) memory...\n\nSo can we quantify the incremental increase in security of SHA256(SHA256)\nover RIPEMD160(SHA256) versus the incremental increase in security of\nhaving a simpler implementation of segwitness?\n\nI'm going to claim that the difference in the first case is very, very,\nvery small-- the risk of an implementation error caused by having multiple\nways of interpreting the segwitness hash in the scriptPubKey is much, much\ngreater.\n\nAnd even if there IS some risk of collision attack now or at some point in\nthe future, I claim that it is easy for wallets to mitigate that risk. In\nfact, the principle of security in depth means wallets that don't\ncompletely control the scriptPubKeys they're creating on behalf of users\nSHOULD be coded to mitigate that risk (e.g. not allowing arbitrary data\naround a user's public key in a Script so targeted substring attacks are\neliminated entirely).\n\nPurely from a security point of view, I think a single 20-byte segwitness\nin the scriptPubKey is the best design.\n\"Keep the design as simple and small as possible\"\nhttps://www.securecoding.cert.org/confluence/plugins/servlet/mobile#content/view/2426\n\nAdd in the implied capacity increase of smaller scriptPubKeys and I still\nthink it is a no-brainer.\n\n\nOn Thu, Jan 7, 2016 at 5:56 PM, Ethan Heilman \u003ceth3rs at gmail.com\u003e wrote:\n\n\u003e \u003eEthan:  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 I'm not sure exactly the properties you want here and determining\n\u003e these properties is not an easy task, but the case is far worse than\n\u003e just two random values. For instance: (a). with a small modification\n\u003e my algorithm can also find collisions containing targeted substrings,\n\u003e (b). length extension attacks are possible with RIPEMD160.\n\u003e\n\u003e (a). targeted cycles:\n\u003e\n\u003e target1 = \"str to prepend\"\n\u003e target2 = \"str to end with\"\n\u003e\n\u003e seed = {0,1}^160\n\u003e x = hash(seed)\n\u003e\n\u003e for i in 2^80:\n\u003e ....x = hash(target1||x||target2)\n\u003e x_final = x\n\u003e\n\u003e y = hash(tartget1||x_final||target2)\n\u003e\n\u003e for j in 2^80:\n\u003e ....if y == x_final:\n\u003e ........print \"cycle len: \"+j\n\u003e ........break\n\u003e ....y = hash(target1||y||target2)\n\u003e\n\u003e If a collision is found, the two colliding inputs must both start with\n\u003e \"str to prepend\" and end with the phrase \"str to end with\". As before\n\u003e this only requires 2^81.5 computations and no real memory. For an\n\u003e additional 2**80 an adversary has an good change of finding two\n\u003e different targeted substrings which collide. Consider the case where\n\u003e the attacker mixes the targeted strings with the hash output:\n\u003e\n\u003e hash(\"my name is=0x329482039483204324423\"+x[1]+\", my favorite number\n\u003e is=\"+x) where x[1] is the first bit of x.\n\u003e\n\u003e (b). length extension attacks\n\u003e\n\u003e Even if all the adversary can do is create two random values that\n\u003e collide, you can append substrings to the input and get collisions.\n\u003e Once you find two random values hash(x) = hash(y), you could use a\n\u003e length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).\n\u003e\n\u003e Now the bitcoin wiki says:\n\u003e \"The padding scheme is identical to MD4 using Merkle–Damgård\n\u003e strengthening to prevent length extension attacks.\"[1]\n\u003e\n\u003e Which is confusing to me because:\n\u003e\n\u003e 1. MD4 is vulnerable to length extension attacks\n\u003e 2. Merkle–Damgård strengthening does not protect against length\n\u003e extension: \"Indeed, we already pointed out that none of the 64\n\u003e variants above can withstand the 'extension' attack on the MAC\n\u003e application, even with the Merkle-Damgard strengthening\" [2]\n\u003e 3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin\n\u003e using a non-standard version of RIPEMD-160.\n\u003e\n\u003e RIPEMD160(SHA256()) does not protect against length extension attacks\n\u003e on SHA256, but should protect RIPEMD-160 against length extension\n\u003e attacks as RIPEMD-160 uses 512-bit message blocks. That being said we\n\u003e should be very careful here. Research has been done that shows that\n\u003e cascading the same hash function twice is weaker than using HMAC[3]. I\n\u003e can't find results on cascading RIPEMD160(SHA256()).\n\u003e\n\u003e RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security\n\u003e should not rest on the notion that an attacker requires 2**80 memory,\n\u003e many targeted collision attacks can work without much memory.\n\u003e\n\u003e [1]: https://en.bitcoin.it/wiki/RIPEMD-160\n\u003e [2]: \"Merkle-Damgard Revisited: How to Construct a Hash Function\"\n\u003e https://www.cs.nyu.edu/~puniya/papers/merkle.pdf\n\u003e [3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf\n\u003e\n\u003e On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev\n\u003e \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e \u003e Maybe I'm asking this question on the wrong mailing list:\n\u003e \u003e\n\u003e \u003e Matt/Adam: do you have some reason to think that RIPEMD160 will be broken\n\u003e \u003e before SHA256?\n\u003e \u003e And do you have some reason to think that they will be so broken that the\n\u003e \u003e nested hash construction RIPEMD160(SHA256()) will be vulnerable?\n\u003e \u003e\n\u003e \u003e Adam: re: \"where to stop\"  :  I'm suggesting we stop exactly at the\n\u003e current\n\u003e \u003e status quo, where we use RIPEMD160 for P2SH and P2PKH.\n\u003e \u003e\n\u003e \u003e Ethan:  your algorithm will find two arbitrary values that collide. That\n\u003e \u003e isn't useful as an attack in the context we're talking about here (both\n\u003e of\n\u003e \u003e those values will be useless as coin destinations with overwhelming\n\u003e \u003e probability).\n\u003e \u003e\n\u003e \u003e Dave: you described a first preimage attack, which is 2**160 cpu time\n\u003e and no\n\u003e \u003e storage.\n\u003e \u003e\n\u003e \u003e\n\u003e \u003e --\n\u003e \u003e --\n\u003e \u003e Gavin Andresen\n\u003e \u003e\n\u003e \u003e _______________________________________________\n\u003e \u003e bitcoin-dev mailing list\n\u003e \u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e \u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e \u003e\n\u003e\n\n\n\n-- \n--\nGavin Andresen\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160107/39e4d3d6/attachment-0001.html\u003e"}