Date: Sun, 19 Feb 2023 22:12:51 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: "David A. Harding" <dave@dtrt.org>
Message-ID: <Y/Ke4yV7eV/87Kat@camus>
References: <CAMZUoKmiwXW50F2onqNUZO8HXQa4+Z=z3s3WyN7-rAMV=KiSgw@mail.gmail.com>
 <CAF90AvmaRYO6HKn9npyfzO6M6FZnN6DRhqopLpeSnHJNK=5i9g@mail.gmail.com>
 <Y+40gVnMpj0prfQk@camus>
 <f19acdabd3fbc0ff389669131acbb79e@dtrt.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
 protocol="application/pgp-signature"; boundary="E3nj//M6y2mWiy+S"
Content-Disposition: inline
In-Reply-To: <f19acdabd3fbc0ff389669131acbb79e@dtrt.org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Codex32
Precedence: list


--E3nj//M6y2mWiy+S
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sun, Feb 19, 2023 at 10:13:33AM -1000, David A. Harding wrote:
> On 2023-02-16 03:49, Andrew Poelstra via bitcoin-dev wrote:
> > the draft lists several benefits over SLIP-0039.
>=20
> The only benefit over SLIP39 that I see explicitly mentioned in the
> draft BIP is "simple enough for hand computation".  In the FAQ[1] on the
> project's website, I see some additional reasons:
>

Oh, you're right! I think we removed this text in one of our revisions.
I'll see if it makes sense to put it back.

> | This scheme is essentially the same as SLIP39, with the following
> differences:
> |
> | - The checksum is longer, slightly stronger, and designed to be
> |   computable by hand.
> |
> | - Our encoding is more compact, giving us room for a bit of more
> |   metadata, which is also designed to be readable by hand.
> |
> | - Unlike SLIP39, we do not support passphrases or hardening of any
> |   form.
> |
> | - Unlike SLIP39, we have no hardware wallet support. But we hope that
> |   will change!
>=20

These are roughly the benefits -- a more compact encoding which is
always a fixed width. We also list "not supporting features such as
passphrases" as a benefit, for users who don't need/want this.

> <snip>
>=20
> When I first saw the post about this, it was unclear to me that it was a
> serious project, but I've become increasingly interested as I researched
> it.  I'm not personally that interested in generating entropy from dice
> or encoding shares by hand---it's already imperative that I acquire a
> trustworthy computer and load it with trustworthy software in order to
> use my seed securely, so I might as well have it generate my seeds and my
> recovery codes for me.
>

Yes, we've been a bit coy about how serious this project is, because on
its face it's such a silly thing. But for my part, I've been using it
for real coins for over a year and I consider it to be serious.

> What really did catch my attention, but which was kind of buried in the
> project documentation, is the ability to verify the integrity of each
> share independently without using a computer.  For example, if I store a
> share with some relative who lives thousands of kilometers away, I'll be
> able to take that share out of its tamper-evident bag on my annual
> holiday visit, verify that I can still read it accurately by validating
> its checksum, and put it into a new bag for another year.  For this
> procedure, I don't need to bring copies of any of my other shares,
> allowing them (and my seed) to stay safe.
>=20

This is good feedback. I strongly agree that this is the big selling
point for this -- that you can vet shares/seeds which *aren't* being
actively used, without exposing them to the sorts of threats associated
with active use.

We should make this more prominent in the BIP motivation.

>=20
> I do have one question after watching an excellent video[2] about the
> motivation for this system.  In the video, one of the threat models
> described is a disarrangement of the words in a metal backup system.
> The implication seems to be that this would be an accidental
> disarrangement, which obviously the Codex32 checksum would catch during
> periodic offline verification.  But what about deliberate modification
> of a recovery code?  For example, Bob doesn't keep his seed loaded on
> any computer; it only exists in Codex32 shares which Bob plans to
> combine together in 20 years when he retires, although he makes regular
> deposits to the pubkeys derived from the seed's master xpub.  Mallory is
> able to obtain access to Bob's shares, allowing her to immediately steal
> his current funds---but also allowing her to replace them with
> similar-looking
> shares with the same metadata and valid checksums so that Bob
> continues making deposits to the wallet.
>=20
> 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.

BTW, to execute this attack Alice doesn't need to compromise *all* the
shares. Just enough that Bob no longer has threshold-many un-tampered
ones left.

--=20
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


--E3nj//M6y2mWiy+S
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmPynt8ACgkQxYjWPOQb
l8Hw2Qf+OSKs5tcPcHoueuICfpg6pZsy7N4Cqjq6mjjvgJpGztMFxp95R+1Uqh3g
ixN2ayhZdSD8p9/4bkMpfPTVMXG2bmyJPaX8BH57cdrBQE5SwZTxxHd2rwNx0ne+
276hJvtmNZAIyLT9TVyJkdbpa8E0FjkrVfq64YKL/t9Zr0d7Ixvaiep6h9POjslI
9lHa5Dujg5eN1ann973eJc72M5FjLitLZ8QM7MNXuU+SSz4aNm/ecN3b2yHrXNAK
gPh0G6dwrrRkQneynxHhWH+Y/ZE49w8K/dlN4tZ36oudUjOqD79b+sQQq1o6EilF
wpFZ7Hib2sHM6LhkTIUkj5PKOYQc8Q==
=sDlU
-----END PGP SIGNATURE-----

--E3nj//M6y2mWiy+S--