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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
|
Return-Path: <tristan.hoy@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DB33BD97
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 13 Feb 2018 10:06:36 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ot0-f193.google.com (mail-ot0-f193.google.com
[74.125.82.193])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 33B9942D
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 13 Feb 2018 10:06:36 +0000 (UTC)
Received: by mail-ot0-f193.google.com with SMTP id q12so16807364otg.10
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 13 Feb 2018 02:06:36 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=subject:to:references:from:message-id:date:user-agent:mime-version
:in-reply-to:content-transfer-encoding:content-language;
bh=3WM/Z1wx7DVr54fJAtuV/L7288JZcBoPjefM0EL11eI=;
b=baROAq82wGaIAi0uuCkoHj2vsdDWJFmPm8kGskZH7QzSbwAmvOjOpbOElk4ofxnL/8
ceKg1+XGpnn2lAyHrUUQ/EW02HsobT9H638XhX79mu0EoyWf6JE2bJQ2SBmf/5EhCppy
SsIGR4FM2jBG1TET5TPnOJkqsYwzDQksXs4e8XVVZ64Zx+CNPgczR0ZY5XBByGhd/tJq
xm44UbNVfCVTlE1A4xnGX4rMLphEViygjJvxHAiO84TDOaA7HLhi9G1io8Mta9XMwDDy
Cm1Pub3nCJqI3s96OtelAsL0qhr6Jc4jrXx/e4nBfxub3q/SEQF2fE/9FJpiDFg18rIW
U0+g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:subject:to:references:from:message-id:date
:user-agent:mime-version:in-reply-to:content-transfer-encoding
:content-language;
bh=3WM/Z1wx7DVr54fJAtuV/L7288JZcBoPjefM0EL11eI=;
b=Y/4xfPuD7/NXWsBlQvm/4TijKjP3cmd9zuVd7ytU3wdU27XyDNjijCMh8S2SGuwS2C
1K+2KXFH1MsniD8lsVdgzqJkCIM61SasDkLxjznevTJXJPVAIbiB+oNK5SnHAAO8c9ny
mo2YkLuhm33QdHUSS0mJuzagTilcvSAFx0r2SvujdTzSux4PfSgAoxZ1j+GBA0RzZ3+3
OHDaM/DgzNoGlR7DcUTXdReAFajpkFJFHVFGZYSttEpZMIdCpkQPkfF4GF4sqw/nswPg
LWEX85bFy09GH/FqaYeYXM8iKzBUhZtugmGqW2L7OlJqMaYNfWjR//Xj15avsIpv0Dlm
+0ZA==
X-Gm-Message-State: APf1xPCrmcbFxS1AACtTyoRXsDobsUNst17x2SKeJwCK0x3lOFdTqCSY
Vl6APIQpwBwcRVLvTD1MC03PZ9v9
X-Google-Smtp-Source: AH8x226lIGJ822ZvlviA/A23ZvFE+ezosHhS2IGcdj/rEeyxdLZvTDHiQcu1QvQmWbryZ69Mr96XwQ==
X-Received: by 10.157.51.54 with SMTP id f51mr465193otc.145.1518516394859;
Tue, 13 Feb 2018 02:06:34 -0800 (PST)
Received: from [172.16.19.228] (59-100-254-154.syd.static-ipl.aapt.com.au.
[59.100.254.154]) by smtp.gmail.com with ESMTPSA id
c34sm6020596otd.16.2018.02.13.02.06.32
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Tue, 13 Feb 2018 02:06:33 -0800 (PST)
To: bitcoin-dev@lists.linuxfoundation.org
References: <CAFEpHQHP7XXBYUP6CF1OeYoBpj0UwK+qpYG-14_zQZDX4Md7UA@mail.gmail.com>
<1518450650.7829.87.camel@mmci.uni-saarland.de>
<CAFEpHQHYdE3m2GUtN=ijvtYUudwtcG52rRxzH66VFbgO1KEihw@mail.gmail.com>
<1518504374.9878.24.camel@mmci.uni-saarland.de>
From: Tristan Hoy <tristan.hoy@gmail.com>
Message-ID: <882306fa-3ea0-99bd-61c6-f646d27c2ab6@gmail.com>
Date: Tue, 13 Feb 2018 21:06:31 +1100
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101
Thunderbird/52.6.0
MIME-Version: 1.0
In-Reply-To: <1518504374.9878.24.camel@mmci.uni-saarland.de>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Content-Language: en-US
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE autolearn=ham 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, 13 Feb 2018 14:05:10 +0000
Subject: Re: [bitcoin-dev] Transition to post-quantum
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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, 13 Feb 2018 10:06:37 -0000
On 13/02/2018 5:46 PM, Tim Ruffing via bitcoin-dev wrote:
> On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:
>> In a post-quantum world, your second "d" type transaction is
>> completely forgeable, which means it is vulnerable to front-running.
>> An adversary capable of breaking ECDSA needs only listen for these
>> transactions, obtain "classic_sk" and then use a higher fee (or
>> relationship with a miner) to effectively turn your original "d"
>> transaction into a double-spend, with the forged transaction sending
>> all your funds to the adversary.
> That's not true. The d(ecommit) transaction, or better let's call it
> "decommit step" of a two-step transaction does not specify the effects
> (output script). This is what I denote by "tx" in the writeup, and it's
> already fixed by the c(ommit) step.
>
> So yes, if the user finally reveals
> d = classic_pk||Sign(classic_sk, tx)
> a quantum attacker can indeed forge
> d' = classic_pk||Sign(classic_sk, tx')
> for tx' != tx of his choice. But that won't help him, because the first
> valid c step in the chain is for tx and not for tx'.
Thank you for clarifying, I should have caught that.
>> The other issue with your approach is that if it is rolled out today,
>> it will effectively double transaction volumes - this is what I tried
>> to solve in solutions 2 and 3 in my article by instead modifying the
>> address generation process.
> Yep, it needs two entries in the blockchain, and that does not mean
> that it doubles the data. It will need some more bytes in the
> blockchain but also proper PQ-transactions could need more bytes in the
> blockchain, so I don't think that's the major issue.
>
The worst-case outcome is that ECDSA is broken before PQ addresses are
rolled out. There is no reactive response to this - all the existing
ECDSA addresses will be compromised. A proactive measure is required,
and it should be deployed sooner rather than later.
Any two-step approach adopted now as a proactive measure will not only
bloat the blockchain, it will also double the effective confirmation
time - for all transactions between now and when PQ addresses are rolled
out, which seems unlikely to happen in the next 5 years. The bloat will
be permanent.
Either way, would you mind if I included your approach in the article,
with credit? I will seek your review before publishing.
>> Regards,
>>
>> Tristan
>>
>> On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
>> -dev@lists.linuxfoundation.org> wrote:
>>> Hi Tristan,
>>>
>>> Regarding the "Post-Quantum Address Recovery" part (I haven't read
>>> the
>>> other parts), you may be interested in my message to the list from
>>> last
>>> month and the rest of the thread:
>>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar
>>> y/015659.html
>>>
>>> This is an approach which aims to avoid the issues that you've
>>> mentioned in your blog post.
>>>
>>> Best,
>>> Tim
>>>
>>> On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev
>>> wrote:
>>>> Hi all,
>>>>
>>>> Recently I've been exploring what a post-quantum attack on
>>> Bitcoin
>>>> would actually look like, and what options exist for mitigating
>>> it.
>>>> I've put up a draft of my research here: https://medium.com/@tris
>>> tanh
>>>> oy/11271f430c41
>>>>
>>>> In summary:
>>>> 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
>>>> scalable
>>>> 2) This is a rapidly advancing space and committment to a
>>> specific
>>>> post-quantum DSA now would be premature
>>>> 3) I've identified a strategy (solution 3 in the draft) that
>>>> mitigates against the worst case scenario (unexpectedly early
>>> attack
>>>> on ECDSA) without requiring any changes to the Bitcoin protocol
>>> or
>>>> total committment to a specific post-quantum DSA that will likely
>>> be
>>>> superseded in the next 3-5 years
>>>> 4) This strategy also serves as a secure means of transferring
>>>> balances into a post-quantum DSA address space, even in the event
>>>> that ECDSA is fully compromised and the transition is reactionary
>>>>
>>>> The proposal is a change to key generation only and will be
>>>> implemented by wallet providers.
>>>>
>>>> Feedback would be most appreciated.
>>>>
>>>> Regards,
>>>>
>>>> Tristan
>>>> _______________________________________________
>>>> bitcoin-dev mailing list
>>>> bitcoin-dev@lists.linuxfoundation.org
>>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
|
