summaryrefslogtreecommitdiff
path: root/5d/6b4afde7d03c42bb9e3bab3824f34a678c2558
blob: 093e780187635aeeab457a6f0d4b010b70061124 (plain)
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
Return-Path: <keatonatron@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id E90CBC002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  9 Jul 2022 22:21:44 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id CAE12419DE
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  9 Jul 2022 22:21:44 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org CAE12419DE
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=YlVSBWYu
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 9t2ei0KqJ1iU
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  9 Jul 2022 22:21:43 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 865334188A
Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com
 [IPv6:2607:f8b0:4864:20::102e])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 865334188A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  9 Jul 2022 22:21:43 +0000 (UTC)
Received: by mail-pj1-x102e.google.com with SMTP id
 t5-20020a17090a6a0500b001ef965b262eso1754041pjj.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 09 Jul 2022 15:21:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=+3VbEgVtF2X30KkT1WbIMpMVuLkOmqbXlJtApLiX+xA=;
 b=YlVSBWYuEIa7aXRYwIp78vQbry1uGK2A8abIbiJbhMxRAcfFUQFpj9IUzD1pVtmf/y
 gQdWX1XmmSnZqTJUPlxj7r0H2kG+gNVRJC4QIblvC2EnijuuCWpkGZNLSSLAqxXsTKrP
 xTjyWH2EImFQPRQ3NbEO3E+/PU5Y531Nb5mmKFC+XP3GS0YMq3RGlLTxh/ngxC4cCyg1
 /Jye49lNhz9FYg79fzqYB+c9ChukFcXAsdocZEYXn7q5FqEfaqtsJGXSoOEPN0wkLriv
 X/Mge9y0mwdetyZECzIEg/uOvEqZs63r4zLWPqsAhI9CMOiSiJAd9uS+l3nNc6/RbzM2
 WgzA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=+3VbEgVtF2X30KkT1WbIMpMVuLkOmqbXlJtApLiX+xA=;
 b=Trs45gnkZLNuz4X6xijtvEbwaryNgOOBPU3TQtA+5vbk/jn9Qq//BG0LS7PuUt0wda
 JuMXpHoJmDSMbOnWUkRMFXvpufCGIcLfoaRIGpSP+xSyUgKZhtq8H8ag7rxuwai3maEG
 Bt7LWg0PeGozVEFAx5IJmr2w9isaaQ5IfAfwiMYtnk2fQyvpb2dXUr/d9KTrZhamhjDf
 +uOSsgHRhDvWR2VV3v+JbbdPOaDx8t0qRrcZHibZnrBNMnuzM4d93KSmeVP4poKpQQiC
 SpKDxstE2YwnFXWIgKX43ezSw1ssutgdLIEIhE9yjaXrWpbml5ryPsKankX/DKmVolfS
 ippA==
X-Gm-Message-State: AJIora/arO1897y0JCX+fJySeIBWAM01EnBVZQk6KO8w/pSN/1S1cGJy
 b/sunGD/byl2Yfqfs5X29hJfLszSQ2sC8yxioOsg/5lLRJhdzw==
X-Google-Smtp-Source: AGRyM1scFMMoIG8XC52Jl40cjifuTBVQ1IoHu7cvk2W9Mr252bFsVQi30fzRfWldBzTOj3vImijy3gqbfCUZOLU0QPE=
X-Received: by 2002:a17:903:183:b0:16a:5c43:9a9c with SMTP id
 z3-20020a170903018300b0016a5c439a9cmr10521536plg.153.1657405302650; Sat, 09
 Jul 2022 15:21:42 -0700 (PDT)
MIME-Version: 1.0
References: <3D3BFE9C-CFF3-49FF-840F-063B52C69A42@voskuil.org>
 <164256450-0ee6752f92c0be297952fc72b59076df@pmq5v.m5r2.onet>
 <CA+XQW1iKVRmEnyP-CGM2Fo4qHi3SQHUfjEmKftDdju-uxHViJg@mail.gmail.com>
 <CAH+Axy4X+uQG5Vw0Efiz6AtNyK=++h-jDeZL1ZxpVJus8BVKeA@mail.gmail.com>
 <CAJ4-pEA7WJpbExcsgdPWVNuZLrbDDhVYr37g6_6NSf7t41eB4w@mail.gmail.com>
