path: root/d6/a3d3da7bde9cfc60f208a9f5235b4f196f3c58

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 556F7C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:12:07 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 27ECA41705
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:12:07 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 27ECA41705
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=3Hj0Fkty
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 6rQHk4xEwHLk
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:12:05 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 64B9F41701
Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com
 [IPv6:2a00:1450:4864:20::12d])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 64B9F41701
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 13:12:05 +0000 (UTC)
Received: by mail-lf1-x12d.google.com with SMTP id d12so8577500lfq.12
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 11 Jul 2022 06:12:05 -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=A9NAg0wkAVdRAcmY3ThNJIOEaeHtM6fbQTKULt9zm/A=;
 b=3Hj0Fkty++NyELFVpxaMFtmYqaCDn7arp7QLtPK2b9aMJtFwv8gHUSJ+khty8rn+P6
 ko2TknWP3l2kjZ16EFFGPSFUn6em1V07mxRsRGHALcf0gSuKnRX1IzCQAT8k2Amc19q8
 sl4dWYtDHUCWTtCmdaPy72sUkWCaU9m+fgblSKLJ0jfCkMHOAY6yujVKkRfMq5NaF0Cb
 pigspz8IyzrJQDwOvidUCHyEvA8Fpjm2MrWOvr+EhOCuZfpRghsqooFhu+Mm+Ji4RNmf
 LaxGq7fvMZX08k/koky9zGq6S3LTgNZP9QeF6pKDG8x7c8+10BtZPs+f5vUWt0cJYyVH
 i4mw==
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=A9NAg0wkAVdRAcmY3ThNJIOEaeHtM6fbQTKULt9zm/A=;
 b=RVXsfdeVmN9yMP5JOX3JraNyW+GwH8ci/l5VSjwDknU6M/lg0wEJmAcLtL7uQyYKkt
 Om76ogE+Ot+YObIjmpqpMvGgMU+qA+WPPPwLmKESzt/fIRg00B6HycJmFSsyRKOtQuNf
 y/wGspWivn6eDCaZlk6mLMWG+lOn2oAOjeOVTMwnoCdy6RVKZs4ACKq2cc3+67yh5ZdX
 8ONizGE4oA2lJjBKb+tk/O1RSvpea5S1xeqMgf2ipSEeJ2BpalifVNxOZAMAmKa+8BE6
 1QA63GujMmVcdfGgBvRJ/ljDaEz2qocrLX3and6UMfJIT7LJXnMOpo8wulWKogosNq92
 mHzA==
X-Gm-Message-State: AJIora/87HjA/0MpGBxtuBku4E5N8wDlGI7X73sWDDXy6k+Xnb/cTGpM
 g6yH6wU0YgOSkfzyk3K/YOYRbtZP+Bm1iPR6dArRTq4eSieI
X-Google-Smtp-Source: AGRyM1up8cKEvSmG37P2iBJW11tSIjSH8bMGLqauqyszGRFsVUslWPCBoBZVyiB8XrFcdBPWfVU2rtl57MkGcy/La50=
X-Received: by 2002:a05:6512:4003:b0:47f:97e9:28b8 with SMTP id
 br3-20020a056512400300b0047f97e928b8mr11250064lfb.141.1657545123065; Mon, 11
 Jul 2022 06:12:03 -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>
In-Reply-To: <bf3b36b1-e999-43bf-88d4-3aab19d10e9d@www.fastmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Mon, 11 Jul 2022 09:11:53 -0400
Message-ID: <CAJowKgJq23W3yq91pF+xm6CMjOy+tXz=zxkMVRPqCY_zWsBdiQ@mail.gmail.com>
To: Anton Shevchenko <anton@sancoder.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000004272e705e3874c8e"
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:12:07 -0000

--0000000000004272e705e3874c8e
Content-Type: text/plain; charset="UTF-8"

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
>

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

<div dir=3D"ltr"><div>1. You can swap two positions, and then your recovery=
 algorithm can brute-force the result by trying all 132 possible swaps.<br>=
</div><div>2. You can make a single deletion and only have to brute 2048<di=
v>3. You can keep doing these, being aware that it becomes geometrically mo=
re difficult each time (deletion=C2=A0+ swap =3D 270k ops)</div></div><div>=
4. A home PC can make 20k secpk256=C2=A0operations per second 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 class=3D"gmail_quot=
e"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, Jul 9, 2022 at 8:01 PM Ant=
on Shevchenko via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linux=
foundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></d=
iv><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord=
er-left:1px solid rgb(204,204,204);padding-left:1ex"><u></u><div><div style=
=3D"font-family:helvetica,arial,sans-serif"><div style=3D"font-family:helve=
tica,arial,sans-serif">I would say removing ordering from 12-word seed redu=
ces 25 bits of entropy, not 29. Additional 4 bits come from checksum (12 wo=
rds 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 project] was to feed its output to som=
e 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 orde=
r is probably good enough. So at this point there&#39;s not much sense of u=
sing the proposed encoding. Unless a remembered story has wholes/errors. In=
 this case recovering few words would be easier with unordered encoding. An=
y thoughts?<br></div></div><div style=3D"font-family:helvetica,arial,sans-s=
erif"><br></div><div id=3D"gmail-m_-2905539887539807527sig127103648"><div>-=
-=C2=A0 Anton Shevchenko<br></div></div><div style=3D"font-family:helvetica=
,arial,sans-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 b=
itcoin-dev wrote:<br></div><blockquote type=3D"cite" id=3D"gmail-m_-2905539=
887539807527qt"><div dir=3D"auto">Sorting a seed alphabetically reduces ent=
ropy 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, which is ln(469m) / =
ln(2) ~=3D 29 bits of entropy. Sorting removes this entropy entirely, reduc=
ing 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 vi=
a bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br><=
/div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><br></di=
v><div><blockquote 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 alp=
habetically?<br></div></blockquote><div><br></div><div><div>That couldn&#39=
;t happen. If one word is the very last from the wordlist, it would end up =
at the end of your mnemonic=C2=A0once you rearrange your 12 words alphabeti=
cally.<br></div><div><br></div><div>However!=C2=A0<br></div></div><div><div=
><br></div><div>(@vjudeu) Choosing 11 random words and then sorting them al=
phabetically before assigning=C2=A0a checksum would reduce entropy consider=
ably. If you think about it, to bruteforce the entire keyspace one would on=
ly need to come up with every possible combination of 11 words=C2=A0+ 1 che=
cksum. I&#39;m not the best at napkin math, but I think that leaves you wit=
h around=C2=A010 trillion combinations, which would only take a couple mont=
hs to exhaust with hardware that can do 1 million guesses per second.<br></=
div></div></div></div><div dir=3D"ltr"><div><div><br></div><div><br></div><=
div>James<br></div></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.linu=
xfoundation.org/mailman/listinfo/bitcoin-dev" rel=3D"noreferrer" target=3D"=
_blank">https://lists.linuxfoundation.org/mailman/listinfo/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-de=
v@lists.linuxfoundation.org</a><br></div><div><a href=3D"https://lists.linu=
xfoundation.org/mailman/listinfo/bitcoin-dev" target=3D"_blank">https://lis=
ts.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br></div><div><br><=
/div></blockquote><div style=3D"font-family:helvetica,arial,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>

--0000000000004272e705e3874c8e--