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