MIME-Version: 1.0
References: <CAMZUoKmiwXW50F2onqNUZO8HXQa4+Z=z3s3WyN7-rAMV=KiSgw@mail.gmail.com>
 <CAF90AvmaRYO6HKn9npyfzO6M6FZnN6DRhqopLpeSnHJNK=5i9g@mail.gmail.com>
 <Y+40gVnMpj0prfQk@camus> <f19acdabd3fbc0ff389669131acbb79e@dtrt.org>
In-Reply-To: <f19acdabd3fbc0ff389669131acbb79e@dtrt.org>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Wed, 22 Feb 2023 12:24:19 -0500
Message-ID: <CAMZUoKnV6gGBY1_zzAdPyzHLhNAMzM1PiLAHDwiPdBQds3MAxA@mail.gmail.com>
To: "David A. Harding" <dave@dtrt.org>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000043708a05f54d2b68"
Subject: Re: [bitcoin-dev] Codex32
Precedence: list

--00000000000043708a05f54d2b68
Content-Type: text/plain; charset="UTF-8"

On Sun, Feb 19, 2023 at 3:13 PM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>    Codex32 allows the individual to periodically perform their
>    recollection on paper in a private room without electronics and use
>    nothing but a pen and some loookup tables (or a paper device) to
>    verify that they recalled the string correctly (and its checksum can
>    help with correcting up to several errors, although you might need a
>    computer for error location and correction assistance).
>

While perhaps not entirely impossible, doing error correction by hand is
far more difficult than just the error detection process.
Fortunately, error correction can be aided by a computer needing very
little trust.

When doing hand computation of the checksum, there is an error if the final
"residue" is different from the value given in the codex32 spec.
After double checking your hand computation by redoing it, if you still get
the same incorrect residue, there is an error in your share data somewhere.

What you can do is plug in the residue that you did compute into a
computer, and have it produce an error correction string.
You can then, by hand, add this error correction string to your share to
get a corrected share.

If it were the case that all types of character errors were equally likely
(as in during an error any character is equally likely to be transformed
into any other character), then the computer would gain zero information
about your actual share data.  Of course, it is not in fact the case that
all transcription errors are equally likely, and so the computer can learn
a little bit about your share. The fewer errors that are made, the less
data it can recover. If you only have one character in error, then 5 bits
is the most data it can recover, and that is assuming that it can somehow
infer your error perfectly from the delta of the error correction, which
isn't actually going to be the case.

Of course, a single share from a split secret has no information about your
master seed (the master seed is hidden in the correlation between different
shares).  So learning partial information about one share isn't going to be
enough by itself to even begin compromising your master key.

This all still needs to be written up in more detail, but I figured I would
give a preview here.

- Hierarchy: Codex32 does not natively provide support for nested SSSS
>    whereas SLIP39 does.  E.g., in SLIP39, you can require 2-of-3 for
>    {me, family, friends} where me is 2-of-3 {fire_safe, bank_safe,
>    buried_in_woods}, family is 1-of-3 {alice, bob, carol}, and friends
>    are 2-of-5 {d, e, f, g, h}.  I assume you can do the same with Codex32
>    by using the share for one level as the secret for the next level,
>    although this is not described in the protocol.
>

There was a design for a second level share scheme floating around
somewhere. I'll have to dig it up. As I recall this is made slightly more
complicated by needing to incorporate share metadata (i.e. the share index)
when doing a second split, but it seemed doable at the time.


> - Versioning: Codex32's metadata can store version information for
>    wallets that use implicit BIP32 paths (e.g. BIP44/49/84/86), although
>    this would cut into the space available for users to set their own
>    metadata and it is not specified in the draft BIP.  SLIP39 also
>    doesn't specify anything about implicit path versioning and, AFAICT,
>    doesn't have any room to store such metadata without reducing seed
>    entropy.
>

Personally, I don't consider the derivation path / descriptor data as that
sensitive, and I would recommend making wide backups of that data.
It certainly would make sense to store descriptor data alongside wherever
you keep your shares, and more places beyond that.
On the other hand, if you are trying to keep your shares innocuous somehow,
perhaps you won't be able to keep the descriptor data alongside your shares.

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.
>

I do think hardware wallets are great, and overall provide a lot of
practical protection.  What is notable is that once the secrets are loaded
onto a hardware wallet, as long as that wallet remains isolated, it cannot
leak any secrets.

Of course, a wallet needs to interact with the Bitcoin protocol and P2P
network, at least indirectly, in order to  function, so we must break that
isolation.  However, if we can limit the communication capabilities of a
hardware wallet, even a malicious wallet shouldn't be able to leak the
secret data.

There are three main vectors a hardware wallet can try to communicate that
I am aware of:

