1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
|
Return-Path: <fireduck@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id A8ACBA49
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 3 Dec 2018 20:54:23 +0000 (UTC)
Received: by mail-ua1-f52.google.com with SMTP id j3so4958206uap.3
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <CABsxsG234DhY8Lxn0UMgXG0YnPdyJ5__U9P-aweV9L=xw7hxyw@mail.gmail.com>
In-Reply-To: <CABsxsG234DhY8Lxn0UMgXG0YnPdyJ5__U9P-aweV9L=xw7hxyw@mail.gmail.com>
From: =?UTF-8?B?Sm9zZXBoIEdsZWFzb24g4pGI?= <fireduck@gmail.com>
Date: Mon, 3 Dec 2018 12:54:10 -0800
Message-ID: <CA+ASnrGEbksc-YeKR7bKpAv5=rcWcg8BeR6XDVUzvJ9C76bGpA@mail.gmail.com>
To: shatzakis@gmail.com,
slurms--- via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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
<div dir=3D"ltr">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.<div><br></div><div>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.</div></div><br><div class=3D"gmail_quote"><div dir=
=3D"ltr">On Mon, Dec 3, 2018 at 10:45 AM Steven Hatzakis via bitcoin-dev &l=
t;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@list=
s.linuxfoundation.org</a>> wrote:<br></div><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex=
"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div =
class=3D"gmail_default"><p style=3D"font-family:-apple-system,system-ui,&qu=
ot;Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji",=
"Segoe UI Emoji","Segoe UI Symbol";box-sizing:border-bo=
x;margin-bottom:16px;color:rgb(36,41,46);font-size:14px;margin-top:0px">Hi =
All,=C2=A0</p><p style=3D"font-family:-apple-system,system-ui,"Segoe U=
I",Helvetica,Arial,sans-serif,"Apple Color Emoji","Sego=
e UI Emoji","Segoe UI Symbol";box-sizing:border-box;margin-b=
ottom:16px;color:rgb(36,41,46);font-size:14px;margin-top:0px">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."</p><p style=3D"font-family:-apple-system=
,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Colo=
r Emoji","Segoe UI Emoji","Segoe UI Symbol";box-si=
zing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-=
size:14px"><span style=3D"box-sizing:border-box;font-weight:600">Purpose:</=
span><br style=3D"box-sizing:border-box">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.</p><p style=3D"font-family:-apple-=
system,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Appl=
e Color Emoji","Segoe UI Emoji","Segoe UI Symbol";=
box-sizing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46)=
;font-size:14px"><span style=3D"box-sizing:border-box;font-weight:600">Secu=
rity:</span><br style=3D"box-sizing:border-box">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^<span style=3D"box-sizing:border-box">12=
4 for 12 words, that search must still be conducted over a field of 2</span=
><span style=3D"box-sizing:border-box;font-weight:600">^</span>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.</p><p style=3D"font-family:-apple-system,system-ui,"=
Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji",&qu=
ot;Segoe UI Emoji","Segoe UI Symbol";box-sizing:border-box;m=
argin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-size:14px">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</p>Example 12 words =
reversible (with valid checksum each way): <br><br>limit exact seven clarif=
y utility road image fresh leg cabbage hint canoe<br><br>And Reversed:<br><=
br>canoe hint cabbage leg fresh image road utility clarify seven exact limi=
t<br><br><br>Example 24 reversible:<br><br>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</div><div class=3D"gmail_defaul=
t"><br>And reversed:</div><div class=3D"gmail_default"><br>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<p class=3D"m_67=
11322012586516752gmail-p1" style=3D"margin:0px;font-variant-numeric:normal;=
font-variant-east-asian:normal;font-stretch:normal;font-size:11px;line-heig=
ht:normal;font-family:Menlo;color:rgb(0,0,0)"><span class=3D"m_671132201258=
6516752gmail-s1" style=3D"font-variant-ligatures:no-common-ligatures"><br><=
/span></p><p style=3D"box-sizing:border-box;margin-bottom:16px;margin-top:0=
px"><span style=3D"color:rgb(36,41,46);font-family:-apple-system,system-ui,=
"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji&quo=
t;,"Segoe UI Emoji","Segoe UI Symbol";font-size:14px">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?</span><br></p><p style=3D"box-sizing:border-box;margin-bott=
om:16px;margin-top:0px"><span style=3D"font-family:arial,helvetica,sans-ser=
if;font-size:12.8px">Best regards,</span></p></div><div><div dir=3D"ltr" cl=
ass=3D"m_6711322012586516752gmail_signature"><div dir=3D"ltr"><div dir=3D"l=
tr"><div style=3D"font-size:12.8px;font-family:arial,helvetica,sans-serif">=
<span><br>Steven</span>=C2=A0<span>Hatzakis</span>=C2=A0</div><div style=3D=
"font-size:12.8px;font-family:arial,helvetica,sans-serif"><span class=3D"gm=
ail_default" style=3D"font-family:arial,helvetica,sans-serif"> </span></div=
></div></div></div></div></div></div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
--0000000000008085a9057c245a42--
|
