path: root/a8/177072d967250834d4eed0232378e16c1985b2

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 D5CA6EAF
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 12 Feb 2018 21:32:38 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf0-f50.google.com (mail-lf0-f50.google.com
	[209.85.215.50])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D59D7165
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 12 Feb 2018 21:32:37 +0000 (UTC)
Received: by mail-lf0-f50.google.com with SMTP id k19so22374825lfj.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 12 Feb 2018 13:32:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=oD5vlXPcmLUJsWEXzKKSVPAV9aQxct7f/XhVzfY7DzI=;
	b=k1+lIGqpyt8nCF6tL3si5WmP2f0MxLqJhWsvhX6RjeMRtMol7CnTLFssGvhpPXDUWa
	aYpley8qWTE0OlhXb88UUtY/Ha8vOVJbQmMuhz242w55tRb2cxGJXRmpTQnGikIXESxk
	/PA3nxSBExtlPrZqJVv0b5PfRyvQogdgzxCQCkhzP0kOOAAdVkM46eJjN+5XIVX1NH8Z
	qKCbxJHZY1I4lvaiKAGWtgh0A22Opw8HtIWqjV2TuDaXOcz9yzOim2ZoWQa0aE8N3+8U
	WWgWk17fSGYj5OvlPtyfUasyDH6OkvoaTwFP5c6gTRJsA47ShuoFvojT2SG9Ac02lv/v
	KQdA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=oD5vlXPcmLUJsWEXzKKSVPAV9aQxct7f/XhVzfY7DzI=;
	b=piygfXestexrd7Xw/MumLD3hbsDKcIjvCufKmwvPkKe7ipb4DcYfYiJUV7dMdmVPLu
	CIp33FJyd/BD/Db9Oq+U5cHqbIRISAMDqUhQNBoXpsI2Q/eOKtnHm7E18J265NtqVABc
	3tWouGXcbl265/JFWAInakJ/0zUcXtzpou/Bz/Dy3nrTFhCBzVF3pAD0SpsP5J0MVkpm
	1I+BwisOz5J8vtlxONTQ3B8W7pl8ybhQbjFulAPe7tBQ8O0I2tXGcpD92pi5HepH/lLl
	k3F3xxhgPotHFlBYFsC/CJs/tdmmUiQnbA8uacw+wv098B6xqSJSYiN1ksGraI9dWTR4
	ClDA==
X-Gm-Message-State: APf1xPA3OJVrUrBoAHiX6Lu3Or3SFBzIFhpjhQpXzE22SRt4uhEH3YzC
	jfcJXs2/PEmCc9Jtc+YRIzeh6O0EXrq6mJqEETU=
X-Google-Smtp-Source: AH8x227pUdcOZxA596y+BsfpieWApeW46KucGj3zoXcdRk+4DybHr26wNaexFoJq4my+K24YQUbizM41UymL6bU1DHg=
X-Received: by 10.25.153.213 with SMTP id b204mr206702lfe.144.1518471156007;
	Mon, 12 Feb 2018 13:32:36 -0800 (PST)
MIME-Version: 1.0
Received: by 10.25.89.140 with HTTP; Mon, 12 Feb 2018 13:32:35 -0800 (PST)
In-Reply-To: <1518450650.7829.87.camel@mmci.uni-saarland.de>
References: <CAFEpHQHP7XXBYUP6CF1OeYoBpj0UwK+qpYG-14_zQZDX4Md7UA@mail.gmail.com>
	<1518450650.7829.87.camel@mmci.uni-saarland.de>
From: Tristan Hoy <tristan.hoy@gmail.com>
Date: Tue, 13 Feb 2018 08:32:35 +1100
Message-ID: <CAFEpHQHYdE3m2GUtN=ijvtYUudwtcG52rRxzH66VFbgO1KEihw@mail.gmail.com>
To: Tim Ruffing <tim.ruffing@mmci.uni-saarland.de>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="001a11401934db0d8605650a9d95"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	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: Mon, 12 Feb 2018 22:55:21 +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: Mon, 12 Feb 2018 21:32:38 -0000

