Subject: Re: [bitcoin-dev] No Order Mnemonic

From: Erik Aronesty <[email-masked]>
Date: Mon, 11 Jul 2022 09:11:53 -0400

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 <
[email-masked]> 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 <
> [email-masked]> 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
> [email-masked]
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> [email-masked]
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> _______________________________________________
> bitcoin-dev mailing list
> [email-masked]
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>