* [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
@ 2016-01-07 19:02 Gavin Andresen
2016-01-07 19:13 ` Matt Corallo
` (3 more replies)
0 siblings, 4 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-07 19:02 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2810 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 4254 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 19:02 [bitcoin-dev] Time to worry about 80-bit collision attacks or not? Gavin Andresen
@ 2016-01-07 19:13 ` Matt Corallo
2016-01-07 19:19 ` Adam Back
` (2 subsequent siblings)
3 siblings, 0 replies; 34+ messages in thread
From: Matt Corallo @ 2016-01-07 19:13 UTC (permalink / raw)
To: Gavin Andresen, Bitcoin Dev
We absolutely should be worried about 80-bit collision resistance.
Collisions only take 2**80 work if the hash is theoretically perfect,
which is never the case, not to mention that collision resistance is
almost always the first thing to go for hash functions, and often starts
to get easier slowly long, long before anyone is truly worried about the
security of the hash function.
I would never assume RIPEMD160's collision resistance is 2**80, and
would definitely never wager a significant amount of money that this
remains true for, say, five years.
Matt
On 01/07/16 19:02, Gavin Andresen via bitcoin-dev 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@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 19:02 [bitcoin-dev] Time to worry about 80-bit collision attacks or not? Gavin Andresen
2016-01-07 19:13 ` Matt Corallo
@ 2016-01-07 19:19 ` Adam Back
2016-01-07 20:56 ` Dave Scotese
2016-01-07 20:40 ` Ethan Heilman
2016-01-07 23:52 ` Pieter Wuille
3 siblings, 1 reply; 34+ messages in thread
From: Adam Back @ 2016-01-07 19:19 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
You could say 256 bit ECDSA is overkill lets go to 160 equivalently.
Saves even more bytes.
The problem with arguing down is where to stop.
As Matt said these things dont degrade gracefully so a best practice
is to aim for a bit of extra margin.
256-bit is quite common at this point since AES, SHA256 etc even in
things with much less at stake than Bitcoin.
You could send the compressed (unhashed) pubkey then there's no hash
(and omit it from the sig). Greg had mentioned that in the past.
I think it might be possible to do both (reclaim the hash bits in the
serialisation of the pub key).
Adam
On 7 January 2016 at 20:02, Gavin Andresen via bitcoin-dev
<bitcoin-dev@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@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 19:02 [bitcoin-dev] Time to worry about 80-bit collision attacks or not? Gavin Andresen
2016-01-07 19:13 ` Matt Corallo
2016-01-07 19:19 ` Adam Back
@ 2016-01-07 20:40 ` Ethan Heilman
2016-01-07 23:52 ` Pieter Wuille
3 siblings, 0 replies; 34+ messages in thread
From: Ethan Heilman @ 2016-01-07 20:40 UTC (permalink / raw)
To: Bitcoin Dev
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@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@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 19:19 ` Adam Back
@ 2016-01-07 20:56 ` Dave Scotese
2016-01-07 21:06 ` Gavin Andresen
0 siblings, 1 reply; 34+ messages in thread
From: Dave Scotese @ 2016-01-07 20:56 UTC (permalink / raw)
To: Adam Back; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 5685 bytes --]
Maybe I'm being dense, but I don't see why 2**80 storage is required for
this attack. Also, I don't see why the attacker ever needs to get the
victim to accept "arbitrary_data". Perhaps I'm wrong about how the
collision attack works:
1. Create a script which is perfectly acceptable and would pass the
sniff test Gavin proposed (no arbitrary_data).
2. Set off CPU power to construct a second script that lets attacker
keep his coins and has the same hash. (This is where you get
"arbitrary_data").
3. Send a transaction with the first script to the seller as payment.
4. Wait for the transaction to be included in a block.
5. Redeem the transaction with the second script, thus stealing the
coins back.
So the seller would never see the I'd appreciate any correction to my
understanding here. Where do you need 2**80 storage? And when does the
seller have to accept "arbitrary_data"?
Thanks!
On Thu, Jan 7, 2016 at 11:19 AM, Adam Back via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> You could say 256 bit ECDSA is overkill lets go to 160 equivalently.
> Saves even more bytes.
>
> The problem with arguing down is where to stop.
>
> As Matt said these things dont degrade gracefully so a best practice
> is to aim for a bit of extra margin.
>
> 256-bit is quite common at this point since AES, SHA256 etc even in
> things with much less at stake than Bitcoin.
>
> You could send the compressed (unhashed) pubkey then there's no hash
> (and omit it from the sig). Greg had mentioned that in the past.
>
> I think it might be possible to do both (reclaim the hash bits in the
> serialisation of the pub key).
>
> Adam
>
> On 7 January 2016 at 20:02, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@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@lists•linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--
I like to provide some work at no charge to prove my value. Do you need a
techie?
I own Litmocracy <http://www.litmocracy.com> and Meme Racing
<http://www.memeracing.net> (in alpha).
I'm the webmaster for The Voluntaryist <http://www.voluntaryist.com> which
now accepts Bitcoin.
I also code for The Dollar Vigilante <http://dollarvigilante.com/>.
"He ought to find it more profitable to play by the rules" - Satoshi
Nakamoto
[-- Attachment #2: Type: text/html, Size: 7728 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 20:56 ` Dave Scotese
@ 2016-01-07 21:06 ` Gavin Andresen
2016-01-07 22:56 ` Ethan Heilman
0 siblings, 1 reply; 34+ messages in thread
From: Gavin Andresen @ 2016-01-07 21:06 UTC (permalink / raw)
To: Dave Scotese; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 761 bytes --]
Maybe I'm asking this question on the wrong mailing list:
Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
before SHA256?
And do you have some reason to think that they will be so broken that the
nested hash construction RIPEMD160(SHA256()) will be vulnerable?
Adam: re: "where to stop" : I'm suggesting we stop exactly at the current
status quo, where we use RIPEMD160 for P2SH and P2PKH.
Ethan: 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).
Dave: you described a first preimage attack, which is 2**160 cpu time and
no storage.
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 1034 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 21:06 ` Gavin Andresen
@ 2016-01-07 22:56 ` Ethan Heilman
2016-01-07 23:39 ` Gavin Andresen
0 siblings, 1 reply; 34+ messages in thread
From: Ethan Heilman @ 2016-01-07 22:56 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
>Ethan: 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).
I'm not sure exactly the properties you want here and determining
these properties is not an easy task, but the case is far worse than
just two random values. For instance: (a). with a small modification
my algorithm can also find collisions containing targeted substrings,
(b). length extension attacks are possible with RIPEMD160.
(a). targeted cycles:
target1 = "str to prepend"
target2 = "str to end with"
seed = {0,1}^160
x = hash(seed)
for i in 2^80:
....x = hash(target1||x||target2)
x_final = x
y = hash(tartget1||x_final||target2)
for j in 2^80:
....if y == x_final:
........print "cycle len: "+j
........break
....y = hash(target1||y||target2)
If a collision is found, the two colliding inputs must both start with
"str to prepend" and end with the phrase "str to end with". As before
this only requires 2^81.5 computations and no real memory. For an
additional 2**80 an adversary has an good change of finding two
different targeted substrings which collide. Consider the case where
the attacker mixes the targeted strings with the hash output:
hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
is="+x) where x[1] is the first bit of x.
(b). length extension attacks
Even if all the adversary can do is create two random values that
collide, you can append substrings to the input and get collisions.
Once you find two random values hash(x) = hash(y), you could use a
length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).
Now the bitcoin wiki says:
"The padding scheme is identical to MD4 using Merkle–Damgård
strengthening to prevent length extension attacks."[1]
Which is confusing to me because:
1. MD4 is vulnerable to length extension attacks
2. Merkle–Damgård strengthening does not protect against length
extension: "Indeed, we already pointed out that none of the 64
variants above can withstand the 'extension' attack on the MAC
application, even with the Merkle-Damgard strengthening" [2]
3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
using a non-standard version of RIPEMD-160.
RIPEMD160(SHA256()) does not protect against length extension attacks
on SHA256, but should protect RIPEMD-160 against length extension
attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
should be very careful here. Research has been done that shows that
cascading the same hash function twice is weaker than using HMAC[3]. I
can't find results on cascading RIPEMD160(SHA256()).
RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
should not rest on the notion that an attacker requires 2**80 memory,
many targeted collision attacks can work without much memory.
[1]: https://en.bitcoin.it/wiki/RIPEMD-160
[2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
[3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf
On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> Maybe I'm asking this question on the wrong mailing list:
>
> Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
> before SHA256?
> And do you have some reason to think that they will be so broken that the
> nested hash construction RIPEMD160(SHA256()) will be vulnerable?
>
> Adam: re: "where to stop" : I'm suggesting we stop exactly at the current
> status quo, where we use RIPEMD160 for P2SH and P2PKH.
>
> Ethan: 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).
>
> Dave: you described a first preimage attack, which is 2**160 cpu time and no
> storage.
>
>
> --
> --
> Gavin Andresen
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 22:56 ` Ethan Heilman
@ 2016-01-07 23:39 ` Gavin Andresen
2016-01-08 1:26 ` Matt Corallo
0 siblings, 1 reply; 34+ messages in thread
From: Gavin Andresen @ 2016-01-07 23:39 UTC (permalink / raw)
To: Ethan Heilman; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 6004 bytes --]
Thanks, Ethan, that's helpful and I'll stop thinking that collision attacks
require 2^(n/2) memory...
So can we quantify the incremental increase in security of SHA256(SHA256)
over RIPEMD160(SHA256) versus the incremental increase in security of
having a simpler implementation of segwitness?
I'm going to claim that the difference in the first case is very, very,
very small-- the risk of an implementation error caused by having multiple
ways of interpreting the segwitness hash in the scriptPubKey is much, much
greater.
And even if there IS some risk of collision attack now or at some point in
the future, I claim that it is easy for wallets to mitigate that risk. In
fact, the principle of security in depth means wallets that don't
completely control the scriptPubKeys they're creating on behalf of users
SHOULD be coded to mitigate that risk (e.g. not allowing arbitrary data
around a user's public key in a Script so targeted substring attacks are
eliminated entirely).
Purely from a security point of view, I think a single 20-byte segwitness
in the scriptPubKey is the best design.
"Keep the design as simple and small as possible"
https://www.securecoding.cert.org/confluence/plugins/servlet/mobile#content/view/2426
Add in the implied capacity increase of smaller scriptPubKeys and I still
think it is a no-brainer.
On Thu, Jan 7, 2016 at 5:56 PM, Ethan Heilman <eth3rs@gmail•com> wrote:
> >Ethan: 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).
>
> I'm not sure exactly the properties you want here and determining
> these properties is not an easy task, but the case is far worse than
> just two random values. For instance: (a). with a small modification
> my algorithm can also find collisions containing targeted substrings,
> (b). length extension attacks are possible with RIPEMD160.
>
> (a). targeted cycles:
>
> target1 = "str to prepend"
> target2 = "str to end with"
>
> seed = {0,1}^160
> x = hash(seed)
>
> for i in 2^80:
> ....x = hash(target1||x||target2)
> x_final = x
>
> y = hash(tartget1||x_final||target2)
>
> for j in 2^80:
> ....if y == x_final:
> ........print "cycle len: "+j
> ........break
> ....y = hash(target1||y||target2)
>
> If a collision is found, the two colliding inputs must both start with
> "str to prepend" and end with the phrase "str to end with". As before
> this only requires 2^81.5 computations and no real memory. For an
> additional 2**80 an adversary has an good change of finding two
> different targeted substrings which collide. Consider the case where
> the attacker mixes the targeted strings with the hash output:
>
> hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
> is="+x) where x[1] is the first bit of x.
>
> (b). length extension attacks
>
> Even if all the adversary can do is create two random values that
> collide, you can append substrings to the input and get collisions.
> Once you find two random values hash(x) = hash(y), you could use a
> length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).
>
> Now the bitcoin wiki says:
> "The padding scheme is identical to MD4 using Merkle–Damgård
> strengthening to prevent length extension attacks."[1]
>
> Which is confusing to me because:
>
> 1. MD4 is vulnerable to length extension attacks
> 2. Merkle–Damgård strengthening does not protect against length
> extension: "Indeed, we already pointed out that none of the 64
> variants above can withstand the 'extension' attack on the MAC
> application, even with the Merkle-Damgard strengthening" [2]
> 3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
> using a non-standard version of RIPEMD-160.
>
> RIPEMD160(SHA256()) does not protect against length extension attacks
> on SHA256, but should protect RIPEMD-160 against length extension
> attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
> should be very careful here. Research has been done that shows that
> cascading the same hash function twice is weaker than using HMAC[3]. I
> can't find results on cascading RIPEMD160(SHA256()).
>
> RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
> should not rest on the notion that an attacker requires 2**80 memory,
> many targeted collision attacks can work without much memory.
>
> [1]: https://en.bitcoin.it/wiki/RIPEMD-160
> [2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
> https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
> [3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf
>
> On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation.org> wrote:
> > Maybe I'm asking this question on the wrong mailing list:
> >
> > Matt/Adam: do you have some reason to think that RIPEMD160 will be broken
> > before SHA256?
> > And do you have some reason to think that they will be so broken that the
> > nested hash construction RIPEMD160(SHA256()) will be vulnerable?
> >
> > Adam: re: "where to stop" : I'm suggesting we stop exactly at the
> current
> > status quo, where we use RIPEMD160 for P2SH and P2PKH.
> >
> > Ethan: 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).
> >
> > Dave: you described a first preimage attack, which is 2**160 cpu time
> and no
> > storage.
> >
> >
> > --
> > --
> > Gavin Andresen
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists•linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
>
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 7775 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 19:02 [bitcoin-dev] Time to worry about 80-bit collision attacks or not? Gavin Andresen
` (2 preceding siblings ...)
2016-01-07 20:40 ` Ethan Heilman
@ 2016-01-07 23:52 ` Pieter Wuille
2016-01-08 1:00 ` Gavin Andresen
2016-01-08 3:30 ` Rusty Russell
3 siblings, 2 replies; 34+ messages in thread
From: Pieter Wuille @ 2016-01-07 23:52 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 2048 bytes --]
> "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.
Yes, this is what I worry about. We're constructing a 2-of-2 multisig
escrow in a contract. I reveal my public key A, you do a 80-bit search for
B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
happily send to H(A and B), which you steal with H(B and C).
Sending along a proof does not help, you can't prove that you do not know
of a collision. Pre-committing does help, but is a very non-obvious
security requirement, something I strongly believe is far riskier in
practice.
Bitcoin does have parts that rely on economic arguments for security or
privacy, but can we please stick to using cryptography that is up to par
for parts where we can? It's a small constant factor of data, and it
categorically removes the worry about security levels.
--
Pieter
[-- Attachment #2: Type: text/html, Size: 2312 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 23:52 ` Pieter Wuille
@ 2016-01-08 1:00 ` Gavin Andresen
2016-01-08 1:27 ` Watson Ladd
2016-01-08 3:30 ` Rusty Russell
1 sibling, 1 reply; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 1:00 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1030 bytes --]
On Thu, Jan 7, 2016 at 6:52 PM, Pieter Wuille <pieter.wuille@gmail•com>
wrote:
> Bitcoin does have parts that rely on economic arguments for security or
> privacy, but can we please stick to using cryptography that is up to par
> for parts where we can? It's a small constant factor of data, and it
> categorically removes the worry about security levels.
>
Our message may have crossed in the mod queue:
"So can we quantify the incremental increase in security of SHA256(SHA256)
over RIPEMD160(SHA256) versus the incremental increase in security of
having a simpler implementation of segwitness?"
I believe the history of computer security is that implementation errors
and sidechannel attacks are much, much more common than brute-force breaks.
KEEP IT SIMPLE.
(and a quibble: "do a 80-bit search for B and C such that H(A and B) = H(B
and C)" isn't enough, you have to end up with a C public key for which you
know the corresponding private key or the attacker just succeeds in burning
the funds)
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 1761 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 23:39 ` Gavin Andresen
@ 2016-01-08 1:26 ` Matt Corallo
2016-01-08 1:54 ` Gavin Andresen
0 siblings, 1 reply; 34+ messages in thread
From: Matt Corallo @ 2016-01-08 1:26 UTC (permalink / raw)
To: Gavin Andresen, Ethan Heilman; +Cc: Bitcoin Dev
So just because other attacks are possible we should weaken the crypto
we use? You may feel comfortable weakening crypto used to protect a few
billion dollars of other peoples' money, but I dont.
On 01/07/16 23:39, Gavin Andresen via bitcoin-dev wrote:
> Thanks, Ethan, that's helpful and I'll stop thinking that collision
> attacks require 2^(n/2) memory...
>
> So can we quantify the incremental increase in security of
> SHA256(SHA256) over RIPEMD160(SHA256) versus the incremental increase in
> security of having a simpler implementation of segwitness?
>
> I'm going to claim that the difference in the first case is very, very,
> very small-- the risk of an implementation error caused by having
> multiple ways of interpreting the segwitness hash in the scriptPubKey is
> much, much greater.
>
> And even if there IS some risk of collision attack now or at some point
> in the future, I claim that it is easy for wallets to mitigate that
> risk. In fact, the principle of security in depth means wallets that
> don't completely control the scriptPubKeys they're creating on behalf of
> users SHOULD be coded to mitigate that risk (e.g. not allowing arbitrary
> data around a user's public key in a Script so targeted substring
> attacks are eliminated entirely).
>
> Purely from a security point of view, I think a single 20-byte
> segwitness in the scriptPubKey is the best design.
> "Keep the design as simple and small as possible"
> https://www.securecoding.cert.org/confluence/plugins/servlet/mobile#content/view/2426
>
> Add in the implied capacity increase of smaller scriptPubKeys and I
> still think it is a no-brainer.
>
>
> On Thu, Jan 7, 2016 at 5:56 PM, Ethan Heilman <eth3rs@gmail•com
> <mailto:eth3rs@gmail•com>> wrote:
>
> >Ethan: 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).
>
> I'm not sure exactly the properties you want here and determining
> these properties is not an easy task, but the case is far worse than
> just two random values. For instance: (a). with a small modification
> my algorithm can also find collisions containing targeted substrings,
> (b). length extension attacks are possible with RIPEMD160.
>
> (a). targeted cycles:
>
> target1 = "str to prepend"
> target2 = "str to end with"
>
> seed = {0,1}^160
> x = hash(seed)
>
> for i in 2^80:
> ....x = hash(target1||x||target2)
> x_final = x
>
> y = hash(tartget1||x_final||target2)
>
> for j in 2^80:
> ....if y == x_final:
> ........print "cycle len: "+j
> ........break
> ....y = hash(target1||y||target2)
>
> If a collision is found, the two colliding inputs must both start with
> "str to prepend" and end with the phrase "str to end with". As before
> this only requires 2^81.5 computations and no real memory. For an
> additional 2**80 an adversary has an good change of finding two
> different targeted substrings which collide. Consider the case where
> the attacker mixes the targeted strings with the hash output:
>
> hash("my name is=0x329482039483204324423"+x[1]+", my favorite number
> is="+x) where x[1] is the first bit of x.
>
> (b). length extension attacks
>
> Even if all the adversary can do is create two random values that
> collide, you can append substrings to the input and get collisions.
> Once you find two random values hash(x) = hash(y), you could use a
> length extension attack on RIPEMD-160 to find hash(x||z) = hash(y||z).
>
> Now the bitcoin wiki says:
> "The padding scheme is identical to MD4 using Merkle–Damgård
> strengthening to prevent length extension attacks."[1]
>
> Which is confusing to me because:
>
> 1. MD4 is vulnerable to length extension attacks
> 2. Merkle–Damgård strengthening does not protect against length
> extension: "Indeed, we already pointed out that none of the 64
> variants above can withstand the 'extension' attack on the MAC
> application, even with the Merkle-Damgard strengthening" [2]
> 3. RIPEMD-160 is vulnerable to length extension attacks, is Bitcoin
> using a non-standard version of RIPEMD-160.
>
> RIPEMD160(SHA256()) does not protect against length extension attacks
> on SHA256, but should protect RIPEMD-160 against length extension
> attacks as RIPEMD-160 uses 512-bit message blocks. That being said we
> should be very careful here. Research has been done that shows that
> cascading the same hash function twice is weaker than using HMAC[3]. I
> can't find results on cascading RIPEMD160(SHA256()).
>
> RIPEMD160(SHA256()) seems better than RIPEMD160() though, but security
> should not rest on the notion that an attacker requires 2**80 memory,
> many targeted collision attacks can work without much memory.
>
> [1]: https://en.bitcoin.it/wiki/RIPEMD-160
> [2]: "Merkle-Damgard Revisited: How to Construct a Hash Function"
> https://www.cs.nyu.edu/~puniya/papers/merkle.pdf
> [3]: https://www.cs.nyu.edu/~dodis/ps/h-of-h.pdf
>
> On Thu, Jan 7, 2016 at 4:06 PM, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation.org
> <mailto:bitcoin-dev@lists•linuxfoundation.org>> wrote:
> > Maybe I'm asking this question on the wrong mailing list:
> >
> > Matt/Adam: do you have some reason to think that RIPEMD160 will be
> broken
> > before SHA256?
> > And do you have some reason to think that they will be so broken
> that the
> > nested hash construction RIPEMD160(SHA256()) will be vulnerable?
> >
> > Adam: re: "where to stop" : I'm suggesting we stop exactly at
> the current
> > status quo, where we use RIPEMD160 for P2SH and P2PKH.
> >
> > Ethan: 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).
> >
> > Dave: you described a first preimage attack, which is 2**160 cpu
> time and no
> > storage.
> >
> >
> > --
> > --
> > Gavin Andresen
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists•linuxfoundation.org
> <mailto:bitcoin-dev@lists•linuxfoundation.org>
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
>
>
>
>
> --
> --
> Gavin Andresen
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 1:00 ` Gavin Andresen
@ 2016-01-08 1:27 ` Watson Ladd
0 siblings, 0 replies; 34+ messages in thread
From: Watson Ladd @ 2016-01-08 1:27 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1615 bytes --]
On Jan 7, 2016 5:22 PM, "Gavin Andresen via bitcoin-dev" <
bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> On Thu, Jan 7, 2016 at 6:52 PM, Pieter Wuille <pieter.wuille@gmail•com>
wrote:
>>
>> Bitcoin does have parts that rely on economic arguments for security or
privacy, but can we please stick to using cryptography that is up to par
for parts where we can? It's a small constant factor of data, and it
categorically removes the worry about security levels.
>
> Our message may have crossed in the mod queue:
>
> "So can we quantify the incremental increase in security of
SHA256(SHA256) over RIPEMD160(SHA256) versus the incremental increase in
security of having a simpler implementation of segwitness?"
There are several clever ways to exploit even chosen prefix collisions
using the scripting language. One could search for collisions where one
message is some data and the other is a jump over a critical check.
>
> I believe the history of computer security is that implementation errors
and sidechannel attacks are much, much more common than brute-force breaks.
KEEP IT SIMPLE.
Ask the Iranian nuclear program. Or those brainwallet users.
>
> (and a quibble: "do a 80-bit search for B and C such that H(A and B) =
H(B and C)" isn't enough, you have to end up with a C public key for which
you know the corresponding private key or the attacker just succeeds in
burning the funds)
>
>
> --
> --
> Gavin Andresen
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 2173 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 1:26 ` Matt Corallo
@ 2016-01-08 1:54 ` Gavin Andresen
2016-01-08 17:38 ` Pieter Wuille
2016-01-08 18:41 ` Peter Todd
0 siblings, 2 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 1:54 UTC (permalink / raw)
To: Matt Corallo; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1555 bytes --]
On Thu, Jan 7, 2016 at 8:26 PM, Matt Corallo <lf-lists@mattcorallo•com>
wrote:
> So just because other attacks are possible we should weaken the crypto
> we use? You may feel comfortable weakening crypto used to protect a few
> billion dollars of other peoples' money, but I dont.
>
No...
I'm saying we can eliminate one somewhat unlikely attack (that there is a
bug in the code or test cases, today or some future version, that has to
decide what to do with "version 0" versus "version 1" witness programs) by
accepting the risk of another insanely, extremely unlikely attack.
Reference for those who are lost:
https://github.com/CodeShark/bips/blob/segwit/bip-codeshark-jl2012-segwit.mediawiki#witness-program
My proposal would be to just do a version 0 witness program now, that is
RIPEMD160(SHA256(script)).
And ten or twenty years from now, if there is a plausible attack on
RIPEMD160 and/or SHA256, revisit and do a version 11 (or whatever).
It will simplify the BIP, means half as many test cases have to be written,
means a little more scalability, and is as secure as the P2SH and P2PKH
everybody is using to secure their bitcoin today.
Tell you what: I'll change my mind if anybody can describe a plausible
attack if we were using MD5(SHA256), given what we know about how MD5 is
broken.
---
I'm really disappointed with the "Here's the spec, take it or leave it"
attitude. What's the point of having a BIP process if the discussion just
comes down to "We think more is better. We don't care what you think."
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 2753 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-07 23:52 ` Pieter Wuille
2016-01-08 1:00 ` Gavin Andresen
@ 2016-01-08 3:30 ` Rusty Russell
2016-01-08 3:41 ` Matt Corallo
2016-01-08 18:52 ` Peter Todd
1 sibling, 2 replies; 34+ messages in thread
From: Rusty Russell @ 2016-01-08 3:30 UTC (permalink / raw)
To: Pieter Wuille, Gavin Andresen; +Cc: Bitcoin Dev
Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>
writes:
> Yes, this is what I worry about. We're constructing a 2-of-2 multisig
> escrow in a contract. I reveal my public key A, you do a 80-bit search for
> B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
> happily send to H(A and B), which you steal with H(B and C).
FWIW, this attack would effect the current lightning-network "deployable
lightning" design at channel establishment; we reveal our pubkey in the
opening packet (which is used to redeem a P2SH using normal 2of2).
At least you need to grind before replying (which will presumably time
out), rather than being able to do it once the channel is open.
We could pre-commit by exchanging hashes of pubkeys first, but contracts
on bitcoin are hard enough to get right that I'm reluctant to add more
hoops.
Cheers,
Rusty.
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 3:30 ` Rusty Russell
@ 2016-01-08 3:41 ` Matt Corallo
2016-01-08 12:02 ` Rusty Russell
2016-01-08 18:52 ` Peter Todd
1 sibling, 1 reply; 34+ messages in thread
From: Matt Corallo @ 2016-01-08 3:41 UTC (permalink / raw)
To: Rusty Russell, Rusty Russell via bitcoin-dev, Pieter Wuille,
Gavin Andresen
Cc: Bitcoin Dev
Indeed, anything which uses P2SH is obviously vulnerable if there is an attack on RIPEMD160 which reduces it's security only marginally. While no one thought hard about these attacks when P2SH was designed, we realized later this was not such a good idea to reuse the structure from P2PKH. Hence why this discussion came up.
On January 7, 2016 7:30:11 PM PST, Rusty Russell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>
>writes:
>> Yes, this is what I worry about. We're constructing a 2-of-2 multisig
>> escrow in a contract. I reveal my public key A, you do a 80-bit
>search for
>> B and C such that H(A and B) = H(B and C). You tell me your keys B,
>and I
>> happily send to H(A and B), which you steal with H(B and C).
>
>FWIW, this attack would effect the current lightning-network
>"deployable
>lightning" design at channel establishment; we reveal our pubkey in the
>opening packet (which is used to redeem a P2SH using normal 2of2).
>
>At least you need to grind before replying (which will presumably time
>out), rather than being able to do it once the channel is open.
>
>We could pre-commit by exchanging hashes of pubkeys first, but
>contracts
>on bitcoin are hard enough to get right that I'm reluctant to add more
>hoops.
>
>Cheers,
>Rusty.
>_______________________________________________
>bitcoin-dev mailing list
>bitcoin-dev@lists•linuxfoundation.org
>https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 3:41 ` Matt Corallo
@ 2016-01-08 12:02 ` Rusty Russell
2016-01-08 12:38 ` Gavin Andresen
0 siblings, 1 reply; 34+ messages in thread
From: Rusty Russell @ 2016-01-08 12:02 UTC (permalink / raw)
To: Matt Corallo, Rusty Russell via bitcoin-dev, Pieter Wuille,
Gavin Andresen
Cc: Bitcoin Dev
Matt Corallo <lf-lists@mattcorallo•com> writes:
> Indeed, anything which uses P2SH is obviously vulnerable if there is
> an attack on RIPEMD160 which reduces it's security only marginally.
I don't think this is true? Even if you can generate a collision in
RIPEMD160, that doesn't help you since you need to create a specific
SHA256 hash for the RIPEMD160 preimage.
Even a preimage attack only helps if it leads to more than one preimage
fairly cheaply; that would make grinding out the SHA256 preimage easier.
AFAICT even MD4 isn't this broken.
But just with Moore's law (doubling every 18 months), we'll worry about
economically viable attacks in 20 years.[1]
That's far enough away that I would choose simplicity, and have all SW
scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
not a no-brainer.
Cheers,
Rusty.
[1] Assume bitcoin-network-level compute (collision in 19 days) costs
$1B to build today. Assume there will be 100 million dollars a day
in vulnerable txs, and you're on one end of all of them (or can MITM
if you find a collision), *and* can delay them all by 10 seconds,
and none are in parallel so you can attack all of them. IOW, just
like a single $100M opportunity for 3650 seconds each year.
Our machine has a 0.11% chance of finding a collision in 1 hour, so
it's worth about $110,000. We can build it for that in about 20
years.
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 12:02 ` Rusty Russell
@ 2016-01-08 12:38 ` Gavin Andresen
2016-01-08 14:34 ` Watson Ladd
2016-01-08 15:33 ` Anthony Towns
0 siblings, 2 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 12:38 UTC (permalink / raw)
To: Rusty Russell; +Cc: Rusty Russell via bitcoin-dev
[-- Attachment #1: Type: text/plain, Size: 2000 bytes --]
On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell <rusty@rustcorp•com.au> wrote:
> Matt Corallo <lf-lists@mattcorallo•com> writes:
> > Indeed, anything which uses P2SH is obviously vulnerable if there is
> > an attack on RIPEMD160 which reduces it's security only marginally.
>
> I don't think this is true? Even if you can generate a collision in
> RIPEMD160, that doesn't help you since you need to create a specific
> SHA256 hash for the RIPEMD160 preimage.
>
> Even a preimage attack only helps if it leads to more than one preimage
> fairly cheaply; that would make grinding out the SHA256 preimage easier.
> AFAICT even MD4 isn't this broken.
>
It feels like we've gone over that before, but I can never remember where
or when. I believe consensus was that if we were using the broken MD5 in
all the places we use RIPEMD160 we'd still be secure today because of
Satoshi's use of nested hash functions everywhere.
> But just with Moore's law (doubling every 18 months), we'll worry about
> economically viable attacks in 20 years.[1]
> That's far enough away that I would choose simplicity, and have all SW
> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
> not a no-brainer.
Lets see if I've followed the specifics of the collision attack correctly,
Ethan (or somebody) please let me know if I'm missing something:
So attacker is in the middle of establishing a payment channel with
somebody. Victim gives their public key, attacker creates the innocent
fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A
is attacker's) but doesn't give it to the victim yet.
Instead they then generate about 2^81scripts that are some form of
pay-to-attacker ....
... wait, no that doesn't work, because SHA256 is used as the inner hash
function. They'd have to generate 2^129 to find a cycle in SHA256.
Instead, they .. what? I don't see a viable attack unless RIPEMD160 and
SHA256 (or the combination) suffers a cryptographic break.
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 2971 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 12:38 ` Gavin Andresen
@ 2016-01-08 14:34 ` Watson Ladd
2016-01-08 15:26 ` Adam Back
2016-01-08 15:33 ` Anthony Towns
1 sibling, 1 reply; 34+ messages in thread
From: Watson Ladd @ 2016-01-08 14:34 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Rusty Russell via bitcoin-dev
On Fri, Jan 8, 2016 at 4:38 AM, Gavin Andresen via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell <rusty@rustcorp•com.au> wrote:
>>
>> Matt Corallo <lf-lists@mattcorallo•com> writes:
>> > Indeed, anything which uses P2SH is obviously vulnerable if there is
>> > an attack on RIPEMD160 which reduces it's security only marginally.
>>
>> I don't think this is true? Even if you can generate a collision in
>> RIPEMD160, that doesn't help you since you need to create a specific
>> SHA256 hash for the RIPEMD160 preimage.
>>
>> Even a preimage attack only helps if it leads to more than one preimage
>> fairly cheaply; that would make grinding out the SHA256 preimage easier.
>> AFAICT even MD4 isn't this broken.
>
>
> It feels like we've gone over that before, but I can never remember where or
> when. I believe consensus was that if we were using the broken MD5 in all
> the places we use RIPEMD160 we'd still be secure today because of Satoshi's
> use of nested hash functions everywhere.
>
>>
>> But just with Moore's law (doubling every 18 months), we'll worry about
>> economically viable attacks in 20 years.[1]
>>
>>
>> That's far enough away that I would choose simplicity, and have all SW
>> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
>> not a no-brainer.
>
>
> Lets see if I've followed the specifics of the collision attack correctly,
> Ethan (or somebody) please let me know if I'm missing something:
>
> So attacker is in the middle of establishing a payment channel with
> somebody. Victim gives their public key, attacker creates the innocent
> fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A is
> attacker's) but doesn't give it to the victim yet.
>
> Instead they then generate about 2^81scripts that are some form of
> pay-to-attacker ....
> ... wait, no that doesn't work, because SHA256 is used as the inner hash
> function. They'd have to generate 2^129 to find a cycle in SHA256.
For 2^80 they simply generate 2^80 scripts that look innocent, and
2^80 that are not. With high probability there is a collision. I agree
that most cryptanalysis won't work because of the nesting, but 2^80 is
not good.
>
> Instead, they .. what? I don't see a viable attack unless RIPEMD160 and
> SHA256 (or the combination) suffers a cryptographic break.
>
>
> --
> --
> Gavin Andresen
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--
"Man is born free, but everywhere he is in chains".
--Rousseau.
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 14:34 ` Watson Ladd
@ 2016-01-08 15:26 ` Adam Back
0 siblings, 0 replies; 34+ messages in thread
From: Adam Back @ 2016-01-08 15:26 UTC (permalink / raw)
To: Watson Ladd; +Cc: Rusty Russell via bitcoin-dev
Tricky choice. On the one hand I had spotted this too before and maybe
one or two more exceptions to bitcoin's 128-bit security target and
been vaguely tut-tutting about them in the background. It's kind of a
violation of crypto rule of thumb that you want to balance things and
not have odd weak points as Watson was implying, it puts you closer to
the margin if there is a slip or other problem so you have an
imbalanced crypto format.
On the other hand it's not currently a problem as such and it's less
change and slightly more compact.
RIPEMD probably is less well reviewed than SHA2. However SHA1 has
problems, and SHA2 is a bigger SHA1 basically so, hence the NIST
motivation for SHA3 designed to fix the design flaw in SHA1 (and SHA2
in principle).
So then if we agree with this rule of thumb (and not doing so would
fly against best practices which we probably shouldnt look to do in
such a security focussed domain) then what this discussion is more
about is when is a good time to write down tech debt.
I think that comes to segregated-witness itself which writes down a
tidily organised by lines of code robust fix to a bunch of long
standing problems.
Doing a 2MB hard-fork in comparison fixes nothing really. Leaving
known issues to bake in for another N years eventually builds up on
you (not even in security just in software engineering) as another
rule of thumb. I mean if we dont fix it now that we are making a
change that connects, when will we?
In software projects I ran we always disguised the cost of tech-debt
as non-negotiable baked into our estimates without a line item to
escape the PHB syndrome of haggling for features instead of tech debt
(which is _never_ a good idea:)
Pragmatism vs refactoring as you go.
But for scale I think segregated-witness does offer the intriguing
next step of being able to do 2 of 2, 3 of 3 and N of N which give
size of one sig multisig (indistinguishable even for privacy) as well
as K of N key tree sigs, which are also significantly more compact.
There was also the other thing I mentioned further up the thread that
if we want to take an approach of living with little bit of bloat from
getting back to a universal 128-bit target, there are still some
fixable bloat things going on:
a) sending pubKey in the signature vs recovery (modulo interference
with Schnorr batch verify compatibility*);
b) using the PubKey instead of PKH in the ScriptPubKey, though that
loses the nice property of of not having the key to do DL attacks on
until the signed transaction is broadcast;
c) I think there might be a way to combine hash & PubKey to keep the
delayed PubKey publication property and yet still save the bloat of
having both.
* I did suggest to Pieter that you could let the miner decide to forgo
Schnorr batch verifiability to get compaction from recovery - the pub
key could be optionally elided from the scriptSig serialisation by the
miner.
The other thing we could consider is variable sized hashes (& a few
pubkey size choices) that is software complexity however. We might be
better of focussing on the bigger picture like IBLT/weak-blocks and
bigger wins like MAST, multiSig Schnorr & key tree sigs.
Didnt get time to muse on c) but a nice crypto question for someone :)
Another thing to note is combining has been known to be fragile to bad
interactions or unexpected behaviours. This paper talks about things
tradeoffs and weaknesses in hash combiners.
http://tuprints.ulb.tu-darmstadt.de/2094/1/thesis.lehmann.pdf
Weak concept NACK I think for losing a cleanup opportunity to store it
up for the future when there is a reasonable opportunity to fix it?
Adam
On 8 January 2016 at 15:34, Watson Ladd via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> On Fri, Jan 8, 2016 at 4:38 AM, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation.org> wrote:
>> On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell <rusty@rustcorp•com.au> wrote:
>>>
>>> Matt Corallo <lf-lists@mattcorallo•com> writes:
>>> > Indeed, anything which uses P2SH is obviously vulnerable if there is
>>> > an attack on RIPEMD160 which reduces it's security only marginally.
>>>
>>> I don't think this is true? Even if you can generate a collision in
>>> RIPEMD160, that doesn't help you since you need to create a specific
>>> SHA256 hash for the RIPEMD160 preimage.
>>>
>>> Even a preimage attack only helps if it leads to more than one preimage
>>> fairly cheaply; that would make grinding out the SHA256 preimage easier.
>>> AFAICT even MD4 isn't this broken.
>>
>>
>> It feels like we've gone over that before, but I can never remember where or
>> when. I believe consensus was that if we were using the broken MD5 in all
>> the places we use RIPEMD160 we'd still be secure today because of Satoshi's
>> use of nested hash functions everywhere.
>>
>>>
>>> But just with Moore's law (doubling every 18 months), we'll worry about
>>> economically viable attacks in 20 years.[1]
>>>
>>>
>>> That's far enough away that I would choose simplicity, and have all SW
>>> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
>>> not a no-brainer.
>>
>>
>> Lets see if I've followed the specifics of the collision attack correctly,
>> Ethan (or somebody) please let me know if I'm missing something:
>>
>> So attacker is in the middle of establishing a payment channel with
>> somebody. Victim gives their public key, attacker creates the innocent
>> fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A is
>> attacker's) but doesn't give it to the victim yet.
>>
>> Instead they then generate about 2^81scripts that are some form of
>> pay-to-attacker ....
>> ... wait, no that doesn't work, because SHA256 is used as the inner hash
>> function. They'd have to generate 2^129 to find a cycle in SHA256.
>
> For 2^80 they simply generate 2^80 scripts that look innocent, and
> 2^80 that are not. With high probability there is a collision. I agree
> that most cryptanalysis won't work because of the nesting, but 2^80 is
> not good.
>>
>> Instead, they .. what? I don't see a viable attack unless RIPEMD160 and
>> SHA256 (or the combination) suffers a cryptographic break.
>>
>>
>> --
>> --
>> Gavin Andresen
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
>
>
> --
> "Man is born free, but everywhere he is in chains".
> --Rousseau.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 12:38 ` Gavin Andresen
2016-01-08 14:34 ` Watson Ladd
@ 2016-01-08 15:33 ` Anthony Towns
2016-01-08 15:46 ` Gavin Andresen
1 sibling, 1 reply; 34+ messages in thread
From: Anthony Towns @ 2016-01-08 15:33 UTC (permalink / raw)
To: Gavin Andresen; +Cc: bitcoin-dev
On Fri, Jan 08, 2016 at 07:38:50AM -0500, Gavin Andresen via bitcoin-dev wrote:
> Lets see if I've followed the specifics of the collision attack correctly,
> Ethan (or somebody) please let me know if I'm missing something:
>
> So attacker is in the middle of establishing a payment channel with
> somebody. Victim gives their public key, attacker creates the innocent
> fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A
> is attacker's) but doesn't give it to the victim yet.
Using Ethan Heilman's procedure, the attacker can create two scripts:
2 V __A1__ 2 CHECKMULTISIG
2 V __A2__ 2 CHECKMULTISIG
and find values A1 and A2 which hash the scripts to the same result
with under 3*2**80 work. I think you can do that by setting the next
private key as the result of RIPEMD(SHA256(script with pubkey)), so you
could still spend either. But it doesn't change the script, so it's not
*that* helpful -- you've just got two different keys you can use.
Ah, but you can make the form of the script be a function of your key, so:
if privkey % 2 == 0:
script = "2 V %s 2 CHECKMULTISIG" % (pubkey)
else:
script = "%s CHECKSIG" % (pubkey)
hash = ripemd160(sha256(script))
nextprivkey = hash
Then you have a 50% chance of your cycle giving you a matching hash for
one script with A1 and the other script with A2, and you can find the
cycle with under 3*2**80 work. Doing five attempts should give you ~96%
chance of hitting a usable pair, and should take under 15*2**80 work ~=
2**84 work, with trivial memory use.
Trying that in python with a vastly weakened hash function (namely,
the first five bytes of ripemd160(sha256()), with 40 bits of security
and 3*2**20 work) works as expected -- I got a "useful" collision on my
second try in about 7 seconds, seeding with "grumpycat3" ("grumpycat2"
didn't work) with the result being:
hexlify(ripemd160(sha256("foo%sbar"%unhexlify("86f9fbac1a")))[:5])
'ae94d9f908'
hexlify(ripemd160(sha256("baz%squux"%unhexlify("104fc5093f")))[:5])
'ae94d9f908'
Cheers,
aj
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:33 ` Anthony Towns
@ 2016-01-08 15:46 ` Gavin Andresen
2016-01-08 15:50 ` Gavin Andresen
` (3 more replies)
0 siblings, 4 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 15:46 UTC (permalink / raw)
To: Anthony Towns; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 533 bytes --]
Thanks, Anthony, that works!
So...
How many years until we think a 2^84 attack where the work is an ECDSA
private->public key derivation will take a reasonable amount of time?
And Ethan or Anthony: can you think of a similar attack scheme if you
assume we had switched to Schnorr 2-of-2 signatures by then?
And to everybody who might not be reading this closely: All of the above
is discussing collision attacks; none of it is relevant in the normal case
where your wallet generates the scriptPubKey.
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 914 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:46 ` Gavin Andresen
@ 2016-01-08 15:50 ` Gavin Andresen
2016-01-08 15:59 ` Gavin Andresen
2016-01-11 20:32 ` Jorge Timón
2016-01-08 16:06 ` Gavin Andresen
` (2 subsequent siblings)
3 siblings, 2 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 15:50 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 325 bytes --]
And to fend off the messag that I bet somebody is composing right now:
Yes, I know about a "security first" mindset. But as I said earlier in the
thread, there is a tradeoff here between crypto strength and code
complexity, and "the strength of the crypto is all that matters" is NOT
security first.
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 542 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:50 ` Gavin Andresen
@ 2016-01-08 15:59 ` Gavin Andresen
2016-01-11 20:32 ` Jorge Timón
1 sibling, 0 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 15:59 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1111 bytes --]
On Fri, Jan 8, 2016 at 10:50 AM, Gavin Andresen <gavinandresen@gmail•com>
wrote:
> But as I said earlier in the thread, there is a tradeoff here between
> crypto strength and code complexity, and "the strength of the crypto is all
> that matters" is NOT security first.
I should be more explicit about code complexity:
The big picture is "segwitness will help scale in the very short term."
So the spec gives two ways of stuffing the segwitness hash into the
scriptPubKey -- one way that uses a 32-bit hash, but if used would actually
make scalability a bit worse as coins moved into segwitness-locked
transactions (DUP HASH160 EQUALVERIFY pay-to-script-hash scriptpubkeys are
just 24 bytes).
And another way that add just one byte to the scriptpubkey.
THAT is the code complexity I'm talking about. Better to always move the
script into the witness data, in my opinion, on the keep the design as
simple as possible principle.
It could be a 32-byte hash... but then the short-term scalability goal is
compromised.
Maybe I'm being dense, but I still think it is a no-brainer....
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 1828 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:46 ` Gavin Andresen
2016-01-08 15:50 ` Gavin Andresen
@ 2016-01-08 16:06 ` Gavin Andresen
2016-01-11 3:57 ` Rusty Russell
2016-01-11 23:57 ` Tier Nolan
3 siblings, 0 replies; 34+ messages in thread
From: Gavin Andresen @ 2016-01-08 16:06 UTC (permalink / raw)
To: Anthony Towns, Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 327 bytes --]
On Fri, Jan 8, 2016 at 10:46 AM, Gavin Andresen <gavinandresen@gmail•com>
wrote:
> And Ethan or Anthony: can you think of a similar attack scheme if you
> assume we had switched to Schnorr 2-of-2 signatures by then?
Don't answer that, I was being dense again, Anthony's scheme works with
Schnorr...
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 703 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 1:54 ` Gavin Andresen
@ 2016-01-08 17:38 ` Pieter Wuille
2016-01-08 18:41 ` Peter Todd
1 sibling, 0 replies; 34+ messages in thread
From: Pieter Wuille @ 2016-01-08 17:38 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1923 bytes --]
On Fri, Jan 8, 2016 at 2:54 AM, Gavin Andresen via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> I'm saying we can eliminate one somewhat unlikely attack (that there is a
> bug in the code or test cases, today or some future version, that has to
> decide what to do with "version 0" versus "version 1" witness programs) by
> accepting the risk of another insanely, extremely unlikely attack.
Ok, just having one witness program version now is a somewhat different
proposal. It would be simpler for sure. The reasoning was that you'd need
this to not add significant overhead to small scripts, but that may not be
the case anymore. I wouldn't mind seeing numbers.
> My proposal would be to just do a version 0 witness program now, that is
> RIPEMD160(SHA256(script)).
I don't think that is wise. Bitcoin has a 128-bit security target for
everything else. We did not know that P2SH and similar constructs were
vulnerable to a collision attack at the time, but now we do, so the obvious
choice is to pick a size that is sufficiently large to maintain the 128-bit
security target. This is a no brainer to me; we're not proposing switching
to a 160-bit EC curve either, right?
> I'm really disappointed with the "Here's the spec, take it or leave it"
> attitude. What's the point of having a BIP process if the discussion just
> comes down to "We think more is better. We don't care what you think."
It is a proposal and we are discussing it. You first brought up some
criticisms in private, and I agreed with several things you said.
But it remains the proposal of a few people including me, and I do not
agree with the specific suggestion of reducing the security target for
witness scripts to 80 bits.
We are not deciding what the system will be. We're making a proposal, and
hope that due to its technical merit, the ecosystem will adopt it. You're
free to participate in that discussion.
--
Pieter
[-- Attachment #2: Type: text/html, Size: 2293 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 1:54 ` Gavin Andresen
2016-01-08 17:38 ` Pieter Wuille
@ 2016-01-08 18:41 ` Peter Todd
1 sibling, 0 replies; 34+ messages in thread
From: Peter Todd @ 2016-01-08 18:41 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1303 bytes --]
On Thu, Jan 07, 2016 at 08:54:00PM -0500, Gavin Andresen via bitcoin-dev wrote:
> ---
>
> I'm really disappointed with the "Here's the spec, take it or leave it"
> attitude. What's the point of having a BIP process if the discussion just
> comes down to "We think more is better. We don't care what you think."
I'll point out that I personally raised an issue with segpregated
witnesses quite recently - my concern that it could make validationless
mining easier and more profitable(1). Neither Pieter Wuille nor Gregory
Maxwell believed my concern to be important at first in private
communication. However, it was still discussed on IRC, with Pieter,
Greg, and others contributing valuable input on the problem and my
proposed fix. Right now I think the next step for me is to write the
code to implement my fix and submit a pull-req against the segwit
branch.
I certainly wouldn't describe that experience as "Here's the spec, take
it or leave it; We don't what what you think."
1) "Segregated witnesses and validationless mining",
Peter Todd, Dec 23 2015, Bitcoin-dev mailing list,
http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/012103.html
--
'peter'[:-1]@petertodd.org
000000000000000004aea2cfdb89c4816b7a42208dca1f3cfd66a1c9b5df4506
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 3:30 ` Rusty Russell
2016-01-08 3:41 ` Matt Corallo
@ 2016-01-08 18:52 ` Peter Todd
1 sibling, 0 replies; 34+ messages in thread
From: Peter Todd @ 2016-01-08 18:52 UTC (permalink / raw)
To: Rusty Russell; +Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1639 bytes --]
On Fri, Jan 08, 2016 at 02:00:11PM +1030, Rusty Russell via bitcoin-dev wrote:
> Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>
> writes:
> > Yes, this is what I worry about. We're constructing a 2-of-2 multisig
> > escrow in a contract. I reveal my public key A, you do a 80-bit search for
> > B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
> > happily send to H(A and B), which you steal with H(B and C).
>
> FWIW, this attack would effect the current lightning-network "deployable
> lightning" design at channel establishment; we reveal our pubkey in the
> opening packet (which is used to redeem a P2SH using normal 2of2).
>
> At least you need to grind before replying (which will presumably time
> out), rather than being able to do it once the channel is open.
>
> We could pre-commit by exchanging hashes of pubkeys first, but contracts
> on bitcoin are hard enough to get right that I'm reluctant to add more
> hoops.
Note how this is a good example where trying to avoid the relatively
small amount of complexity of having two different segregated witness
schemes to allow for 128bit security could lead to a significant amount
of upper level complexity trying to regain security. I wouldn't be
surprised at all if this upper level complexity leads to exploits; at
the very least it'll lead to a lot of wasted mental effort from
cryptographers concerned about the potential weakness, both within and
external to the Bitcoin development community.
--
'peter'[:-1]@petertodd.org
000000000000000004aea2cfdb89c4816b7a42208dca1f3cfd66a1c9b5df4506
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:46 ` Gavin Andresen
2016-01-08 15:50 ` Gavin Andresen
2016-01-08 16:06 ` Gavin Andresen
@ 2016-01-11 3:57 ` Rusty Russell
2016-01-11 6:57 ` Peter Todd
2016-01-11 23:57 ` Tier Nolan
3 siblings, 1 reply; 34+ messages in thread
From: Rusty Russell @ 2016-01-11 3:57 UTC (permalink / raw)
To: Gavin Andresen, Anthony Towns; +Cc: Bitcoin Dev
Gavin Andresen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> writes:
> How many years until we think a 2^84 attack where the work is an ECDSA
> private->public key derivation will take a reasonable amount of time?
vanitygen can generate keypairs pretty fast (on my CPU it's comparable
with hashing time), and there are ways to make it faster. Since you can
generate multiple script variations, too, I think hashing is the
bottleneck.
Antminer S7 can do 4.73 Terahash per second for $1.2k. (Double SHA, but
let's assume RIPEMD160(SHA256()) is the same speed).
766,760,562,123 seconds to do 3*2^80, so you'd need over 200 million
S7s to do it in an hour.[1] If you want to do that for $1M, wait 27
years and hope Moore's Law holds?
Also, a colleague points out you could use this attack against a site
like bitrated.com which publishes one side's pubkey, giving you a much
longer attack window.
Cheers,
Rusty.
[1] Weirdly, the bitcoin network is doing this much work every 57
days, for about $92M. If that's all the attack costs, it's under
1M in 10 years.
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-11 3:57 ` Rusty Russell
@ 2016-01-11 6:57 ` Peter Todd
0 siblings, 0 replies; 34+ messages in thread
From: Peter Todd @ 2016-01-11 6:57 UTC (permalink / raw)
To: Rusty Russell, Rusty Russell via bitcoin-dev, Gavin Andresen,
Anthony Towns
Cc: Bitcoin Dev
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
On 10 January 2016 22:57:15 GMT-05:00, Rusty
>Cheers,
>Rusty.
>[1] Weirdly, the bitcoin network is doing this much work every 57
> days, for about $92M. If that's all the attack costs, it's under
> 1M in 10 years.
Don't get too caught up in Moore's law here - more likely the attack will become feasible because SHA2 is partially weakened, as happened with SHA1. Having industry standard safety margins would make such a weakening be an academic problem rather than an emergency.
-----BEGIN PGP SIGNATURE-----
iQE9BAEBCgAnIBxQZXRlciBUb2RkIDxwZXRlQHBldGVydG9kZC5vcmc+BQJWk1Jc
AAoJEMCF8hzn9Lncz4MH/RYReh4+oPkt8D4uW2FhiB/BlzY5Q1FP94nyi/jQAAh9
er3cUA47RhSLLd2ukC2XDgbw8CZzhnzECs7vBVsXacc3dGpzV59n8L/pnX47IRJh
i1BPWHzEl/UeE/uBYUVgmy+kCVkJ80gnL2GGgZ3IXL5P+CHYY9dvhBrr53Q3HSpi
aEXVivBvBnX0GeATMVY5TAiailUfsUbUmPdEHu0x5hqqTh0sUpi+R+wXWJfPESB2
hzMVZd8ALz1SJhDqbkmBNHy2CX0fhGlnMSapm6EkQksfshkcwJ7tj8s2CEOYD68T
4mR7Xh+FsOA2bbZP8M/lMd3rrXbwFzXi0rWPa70mxqI=
=2W58
-----END PGP SIGNATURE-----
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:50 ` Gavin Andresen
2016-01-08 15:59 ` Gavin Andresen
@ 2016-01-11 20:32 ` Jorge Timón
1 sibling, 0 replies; 34+ messages in thread
From: Jorge Timón @ 2016-01-11 20:32 UTC (permalink / raw)
To: Gavin Andresen; +Cc: Bitcoin Dev
On Fri, Jan 8, 2016 at 4:50 PM, Gavin Andresen via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> And to fend off the messag that I bet somebody is composing right now:
>
> Yes, I know about a "security first" mindset. But as I said earlier in the
> thread, there is a tradeoff here between crypto strength and code
> complexity, and "the strength of the crypto is all that matters" is NOT
> security first.
If the crypto code is properly encapsulated, the code complexity costs
of choosing one hashing function over another should be non-existent.
You made the space argument which is valid, but in my opinion code
complexity shouldn't be a valid concern in this discussion.
As a maybe uninteresting anecdote, I proposed the asset IDs in
https://github.com/ElementsProject/elements/tree/alpha-0.10-multi-asset
to do the same ```ripemd160 . sha256``` choice that Mark Friedenbach
had proposed and I had approved for
https://github.com/jtimon/freimarkets/blob/master/doc/freimarkets_specs.org#asset-tags
. More humble than me, he admitted he had made a design mistake much
earlier than me, who (maybe paradoxically) probably had less knowledge
for making crypto choices at the low level. In the end I was convinced
with examples I failed to write down for documentation and can't
remember.
That's not to say I have anything to say in this debate other than
code complexity (which I do feel qualified to talk about) shouldn't be
a concern in this debate. Just want to focus the discussion on what it
should be: security vs space tradeoff.
Since I am admittedly in doubt, I tend to prefer to play safe, but
neither my feelings nor my anecdote are logical arguments and should,
therefore, be ignored for any conclusions in the ```ripemd160 .
sha256``` vs sha256d debate. Just like you non-sequitor "sha256d will
lead to more code complexity", if anything, sha256d should be simpler
than ```ripemd160 . sha256``` (but not simpler enough that it matters
much).
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-08 15:46 ` Gavin Andresen
` (2 preceding siblings ...)
2016-01-11 3:57 ` Rusty Russell
@ 2016-01-11 23:57 ` Tier Nolan
2016-01-12 0:00 ` Tier Nolan
3 siblings, 1 reply; 34+ messages in thread
From: Tier Nolan @ 2016-01-11 23:57 UTC (permalink / raw)
Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1030 bytes --]
On Fri, Jan 8, 2016 at 3:46 PM, Gavin Andresen via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> How many years until we think a 2^84 attack where the work is an ECDSA
> private->public key derivation will take a reasonable amount of time?
>
I think the EC multiply is not actually required. With compressed public
keys, the script selection rule can just be a sha256 call instead.
V is the public key of the victim, and const_pub_key is the attacker's
public key.
if prev_hash % 2 == 0:
script = "2 V 0x02%s 2 CHECKMULTISIG" % (sha256(prev_hash)))
else:
script = "CHECKSIG %s OP_DROP" % (prev_hash, const_pub_key)
next_hash = ripemd160(sha256(script))
If a collision is found, there is a 50% chance that the two scripts have
different parity and there is a 50% chance that a compressed key is a valid
key.
This means that you need to run the algorithm 4 times instead of 2.
The advantage is that each step is 2 sha256 calls and a ripemd160 call. No
EC multiply is required.
[-- Attachment #2: Type: text/html, Size: 1609 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-11 23:57 ` Tier Nolan
@ 2016-01-12 0:00 ` Tier Nolan
2016-01-12 12:08 ` Gavin Andresen
0 siblings, 1 reply; 34+ messages in thread
From: Tier Nolan @ 2016-01-12 0:00 UTC (permalink / raw)
Cc: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 241 bytes --]
On Mon, Jan 11, 2016 at 11:57 PM, Tier Nolan <tier.nolan@gmail•com> wrote:
>
> else:
> script = "CHECKSIG %s OP_DROP" % (prev_hash, const_pub_key)
>
That should be
script = "%s CHECKSIG %s OP_DROP" % (const_pub_key, prev_hash)
[-- Attachment #2: Type: text/html, Size: 735 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-12 0:00 ` Tier Nolan
@ 2016-01-12 12:08 ` Gavin Andresen
2016-01-12 23:22 ` Zooko Wilcox-O'Hearn
0 siblings, 1 reply; 34+ messages in thread
From: Gavin Andresen @ 2016-01-12 12:08 UTC (permalink / raw)
To: Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 1301 bytes --]
I'm convinced-- it is a good idea to worry about 80-bit collision attacks
now.
Thanks to all the people smarter than me who contributed to this
discussion, I learned a lot about collision attacks that I didn't know
before.
Would this be a reasonable "executive summary" :
If you are agreeing to lock up funds with somebody else, and they control
what public key to use, you are susceptible to collision attacks.
It is very likely an 80-bit-collision-in-ten-minutes attack will cost less
than $1million in 10 to twenty years (possibly sooner if there are crypto
breaks in that time).
If you don't trust the person with whom you're locking up funds and you're
locking up a significant amount of money (tens of millions of dollars
today, tens of thousands of dollars in a few years):
Then you should avoid using pay-to-script-hash addresses and instead use
the payment protocol and "raw" multisig outputs.
AND/OR
Have them give you a hierarchical deterministic (BIP32) seed, and derive a
public key for them to use.
----------
Following the security in depth and validate all input secure coding
principles would mean doing both-- avoid p2sh AND have all parties to a
transaction exchange HD seeds, add randomness, and use the resulting public
keys in the transaction.
--
--
Gavin Andresen
[-- Attachment #2: Type: text/html, Size: 1722 bytes --]
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
2016-01-12 12:08 ` Gavin Andresen
@ 2016-01-12 23:22 ` Zooko Wilcox-O'Hearn
0 siblings, 0 replies; 34+ messages in thread
From: Zooko Wilcox-O'Hearn @ 2016-01-12 23:22 UTC (permalink / raw)
Cc: Bitcoin Dev
Folks:
I don't fully understand this thread, but it sounds like to me it
might be omitting consideration of multi-target attacks. For example,
Tier Nolan's attack
(http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012230.html),
which seems to be the best attack on this thread, seems to start with
one specific public key of an intended victim, but if the attacker is
happy to find a collision with *any* one out of a large number of
potential victims, he gets an advantage proportional to the number of
potential victims.
So it would be wise, in addition to the kind of analysis already done
on this thread (which appears to have already settled at "Yes, we need
> 80-bit security."), to make a nice optimistic estimate of how many
public keys we could eventually have in use. 2⁴⁰? 2⁵⁰? Or maybe be
*very* optimistic, with some added IoT [*] goodness, and budget for
2⁶⁰?
Then we need to budget that many more bits of security to keep the
future attacker's chances of success low enough that the attacker will
never succeed. (Assuming that's our requirement.)
You might enjoy this recent blog post by DJB, legendary cryptographer
who works in this niche of cryptography as well as several other
niches:
http://blog.cr.yp.to/20151120-batchattacks.html
It has some interesting philosophical musings about the "Attacker
Economist" approach. (N.B. My respect for DJB's accomplishments is
tremendous, but that doesn't mean I automatically agree with
everything he says. I haven't made up my mind what I think about this
particular philosophical argument.)
Sincerely,
Zooko
[*] The Internet of Targets
^ permalink raw reply [flat|nested] 34+ messages in thread
end of thread, other threads:[~2016-01-12 23:22 UTC | newest]
Thread overview: 34+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-01-07 19:02 [bitcoin-dev] Time to worry about 80-bit collision attacks or not? Gavin Andresen
2016-01-07 19:13 ` Matt Corallo
2016-01-07 19:19 ` Adam Back
2016-01-07 20:56 ` Dave Scotese
2016-01-07 21:06 ` Gavin Andresen
2016-01-07 22:56 ` Ethan Heilman
2016-01-07 23:39 ` Gavin Andresen
2016-01-08 1:26 ` Matt Corallo
2016-01-08 1:54 ` Gavin Andresen
2016-01-08 17:38 ` Pieter Wuille
2016-01-08 18:41 ` Peter Todd
2016-01-07 20:40 ` Ethan Heilman
2016-01-07 23:52 ` Pieter Wuille
2016-01-08 1:00 ` Gavin Andresen
2016-01-08 1:27 ` Watson Ladd
2016-01-08 3:30 ` Rusty Russell
2016-01-08 3:41 ` Matt Corallo
2016-01-08 12:02 ` Rusty Russell
2016-01-08 12:38 ` Gavin Andresen
2016-01-08 14:34 ` Watson Ladd
2016-01-08 15:26 ` Adam Back
2016-01-08 15:33 ` Anthony Towns
2016-01-08 15:46 ` Gavin Andresen
2016-01-08 15:50 ` Gavin Andresen
2016-01-08 15:59 ` Gavin Andresen
2016-01-11 20:32 ` Jorge Timón
2016-01-08 16:06 ` Gavin Andresen
2016-01-11 3:57 ` Rusty Russell
2016-01-11 6:57 ` Peter Todd
2016-01-11 23:57 ` Tier Nolan
2016-01-12 0:00 ` Tier Nolan
2016-01-12 12:08 ` Gavin Andresen
2016-01-12 23:22 ` Zooko Wilcox-O'Hearn
2016-01-08 18:52 ` Peter Todd
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox