Erik Aronesty [ARCHIVE] on Nostr: 📅 Original date posted:2022-07-11 📝 Original message:Sorry, I totally forgot ...
📅 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>;
📝 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>;