MIME-Version: 1.0
References: <3D3BFE9C-CFF3-49FF-840F-063B52C69A42@voskuil.org>
 <164256450-0ee6752f92c0be297952fc72b59076df@pmq5v.m5r2.onet>
 <CA+XQW1iKVRmEnyP-CGM2Fo4qHi3SQHUfjEmKftDdju-uxHViJg@mail.gmail.com>
 <CAH+Axy4X+uQG5Vw0Efiz6AtNyK=++h-jDeZL1ZxpVJus8BVKeA@mail.gmail.com>
 <CAJ4-pEA7WJpbExcsgdPWVNuZLrbDDhVYr37g6_6NSf7t41eB4w@mail.gmail.com>
 <bf3b36b1-e999-43bf-88d4-3aab19d10e9d@www.fastmail.com>
 <CAJowKgJq23W3yq91pF+xm6CMjOy+tXz=zxkMVRPqCY_zWsBdiQ@mail.gmail.com>
In-Reply-To: <CAJowKgJq23W3yq91pF+xm6CMjOy+tXz=zxkMVRPqCY_zWsBdiQ@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Mon, 11 Jul 2022 09:18:14 -0400
Message-ID: <CAJowKgLRMyXQ27-m9-ud9F8Qu=6dkcfJHjoxLJh4LKyU8Nf9pw@mail.gmail.com>
To: Anton Shevchenko <anton@sancoder.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000046fe005e387638a"
Subject: Re: [bitcoin-dev] No Order Mnemonic
Precedence: list

--000000000000046fe005e387638a
Content-Type: text/plain; charset="UTF-8"

Sorry, I totally forgot the checksum.

You can take my ops-per-second and multiply it by about 16 (because of the
4 check bits), making a delete + two swaps or 4 swaps, etc. still pretty
reasonable.



On Mon, Jul 11, 2022 at 9:11 AM Erik Aronesty <erik@q32.com> wrote:

> 1. You can swap two positions, and then your recovery algorithm can
> brute-force the result by trying all 132 possible swaps.
> 2. You can make a single deletion and only have to brute 2048
> 3. You can keep doing these, being aware that it becomes geometrically
> more difficult each time (deletion + swap = 270k ops)
> 4. A home PC can make 20k secpk256 operations per second per core, so try
> to keep your number under a few million ops and it's still a decent UX
> (under a minute)
>
>
> On Sat, Jul 9, 2022 at 8:01 PM Anton Shevchenko via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> I would say removing ordering from 12-word seed reduces 25 bits of
>> entropy, not 29. Additional 4 bits come from checksum (12 words encode 132
>> bits, not 128).
>>
>> My idea [for developing this project] was to feed its output to some kind
>> of AI story generator (GPT-3 based?) so a user can remember a story, not
>> ordered words. But as others pointed out, having 12 words without order is
>> probably good enough. So at this point there's not much sense of using the
>> proposed encoding. Unless a remembered story has wholes/errors. In this
>> case recovering few words would be easier with unordered encoding. Any
>> thoughts?
>>
>> --  Anton Shevchenko
>>
>>
>> On Sat, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-dev wrote:
>>
>> Sorting a seed alphabetically reduces entropy by ~29 bits.
>>
>> A 12-word seed has (12, 12) permutations or 479 million, which is
>> ln(469m) / ln(2) ~= 29 bits of entropy. Sorting removes this entropy
>> entirely, reducing the seed entropy from 128 to 99 bits.
>>
>> Zac
>>
>>
>> On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>
>> What do you do if the "first" word (of 12), happens to be the last word
>> in the list alphabetically?
>>
>>
>> That couldn't happen. If one word is the very last from the wordlist, it
>> would end up at the end of your mnemonic once you rearrange your 12 words
>> alphabetically.
>>
>> However!
>>
>> (@vjudeu) Choosing 11 random words and then sorting them alphabetically
>> before assigning a checksum would reduce entropy considerably. If you think
>> about it, to bruteforce the entire keyspace one would only need to come up
>> with every possible combination of 11 words + 1 checksum. I'm not the best
>> at napkin math, but I think that leaves you with around 10 trillion
>> combinations, which would only take a couple months to exhaust with
>> hardware that can do 1 million guesses per second.
>>
>>
>> James
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

--000000000000046fe005e387638a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Sorry, I totally forgot the checksum.=C2=A0 =C2=A0<div><br=
></div><div>You can take my ops-per-second and multiply it by about 16 (bec=
ause of the 4 check bits), making a delete=C2=A0+ two swaps or 4 swaps, etc=
. still pretty reasonable.<div><div><br></div><div><br></div></div></div></=
div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On=
 Mon, Jul 11, 2022 at 9:11 AM Erik Aronesty &lt;<a href=3D"mailto:erik@q32.=