1. Compromise at seed/master secret (or in this case shares of the master
secret) during generation time.
2. Lie about public keys at public key generation time.
3. Exfiltrate data though signature data or otherwise during signature
generation time.

#3 is largely mitigated through using anti-exfil signing and air gapping
the hardware wallet (e.g. using QR codes, or using RS-232
<https://en.wikipedia.org/wiki/RS-232> if you consider that air gaping).
Using multiple wallets from different vendors doing deterministic signing
is another possibility, but I consider the method deprecated in favour of
anti-exfil.

Addressing #1 is where codex32 lies, by taking master secret handling
functions out of the hardware wallet.

My understanding is that it is difficult for digital hardware, which tries
very hard to be deterministic, to generate randomness, especially for
isolated hardware devices like hardware wallets.
Also it is hard for hardware to tell if their hardware random number
generator is broken.  Generally I don't trust small pieces of isolated
digital hardware to generate master seeds, even when they are not
malicious. This may just be due to my ignorance of how they operate.

#2 seems to be the hardest issue to address.  My current thinking is to
generate addresses on a diverse set of hardware and/or using public
derivations.
Perhaps an alternative to BIP-32 could be designed to make it easy to
generate zero-knowledge proofs of pubkey derivations.

Of course there are other ways for a hardware wallets to exfiltrate data:
The wallet can blink lights, make noise, or it can try to use radio
broadcasts, etc.  These other attack vectors seem to require physically
local support, which is a fairly big hurdle to overcome.  I suppose even
these vectors could be mitigated through various levels of tinfoil.

--00000000000043708a05f54d2b68
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 3:13 PM David A. Harding via bitcoin-dev &lt=
;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists=
.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204=
);padding-left:1ex">
=C2=A0 =C2=A0Codex32 allows the individual to periodically perform their<br=
>
=C2=A0 =C2=A0recollection on paper in a private room without electronics an=
d use<br>
=C2=A0 =C2=A0nothing but a pen and some loookup tables (or a paper device) =
to<br>
=C2=A0 =C2=A0verify that they recalled the string correctly (and its checks=
um can<br>
=C2=A0 =C2=A0help with correcting up to several errors, although you might =
need a<br>
=C2=A0 =C2=A0computer for error location and correction assistance).<br></b=
lockquote><div><br></div><div>While perhaps not entirely impossible, doing =
error correction by hand is far more difficult than just the error detectio=
n process.</div><div>Fortunately, error correction can be aided by a comput=
er needing very little trust.</div><div><br></div><div>When doing hand comp=
utation of the checksum, there is an error if the final &quot;residue&quot;=
 is different from the value given in the codex32 spec.</div><div>After dou=
ble checking your hand computation by redoing it, if you still get the same=
 incorrect residue, there is an error in your share data somewhere.</div><d=
iv><br></div><div>What you can do is plug in the residue that you did compu=
te into a computer, and have it produce an error correction string.</div><d=
iv>You can then, by hand, add this error correction string to your share to=
 get a corrected share.</div><div><br></div><div>If it were the case that a=
ll types of character errors were equally likely (as in during an error any=
 character is equally likely to be transformed into any other character), t=
hen the computer would gain zero information about your actual share data.=
=C2=A0 Of course, it is not in fact the case that all transcription errors =
are equally likely, and so the computer can learn a little bit about your s=
hare. The fewer errors that are made, the less data it can recover. If you =
only have one character in error, then 5 bits is the most data it can recov=
er, and that is assuming that it can somehow infer your error perfectly fro=
m the delta of the error correction, which isn&#39;t actually going to be t=
he case.</div><div><br></div><div>Of course, a single share from a split se=
cret has no information about your master seed (the master seed is hidden i=
n the correlation between different shares).=C2=A0 So learning partial info=
rmation about one share isn&#39;t going to be enough by itself to even begi=
n compromising your master key.</div><div><br></div><div>This all still nee=
ds to be written up in more detail, but I figured I would give a preview he=
re.<br></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"marg=
in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e=
x">
- Hierarchy: Codex32 does not natively provide support for nested SSSS<br>
=C2=A0 =C2=A0whereas SLIP39 does.=C2=A0 E.g., in SLIP39, you can require 2-=
of-3 for<br>
=C2=A0 =C2=A0{me, family, friends} where me is 2-of-3 {fire_safe, bank_safe=
,<br>
=C2=A0 =C2=A0buried_in_woods}, family is 1-of-3 {alice, bob, carol}, and fr=
iends<br>
=C2=A0 =C2=A0are 2-of-5 {d, e, f, g, h}.=C2=A0 I assume you can do the same=
 with Codex32<br>
=C2=A0 =C2=A0by using the share for one level as the secret for the next le=
vel,<br>
=C2=A0 =C2=A0although this is not described in the protocol.<br></blockquot=
e><div><br></div><div>There was a design for a second level share scheme fl=
oating around somewhere. I&#39;ll have to dig it up. As I recall this is ma=
de slightly more complicated by needing to incorporate share metadata (i.e.=
 the share index) when doing a second split, but it seemed doable at the ti=
