Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id B9F2BC002D for ; Sat, 9 Jul 2022 23:46:47 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 6A3A640471 for ; Sat, 9 Jul 2022 23:46:47 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 6A3A640471 Authentication-Results: smtp2.osuosl.org; dkim=pass (2048-bit key, unprotected) header.d=sancoder.com header.i=@sancoder.com header.a=rsa-sha256 header.s=fm3 header.b=UaBL/Mgj; dkim=pass (2048-bit key, unprotected) header.d=messagingengine.com header.i=@messagingengine.com header.a=rsa-sha256 header.s=fm3 header.b=MrvXKW8O X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.799 X-Spam-Level: X-Spam-Status: No, score=-2.799 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Yy5AkqRRmFpf for ; Sat, 9 Jul 2022 23:46:46 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org E8BB3401C2 Received: from out4-smtp.messagingengine.com (out4-smtp.messagingengine.com [66.111.4.28]) by smtp2.osuosl.org (Postfix) with ESMTPS id E8BB3401C2 for ; Sat, 9 Jul 2022 23:46:45 +0000 (UTC) Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailout.nyi.internal (Postfix) with ESMTP id 16D245C00B9 for ; Sat, 9 Jul 2022 19:46:41 -0400 (EDT) Received: from imap46 ([10.202.2.96]) by compute2.internal (MEProxy); Sat, 09 Jul 2022 19:46:41 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sancoder.com; h= cc:content-type:date:date:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:sender:subject :subject:to:to; s=fm3; t=1657410401; x=1657496801; bh=/Khr+1LVOE AJthJ0VRj31NOZWAuvTa3kBUSKzUDD+yI=; b=UaBL/MgjnJ71+eDwMGwU7qJSUN 6wmyWoXE6zKqBsKUFXOK0cP7/u870LEgamPBt6R4n0DUmZ038yjTDew8pv9CKHqR EcGe+geOK22hy5fZwlVfyx5/0tuPIgYIU6DwuvrlV69L0xZjBWl5R+KOosDq/VJc cPTtswy2mSHQctAlz2SVPGEPt9iFzVyYEUz8X9mug6yzM96LV9O4Imbt4aDK2n0t Uc6OEOKWzHgf4pHDqBBPufIsMECh9jIN9GbBsReq5fRvFXVAeQQth3GHKdtddNG3 THCHyNT9eTSNKtemndB42pybYTciyEglZKpM0pHJaxcF4FBVwPoMoRG+HDjw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:date:feedback-id :feedback-id:from:from:in-reply-to:in-reply-to:message-id :mime-version:references:reply-to:sender:subject:subject:to:to :x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1657410401; x=1657496801; bh=/Khr+1LVOEAJthJ0VRj31NOZWAuv Ta3kBUSKzUDD+yI=; b=MrvXKW8OkJfYEFMCkUFiGbqoFUWTkYmTfFRjcdaBoalf N1EKEQz1fPS7AOMIiLVI7eWhNB7j1AQtFJTeIUc6vrgKWVGctZe1dJXLbVmlocyf lTuBWMXvNjcaUx8eYfqaAFcBaNAWLGFcMy8lz+75zYQeVTz+HbW0IL1AfyzCG5gq BcqGxNm2ACryfMjxEjRCw0RjP2k96EA+jCNn44KMvtPmRCGk+b0y4ndgZJl1tJ+N fLS6K2ZkDqiVOWr/mrodKUrDKLxHAwlq/XM+LX7I0GV7W96oCCCVhotohQulBPHu E4FaS1mD+2zC7McGheZA+jiOnfkFVo/Fs3OSJwf/ZA== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvfedrudejtddgvdeiucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtsegrtd erreerredtnecuhfhrohhmpedftehnthhonhcuufhhvghvtghhvghnkhhofdcuoegrnhht ohhnsehsrghntghouggvrhdrtghomheqnecuggftrfgrthhtvghrnhepgfdtieejgfdvhf fhfefgffeigfeghfekveefvdffvdekuefhveejgfdvffetffdunecuffhomhgrihhnpehl ihhnuhigfhhouhhnuggrthhiohhnrdhorhhgnecuvehluhhsthgvrhfuihiivgeptdenuc frrghrrghmpehmrghilhhfrhhomheprghnthhonhesshgrnhgtohguvghrrdgtohhm X-ME-Proxy: Feedback-ID: i4779463d:Fastmail Received: by mailuser.nyi.internal (Postfix, from userid 501) id A0EE32A20075; Sat, 9 Jul 2022 19:46:40 -0400 (EDT) X-Mailer: MessagingEngine.com Webmail Interface User-Agent: Cyrus-JMAP/3.7.0-alpha0-720-gbf5afa95ff-fm-20220708.001-gbf5afa95 Mime-Version: 1.0 Message-Id: In-Reply-To: References: <3D3BFE9C-CFF3-49FF-840F-063B52C69A42@voskuil.org> <164256450-0ee6752f92c0be297952fc72b59076df@pmq5v.m5r2.onet> Date: Sat, 09 Jul 2022 16:46:19 -0700 From: "Anton Shevchenko" To: "Alfred Hodler" Content-Type: multipart/alternative; boundary=d0015dfb91e24b9e844e02c78a424d02 X-Mailman-Approved-At: Sun, 10 Jul 2022 00:01:00 +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: Sat, 09 Jul 2022 23:46:47 -0000 --d0015dfb91e24b9e844e02c78a424d02 Content-Type: text/plain 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 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 > --d0015dfb91e24b9e844e02c78a424d02 Content-Type: text/html Content-Transfer-Encoding: quoted-printable
I would say removing ordering from 12-word seed re= duces 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 fe= ed its output to some kind of AI story generator (GPT-3 based?) so a use= r can remember a story, not ordered words. But as others pointed out, ha= ving 12 words without order is probably good enough. So at this point th= ere's not much sense of using the proposed encoding. Unless a remembered= story has wholes/errors. In this case recovering few words would be eas= ier with unordered encoding. Any thoughts?

--  Anton Shevchenko
=


On Sa= t, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-dev wrote:
Sorti= ng a seed alphabetically reduces entropy by ~29 bits.

A 12-word seed has (12, 12) permutati= ons or 479 million, which is ln(469m) / ln(2) ~=3D 29 bits of entropy. S= orting removes this entropy entirely, reducing the seed entropy from 128= to 99 bits.

Zac<= br>


On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev <<= a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@list= s.linuxfoundation.org> wrote:

What do = you do if the "first" word (of 12), happens to be the last word in the l= ist alphabetically?

That = couldn't happen. If one word is the very last from the wordlist, it woul= d end up at the end of your mnemonic once you rearrange your 12 wor= ds alphabetically.

However! 
=

(@vjudeu) Choosing 11 random words and th= en sorting them alphabetically before assigning a checksum would re= duce entropy considerably. If you think about it, to bruteforce the enti= re keyspace one would only need to come up with every possible combinati= on 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 m= illion guesses per second.
<= div class=3D"qt-gmail_quote">


James
_______________________________________________<= br>
bitcoin-dev mailing list


<= /body> --d0015dfb91e24b9e844e02c78a424d02--