com">erik@q32.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex"><div dir=3D"ltr"><div>1. You can swap two positions, and t=
hen your recovery algorithm can brute-force the result by trying all 132 po=
ssible swaps.<br></div><div>2. You can make a single deletion and only have=
 to brute 2048<div>3. You can keep doing these, being aware that it becomes=
 geometrically more difficult each time (deletion=C2=A0+ swap =3D 270k ops)=
</div></div><div>4. A home PC can make 20k secpk256=C2=A0operations per sec=
ond per core, so try to keep your number under a few million ops and it&#39=
;s still a decent UX (under a minute)</div><div><br></div></div><br><div cl=
ass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, Jul 9, 20=
22 at 8:01 PM Anton Shevchenko via bitcoin-dev &lt;<a href=3D"mailto:bitcoi=
n-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxf=
oundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddi=
ng-left:1ex"><u></u><div><div style=3D"font-family:helvetica,arial,sans-ser=
if"><div style=3D"font-family:helvetica,arial,sans-serif">I would say remov=
ing ordering from 12-word seed reduces 25 bits of entropy, not 29. Addition=
al 4 bits come from checksum (12 words encode 132 bits, not 128).<br></div>=
<div style=3D"font-family:helvetica,arial,sans-serif"><br></div><div style=
=3D"font-family:helvetica,arial,sans-serif">My idea [for developing this pr=
oject] was to feed its output to some kind of AI story generator (GPT-3 bas=
ed?) so a user can remember a story, not ordered words. But as others point=
ed out, having 12 words without order is probably good enough. So at this p=
oint there&#39;s not much sense of using the proposed encoding. Unless a re=
membered story has wholes/errors. In this case recovering few words would b=
e easier with unordered encoding. Any thoughts?<br></div></div><div style=
=3D"font-family:helvetica,arial,sans-serif"><br></div><div id=3D"gmail-m_-5=
237753648968162431gmail-m_-2905539887539807527sig127103648"><div>--=C2=A0 A=
nton Shevchenko<br></div></div><div style=3D"font-family:helvetica,arial,sa=
ns-serif"><br></div><div style=3D"font-family:helvetica,arial,sans-serif"><=
br></div><div>On Sat, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-de=
v wrote:<br></div><blockquote type=3D"cite" id=3D"gmail-m_-5237753648968162=
431gmail-m_-2905539887539807527qt"><div dir=3D"auto">Sorting a seed alphabe=
tically reduces entropy by ~29 bits.<br></div><div dir=3D"auto"><br></div><=
div dir=3D"auto">A 12-word seed has (12, 12) permutations or 479 million, w=
hich is ln(469m) / ln(2) ~=3D 29 bits of entropy. Sorting removes this entr=
opy entirely, reducing the seed entropy from 128 to 99 bits.<br></div><div =
dir=3D"auto"><br></div><div dir=3D"auto">Zac<br></div><div><div><br></div><=
div><div dir=3D"ltr"><br></div><div dir=3D"ltr">On Fri, 8 Jul 2022 at 16:09=
, James MacWhyte via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.li=
nuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org<=
/a>&gt; wrote:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;borde=
r-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div d=
ir=3D"ltr"><br></div><div><blockquote style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"auto">Wha=
t do you do if the &quot;first&quot; word (of 12), happens to be the last w=
ord in the list alphabetically?<br></div></blockquote><div><br></div><div><=
div>That couldn&#39;t happen. If one word is the very last from the wordlis=
t, it would end up at the end of your mnemonic=C2=A0once you rearrange your=
 12 words alphabetically.<br></div><div><br></div><div>However!=C2=A0<br></=
div></div><div><div><br></div><div>(@vjudeu) Choosing 11 random words and t=
hen sorting them alphabetically before assigning=C2=A0a checksum would redu=
ce entropy considerably. If you think about it, to bruteforce the entire ke=
yspace one would only need to come up with every possible combination of 11=
 words=C2=A0+ 1 checksum. I&#39;m not the best at napkin math, but I think =
that leaves you with around=C2=A010 trillion combinations, which would only=
 take a couple months to exhaust with hardware that can do 1 million guesse=
s per second.<br></div></div></div></div><div dir=3D"ltr"><div><div><br></d=
iv><div><br></div><div>James<br></div></div></div><div>____________________=
___________________________<br></div><div> bitcoin-dev mailing list<br></di=
v><div> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"=
_blank">bitcoin-dev@lists.linuxfoundation.org</a><br></div><div> <a href=3D=
"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" rel=3D"nor=
eferrer" target=3D"_blank">https://lists.linuxfoundation.org/mailman/listin=
fo/bitcoin-dev</a><br></div></blockquote></div></div><div>_________________=
______________________________<br></div><div>bitcoin-dev mailing list<br></=
div><div><a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br></div><div><a href=3D=
"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" target=3D"=
_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><=
br></div><div><br></div></blockquote><div style=3D"font-family:helvetica,ar=
ial,sans-serif"><br></div></div>___________________________________________=
____<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
</blockquote></div>

--000000000000046fe005e387638a--