Re: [bitcoin-dev] No Order Mnemonic

From: Erik Aronesty <erik@q32.com>
To: Anton Shevchenko <anton@sancoder.com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] No Order Mnemonic
Date: Mon, 11 Jul 2022 09:11:53 -0400	[thread overview]
Message-ID: <CAJowKgJq23W3yq91pF+xm6CMjOy+tXz=zxkMVRPqCY_zWsBdiQ@mail.gmail.com> (raw)
In-Reply-To: <bf3b36b1-e999-43bf-88d4-3aab19d10e9d@www.fastmail.com>

[-- Attachment #1: Type: text/plain, Size: 3068 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 5468 bytes --]