Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id A8ACBA49 for ; Mon, 3 Dec 2018 20:54:24 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua1-f52.google.com (mail-ua1-f52.google.com [209.85.222.52]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C3C72853 for ; Mon, 3 Dec 2018 20:54:23 +0000 (UTC) Received: by mail-ua1-f52.google.com with SMTP id j3so4958206uap.3 for ; Mon, 03 Dec 2018 12:54:23 -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; bh=0nzG6+otp6+hBAxBlVmvwPeZhJIgI9oFlOwwmXLdhVc=; b=P4O2/u1FhLBUC9qh9NZ9doj4FjFPHLhyyq0fNhAy50xgWDii1mFd0jVpo2THj/e1rH 3SdHArPh7jd/Wcm8NuQfB84I1oV6w4VmuosIxawfSgY6kDB50/BRDhhYHcFlESm+IyLH 5Idb7ouM/x6JJMGyU4kxn5O60KL0j6ub7vhd3LPvjs+Cz4sX1i2WKuIGbLvxHgRZlv9X pFPUSgRhVgkKQID0HejY5oIfR9FUpAlWlPbqvfWYsvlE5km8r+q/CEs2Zz5Nxtw+4jcl k7YHwX0SzHj8gYBlfsMs4FZJk9rL+0gPiikcEajBY8LFtGmMcZRH8Byuy1XDNrDnhGWc OPfw== 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; bh=0nzG6+otp6+hBAxBlVmvwPeZhJIgI9oFlOwwmXLdhVc=; b=BPAxr0TFe/Z3XlhvPuWmviMR9UFhsbsmKmfzioD+VVHe/PlBXGcZdENElTlaSn0ERT 0bEcvlRlZ8jf37eWDB/zOkFTp0YWhduBuUsYeww7eT241oK38QMEPgGImtJDEgg9mn1m km/nfIyXbV3lfqEsVAZjBwhD63El57hGNpqFUvfNIGF/0q7RFAm4Ib8ETnJ2K6GALueq XgNeWvdXOTRYtbtgujsQkaSZfz9S1G8SJaaH0yJkfNz63WFCkH7aPEzYWqEsBVoVS3X1 C1cj1VLNbmzA/00n4wyuKM+LR8sCPxbQ/LyIJWc/0yzMZresL5SQPci3GSbpiIkd9od/ gIxw== X-Gm-Message-State: AA+aEWZnoJycfmY3RyJ0MZDuABO2YO3IXeuhyVcYGJcDHQ1XxbgWUenn bn0RWMgOX32KCVBNK/8nVkXCemlfCe4lttQFd3g= X-Google-Smtp-Source: AFSGD/W6jxRW3Lkezx1VGluX/sA7+R+n4A4dK7Nvp29GmngSLvAaZkL7tglKM1rJojP13B4uxly66vy5HLWkHEmjDdE= X-Received: by 2002:ab0:234a:: with SMTP id h10mr7347707uao.71.1543870462590; Mon, 03 Dec 2018 12:54:22 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: =?UTF-8?B?Sm9zZXBoIEdsZWFzb24g4pGI?= Date: Mon, 3 Dec 2018 12:54:10 -0800 Message-ID: To: shatzakis@gmail.com, slurms--- via bitcoin-dev Content-Type: multipart/alternative; boundary="0000000000008085a9057c245a42" X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, FROM_EXCESS_BASE64, 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: Mon, 03 Dec 2018 20:59:39 +0000 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: Mon, 03 Dec 2018 20:54:24 -0000 --0000000000008085a9057c245a42 Content-Type: text/plain; charset="UTF-8" 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 > --0000000000008085a9057c245a42 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I have a suggestion.=C2=A0 If you are concerned about plau= sible deniability, then it might make sense to just have the single mnemoni= c seed lead to a single xprv key (as usual) and then do a private key deriv= ation from that based on a password string.=C2=A0 The password can be simpl= e, as it is based on the security of the seed, just as long as the user fee= ls they need for deniability.

A simple reverse scheme li= ke 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 &l= t;bitcoin-dev@list= s.linuxfoundation.org> wrote:

Hi = All,=C2=A0

I've deve= loped 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 mnemon= ic allows two separate vaults to be connected to the same mnemonic string o= f 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 acce= ss the secondary (reversed words) vault. This utility could provide multipl= e use-cases, including related to combinations with passphrases and plausib= le deniability, as well as conveniences for those wishing to use a separate= vault tied to the same string of words.

Secu= rity:
For any randomly generated = 12-word mnemonic (128-bits of security) the chances of it also being revers= ible 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 strin= g 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 vali= d reversible mnemonics should be 2^12= 4 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 f= ind valid reversible mnemonics without first going through invalid reversib= le ones to check. I think others should chime in on whether they believe th= ere is any security loss, in terms of entropy bits (assuming the initial 12= 8 bits were generated securely). I estimate at most it would be 4-bits of l= oss for a 12-word mnemonic, but only if an attacker had a way to search onl= y 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 assum= ptions, this is a work in progress and sharing it here to solicit initial f= eedback/interest.

I'= ve already written the code that can be used for testing (on GitHub user @h= atgit), 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 minu= tes to find a valid 24-word reversible mnemonic.=C2=A0

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

limit exact seven clarif= y utility road image fresh leg cabbage hint canoe

And Reversed:
<= br>canoe hint cabbage leg fresh image road utility clarify seven exact limi= t


Example 24 reversible:

favorite uncover sugar wealth ar= my shift goose fury market toe message remain direct arrow duck afraid enro= ll salt knife school duck sunny grunt argue

And reversed:

argue grunt sunn= y duck school knife salt enroll afraid duck arrow direct remain message toe= market fury goose shift army wealth sugar uncover favorite


<= /span>

M= y 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 neg= ligible or not?

Best regards,

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