📅 Original date posted:2022-07-11
📝 Original message: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 at 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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220711/de802042/attachment-0001.html>;
Erik Aronesty [ARCHIVE] /
npub1y2…5taj0
2023-06-07 23:11:18
in reply to nevent1q…glqj
Author Public Key
npub1y22yec0znyzw8qndy5qn5c2wgejkj0k9zsqra7kvrd6cd6896z4qm5taj0Published at
2023-06-07 23:11:18Event JSON
{
"id": "26e21268ccfbe7d62f3e5045d8a063c5f45fa12234021e244fd4334ab16b9e48",
"pubkey": "22944ce1e29904e3826d25013a614e4665693ec514003efacc1b7586e8e5d0aa",
"created_at": 1686179478,
"kind": 1,
"tags": [
[
"e",
"eac87b4c91a108febb37fcfdedf34b8ebc91e557769313850338d8ae3e1c4c99",
"",
"root"
],
[
"e",
"5f2d245e4789c25a9a5f4a42d3acb6a91876b7f2f969edf296dc09d954a01457",
"",
"reply"
],
[
"p",
"845fcd294cd02e515ce70ee633f6eca61a6bea1fe447705e9e60a0381ee7066e"
]
],
"content": "📅 Original date posted:2022-07-11\n📝 Original message:1. You can swap two positions, and then your recovery algorithm can\nbrute-force the result by trying all 132 possible swaps.\n2. You can make a single deletion and only have to brute 2048\n3. You can keep doing these, being aware that it becomes geometrically more\ndifficult each time (deletion + swap = 270k ops)\n4. A home PC can make 20k secpk256 operations per second per core, so try\nto keep your number under a few million ops and it's still a decent UX\n(under a minute)\n\n\nOn Sat, Jul 9, 2022 at 8:01 PM Anton Shevchenko via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e I would say removing ordering from 12-word seed reduces 25 bits of\n\u003e entropy, not 29. Additional 4 bits come from checksum (12 words encode 132\n\u003e bits, not 128).\n\u003e\n\u003e My idea [for developing this project] was to feed its output to some kind\n\u003e of AI story generator (GPT-3 based?) so a user can remember a story, not\n\u003e ordered words. But as others pointed out, having 12 words without order is\n\u003e probably good enough. So at this point there's not much sense of using the\n\u003e proposed encoding. Unless a remembered story has wholes/errors. In this\n\u003e case recovering few words would be easier with unordered encoding. Any\n\u003e thoughts?\n\u003e\n\u003e -- Anton Shevchenko\n\u003e\n\u003e\n\u003e On Sat, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-dev wrote:\n\u003e\n\u003e Sorting a seed alphabetically reduces entropy by ~29 bits.\n\u003e\n\u003e A 12-word seed has (12, 12) permutations or 479 million, which is ln(469m)\n\u003e / ln(2) ~= 29 bits of entropy. Sorting removes this entropy entirely,\n\u003e reducing the seed entropy from 128 to 99 bits.\n\u003e\n\u003e Zac\n\u003e\n\u003e\n\u003e On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\n\u003e What do you do if the \"first\" word (of 12), happens to be the last word in\n\u003e the list alphabetically?\n\u003e\n\u003e\n\u003e That couldn't happen. If one word is the very last from the wordlist, it\n\u003e would end up at the end of your mnemonic once you rearrange your 12 words\n\u003e alphabetically.\n\u003e\n\u003e However!\n\u003e\n\u003e (@vjudeu) Choosing 11 random words and then sorting them alphabetically\n\u003e before assigning a checksum would reduce entropy considerably. If you think\n\u003e about it, to bruteforce the entire keyspace one would only need to come up\n\u003e with every possible combination of 11 words + 1 checksum. I'm not the best\n\u003e at napkin math, but I think that leaves you with around 10 trillion\n\u003e combinations, which would only take a couple months to exhaust with\n\u003e hardware that can do 1 million guesses per second.\n\u003e\n\u003e\n\u003e James\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220711/de802042/attachment-0001.html\u003e",
"sig": "1d4f4c2c0fcd2821afe7494d486612047408da05e28ab9ac3cd968055e6284f22280763a96617ce5089f98103d227d505f7f47ae0ff00de754982d5d61590c49"
}