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
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 93F4B10B1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 17 Jan 2018 15:31:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f48.google.com (mail-vk0-f48.google.com
[209.85.213.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 04B00157
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 17 Jan 2018 15:31:46 +0000 (UTC)
Received: by mail-vk0-f48.google.com with SMTP id e125so8490381vkh.13
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 17 Jan 2018 07:31:46 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:sender:in-reply-to:references:from:date:message-id
:subject:to:content-transfer-encoding;
bh=z3+F3pl4LAhBYFCzsXUa/7v1l9fUNDxXdDE/CjUtNjE=;
b=QKIocIoLOSEfKyCI38LzEfmFdtGiuG52oWzqpYG7XVzwryN/hX0XWzZLPB+EKzk2Gx
IoMY4uP1fhb5KMSA6B0IKd10b692frI7UakdUVKRdEgQzG4owRQzU0Wl0bXNbMtgo81T
zjVAHQV81ex6Ap8PCtP//xpDg7FEEY3zo4z1rvbpK1iFqwQgn+XyzuGQqoCucBZDp1Mt
QVuo0NCIf/I0wIyuIf3op1FzjC0bSTqOkdlRMBxWzGTZECMgSIbvpFvVXnkKTedW3gfl
y/cmM86TewPH0GMihANIlEnzPOgnFV5yGzUqQJ9XO2e2ghPKIF4QiyQ3PsD9rYxlbRh1
Zejw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:from
:date:message-id:subject:to:content-transfer-encoding;
bh=z3+F3pl4LAhBYFCzsXUa/7v1l9fUNDxXdDE/CjUtNjE=;
b=tG29vXzbakUbi1Y1z577BP1iYjPPZZHSZrP2gDbwXMXOtls3aa3UlApeSL4uEiUdH0
3vcqBUHdh2LNun7rpCGNbPeGcnBVQco10ZNDix3TTdXioRIiWoNYjNVpjStnvj81HWyn
J7S+smHzwjXVna+ewbBq3wt/m1sSe1bJw5dbpLONbTarBc0eBwk8wQy3G03O8nmn6E2X
8Mz8U3xJY6qX3FbNxxJ7vEa01SZTb/BXgAXlGGjw2Foh5RWdwbTIrCA73tbukV013sPk
mFbAMAQ8AQEJYPu+V5S5WWQQO4I7xQ3WsyAWSlmj9Sfa/MWDoFM1YT/ZndyHr11qlN+K
10zw==
X-Gm-Message-State: AKwxytdcBSoAe3sV2MZDEkrfe5JtdymcjO8/hW095S9DSlpXMzhRUL9+
YGSKPcFiqd+0IyGYY/dazZwi6GrXWtOx+REAdnMFbw==
X-Google-Smtp-Source: ACJfBouINu/RvTdsrgIR9Db1rSptE8vrI6bgOVjDskA5+aVQMzAHPjKhy5Zz6KVE9QHQ3Gy4xIkogxmgQJ9Jc0RVO8U=
X-Received: by 10.31.3.94 with SMTP id 91mr2228577vkd.124.1516203105957; Wed,
17 Jan 2018 07:31:45 -0800 (PST)
MIME-Version: 1.0
Sender: gmaxwell@gmail.com
Received: by 10.103.85.152 with HTTP; Wed, 17 Jan 2018 07:31:44 -0800 (PST)
In-Reply-To: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com>
References: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Wed, 17 Jan 2018 15:31:44 +0000
X-Google-Sender-Auth: cjJx6mBqjvpYSoZrr4dSrXVHSl8
Message-ID: <CAAS2fgRQk4EUp6FO2f+RkJpDTyZX0N4=uGp7ZF=0aUchZX8hSA@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: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, 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
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:31:47 -0000
On Wed, Jan 17, 2018 at 11:39 AM, Ond=C5=99ej Vejpustek via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> 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).
I'm sorry but I must not be following your message. I read the above
as "these are similar because they are based on math"...
Shamir secret sharing, correctly implemented (which indeed seems to be
many parties problem...) achieves information theoretic security. In
this critical sense it is utterly unrelated to RSA.
In fact this applies generally given any fixed threashold-1 set of
shares there is an value of the final remaining share which decodes to
every possible message. So without knowing of an extra share you know
nothing of the message.
The simplest demonstration is the 2 of 2 case, which can most simply
be constructed over GF(2) as in the traditional "one time pad":
message =3D share1 xor share2. For any given share1 or given share2
there exist a value of share2 or share1 respectively which yields
every possible message.
If the generalization isn't obvious, it might be helpful to make a
little test utility that tries all possible one byte messages with all
possible share values using the GF(256) sharing scheme proposed in the
draft-- in this case information theory is why we can know SSS (and
similar) have (within their limited scope) _perfect_ security, rather
than it being a reason to speculate that they might not turn out to be
secure at all. (or, instead of a test utility just work through some
examples on paper in a small field).
This doesn't change when you add additional conditionals on it-- e.g.
Say you a 2-of-3 sharing where you have your choice of any of the
three shares but do not know the others and assume you know every bit
of the plaintext save one bit or any linear or non-linear relationship
between plaintext bits (excepting for actually knowing the secret)...
In these case there can still be no attack arising out of this
charitably bad plaintext structure because-- as pointed out above--
all possible plaintexts are equal-probable you know nothing of which
of the two possible solutions is correct without knowing about the
other shares because for each possible value there exists a value for
the unknown shares which would cause that decoding-- there is no
leakage at all, the share doesn't teach you anything you didn't
already know.
In my view any SSS tool should also include a forgery utility which
demonstrates this property, both as a critical test-- but also because
being able to forge an alternative answer to deceive an attacker which
has compromised some of your shares is one of the (at least
theoretical) arguments for using SSS over computational secret
sharing.
> unless it is introduced in a complicated way
Complicated does not mean secure. And from an information theoretic
perspective the hash does almost nothing (other then some small
destruction of entropy due to its lack of perfect uniformity which is
information theoretically equivalent to using a smaller perfect code).
There are many cases where I too am more comfortable using a hash --
where it may destroy some structure which I cannot _prove_ would be
safe to retain, but this is not one of those cases.
> * CRCs (and error-correcting codes generally) introduce redundancy
into the message
The discussion of using a proper code was primarily related to the
outer check value which protects the shares themselves and is sitting
unprotected in plaintext; not so much the one inside the sharing in
any case; since its the outer one which could be structured to provide
perfect detection of errors that align with words (e.g. transposing
two words).
|
