path: root/9f/622e0b06bac820cf5c6c11909929d11a77bcc6

Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id C717D10A3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 17 Jan 2018 15:28:37 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f179.google.com (mail-io0-f179.google.com
	[209.85.223.179])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C4DA914E
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 17 Jan 2018 15:28:36 +0000 (UTC)
Received: by mail-io0-f179.google.com with SMTP id f89so13197745ioj.4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 17 Jan 2018 07:28:36 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=blockstream.io; s=google;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=Q42ck9Tqxwiwz1xtSEnsoiW9NUJ740sfY3ivm8Z0FP8=;
	b=MdV4Nfd1gZl5/FkLi9eTf7WXqwNH2KAnmwgI2YyeSu8f5AfTtKuXeVG1yyYJCm2OVb
	O8PyJdfWLTez0CTL2p6VLa9cyVcy3P2VejvJ2+AYxwDcqkvERBF6EJBJXH7UoZ40V7ZY
	Gpa0PAipVuwROViG0yWWx7NnUvU+IImseq2eQ=
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=Q42ck9Tqxwiwz1xtSEnsoiW9NUJ740sfY3ivm8Z0FP8=;
	b=gM6875Q5u9/FMSUAhKMY9PtgkrmlR94oC8p53/NXPw9133k/W1dhVc+1foYrJbZDTh
	peZfQAov9pe05+0juc1KpztiA1LGqgjRDYOeBgowMmmzyLjF5PVHj1VyIsd4yvJqxzvx
	4XDl+uoQYigTs2+eVC5OUQEwOvpWXOzP10HigSzwiR6DAJGQzi6mR/Pq7AOojzhnyKxj
	125gEAEDrq5F6NHnkGQGT+qD+lTPOIC91RjQMEN3ulqEa9eeIO+yzb9CxiWx/kUnSKfq
	7tNuBu5QjhGaGwtQ8LVLBUA/80AodwFGrevV93q40O2aOLmOVb2qkzXhKxRWQLjDqH+7
	Z5WQ==
X-Gm-Message-State: AKwxytdPwf0E5WRZVuwGZwT4xhthJhzuXy0wujWYehDJwTVcNzcK7QZr
	IUTXjYByXBeq0rvvrrLoGXzgNcPPy24OX0pSYdFVbEi/2N8=
X-Google-Smtp-Source: ACJfBos3KxiWoV+RXrxOpeJDV6fi4Rnp7UYq2sYs0+mcs700KlOpoKT2JytkqQA3WtQrrIsTpcow0HdLzs1EshF6Lnw=
X-Received: by 10.107.82.15 with SMTP id g15mr11424713iob.157.1516202915792;
	Wed, 17 Jan 2018 07:28:35 -0800 (PST)
MIME-Version: 1.0
Received: by 10.2.165.7 with HTTP; Wed, 17 Jan 2018 07:28:15 -0800 (PST)
In-Reply-To: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com>
References: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Wed, 17 Jan 2018 10:28:15 -0500
Message-ID: <CAMZUoKnJM+U0QrVgD1VP4Q=krYDHmCn-poydVrz79r-w-89+yw@mail.gmail.com>
To: =?UTF-8?Q?Ond=C5=99ej_Vejpustek?= <ondrej.vejpustek@satoshilabs.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="089e08265de83450a00562fa80c0"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, 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
Subject: Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
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: Wed, 17 Jan 2018 15:28:37 -0000

--089e08265de83450a00562fa80c0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Ond=C5=99ej,

1. There is no similarity between SSS and RSA or any other public-key or
symmetric crypto.  SSS is effectively a one-time pad and is
information-theoretically secure.

2. Even if there were a problem (which there cannot be, due to (1)), using
error correcting codes and truncated hash functions create identical
amounts of information theoretic redundancy.

Let me repeat that SSS is "information-theoretically secure"!  It isn't
only computationally infeasible to break SSS; it is impossible to break
SSS.  If you have all but one necessary share of SSS, there is no
information leaked about the the hidden data, because for every possible
message that could be encoded, there exists some final share that would
decode to that message.  Any of the possibilities for the missing final
share are equally as likely.

It is of no use to apply the precautionary principle against impossible
attacks, especially at the cost of losing the useful properties of a real
error correcting codes that would provide actual guarantees against likely
errors.

On Wed, Jan 17, 2018 at 6:39 AM, Ond=C5=99ej Vejpustek via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The entropy argument is as follows:
>
> There is a rule of thumb which says it is safer plaintext to have low
> redundancy, see
> https://en.wikipedia.org/wiki/Redundancy_(information_theory), i. e.
> it's better to encrypt random or compressed data than natural language.
> This rule is based on Shannon's information theory which means that a
> breach of the rule usually doesn't induce a vulnerability (there is no
> known generic attack). This rule is application of a precautionary
> principle.
>
> Nevertheless, here are some examples of cryptographic attacks which may
> be considered as a consequence of the breach of the rule:
>   * Related Message Attack by Coppersmith, Franklin, Patarin, Reiter
> (https://pdfs.semanticscholar.org/899a/4fdc048102471875e24f7fecb3fb89
> 98d754.pdf)
> - given RSA ciphertext of two plaintexts x and a*x + b, where a, b are
> known, it's possible to effectively compute x provided public exponent
> is three. From the informaton-theoretic point of view the second message
> is redundant, because it's determined by the first one. Which means that
> relative redundancy of both messages is at least one half.
>   * Stereotyped Messages by Coppersmith
> (https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf, section 7) -
> given RSA ciphertext and (1-1/e) fraction of plaintext (where e is
> public exponent), it's possible to effectively compute x. Message is
> highly redundant, because only 1/e of the message is unknown. Relative
> redundancy of the message is at least (1-1/e).
>
> Consider a few notes:
>   * Nowadays there exists more complicated variants of mentioned attacks
> which have weaker premisses.
>   * There is a considerable similarity between RSA and SSS. Both schemes
> are algebraically-based (rather than boolean function based).
>   * CRCs (and error-correcting codes generally) introduce redundancy
> into the message. Moreover the redundancy is induced by a linear
> relationship among message (compare with the premise of the Related
> Message Attack).
>   * Related Message Attack wouldn't be possible if you had two
> plaintexts x and hash(x). The relationship between messages has to be
> (algebraically) uncomplicated. From the information-theoretic point of
> view the situation is the same, but from the practical point of view it
> is completely different.
>
> To sum it up, there is a precautionary principle which tells us not to
> increase redundancy of a message unless it is introduced in a
> complicated way (for example by a hash function). That's why we use SHA
> rather than CRC. One more reason why we stick to the principle is that
> there's no randomisation in our scheme (such as padding or
> initialisation vector). We understood advantages of error-correctings
> codes over hash functions (minimal codewords distance property,
> performance) and we considered it thoroughly.
>
> Ond=C5=99ej Vejpustek
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div>Hi Ond=C5=99ej,<br></div><div><br></div><div>1. There=
 is no similarity between SSS and RSA or any other public-key or symmetric =
crypto.=C2=A0 SSS is effectively a one-time pad and is information-theoreti=
cally secure.</div><div><br></div><div>2. Even if there were a problem (whi=
ch there cannot be, due to (1)), using error correcting codes and truncated=
 hash functions create identical amounts of information theoretic redundanc=
y.</div><div><br></div>Let me repeat that SSS is &quot;information-theoreti=
cally secure&quot;!=C2=A0 It isn&#39;t only computationally infeasible to b=
reak SSS; it is impossible to break SSS.=C2=A0 If you have all but one nece=
ssary share of SSS, there is no information leaked about the the hidden dat=
a, because for every possible message that could be encoded, there exists s=
ome final share that would decode to that message.=C2=A0 Any of the possibi=
lities for the missing final share are equally as likely.<div><br></div><di=
v>It is of no use to apply the precautionary principle against impossible=
=20
attacks, especially at the cost of losing the useful properties of a=20
real error correcting codes that would provide actual guarantees against li=
kely errors.<br><div><br></div><div><div class=3D"gmail_extra"><div class=
=3D"gmail_quote">On Wed, Jan 17, 2018 at 6:39 AM, Ond=C5=99ej Vejpustek via=
 bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linu=
xfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a=
>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Th=
e entropy argument is as follows:<br>
<br>
There is a rule of thumb which says it is safer plaintext to have low<br>
redundancy, see<br>
<a href=3D"https://en.wikipedia.org/wiki/Redundancy_(information_theory)" r=
el=3D"noreferrer" target=3D"_blank">https://en.wikipedia.org/wiki/<wbr>Redu=
ndancy_(information_<wbr>theory)</a>, i. e.<br>
it&#39;s better to encrypt random or compressed data than natural language.=
<br>
This rule is based on Shannon&#39;s information theory which means that a<b=
r>
breach of the rule usually doesn&#39;t induce a vulnerability (there is no<=
br>
known generic attack). This rule is application of a precautionary<br>
principle.<br>
<br>
Nevertheless, here are some examples of cryptographic attacks which may<br>
be considered as a consequence of the breach of the rule:<br>
=C2=A0 * Related Message Attack by Coppersmith, Franklin, Patarin, Reiter<b=
r>
(<a href=3D"https://pdfs.semanticscholar.org/899a/4fdc048102471875e24f7fecb=
3fb8998d754.pdf" rel=3D"noreferrer" target=3D"_blank">https://pdfs.semantic=
scholar.<wbr>org/899a/<wbr>4fdc048102471875e24f7fecb3fb89<wbr>98d754.pdf</a=
>)<br>
- given RSA ciphertext of two plaintexts x and a*x + b, where a, b are<br>
known, it&#39;s possible to effectively compute x provided public exponent<=
br>
is three. From the informaton-theoretic point of view the second message<br=
>
is redundant, because it&#39;s determined by the first one. Which means tha=
t<br>
relative redundancy of both messages is at least one half.<br>
=C2=A0 * Stereotyped Messages by Coppersmith<br>
(<a href=3D"https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf" rel=
=3D"noreferrer" target=3D"_blank">https://www.di.ens.fr/~<wbr>fouque/ens-re=
nnes/coppersmith.<wbr>pdf</a>, section 7) -<br>
given RSA ciphertext and (1-1/e) fraction of plaintext (where e is<br>
public exponent), it&#39;s possible to effectively compute x. Message is<br=
>
highly redundant, because only 1/e of the message is unknown. Relative<br>
redundancy of the message is at least (1-1/e).<br>
<br>
Consider a few notes:<br>
=C2=A0 * Nowadays there exists more complicated variants of mentioned attac=
ks<br>
which have weaker premisses.<br>
=C2=A0 * There is a considerable similarity between RSA and SSS. Both schem=
es<br>
are algebraically-based (rather than boolean function based).<br>
=C2=A0 * CRCs (and error-correcting codes generally) introduce redundancy<b=
r>
into the message. Moreover the redundancy is induced by a linear<br>
relationship among message (compare with the premise of the Related<br>
Message Attack).<br>
=C2=A0 * Related Message Attack wouldn&#39;t be possible if you had two<br>
plaintexts x and hash(x). The relationship between messages has to be<br>
(algebraically) uncomplicated. From the information-theoretic point of<br>
view the situation is the same, but from the practical point of view it<br>
is completely different.<br>
<br>
To sum it up, there is a precautionary principle which tells us not to<br>
increase redundancy of a message unless it is introduced in a<br>
complicated way (for example by a hash function). That&#39;s why we use SHA=
<br>
rather than CRC. One more reason why we stick to the principle is that<br>
there&#39;s no randomisation in our scheme (such as padding or<br>
initialisation vector). We understood advantages of error-correctings<br>
codes over hash functions (minimal codewords distance property,<br>
performance) and we considered it thoroughly.<br>
<br>
Ond=C5=99ej Vejpustek<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></div></div></div>

--089e08265de83450a00562fa80c0--