{"type":"rich","version":"1.0","author_name":"npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","author_url":"https://nostr.ae/npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-01-07\n📝 Original message:So just because other attacks are possible we should weaken the crypto\nwe use? You may feel comfortable weakening crypto used to protect a few\nbillion dollars of other peoples' money, but I dont.\n\nOn 01/07/16 23:39, Gavin Andresen via bitcoin-dev wrote:\n\u003e Thanks, Ethan, that's helpful and I'll stop thinking that collision\n\u003e attacks require 2^(n/2) memory...\n\u003e \n\u003e So can we quantify the incremental increase in security of\n\u003e SHA256(SHA256) over RIPEMD160(SHA256) versus the incremental increase in\n\u003e security of having a simpler implementation of segwitness?\n\u003e \n\u003e I'm going to claim that the difference in the first case is very, very,\n\u003e very small-- the risk of an implementation error caused by having\n\u003e multiple ways of interpreting the segwitness hash in the scriptPubKey is\n\u003e much, much greater.\n\u003e \n\u003e And even if there IS some risk of collision attack now or at some point\n\u003e in the future, I claim that it is easy for wallets to mitigate that\n\u003e risk. In fact, the principle of security in depth means wallets that\n\u003e don't completely control the scriptPubKeys they're creating on behalf of\n\u003e users SHOULD be coded to mitigate that risk (e.g. not allowing arbitrary\n\u003e data around a user's public key in a Script so targeted substring\n\u003e attacks are eliminated entirely).\n\u003e \n\u003e Purely from a security point of view, I think a single 20-byte\n\u003e segwitness in the scriptPubKey is the best design.\n\u003e \"Keep the design as simple and small as possible\"\n\u003e https://www.securecoding.cert.org/confluence/plugins/servlet/mobile#content/view/2426\n\u003e \n\u003e Add in the implied capacity increase of smaller scriptPubKeys and I\n\u003e still think it is a no-brainer.\n\u003e \n\u003e \n\u003e On Thu, Jan 7, 2016 at 5:56 PM, Ethan Heilman \u003ceth3rs at gmail.com\n\u003e \u003cmailto:eth3rs at gmail.com\u003e\u003e wrote:\n\u003e \n\u003e     \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\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\n\u003e     \u003cmailto:bitcoin-dev at lists.linuxfoundation.org\u003e\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\n\u003e     broken\n\u003e     \u003e before SHA256?\n\u003e     \u003e And do you have some reason to think that they will be so broken\n\u003e     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\n\u003e     the 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\n\u003e     collide. That\n\u003e     \u003e isn't useful as an attack in the context we're talking about here\n\u003e     (both 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\n\u003e     time 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     \u003cmailto:bitcoin-dev at lists.linuxfoundation.org\u003e\n\u003e     \u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e     \u003e\n\u003e \n\u003e \n\u003e \n\u003e \n\u003e -- \n\u003e --\n\u003e Gavin Andresen\n\u003e \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"}