public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: "Zooko Wilcox-O'Hearn" <zooko@z.cash>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
Date: Tue, 12 Jan 2016 23:22:17 +0000	[thread overview]
Message-ID: <CADorodh9s4T3YMVb=bKHkMMbbtuNQ1iimPN=55j0Ws161e3A1g@mail.gmail.com> (raw)
In-Reply-To: <CABsx9T3UTSnLx_BGfMTrQB1=vR9Bdd8OJvSXy=++-_=wfv7+uw@mail.gmail.com>

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⁴⁰? 2⁵⁰? Or maybe be
*very* optimistic, with some added IoT [*] goodness, and budget for
2⁶⁰?

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


  reply	other threads:[~2016-01-12 23:22 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-01-07 19:02 [bitcoin-dev] Time to worry about 80-bit collision attacks or not? Gavin Andresen
2016-01-07 19:13 ` Matt Corallo
2016-01-07 19:19 ` Adam Back
2016-01-07 20:56   ` Dave Scotese
2016-01-07 21:06     ` Gavin Andresen
2016-01-07 22:56       ` Ethan Heilman
2016-01-07 23:39         ` Gavin Andresen
2016-01-08  1:26           ` Matt Corallo
2016-01-08  1:54             ` Gavin Andresen
2016-01-08 17:38               ` Pieter Wuille
2016-01-08 18:41               ` Peter Todd
2016-01-07 20:40 ` Ethan Heilman
2016-01-07 23:52 ` Pieter Wuille
2016-01-08  1:00   ` Gavin Andresen
2016-01-08  1:27     ` Watson Ladd
2016-01-08  3:30   ` Rusty Russell
2016-01-08  3:41     ` Matt Corallo
2016-01-08 12:02       ` Rusty Russell
2016-01-08 12:38         ` Gavin Andresen
2016-01-08 14:34           ` Watson Ladd
2016-01-08 15:26             ` Adam Back
2016-01-08 15:33           ` Anthony Towns
2016-01-08 15:46             ` Gavin Andresen
2016-01-08 15:50               ` Gavin Andresen
2016-01-08 15:59                 ` Gavin Andresen
2016-01-11 20:32                 ` Jorge Timón
2016-01-08 16:06               ` Gavin Andresen
2016-01-11  3:57               ` Rusty Russell
2016-01-11  6:57                 ` Peter Todd
2016-01-11 23:57               ` Tier Nolan
2016-01-12  0:00                 ` Tier Nolan
2016-01-12 12:08                   ` Gavin Andresen
2016-01-12 23:22                     ` Zooko Wilcox-O'Hearn [this message]
2016-01-08 18:52     ` Peter Todd

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CADorodh9s4T3YMVb=bKHkMMbbtuNQ1iimPN=55j0Ws161e3A1g@mail.gmail.com' \
    --to=zooko@z.cash \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox