Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 556F7C002D for ; 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 ; 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 ; 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 ; Mon, 11 Jul 2022 13:12:05 +0000 (UTC) Received: by mail-lf1-x12d.google.com with SMTP id d12so8577500lfq.12 for ; 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> In-Reply-To: From: Erik Aronesty Date: Mon, 11 Jul 2022 09:11:53 -0400 Message-ID: To: Anton Shevchenko , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
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 20483. You can keep doing these, being aware that it becomes geometrically mo= re difficult each time (deletion=C2=A0+ swap =3D 270k ops)
= 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's still a decent= UX (under a minute)


On Sat, Jul 9, 2022 at 8:01 PM Ant= on Shevchenko via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
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).

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

-= -=C2=A0 Anton Shevchenko


On Sat, Jul 9, 2022, at 1:31 PM, Zac Greenwood via b= itcoin-dev wrote:
Sorting a seed alphabetically reduces ent= ropy by ~29 bits.

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.

Zac


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

What do you do if the = "first" word (of 12), happens to be the last word in the list alp= habetically?

That couldn'= ;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.

However!=C2=A0

(@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'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.


<= div>James
_______________________________________= ________
bitcoin-dev mailing list
____________________________________= ___________
bitcoin-dev mailing list

<= /div>
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000004272e705e3874c8e--