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

From: Watson Ladd <watsonbladd@gmail•com>
To: Gavin Andresen <gavinandresen@gmail•com>
Cc: Rusty Russell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
Date: Fri, 8 Jan 2016 06:34:09 -0800	[thread overview]
Message-ID: <CACsn0cmE-c3MCAegH6QaFfDg6NDgNy7tKbczsxtQvkWBnLYJgw@mail.gmail.com> (raw)
In-Reply-To: <CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com>

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.