MIME-Version: 1.0
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
	<2e620d305c86f65cbff44b5fba548dc85c118f84.camel@timruffing.de>
	<20180812163734.GV499@boulet.lan>
	<CAJowKg+h11YkwOo-gyWCw+87Oh-9K34LOnJ1730hhpoVR2m5sA@mail.gmail.com>
	<20180903000518.GB18522@boulet.lan>
	<CAJowKg+PDtEV3je_N9Ra6u3n4+ZQ3ozYapt8ivxGYYU28Qad+w@mail.gmail.com>
	<CAAS2fgT0uBGbLBOW4TxA-qCzOLwoQ1qSV-R0dMKRzPLAm_UOqQ@mail.gmail.com>
	<CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>
In-Reply-To: <CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Tue, 11 Sep 2018 17:00:25 +0000
Message-ID: <CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com>
To: Erik Aronesty <erik@q32.com>
Content-Type: multipart/alternative; boundary="000000000000e3a0c905759b696c"
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Precedence: list

--000000000000e3a0c905759b696c
Content-Type: text/plain; charset="UTF-8"

On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> wrote:

> To answer points:
>
> - I switched to the medium article so that I could correct, edit and
> improve things to make them more clear.
> - I responded to feedback by modifying the protocol to make it work - not
> by ignoring it.
>

To this moment there remains no response at your post.
https://bitcointalk.org/index.php?topic=4973123.0

I'm not sure how I am supposted to have figured out that you wrote a
somewhat different repost of it elsewhere...

- An M-1 rogue-key attack would require the attacker would to either
>
>   - attack the hash function to produce a predictable R based on a known
> mesage
>   - attack the DLP to influence x or k
>
> Neither attack gives any particular advantage to someone who has M-1 keys.
>

You keep asserting this. It isn't true. Asserting it more does not make it
any more true.  I already explained how to attack this style of signature
(e.g. in the BCT thread).

Set aside your 'interpolation' for a moment, and imagine that you construct
a 2 of 2 signature by just adding the keys.  Your tell me your key, P1  and
then I tell you that my key P2 which I derived by computing -P1  + xG.   We
now compute P = P1 + P2 = P1 + -P1 + xG = xG ... and now in spite adding P1
with an unknown discrete log, I know the discrete log of P with respect to
G and I did not need to violate the standard DL security assumption to
achieve that.

With the 'interpolation' in effect the same attack applies but its
execution is somewhat more complex: instead of adding the negation of P1  I
must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4...)
selected so that their interpolation coefficients add up to -1. Finding a
suitable subset requires solving a randomized modular subset sum problem
and Wagner's algorithm provides a computationally tractable solution to it.

The potential of rogue keys applies to both the keys themselves and to the
nonces. There are several ways to prevent these attacks, the musig paper
describes a delinearization technique which doesn't require additional
interaction or communication.

I haven't tested whether the R,s version is susceptible though.
>

There is a perfect bijection between the two encodings which is easily
computable, so they're the same thing from an abstract security perspective.

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

<div dir=3D"ltr"><div dir=3D"ltr">On Tue, Sep 11, 2018 at 4:34 PM Erik Aron=
esty &lt;<a href=3D"mailto:erik@q32.com">erik@q32.com</a>&gt; wrote:<br><di=
v class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><=
div dir=3D"ltr">
<div>To answer points:</div><div><br></div><div>- I switched to the medium =
article so that I could correct, edit and improve things to make them more =
clear.</div><div></div><div>- I responded to feedback by modifying the prot=
ocol to make it work - not by ignoring it.</div></div></blockquote><div><br=
></div><div>To this moment there remains no response at your post.<br></div=
><div><a href=3D"https://bitcointalk.org/index.php?topic=3D4973123.0">https=
://bitcointalk.org/index.php?topic=3D4973123.0</a><br></div><div>=C2=A0</di=
v><div>I&#39;m not sure how I am supposted to have figured out that you wro=
te a somewhat different repost of it elsewhere...<br></div><div><br></div><=
blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l=
eft:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">- An M-1 =
rogue-key attack would require the attacker would to either <br><div><br></=
div><div>=C2=A0 - attack the hash function to produce a predictable R based=
 on a known mesage</div><div>=C2=A0 - attack the DLP to influence x or k=C2=
=A0</div><div><br></div><div>Neither attack gives any particular advantage =
to someone who has M-1 keys.</div></div></blockquote><div><br></div><div>Yo=
u keep asserting this. It isn&#39;t true. Asserting it more does not make i=
t any more true.=C2=A0 I already explained how to attack this style of sign=
ature (e.g. in the BCT thread).<br></div><div><br></div><div>Set aside your=
 &#39;interpolation&#39; for a moment, and imagine that you construct a 2 o=
f 2 signature by just adding the keys.=C2=A0 Your tell me your key, P1=C2=
=A0 and then I tell you that my key P2 which I derived by computing -P1=C2=
=A0 + xG.=C2=A0=C2=A0 We now compute P =3D P1 + P2 =3D P1=C2=A0+ -P1=C2=A0+=
 xG =3D xG ... and now in spite adding P1 with an unknown discrete log, I k=
now the discrete log of P with respect to G and I did not need to violate t=
he standard DL security assumption to achieve that.</div><div><br></div><di=
v>With the &#39;interpolation&#39; in effect the same attack applies but it=
s execution is somewhat more complex: instead of adding the negation of P1=
=C2=A0 I must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4..=
.) selected so that their interpolation coefficients add up to -1. Finding =
a suitable subset requires solving a randomized modular subset sum problem =
and Wagner&#39;s algorithm provides a computationally tractable solution to=
 it.</div><div><br></div><div>The potential of rogue keys applies to both t=
he keys themselves and to the nonces. There are several ways to prevent the=
se attacks, the musig paper describes a delinearization technique which doe=
sn&#39;t require additional interaction or communication.<br></div><div><br=
></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;=
border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><=
div>I haven&#39;t tested whether the R,s version is susceptible though.=C2=
=A0=C2=A0 <br></div></div></blockquote><div><br></div><div>There is a perfe=
ct bijection between the two encodings which is easily computable, so they&=
#39;re the same thing from an abstract security perspective.<br></div><div>=
=C2=A0</div></div></div></div>

--000000000000e3a0c905759b696c--