Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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,

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Fri, Jan 8, 2016 at 4:50 PM, Gavin Andresen via bitcoin-dev 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

-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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Fri, Jan 8, 2016 at 4:38 AM, Gavin Andresen via bitcoin-dev wrote: > On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell wrote: >> >> Matt Corallo writes: >> > Indeed, anything which uses P2SH is obviously

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

Matt Corallo 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell wrote: > Matt Corallo 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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 >

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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"

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Fri, Jan 8, 2016 at 10:50 AM, Gavin Andresen 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Fri, Jan 8, 2016 at 10:46 AM, Gavin Andresen 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

> "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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Thu, Jan 7, 2016 at 6:52 PM, Pieter Wuille 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

>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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

On Thu, Jan 7, 2016 at 8:26 PM, Matt Corallo 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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

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