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