MIME-Version: 1.0
In-Reply-To: <CABsx9T3UTSnLx_BGfMTrQB1=vR9Bdd8OJvSXy=++-_=wfv7+uw@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
	<CAPg+sBhH0MODjjp8Avx+Fy_UGqzMjUq_jn3vT3oH=u3711tsSA@mail.gmail.com>
	<8760z4rbng.fsf@rustcorp.com.au>
	<C4B5B9F1-9C53-45BC-9B30-F572C78096E3@mattcorallo.com>
	<8737u8qnye.fsf@rustcorp.com.au>
	<CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com>
	<20160108153329.GA15731@sapphire.erisian.com.au>
	<CABsx9T3MfndREm9icE-TUF58zsRZ5YsBMvUAMy4E-MmYWxWV=A@mail.gmail.com>
	<CAE-z3OUMRivWPVA+3BgC_95MGYBHN34+hoo6xfCu_gNeLFVknA@mail.gmail.com>
	<CAE-z3OVuAMdpZb+-C4JS_6FEreFohOMAsWpepgE1L5YoBOw4iA@mail.gmail.com>
	<CABsx9T3UTSnLx_BGfMTrQB1=vR9Bdd8OJvSXy=++-_=wfv7+uw@mail.gmail.com>
Date: Tue, 12 Jan 2016 23:22:17 +0000
Message-ID: <CADorodh9s4T3YMVb=bKHkMMbbtuNQ1iimPN=55j0Ws161e3A1g@mail.gmail.com>
From: "Zooko Wilcox-O'Hearn" <zooko@z.cash>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or
	not?
Precedence: list

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=E2=81=B4=E2=81=B0? 2=E2=81=
=B5=E2=81=B0? Or maybe be
*very* optimistic, with some added IoT [*] goodness, and budget for
2=E2=81=B6=E2=81=B0?

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