me.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin=
:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"=
>
- Versioning: Codex32&#39;s metadata can store version information for<br>
=C2=A0 =C2=A0wallets that use implicit BIP32 paths (e.g. BIP44/49/84/86), a=
lthough<br>
=C2=A0 =C2=A0this would cut into the space available for users to set their=
 own<br>
=C2=A0 =C2=A0metadata and it is not specified in the draft BIP.=C2=A0 SLIP3=
9 also<br>
=C2=A0 =C2=A0doesn&#39;t specify anything about implicit path versioning an=
d, AFAICT,<br>
=C2=A0 =C2=A0doesn&#39;t have any room to store such metadata without reduc=
ing seed<br>
=C2=A0 =C2=A0entropy.<br></blockquote><div><br></div><div>Personally, I don=
&#39;t consider the derivation path / descriptor data as that sensitive, an=
d I would recommend making wide backups of that data.</div><div>It certainl=
y would make sense to store descriptor data alongside wherever you keep you=
r shares, and more places beyond that.</div><div>On the other hand, if you =
are trying to keep your shares innocuous somehow, perhaps you won&#39;t be =
able to keep the descriptor data alongside your shares.<br></div><br><block=
quote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1=
px solid rgb(204,204,204);padding-left:1ex">
When I first saw the post about this, it was unclear to me that it was a<br=
>
serious project, but I&#39;ve become increasingly interested as I researche=
d<br>
it.=C2=A0 I&#39;m not personally that interested in generating entropy from=
 dice<br>
or encoding shares by hand---it&#39;s already imperative that I acquire a<b=
r>
trustworthy computer and load it with trustworthy software in order to<br>
use my seed securely, so I might as well have it generate my seeds and <br>
my<br>
recovery codes for me.<br></blockquote><div><br></div><div>I do think hardw=
are wallets are great, and overall provide a lot of practical protection.=
=C2=A0 What is notable is that once the secrets are loaded onto a hardware =
wallet, as long as that wallet remains isolated, it cannot leak any secrets=
.</div><div><br></div><div>Of course, a wallet needs to interact with the B=
itcoin protocol and P2P network, at least indirectly, in order to=C2=A0 fun=
ction, so we must break that isolation.=C2=A0 However, if we can limit the =
communication capabilities of a hardware wallet, even a malicious wallet sh=
ouldn&#39;t be able to leak the secret data.</div><div><br></div><div>There=
 are three main vectors a hardware wallet can try to communicate that I am =
aware of:</div><div><br></div><div>1. Compromise at seed/master secret (or =
in this case shares of the master secret) during generation time.<br></div>=
<div>2. Lie about public keys at public key generation time.<br></div><div>=
3. Exfiltrate data though signature data or otherwise during signature gene=
ration time.</div><div><br></div><div>#3 is largely mitigated through using=
 anti-exfil signing and air gapping the hardware wallet (e.g. using QR code=
s, or using <a href=3D"https://en.wikipedia.org/wiki/RS-232" title=3D"">RS-=
232</a> if you consider that air gaping).</div><div>Using multiple wallets =
from different vendors doing deterministic signing is another possibility, =
but I consider the method deprecated in favour of anti-exfil.<br></div><div=
><br></div><div>Addressing #1 is where codex32 lies, by taking master secre=
t handling functions out of the hardware wallet.</div><div><br></div><div>M=
y understanding is that it is difficult for digital hardware, which tries v=
ery hard to be deterministic, to generate randomness, especially for isolat=
ed hardware devices like hardware wallets.</div><div>Also it is hard for ha=
rdware to tell if their hardware random number generator is broken.=C2=A0 G=
enerally I don&#39;t trust small pieces of isolated digital hardware to gen=
erate master seeds, even when they are not malicious. This may just be due =
to my ignorance of how they operate.</div><div><br></div><div>#2 seems to b=
e the hardest issue to address.=C2=A0 My current thinking is to generate ad=
dresses on a diverse set of hardware and/or using public derivations.</div>=
<div>Perhaps an alternative to BIP-32 could be designed to make it easy to =
generate zero-knowledge proofs of pubkey derivations.</div><div><br></div><=
div>Of course there are other ways for a hardware wallets to exfiltrate dat=
a:=C2=A0 The wallet can blink lights, make noise, or it can try to use radi=
o broadcasts, etc.=C2=A0 These other attack vectors seem to require physica=
lly local support, which is a fairly big hurdle to overcome.=C2=A0 I suppos=
e even these vectors could be mitigated through various levels of tinfoil.<=
br></div><div><br></div></div></div>

--00000000000043708a05f54d2b68--