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