In-Reply-To: <CAJ4-pEA7WJpbExcsgdPWVNuZLrbDDhVYr37g6_6NSf7t41eB4w@mail.gmail.com>
From: James MacWhyte <macwhyte@gmail.com>
Date: Sun, 10 Jul 2022 00:21:16 +0200
Message-ID: <CAH+Axy7bgRgHKZD4hsfVsnUrNooa2kvxwNUhzycmG-MahAgnUQ@mail.gmail.com>
To: Zac Greenwood <zachgrw@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000503cb105e366bef7"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] No Order Mnemonic
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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: Sat, 09 Jul 2022 22:21:45 -0000

--000000000000503cb105e366bef7
Content-Type: text/plain; charset="UTF-8"

Thanks, Zac!

I indeed did get the napkin math very wrong. I now get around 10^30 total
possible phrases, which would take an impossibly long time to brute force.
So, it is less entropy but probably still sufficient for low-stakes usage.

James


On Sat, Jul 9, 2022 at 10:31 PM Zac Greenwood <zachgrw@gmail.com> wrote:

> Sorting a seed alphabetically reduces entropy by ~29 bits.
>
> A 12-word seed has (12, 12) permutations or 479 million, which is ln(469m)
> / ln(2) ~= 29 bits of entropy. Sorting removes this entropy entirely,
> reducing the seed entropy from 128 to 99 bits.
>
> Zac
>
>
> On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>>
>> What do you do if the "first" word (of 12), happens to be the last word
>>> in the list alphabetically?
>>>
>>
>> That couldn't happen. If one word is the very last from the wordlist, it
>> would end up at the end of your mnemonic once you rearrange your 12 words
>> alphabetically.
>>
>> However!
>>
>> (@vjudeu) Choosing 11 random words and then sorting them alphabetically
>> before assigning a checksum would reduce entropy considerably. If you think
>> about it, to bruteforce the entire keyspace one would only need to come up
>> with every possible combination of 11 words + 1 checksum. I'm not the best
>> at napkin math, but I think that leaves you with around 10 trillion
>> combinations, which would only take a couple months to exhaust with
>> hardware that can do 1 million guesses per second.
>>
>>
>> James
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

--000000000000503cb105e366bef7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Thanks, Zac!<br><br>I indeed did get the napkin math very =
wrong. I now get around 10^30 total possible phrases, which would take an i=
mpossibly long time to brute force. So, it is less entropy but probably sti=
ll sufficient for low-stakes usage.<div><br clear=3D"all"><div><div dir=3D"=
ltr" class=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=
=3D"ltr"><div>James<br></div></div></div></div><br></div></div><br><div cla=
ss=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, Jul 9, 202=
2 at 10:31 PM Zac Greenwood &lt;<a href=3D"mailto:zachgrw@gmail.com">zachgr=
w@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div dir=3D"auto">Sorting a seed alphabetically reduces entropy =
by ~29 bits.</div><div dir=3D"auto"><br></div><div dir=3D"auto">A 12-word s=
eed has (12, 12) permutations or 479 million, which is ln(469m) / ln(2) ~=
=3D 29 bits of entropy. Sorting removes this entropy entirely, reducing the=
 seed entropy from 128 to 99 bits.</div><div dir=3D"auto"><br></div><div di=
r=3D"auto">Zac</div><div><br><div class=3D"gmail_quote"><div dir=3D"ltr" cl=
ass=3D"gmail_attr"><br></div><div dir=3D"ltr" class=3D"gmail_attr">On Fri, =
8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev &lt;<a href=3D"mailto:b=
itcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.l=
inuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote=
" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);=
padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><br></div><div class=3D=
"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px=
 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D=
"auto">What do you do if the &quot;first&quot; word (of 12), happens to be =
the last word in the list alphabetically?</div></blockquote><div><br></div>=
<div>That couldn&#39;t happen. If one word is the very last from the wordli=
st, it would end up at the end of your mnemonic=C2=A0once you rearrange you=
r 12 words alphabetically.<br><br>However!=C2=A0</div><div><br>(@vjudeu) Ch=
oosing 11 random words and then sorting them alphabetically before assignin=
g=C2=A0a checksum would reduce entropy considerably. If you think about it,=
 to bruteforce the entire keyspace one would only need to come up with ever=
y possible combination of 11 words=C2=A0+ 1 checksum. I&#39;m not the best =
at napkin math, but I think that leaves you with around=C2=A010 trillion co=
mbinations, which would only take a couple months to exhaust with hardware =
that can do 1 million guesses per second.</div></div></div><div dir=3D"ltr"=
><div class=3D"gmail_quote"><div><br></div><div><br></div><div>James</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></div>
</blockquote></div>

--000000000000503cb105e366bef7--