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
|
Return-Path: <roconnor@blockstream.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 42EC5C002B
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Feb 2023 00:52:50 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 0B360405BD
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Feb 2023 00:52:50 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 0B360405BD
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key) header.d=blockstream-com.20210112.gappssmtp.com
header.i=@blockstream-com.20210112.gappssmtp.com header.a=rsa-sha256
header.s=20210112 header.b=eyL96jrI
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id WzvuFbWTpXLh
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Feb 2023 00:52:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 9E7AE40291
Received: from mail-pg1-x536.google.com (mail-pg1-x536.google.com
[IPv6:2607:f8b0:4864:20::536])
by smtp2.osuosl.org (Postfix) with ESMTPS id 9E7AE40291
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 20 Feb 2023 00:52:48 +0000 (UTC)
Received: by mail-pg1-x536.google.com with SMTP id 20so746881pgq.8
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 19 Feb 2023 16:52:48 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream-com.20210112.gappssmtp.com; s=20210112; t=1676854368;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:from:to:cc:subject:date:message-id:reply-to;
bh=qcM6dz4ONmQliizEC1eqRg6o3t2Jdsxhg1ot39zE8eA=;
b=eyL96jrIStcQxvz+CjpfwEg4OBOwX9UZSvepRe8VI9MFl96HSbO/79blQz2b1XJiPR
8NuLt1HHevvj7YhkRFx+uucaleHsoiDMMR0l1tTQFGikFvphg1tvzElMgMmNe2WgmghC
y9NdXdLvGWKl2WfgckCtAYpIzrE50JZOyo3qWuCzw3dSuV6X+FBu5GbFo3jXDhSflzYf
+TiZVd12qP2l0HQoGKrpEao9KYmYWsHNU+82ESCE7aWOUo/xbYz6aMlFjob1BOKTPA2R
GEZBr1p8Mu7UDlkunay7sZDakvjOsJjKMJiRC3y177Kxk1Tpf47GfvTbcNO4bpMhq1Fq
XAVA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112; t=1676854368;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
bh=qcM6dz4ONmQliizEC1eqRg6o3t2Jdsxhg1ot39zE8eA=;
b=aq909mcPT0OB6Us/3C6ZTrBcgVxE2NrEjTYtEutNmXG5AjkleJ+C9/3UEzY4BdUE/W
Trny6GSYN0M529skpgGyRktXHpSkYs547t3cXkbeDXJ4O9Q6aRwxS5cwCl6sZCO55Thq
b516e/Bpd9kFiBrAT8wMNQO7HqUbKO6JMFknz5l3cDNl7N//UeSSNgPfOY1NrokBjyJA
ost1vBwhByar5k2WkmoMME0yxiKAmKV3U4qAxLDjhWYigRZCmCaOLo1SPPZN409ZWZmi
u1LegUqxJ/ZIkx83tyPofRUMhDaw1PvedsEHwqVxkbOIEriP6VM1IKLsG5XDYAIU3QAh
5QnA==
X-Gm-Message-State: AO0yUKUy08f7rb6eXKxcuaOiXaU0cjeN4elE1zCwyAQWU4WPAXc3nOdC
ZYHizg11wlY0s8YWr7pLH7LgHkVl3vUYRol70IwplA==
X-Google-Smtp-Source: AK7set9EE6DVk7LrXAQFlDsxarkMph9MdgPf77mHOXyh7/DLz6tn17qG4Pl4T8cXsVEKXm+YqkmNIC9Jn8Yp5w2IQdI=
X-Received: by 2002:a05:6a00:d49:b0:5a9:bbac:23c6 with SMTP id
n9-20020a056a000d4900b005a9bbac23c6mr78624pfv.14.1676854367785; Sun, 19 Feb
2023 16:52:47 -0800 (PST)
MIME-Version: 1.0
References: <CAMZUoKmiwXW50F2onqNUZO8HXQa4+Z=z3s3WyN7-rAMV=KiSgw@mail.gmail.com>
<CAF90AvmaRYO6HKn9npyfzO6M6FZnN6DRhqopLpeSnHJNK=5i9g@mail.gmail.com>
<Y+40gVnMpj0prfQk@camus> <f19acdabd3fbc0ff389669131acbb79e@dtrt.org>
<Y/Ke4yV7eV/87Kat@camus>
In-Reply-To: <Y/Ke4yV7eV/87Kat@camus>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Sun, 19 Feb 2023 19:52:36 -0500
Message-ID: <CAMZUoKnXd9yP+5aLCA+tJYV4dW4gqcyjDuc+AbXiXF6JGf7H=g@mail.gmail.com>
To: Andrew Poelstra <apoelstra@wpsoftware.net>,
"David A. Harding" <dave@dtrt.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000eeb19705f5171479"
Subject: Re: [bitcoin-dev] Codex32
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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, 20 Feb 2023 00:52:50 -0000
--000000000000eeb19705f5171479
Content-Type: text/plain; charset="UTF-8"
On Sun, Feb 19, 2023 at 5:13 PM Andrew Poelstra via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Sun, Feb 19, 2023 at 10:13:33AM -1000, David A. Harding wrote:
>
> I'm curious about whether there's a way to prevent this attack without
> > otherwise compromising the properties of the code? For example, some
> > extra data that Bob can carry around (or memorize) for verifying the
> > shares haven't changed, but which is not otherwise needed for recovery
> > (so there's no problem if it's lost).
> >
>
> Unfortunately not, as near as I can tell ... one way to think of this is
> that Alice can flip a lot of random tiles then "error correct" it to get
> a new valid, but incorrect, seed. So as long as we support error
> correction it'll be possible to wreck seeds in this way.
>
> It's actually even worse than this ... as long as there's a clearly
> defined "checksum" at the end of a share, Alice will be able to mangele
> tiles and then just re-compute the checksum at the end.
>
> So what we really need to prevent this is something like a MAC: where
> Bob has a secret value which gets input into the checksum somehow, which
> Alice can't create valid checksums without knowing. Unfortunately I
> don't see any way to do this with linear codes. With a hash-based
> "checksum" a la BIP39 it would definitely be possible, but of course,
> not hand-computable.
>
Speaking off the cuff and as a non-cryptographer (i.e do NOT rush off and
do this without any vetting) but Christopher Allen once referred me to an
cypher tile set called LS47 <https://gitea.blesmrt.net/exa/ls47>. If we
set aside the cypertext, I suspect we can form a MAC by recording some
random initial tile configuration, running the LS47 algorithm, and
recording the final tile configuration. These records are not sensitive as
(presumably!) the share data is not recoverable from just knowing these two
configurations. So one can keep these records with you, digitally sign
them or whatever, and then take them to your share on a regular basis to
rerun the LS47 algorithm to see if you still get the same final state from
the initial state.
Perhaps something more specific to Bech32 could be designed, but otherwise
this (alleged) MAC process isn't Codex32 specific.
--000000000000eeb19705f5171479
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Sun, Feb 19, 2023 at 5:13 PM Andrew Poelstra via bitcoin-dev <=
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br></div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px soli=
d rgb(204,204,204);padding-left:1ex">On Sun, Feb 19, 2023 at 10:13:33AM -10=
00, David A. Harding wrote:<br></blockquote><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex">
> I'm curious about whether there's a way to prevent this attack=
without<br>
> otherwise compromising the properties of the code?=C2=A0 For example, =
some<br>
> extra data that Bob can carry around (or memorize) for verifying the<b=
r>
> shares haven't changed, but which is not otherwise needed for reco=
very<br>
> (so there's no problem if it's lost).<br>
><br>
<br>
Unfortunately not, as near as I can tell ... one way to think of this is<br=
>
that Alice can flip a lot of random tiles then "error correct" it=
to get<br>
a new valid, but incorrect, seed. So as long as we support error<br>
correction it'll be possible to wreck seeds in this way.<br>
<br>
It's actually even worse than this ... as long as there's a clearly=
<br>
defined "checksum" at the end of a share, Alice will be able to m=
angele<br>
tiles and then just re-compute the checksum at the end.<br>
<br>
So what we really need to prevent this is something like a MAC: where<br>
Bob has a secret value which gets input into the checksum somehow, which<br=
>
Alice can't create valid checksums without knowing. Unfortunately I<br>
don't see any way to do this with linear codes. With a hash-based<br>
"checksum" a la BIP39 it would definitely be possible, but of cou=
rse,<br>
not hand-computable.<br></blockquote><br><div>Speaking off the cuff and as =
a non-cryptographer (i.e do NOT rush off and do this without any vetting) b=
ut Christopher Allen once referred me to an cypher tile set called LS47 <=
;<a href=3D"https://gitea.blesmrt.net/exa/ls47">https://gitea.blesmrt.net/e=
xa/ls47</a>>.=C2=A0 If we set aside the cypertext, I suspect we can form=
a MAC by recording some random initial tile configuration, running the LS4=
7 algorithm, and recording the final tile configuration.=C2=A0 These record=
s are not sensitive as (presumably!) the share data is not recoverable from=
just knowing these two configurations.=C2=A0 So one can keep these records=
with you, digitally sign them or whatever, and then take them to your shar=
e on a regular basis to rerun the LS47 algorithm to see if you still get th=
e same final state from the initial state.</div><div><br></div><div>Perhaps=
something more specific to Bech32 could be designed, but otherwise this (a=
lleged) MAC process isn't Codex32 specific.<br></div></div></div>
--000000000000eeb19705f5171479--
|
