Subject: Re: [bitcoin-dev] Codex32

From: "Russell O'Connor" <[email-masked]>
Date: Sun, 19 Feb 2023 19:52:36 -0500

On Sun, Feb 19, 2023 at 5:13 PM Andrew Poelstra via bitcoin-dev <
[email-masked]> 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.