Re: [bitcoin-dev] Proposal for Palindromic (Reversible) Mnemonics

From: Steven Hatzakis <shatzakis@gmail•com>
To: macwhyte@gmail•com
Cc: bitcoin-dev@lists•linuxfoundation.org
Subject: Re: [bitcoin-dev] Proposal for Palindromic (Reversible) Mnemonics
Date: Tue, 4 Dec 2018 14:42:42 +0200	[thread overview]
Message-ID: <CABsxsG2qBVA-imReWJci4JA=S0MhVMq9+ezyMF7SEw7Hqqa-gQ@mail.gmail.com> (raw)
In-Reply-To: <CAH+Axy4=8SyRL5W9Av_6dDOp43Qd+Cdkf2XZnpf1i6zCT4Pemg@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 6586 bytes --]

Thanks, James and Joseph, for the feedback,
It has been a fun experiment!

I just want to note that the plausible deniability was not the motive but
just an example use-case, there are perhaps other use-cases that would be
on the user to decide. I think having a mnemonic that is also reversible
could be useful for other reasons - convenience related perhaps.
*Re security:* I am still not convinced entirely that security is reduced
at all because one still has to search through all entropy in the range
of 2^128 to see whether any of those are reversible (unless there is a way
to only search the field of 2^124 that are reversible, which I don't think
is possible because the hash-derived checksum cannot be determined before
hashing, only afterward). Therefore, security should still be 2^128 for a
12-word mnemonic whether it is reversible or not (as one in every 16 people
that already have one (12-word) is reversible, they just might not realize
it, so we can't say those are less secure).

Best regards,

On Tue, Dec 4, 2018 at 2:16 PM James MacWhyte <macwhyte@gmail•com> wrote:

> I agree with Joseph. If you want plausible deniability, it would be better
> to simply hide the funds somewhere in the HD chain. Same if you want a
> second vault tied to the same phrase.
>
> You are reducing security by eliminating all entropy that doesn't fit the
> reversible criteria, although in practice it doesn't make a difference
> because the numbers are so big. However, it doesn't seem like a very useful
> feature to have.
>
> Thanks for doing all that work though, it was fun to read about your idea
> and what you found out through experimenting!
>
> James
>
>
> On Mon, Dec 3, 2018 at 1:00 PM Joseph Gleason ⑈ via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> I have a suggestion.  If you are concerned about plausible deniability,
>> then it might make sense to just have the single mnemonic seed lead to a
>> single xprv key (as usual) and then do a private key derivation from that
>> based on a password string.  The password can be simple, as it is based on
>> the security of the seed, just as long as the user feels they need for
>> deniability.
>>
>> A simple reverse scheme like you describe would just be another thing a
>> person would know to check if given some seed so I don't see it as
>> providing much value, but I could be missing something.
>>
>> On Mon, Dec 3, 2018 at 10:45 AM Steven Hatzakis via bitcoin-dev <
>> bitcoin-dev@lists•linuxfoundation.org> wrote:
>>
>>> Hi All,
>>>
>>> I've developed a method to check if a mnemonic is also valid when the
>>> words are put into reverse order (not the entropy), where a given 12 or
>>> 24-word mnemonic could be valid both in little endian and big endian
>>> format. I've coined these "Palindromic Mnemonics", but perhaps more
>>> user-friendly is "reversible mnemonics."
>>>
>>> Purpose:
>>> A checksum-valid reversible mnemonic allows two separate vaults to be
>>> connected to the same mnemonic string of words, where all a users must do
>>> is enter the words in reverse order (the last word becomes first, second to
>>> last becomes second, and so on) to access the secondary (reversed words)
>>> vault. This utility could provide multiple use-cases, including related to
>>> combinations with passphrases and plausible deniability, as well as
>>> conveniences for those wishing to use a separate vault tied to the same
>>> string of words.
>>>
>>> Security:
>>> For any randomly generated 12-word mnemonic (128-bits of security) the
>>> chances of it also being reversible are 1/16 (I believe), as a total of 4
>>> bit positions must be identical (4 bits from the normal mnemonic and
>>> another 4 bits from the reversed string must match). For a 24-word
>>> mnemonic, those values increase to 8 bits which need to match 8 bits from
>>> the reversed string, leading to about 1 in every 256 mnemonics also being
>>> reversible. While the message space of valid reversible mnemonics should be
>>> 2^124 for 12 words, that search must still be conducted over a field of
>>> 2^128, as the hash-derived checksum values otherwise prevent a way to
>>> deterministically find valid reversible mnemonics without first going
>>> through invalid reversible ones to check. I think others should chime in on
>>> whether they believe there is any security loss, in terms of entropy bits
>>> (assuming the initial 128 bits were generated securely). I estimate at most
>>> it would be 4-bits of loss for a 12-word mnemonic, but only if an attacker
>>> had a way to search only the space of valid reversible mnemonics (2**124)
>>> which I don't think is feasible (could be wrong?). There could also be
>>> errors in my above assumptions, this is a work in progress and sharing it
>>> here to solicit initial feedback/interest.
>>>
>>> I've already written the code that can be used for testing (on GitHub
>>> user @hatgit), and when run from terminal/command prompt it is pretty fast
>>> to find a valid reversible mnemonics, whereas on IDLE in Python on a 32-bit
>>> and 64-bit machine it could take a few seconds for 12 words and sometimes
>>> 10 minutes to find a valid 24-word reversible mnemonic.
>>> Example 12 words reversible (with valid checksum each way):
>>>
>>> limit exact seven clarify utility road image fresh leg cabbage hint canoe
>>>
>>> And Reversed:
>>>
>>> canoe hint cabbage leg fresh image road utility clarify seven exact limit
>>>
>>>
>>> Example 24 reversible:
>>>
>>> favorite uncover sugar wealth army shift goose fury market toe message
>>> remain direct arrow duck afraid enroll salt knife school duck sunny grunt
>>> argue
>>>
>>> And reversed:
>>>
>>> argue grunt sunny duck school knife salt enroll afraid duck arrow direct
>>> remain message toe market fury goose shift army wealth sugar uncover
>>> favorite
>>>
>>>
>>> My two questions 1) are how useful could this be for
>>> you/users/devs/service providers etc.. and 2) is any security loss
>>> occurring and whether it is negligible or not?
>>>
>>> Best regards,
>>>
>>> Steven Hatzakis
>>> _______________________________________________
>>> 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
>>
>

[-- Attachment #2: Type: text/html, Size: 11391 bytes --]