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
Precedence: list

--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 &lt;=
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a>&gt; 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">
&gt; I&#39;m curious about whether there&#39;s a way to prevent this attack=
 without<br>
&gt; otherwise compromising the properties of the code?=C2=A0 For example, =
some<br>
&gt; extra data that Bob can carry around (or memorize) for verifying the<b=
r>
&gt; shares haven&#39;t changed, but which is not otherwise needed for reco=
very<br>
&gt; (so there&#39;s no problem if it&#39;s lost).<br>
&gt;<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 &quot;error correct&quot; it=
 to get<br>
a new valid, but incorrect, seed. So as long as we support error<br>
correction it&#39;ll be possible to wreck seeds in this way.<br>
<br>
It&#39;s actually even worse than this ... as long as there&#39;s a clearly=
<br>
defined &quot;checksum&quot; 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&#39;t create valid checksums without knowing. Unfortunately I<br>
don&#39;t see any way to do this with linear codes. With a hash-based<br>
&quot;checksum&quot; 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 &lt=
;<a href=3D"https://gitea.blesmrt.net/exa/ls47">https://gitea.blesmrt.net/e=
xa/ls47</a>&gt;.=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&#39;t Codex32 specific.<br></div></div></div>

--000000000000eeb19705f5171479--