diff options
| author | Erik Aronesty <erik@q32.com> | 2022-07-11 09:18:14 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2022-07-11 13:18:29 +0000 |
| commit | 13e8bf40b09f26aab572e275f5a5c4ce296dbba7 (patch) | |
| tree | 75124d1bf41183f71cff3f48931fde15083d3890 | |
| parent | 853daff19d48abbc9c711ebaf574bba8983e66e2 (diff) | |
| download | pi-bitcoindev-13e8bf40b09f26aab572e275f5a5c4ce296dbba7.tar.gz pi-bitcoindev-13e8bf40b09f26aab572e275f5a5c4ce296dbba7.zip | |
Re: [bitcoin-dev] No Order Mnemonic
| -rw-r--r-- | 58/3dbc261095beae8cd17448ecf7495717a16c35 | 285 |
1 files changed, 285 insertions, 0 deletions
diff --git a/58/3dbc261095beae8cd17448ecf7495717a16c35 b/58/3dbc261095beae8cd17448ecf7495717a16c35 new file mode 100644 index 000000000..35cce5ec4 --- /dev/null +++ b/58/3dbc261095beae8cd17448ecf7495717a16c35 @@ -0,0 +1,285 @@ +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 <<a href=3D"mailto:erik@q32.= +com">erik@q32.com</a>> 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'= +;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 <<a href=3D"mailto:bitcoi= +n-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxf= +oundation.org</a>> 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'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 <<a href=3D"mailto:bitcoin-dev@lists.li= +nuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org<= +/a>> 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 "first" word (of 12), happens to be the last w= +ord in the list alphabetically?<br></div></blockquote><div><br></div><div><= +div>That couldn'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'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-- + |