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

From: Peter Todd <[email-masked]>
Date: Fri, 8 Jan 2016 10:52:54 -0800

On Fri, Jan 08, 2016 at 02:00:11PM +1030, Rusty Russell via bitcoin-dev wrote:
> Pieter Wuille via bitcoin-dev <[email-masked]>
> 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