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

From: Ethan Heilman <eth3rs@gmail•com>
To: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
Date: Thu, 7 Jan 2016 15:40:03 -0500	[thread overview]
Message-ID: <CAEM=y+VNGDjS3gQRXh4qCDXccMLMTG8F30OFi-XrM=gJbJQs7A@mail.gmail.com> (raw)
In-Reply-To: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>

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
>