path: root/58/3dbc261095beae8cd17448ecf7495717a16c35

Return-Path: <earonesty@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 21021C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:18:29 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id EF62040997
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:18:28 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org EF62040997
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=q32-com.20210112.gappssmtp.com
 header.i=@q32-com.20210112.gappssmtp.com header.a=rsa-sha256
 header.s=20210112 header.b=hsrBlM0W
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.399
X-Spam-Level: 
X-Spam-Status: No, score=-1.399 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001,
 HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=no autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 4ho49oiL2aBE
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:18:27 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 4369640977
Received: from mail-lj1-x22c.google.com (mail-lj1-x22c.google.com
 [IPv6:2a00:1450:4864:20::22c])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 4369640977
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:18:27 +0000 (UTC)
Received: by mail-lj1-x22c.google.com with SMTP id r9so6150524ljp.9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 06:18:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=q32-com.20210112.gappssmtp.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
 bh=F18bSB63TQsLGhGAozOcz3jFDbsbQTgTh8xJRlk/gCU=;
 b=hsrBlM0WpdDq3yUydi0B9m0My9Y+FUcWI/5JU1/BJu7jVN+hMsygLnlPOoWJtNQmU4
 YCHLNCaGHjhmaWVQZPPsykVNrnzaqEL6D1fmCPV+P4MnjYE58UhIqB4HG4F53rQwfLTF
 4/qrqOUPpL7SlUcu4SBcjmmnveH81L7Y+V6Tqo243uUE8Tu31xy8UEuRLYoo/Za4IUm4
 kn9EOfkQZg97zq18Bbka7/HzrljH0scmSgHC40yoP+kgqmycYkoHffmK8bbnh28moLjE
 5/7bXK6PbfthhOyu2jLgicmRd675gx+jQbsBNgnhscyObNFMDNB0vvsc0QGM5ZVrfLKx
 vWIg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to;
 bh=F18bSB63TQsLGhGAozOcz3jFDbsbQTgTh8xJRlk/gCU=;
 b=VNsJF4Pu4p0mFwWgcAvRPMlOVo1RIxIcDjKvxId8/ZSECKbe5/JZPvvEdYFh7A94d2
 +F0RycKAPbeQSYGgE7i6suHF70lGgL7xO0Rjg9EFeMqXFRaj01DD3FzXgg6Qo/RHiDHs
 FJ2SzL5qtjdQBsohKAAWMyctHfifootqTJ8jhaTWrbUIUSrKUJGe3/EWaUvw7N+yNDHc
 dT7cJe3X/7YAfACWLWyk8IcRRJfjr8VcR5z6LIzAkPJb9Rtu/pB4MLWstKBDLvJu9ir3
 a9nHadvEB1fxm/Dv9fvzQraLG7Dc62wnM28rS9440N0LSgOgKusyeGEshZMmYAz294En
 ydTw==
X-Gm-Message-State: AJIora8r4IkhBpJDFmubzuA19LHIa8c8B6xCVAwOuNdFe/cHG3PF/kao
 XCLwrkB2bJfIvJEaJ/LfyD1gcFIxSydbhH44zaGvzTA=
X-Google-Smtp-Source: AGRyM1sw/nItPFp+XefvxJcxjRO3TgcU10RH6mI+5uqlbQMyuSITlI7BLUtM0lGPm7AmzA9d524P7LtB7/M9j2ezrLk=
X-Received: by 2002:a05:651c:a0f:b0:25b:c834:4604 with SMTP id
 k15-20020a05651c0a0f00b0025bc8344604mr10095643ljq.252.1657545504877; Mon, 11
 Jul 2022 06:18:24 -0700 (PDT)
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"
X-Mailman-Approved-At: Mon, 11 Jul 2022 13:59:03 +0000
Subject: Re: [bitcoin-dev] No Order Mnemonic
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 11 Jul 2022 13:18:29 -0000

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