1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
Return-Path: <zooko@z.cash>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 540E6A1B
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Jan 2016 23:22:19 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f45.google.com (mail-wm0-f45.google.com [74.125.82.45])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8A26014F
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Jan 2016 23:22:18 +0000 (UTC)
Received: by mail-wm0-f45.google.com with SMTP id f206so274080947wmf.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Jan 2016 15:22:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=z-cash.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:date:message-id:subject:from:cc
:content-type:content-transfer-encoding;
bh=JhlnDR78yvZX6/A6NmsKrkLAf90xzzS2HX6NCF8ypl0=;
b=nqG4kk3jQgooKBD3gBKU9ot8FHmiLHHWptN+qSFtqnyEoCcbbUBiYhcZS8fV4ttYR9
nNy03skCabdhJss3L4SepEU4+3BT1KPTiEB6HkJrp4kU+JXhq/yI0g7hwzNPkW618BSr
dXEv0xpFuE1uhzKEqAyFzzihFLh7y9Zu0FzI8TP9ozei5+mG4gSQsjzw50bF18y++VLG
Eu6Y9c+9CNpsctRpTCdi4bfcjrCzwplDr7WTtdB5gdDvsXiVh5eL+ZCHczMlGwOZN/pc
WjGjaepDoCRdM8Lp5xvqVnbMYKqNASla6rvtHHdSrkqEI3djiOjOKwbRDbDbm6+hLzWi
ppDg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:date
:message-id:subject:from:cc:content-type:content-transfer-encoding;
bh=JhlnDR78yvZX6/A6NmsKrkLAf90xzzS2HX6NCF8ypl0=;
b=fP4ZuNXWLRArQmzO25RNSFi78SPYqrwzOpqsP0i2KuKu64nXkORilSXkVgbg6EA4l6
+16PO+hKyqkhrR36TLCHTP0M+HrOfQRXDMQcqXwXF2jh2IfNzRZAbfP9XpwyXx5NvzX8
mRPVwfaio0GAR/iM0FozORUvYTdRoZtJkqlTtnJpBWGKoxFXpz3PcYiyHTEw7YdaQ/59
pHZkggPEvxFWclcl+9XLAqySbOuPNYQkqB/ry9tOcaXKEQ7EmIZ4m8puZ3N4QHG1yRM4
4o0uLAMWeAiTsRLV/CHX6xrgkWV8bkGKwGE5vzVhy1pVmvS/0+9ArT/dvwOfRsMy6J/R
04iw==
X-Gm-Message-State: ALoCoQkVzKju2hhx2Tv8JKnx5xfUqihIU1w513lVbJwGnTNBHcjIrqSwLyk/EZYKlp2NIQPyuDvqND42uQJi53e/Y72bW+FTGQ==
MIME-Version: 1.0
X-Received: by 10.194.113.227 with SMTP id jb3mr15413425wjb.49.1452640937176;
Tue, 12 Jan 2016 15:22:17 -0800 (PST)
Received: by 10.28.96.197 with HTTP; Tue, 12 Jan 2016 15:22:17 -0800 (PST)
X-Originating-IP: [24.9.79.61]
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
X-Spam-Status: No, score=-1.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, MISSING_HEADERS,
RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Tue, 12 Jan 2016 23:23:41 +0000
Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or
not?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 12 Jan 2016 23:22:19 -0000
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
|
