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>
In-Reply-To: <CAJ4-pEA7WJpbExcsgdPWVNuZLrbDDhVYr37g6_6NSf7t41eB4w@mail.gmail.com>
From: James MacWhyte <macwhyte@gmail.com>
Date: Sun, 10 Jul 2022 00:21:16 +0200
Message-ID: <CAH+Axy7bgRgHKZD4hsfVsnUrNooa2kvxwNUhzycmG-MahAgnUQ@mail.gmail.com>
To: Zac Greenwood <zachgrw@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000503cb105e366bef7"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] No Order Mnemonic
Precedence: list

--000000000000503cb105e366bef7
Content-Type: text/plain; charset="UTF-8"

Thanks, Zac!

I indeed did get the napkin math very wrong. I now get around 10^30 total
possible phrases, which would take an impossibly long time to brute force.
So, it is less entropy but probably still sufficient for low-stakes usage.

James


On Sat, Jul 9, 2022 at 10:31 PM Zac Greenwood <zachgrw@gmail.com> 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
>>
>

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

<div dir=3D"ltr">Thanks, Zac!<br><br>I indeed did get the napkin math very =
wrong. I now get around 10^30 total possible phrases, which would take an i=
mpossibly long time to brute force. So, it is less entropy but probably sti=
ll sufficient for low-stakes usage.<div><br clear=3D"all"><div><div dir=3D"=
ltr" class=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=
=3D"ltr"><div>James<br></div></div></div></div><br></div></div><br><div cla=
ss=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, Jul 9, 202=
2 at 10:31 PM Zac Greenwood &lt;<a href=3D"mailto:zachgrw@gmail.com">zachgr=
w@gmail.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);padding=
-left:1ex"><div dir=3D"auto">Sorting a seed alphabetically reduces entropy =
by ~29 bits.</div><div dir=3D"auto"><br></div><div dir=3D"auto">A 12-word s=
eed has (12, 12) permutations or 479 million, which is ln(469m) / ln(2) ~=
=3D 29 bits of entropy. Sorting removes this entropy entirely, reducing the=
 seed entropy from 128 to 99 bits.</div><div dir=3D"auto"><br></div><div di=
r=3D"auto">Zac</div><div><br><div class=3D"gmail_quote"><div dir=3D"ltr" cl=
ass=3D"gmail_attr"><br></div><div dir=3D"ltr" class=3D"gmail_attr">On Fri, =
8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev &lt;<a href=3D"mailto:b=
itcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.l=
inuxfoundation.org</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);=
padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><br></div><div class=3D=
"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px=
 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D=
"auto">What do you do if the &quot;first&quot; word (of 12), happens to be =
the last word in the list alphabetically?</div></blockquote><div><br></div>=
<div>That couldn&#39;t happen. If one word is the very last from the wordli=
st, it would end up at the end of your mnemonic=C2=A0once you rearrange you=
r 12 words alphabetically.<br><br>However!=C2=A0</div><div><br>(@vjudeu) Ch=
oosing 11 random words and then sorting them alphabetically before assignin=
g=C2=A0a checksum would reduce entropy considerably. If you think about it,=
 to bruteforce the entire keyspace one would only need to come up with ever=
y 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 co=
mbinations, which would only take a couple months to exhaust with hardware =
that can do 1 million guesses per second.</div></div></div><div dir=3D"ltr"=
><div class=3D"gmail_quote"><div><br></div><div><br></div><div>James</div><=
/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></div>
</blockquote></div>

--000000000000503cb105e366bef7--