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
|
Return-Path: <shatzakis@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 2CBD5868
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 3 Dec 2018 18:28:06 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qk1-f170.google.com (mail-qk1-f170.google.com
[209.85.222.170])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 66575834
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 3 Dec 2018 18:28:05 +0000 (UTC)
Received: by mail-qk1-f170.google.com with SMTP id r71so7951047qkr.10
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 03 Dec 2018 10:28:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=qYAwNrhXK77rEKna1BaM/S5zDwmTbpM1xW0stFACKnI=;
b=bmksbyJTI7OQoQrog/0G28ufmUeeKPOvrZHlv1ucb68tc6BS3g9/PSAdKCWjlrBBKo
OwhOtqPOUi5UWKpRIra/08PNGwogp7PHU2nLYTfyzZHhqGu4mxg1AovXZ4DLkfbvjv7P
5gm6YhcGrLN1D048FEcfZ8MMN/kRFjDZKb0xo1kCicWvYQpPsPb4VDpXS0sQ61k0UfxE
jqhuTW45zAN2XsXcwLfhkells1QgDfEhowiUM0z37I0QeOqop2rrpszejPwJlNy7FBKt
a/4l1I9gG2J8uLVvAxnevrMY8SbhQF9FfkdjWtzIzAZRak0EFl6WvtahTYgj6Au6Vmdb
SVow==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=qYAwNrhXK77rEKna1BaM/S5zDwmTbpM1xW0stFACKnI=;
b=FCbJs+r811rZ+4MHd9ngMUOJzMofznn/35KjvB5m+WSPK+piBTPAQAF/ROse+gcu0k
N6mwBuQpcoiHFTsnL3fBYRb4QiZ9CtiqI/I6p7VJo7DuXh7JLLIvug4O3d12WxNifB2E
iVcGz3Q26grcEbdkglPC93Iv1Q8ia8jw10rv26f1/PqAblYgsRffIIo1exhHIym3AvSq
DoZOCkU3dqI7jcla8SYIso9f/foVbzsuKRD36ehY06meH1amuBIHmVwkDZrowahCUBIj
9Pdgq1Bcm7S4Lbq8CluJcKvPVAfemUXrBeLfrE/Ctculpw/5MrmI56ckiuen0hcpJ7pJ
jTqA==
X-Gm-Message-State: AA+aEWY9Ax5VXGUeD4kOCCkRwYKA1wUANXsVS/lC/lBaD0gC+vppMKzf
5bSJ+LrzwaknFQMaNM7VjmY4AYJ22gq9K1O4Sxys7dTbUC4=
X-Google-Smtp-Source: AFSGD/Vul4Oj51uEPb0XAZfnc6hY7V6rI2/naYqLxBcaWlE5Qs925hJi/p8MXDp8aDVzISzmV6vRrcqa28PTPSdWpS4=
X-Received: by 2002:ae9:e102:: with SMTP id g2mr14948797qkm.343.1543861684250;
Mon, 03 Dec 2018 10:28:04 -0800 (PST)
MIME-Version: 1.0
From: Steven Hatzakis <shatzakis@gmail.com>
Date: Mon, 3 Dec 2018 20:27:52 +0200
Message-ID: <CABsxsG234DhY8Lxn0UMgXG0YnPdyJ5__U9P-aweV9L=xw7hxyw@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="00000000000045ae78057c224fa3"
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: Mon, 03 Dec 2018 18:44:44 +0000
Subject: [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 18:28:06 -0000
--00000000000045ae78057c224fa3
Content-Type: text/plain; charset="UTF-8"
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
--00000000000045ae78057c224fa3
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div cl=
ass=3D"gmail_default"><p style=3D"font-family:-apple-system,system-ui,"=
;Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji",&q=
uot;Segoe UI Emoji","Segoe UI Symbol";box-sizing:border-box;=
margin-bottom:16px;color:rgb(36,41,46);font-size:14px;margin-top:0px">Hi Al=
l,=C2=A0</p><p style=3D"font-family:-apple-system,system-ui,"Segoe UI&=
quot;,Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe =
UI Emoji","Segoe UI Symbol";box-sizing:border-box;margin-bot=
tom:16px;color:rgb(36,41,46);font-size:14px;margin-top:0px">I've develo=
ped a method to check if a mnemonic is also valid when the words are put in=
to reverse order (not the entropy), where a given 12 or 24-word mnemonic co=
uld be valid both in little endian and big endian format. I've coined t=
hese "Palindromic Mnemonics", but perhaps more user-friendly is &=
quot;reversible mnemonics."</p><p style=3D"font-family:-apple-system,s=
ystem-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color =
Emoji","Segoe UI Emoji","Segoe UI Symbol";box-sizi=
ng:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);font-si=
ze:14px"><span style=3D"box-sizing:border-box;font-weight:600">Purpose:</sp=
an><br style=3D"box-sizing:border-box">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 l=
ast 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 v=
ault tied to the same string of words.</p><p style=3D"font-family:-apple-sy=
stem,system-ui,"Segoe UI",Helvetica,Arial,sans-serif,"Apple =
Color Emoji","Segoe UI Emoji","Segoe UI Symbol";bo=
x-sizing:border-box;margin-bottom:16px;margin-top:0px;color:rgb(36,41,46);f=
ont-size:14px"><span style=3D"box-sizing:border-box;font-weight:600">Securi=
ty:</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 reversib=
le 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,=C2=A0those values increase to 8 bits w=
hich need to match 8 bits from the reversed string, leading to about 1 in e=
very 256 mnemonics also being reversible. While the message space of valid =
reversible mnemonics should be 2^<span style=3D"box-sizing:border-box">124 =
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 ha=
sh-derived checksum values otherwise prevent a way to deterministically fin=
d valid reversible mnemonics without first going through invalid reversible=
ones to check. I think others should chime in on whether they believe ther=
e 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 los=
s 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 assumpt=
ions, this is a work in progress and sharing it here to solicit initial fee=
dback/interest.</p><p style=3D"font-family:-apple-system,system-ui,"Se=
goe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","=
;Segoe UI Emoji","Segoe UI Symbol";box-sizing:border-box;mar=
gin-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 @hat=
git), 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-b=
it machine it could take a few seconds for 12 words and sometimes 10 minute=
s to find a valid 24-word reversible mnemonic.=C2=A0</p>Example 12 words re=
versible (with valid checksum each way): <br><br>limit exact seven clarify =
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 limit<=
br><br><br>Example 24 reversible:<br><br>favorite uncover sugar wealth army=
shift goose fury market toe message remain direct arrow duck afraid enroll=
salt knife school duck sunny grunt argue</div><div class=3D"gmail_default"=
><br>And reversed:</div><div class=3D"gmail_default"><br>argue grunt sunny =
duck school knife salt enroll afraid duck arrow direct remain message toe m=
arket fury goose shift army wealth sugar uncover favorite<p class=3D"gmail-=
p1" style=3D"margin:0px;font-variant-numeric:normal;font-variant-east-asian=
:normal;font-stretch:normal;font-size:11px;line-height:normal;font-family:M=
enlo;color:rgb(0,0,0)"><span class=3D"gmail-s1" style=3D"font-variant-ligat=
ures:no-common-ligatures"><br></span></p><p style=3D"box-sizing:border-box;=
margin-bottom:16px;margin-top:0px"><span style=3D"color:rgb(36,41,46);font-=
family:-apple-system,system-ui,"Segoe UI",Helvetica,Arial,sans-se=
rif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI=
Symbol";font-size:14px">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?</span><br></p><p style=3D"bo=
x-sizing:border-box;margin-bottom:16px;margin-top:0px"><span style=3D"font-=
family:arial,helvetica,sans-serif;font-size:12.8px">Best regards,</span></p=
></div><div><div dir=3D"ltr" class=3D"gmail_signature"><div dir=3D"ltr"><di=
v dir=3D"ltr"><div style=3D"font-size:12.8px;font-family:arial,helvetica,sa=
ns-serif"><span><br>Steven</span>=C2=A0<span>Hatzakis</span>=C2=A0</div><di=
v style=3D"font-size:12.8px;font-family:arial,helvetica,sans-serif"><span c=
lass=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif"> </=
span></div></div></div></div></div></div></div></div></div>
--00000000000045ae78057c224fa3--
|
