Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 21021C002D for ; 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 ; 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 ; 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 ; Mon, 11 Jul 2022 13:18:27 +0000 (UTC) Received: by mail-lj1-x22c.google.com with SMTP id r9so6150524ljp.9 for ; 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> In-Reply-To: From: Erik Aronesty Date: Mon, 11 Jul 2022 09:18:14 -0400 Message-ID: To: Anton Shevchenko , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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
Sorry, I totally forgot the checksum.=C2=A0 =C2=A0
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.



On= Mon, Jul 11, 2022 at 9:11 AM Erik Aronesty <erik@q32.com> wrote:
1. You can swap two positions, and t= hen your recovery algorithm can brute-force the result by trying all 132 po= ssible 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=C2=A0+ swap =3D 270k ops)=
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)


On Sat, Jul 9, 20= 22 at 8:01 PM Anton Shevchenko via bitcoin-dev <bitcoin-dev@lists.linuxf= oundation.org> wrote:
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).
=

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?

--=C2=A0 A= nton Shevchenko

<= br>
On Sat, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-de= v wrote:
Sorting a seed alphabe= tically reduces entropy by ~29 bits.

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

Zac

<= div>

On Fri, 8 Jul 2022 at 16:09= , James MacWhyte via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org<= /a>> wrote:



_________________= ______________________________

___________________________________________= ____
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000046fe005e387638a--