Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 386EA892 for ; Tue, 4 Dec 2018 12:42:56 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-qt1-f176.google.com (mail-qt1-f176.google.com [209.85.160.176]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1BB7A14D for ; Tue, 4 Dec 2018 12:42:55 +0000 (UTC) Received: by mail-qt1-f176.google.com with SMTP id t13so17805002qtn.3 for ; Tue, 04 Dec 2018 04:42:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=CuEVbVDr5An4IpiwbznpOb/03kirODOMTeuSiy9RfQM=; b=W3p/GC30bEGLHiHz7gg36bV1ZRiJL3g6DYDJIrb0kviHIdMsZ6pTXfmRsPT3e4UhcD G4RiMdSLAaH9EeQEqbbpBqzv7PWbZcWQaCgzKlhgg+1lgW4vaftlmehluTLHuJedZiwt 4anb0wHUkUE9pLn5NlAslUOlz0/jsxuz2jQ66Q3nQp/bPt//mhk3M0GPZcFtsK7BbwAr PRu8IEnkH0jUpnbqzjQG9DTKjTQoxAkONiTVUCOddpZLpUr10Z4gguO4QXpf6ZIHV7UM OQMWY9XVn0No9OR8B036eIA8e31lrLsHoOteXsMpeO7XETMRZNV6DbBNlwS1QxqQSvEH VMOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=CuEVbVDr5An4IpiwbznpOb/03kirODOMTeuSiy9RfQM=; b=CP9z7LjOxzPwrairTbtWkqpbp8TcxNwjuStIENIcEohAU6U9Hm1OorOZMCQH5SQT2M yrvrzpGgWyddEN1t8GCtNKREvHjqD7c8ujZCvcja/ZFbInsRORzoxGMfRB63A0lCEkDd r3/iCBvfjxt998zX8TkUodgkkS1o0Rtljw+AvTWDDvIoiy7dqDCZffPmqAqM5n9fjDTM 4oT3K6E0W7Fj5Zj0PoNuTU5T9E7trchR67XIvP7F8ZkECSdYaQA0dVz0cz4TGF+XozWi 0Rish0YEw5xsYB0uhAlM2j7So8ZEwtfBq37IGQbRgL1uv+WoAdw9q/a38HC08RzEQaP7 6r/w== X-Gm-Message-State: AA+aEWbrPt05eNH/8NwhEH3rXcfhaLbFcNv+JaRCEIjcsPiY1mv1HIF4 WnyjfKO7hdexnuVMy9weaPuZcvnwi6kTn8BQyFI= X-Google-Smtp-Source: AFSGD/UsepRzApZiOLYNL3W2V5Xg0dBvkoHtJ9cBOXUuJ/gdeZx4/4WhlssUPdIoq+tpTFv78L/bbD4fCTyiYGjJ3VA= X-Received: by 2002:ad4:410c:: with SMTP id i12mr19413265qvp.219.1543927373988; Tue, 04 Dec 2018 04:42:53 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Steven Hatzakis Date: Tue, 4 Dec 2018 14:42:42 +0200 Message-ID: To: macwhyte@gmail.com Content-Type: multipart/alternative; boundary="000000000000af88c3057c319a4b" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Tue, 04 Dec 2018 13:09:02 +0000 Cc: bitcoin-dev@lists.linuxfoundation.org Subject: Re: [bitcoin-dev] Proposal for Palindromic (Reversible) Mnemonics X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 04 Dec 2018 12:42:56 -0000 --000000000000af88c3057c319a4b Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 wrote: > I agree with Joseph. If you want plausible deniability, it would be bette= r > 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 usef= ul > 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 =E2=91=88 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 tha= t >> 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, secon= d 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 fr= om >>> the reversed string, leading to about 1 in every 256 mnemonics also bei= ng >>> reversible. While the message space of valid reversible mnemonics shoul= d 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 i= n on >>> whether they believe there is any security loss, in terms of entropy bi= ts >>> (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 attac= ker >>> had a way to search only the space of valid reversible mnemonics (2**12= 4) >>> 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 f= ast >>> 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 sometim= es >>> 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 can= oe >>> >>> And Reversed: >>> >>> canoe hint cabbage leg fresh image road utility clarify seven exact lim= it >>> >>> >>> 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 gru= nt >>> argue >>> >>> And reversed: >>> >>> argue grunt sunny duck school knife salt enroll afraid duck arrow direc= t >>> 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 >> > --000000000000af88c3057c319a4b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks, James and Joseph, for the feedback,
It = has been a fun experiment!=C2=A0

I just want to no= te that the plausible deniability was not the motive but just an example us= e-case, there are perhaps other use-cases that would be on the user to deci= de. I think having a mnemonic that is also reversible could be useful for o= ther reasons - convenience related perhaps.=C2=A0
Re security: I am still not convinced entirely that security is reduced at all becaus= e one still has to search through all entropy in the range of=C2=A02^128 to= see whether any of those are reversible (unless there is a way to only sea= rch the field of 2^124 that are reversible, which I don't think is poss= ible because the hash-derived checksum=C2=A0cannot be determined before has= hing, only afterward). Therefore, security should still be 2^128 for a 12-w= ord mnemonic whether it is reversible or=C2=A0not (as one in every 16 peopl= e that already have one (12-word) is reversible, they just might not realiz= e it, so we can't say those are less secure).=C2=A0

<= div>
Best regards,
<= /div>

On Tue, Dec 4, 2018 at 2:16 PM James MacWhyte <macwhyte@gmail.com> wrote:
I agree with Joseph. If you want plausible d= eniability, 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= 9;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 li= ke a very useful feature to have.

Thanks for doing all t= hat 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 =E2=91=88 via bitcoin-dev <bitcoin-dev@lists.l= inuxfoundation.org> wrote:
<= div dir=3D"ltr">I have a suggestion.=C2=A0 If you are concerned about plaus= ible 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 deriva= tion from that based on a password string.=C2=A0 The password can be simple= , as it is based on the security of the seed, just as long as the user feel= s they need for deniability.

A simple reverse scheme lik= e 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 <<= a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">b= itcoin-dev@lists.linuxfoundation.org> wrote:

Hi All,=C2= =A0

I've developed a= method to check if a mnemonic is also valid when the words are put into re= verse order (not the entropy), where a given 12 or 24-word mnemonic could b= e 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 allo= ws 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 w= ord becomes first, second to last becomes second, and so on) to access the = secondary (reversed words) vault. This utility could provide multiple use-c= ases, including related to combinations with passphrases and plausible deni= ability, 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 ar= e 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,=C2=A0those 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 rever= sible mnemonics should be 2^124 for 1= 2 words, that search must still be conducted over a field of 2^128, as the hash-de= rived checksum values otherwise prevent a way to deterministically find val= id 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 s= pace of valid reversible mnemonics (2**124) which I don't think is feas= ible (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 alre= ady 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 vali= d reversible mnemonics, whereas on IDLE in Python on a 32-bit and 64-bit ma= chine it could take a few seconds for 12 words and sometimes 10 minutes to = find a valid 24-word reversible mnemonic.=C2=A0

Example 12 words reversi= ble (with valid checksum each way):

limit exact seven clarify utili= ty road image fresh leg cabbage hint canoe

And Reversed:

cano= e hint cabbage leg fresh image road utility clarify seven exact limit

Example 24 reversible:

favorite uncover sugar wealth army shif= t 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 direc= t remain message toe market fury goose shift army wealth sugar uncover favo= rite


My two questions 1) are how useful could this b= e for you/users/devs/service providers etc.. and 2) is any security loss oc= curring and whether it is negligible or not?

Best regards,

<= /div>
=

Steven=C2=A0Hatzakis=C2=A0
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000af88c3057c319a4b--