--001a11401934db0d8605650a9d95
Content-Type: text/plain; charset="UTF-8"

Hi Tim,

Just read through your post, thanks for the heads up - I only just joined
this mailing list.

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.

I'm pretty confident that a PQ DSA is required to prevent front-running,
and that no "commit-reveal" scheme will be secure without one.

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.

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-January/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/@tristanh
> > 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
>

--001a11401934db0d8605650a9d95
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Tim,<div><br></div><div>Just read through your post, th=
anks for the heads up - I only just joined this mailing list.</div><div><br=
></div><div>In a post-quantum world, your second &quot;d&quot; type transac=
tion is completely forgeable, which means it is vulnerable to front-running=
. An adversary capable of breaking ECDSA needs only listen for these transa=
ctions, obtain &quot;classic_sk&quot; and then use a higher fee (or relatio=
nship with a miner) to effectively turn your original &quot;d&quot; transac=
tion into a double-spend, with the forged transaction sending all your fund=
s to the adversary.</div><div><br></div><div>I&#39;m pretty confident that =
a PQ DSA is required to prevent front-running, and that no &quot;commit-rev=
eal&quot; scheme will be secure without one.</div><div><br></div><div>The o=
ther issue with your approach is that if it is rolled out today, it will ef=
fectively double transaction volumes - this is what I tried to solve in sol=
utions 2 and 3 in my article by instead modifying the address generation pr=
ocess.</div><div><div><br></div><div>Regards,</div><div><br></div><div>Tris=
tan</div></div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <span dir=
=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" targe=
t=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br=
><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1=
px #ccc solid;padding-left:1ex">Hi Tristan,<br>
<br>
Regarding the &quot;Post-Quantum Address Recovery&quot; part (I haven&#39;t=
 read the<br>
other parts), you may be interested in my message to the list from last<br>
month and the rest of the thread:<br>
<a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Jan=
uary/015659.html" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxf=
oundation.<wbr>org/pipermail/bitcoin-dev/<wbr>2018-January/015659.html</a><=
br>
<br>
This is an approach which aims to avoid the issues that you&#39;ve<br>
mentioned in your blog post.<br>
<br>
Best,<br>
Tim<br>
<div><div class=3D"h5"><br>
On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:<br>
&gt; Hi all,<br>
&gt;<br>
&gt; Recently I&#39;ve been exploring what a post-quantum attack on Bitcoin=
<br>
&gt; would actually look like, and what options exist for mitigating it.<br=
>
&gt;<br>
&gt; I&#39;ve put up a draft of my research here: <a href=3D"https://medium=
.com/@tristanh" rel=3D"noreferrer" target=3D"_blank">https://medium.com/@tr=
istanh</a><br>
&gt; oy/11271f430c41<br>
&gt;<br>
&gt; In summary:<br>
&gt; 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are<br>
&gt; scalable<br>
&gt; 2) This is a rapidly advancing space and committment to a specific<br>
&gt; post-quantum DSA now would be premature<br>
&gt; 3) I&#39;ve identified a strategy (solution 3 in the draft) that<br>
&gt; mitigates against the worst case scenario (unexpectedly early attack<b=
r>
&gt; on ECDSA) without requiring any changes to the Bitcoin protocol or<br>
&gt; total committment to a specific post-quantum DSA that will likely be<b=
r>
&gt; superseded in the next 3-5 years<br>
&gt; 4) This strategy also serves as a secure means of transferring<br>
&gt; balances into a post-quantum DSA address space, even in the event<br>
&gt; that ECDSA is fully compromised and the transition is reactionary<br>
&gt;<br>
&gt; The proposal is a change to key generation only and will be<br>
&gt; implemented by wallet providers.<br>
&gt;<br>
&gt; Feedback would be most appreciated.<br>
&gt;<br>
&gt; Regards,<br>
&gt;<br>
&gt; Tristan<br>
</div></div>&gt; ______________________________<wbr>_________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l=
ists.<wbr>linuxfoundation.org</a><br>
&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wb=
r>org/mailman/listinfo/bitcoin-<wbr>dev</a><br>
______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
</blockquote></div><br></div>

--001a11401934db0d8605650a9d95--