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
|
Delivery-date: Tue, 14 May 2024 06:00:23 -0700
Received: from mail-yb1-f183.google.com ([209.85.219.183])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBAABBXGARWZAMGQE2KPQBKI@googlegroups.com>)
id 1s6rlW-0001ZY-Kv
for bitcoindev@gnusha.org; Tue, 14 May 2024 06:00:23 -0700
Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-dc64f63d768sf9981252276.2
for <bitcoindev@gnusha.org>; Tue, 14 May 2024 06:00:22 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1715691616; cv=pass;
d=google.com; s=arc-20160816;
b=B0h0ltfu4oYwtime3NBheT1Q6fnJgzZHpJ0rv+7b93nKIjt95AkLoW+3cNONggyvGI
FsAuoAxpV1uVYlc0ZWgmyO0Cgm6PhtoBmhqNZRxEs3WFZBDj73sq0bIyMp9v7epBuHhx
jOs3kFZ0u8gMPvwBtbdxfcURcH4jZGTcskhMifsDUJaV1SBSG32sdoaNGqGTZS+y4SKa
DnGGND/HCUe4ix8IL8yaME6XIPOS3BrfAMn62BXlkxAeeZZovD+nHepoKGqyz/KRkuZ6
OQ04Uu1ke3mHgGCb3s5mPL+aEQ0oAoEdAtBxwflbROMis9q+oKh3GdK/Pm4d+0CgPPeP
mr3A==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to:mime-version:feedback-id
:references:in-reply-to:message-id:subject:from:to:date
:dkim-signature;
bh=16/+D33cE0+D+GoWmvfphL3Kg8uv8xAZCe3wLEw8kTQ=;
fh=OG+0LkxynbjXrLkI+eXtkGsF4ZVjXfPHGNNcHmX6OyQ=;
b=J7RcXRIQonZ6OoMYTdM2QnQAGL2h3TilKzl34BbaoT4hYc/Hc8GmT2UxQn1lKHH8AB
4oKcRJmtLbegWYyIkLJPqz2QYX8yxYkmmzBGyvWxG+LX+qqtfrlpmxDmsrvvYs853ZDb
pO9hfdaMs6zEcP/MxmsJz1ZuTgdNFKMatSOYjzBVB/pTWOVDargH64Tf72P+Ut1Mk/JJ
uSAggBYYTjngy+KgXv77Ocx2Evemji+W3Lz5YyUnZR/c+d6ou4HhI78EXfv0KzE2Tnqk
rhAP3re6pEEZvkdC+IlXpiXCZ76LD1yLt7x1+liY4JnmfMYA7mgDOUvsxy8mntub/BCw
NJjQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@proton.me header.s=protonmail header.b=g4Swy9nN;
spf=pass (google.com: domain of ganrama@proton.me designates 185.70.40.137 as permitted sender) smtp.mailfrom=ganrama@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1715691616; x=1716296416; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to
:x-original-authentication-results:x-original-sender:mime-version
:feedback-id:references:in-reply-to:message-id:subject:from:to:date
:from:to:cc:subject:date:message-id:reply-to;
bh=16/+D33cE0+D+GoWmvfphL3Kg8uv8xAZCe3wLEw8kTQ=;
b=VGbWZvTzJVqWr/yWmOUK6pktVRNrl9aNqAj7zNZ9CMGx9pwJzhF8t3ik5A3cImOvEY
SOcURkSnGFICKNA6C90xYugCKW5ITIfj078/rQNl8c/keh0RNvufbO0zw4LRoxl724Rh
BZFNgAGsf4udRyOYGXvMeYSYPR3TQxobufC3FwCSGHhk1uf405ApLyefw/kq+3Wxsy7n
H6avQ+ig+CIZeUtyyahUQ7uZNRLKuv1D+gdpdpK1ANHRiDn/fBsA8l3h297dYoO4iLWo
1hSDwy3kJOulnXjE6dK+HcMrCLePs/e/LqFFKKjVwKncGboXLLJCrA+DcvZAuwiu9QOv
xSMA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1715691616; x=1716296416;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to
:x-original-authentication-results:x-original-sender:mime-version
:feedback-id:references:in-reply-to:message-id:subject:from:to:date
:x-beenthere:x-gm-message-state:from:to:cc:subject:date:message-id
:reply-to;
bh=16/+D33cE0+D+GoWmvfphL3Kg8uv8xAZCe3wLEw8kTQ=;
b=EzVT7WX++G4vGUlWllOGD7TweQT5EyzgLT4QfYx6ogPfHBawxbBLw3Pvo1EalNYlly
EhNRhpRhIukzFuEqynCZpJ410mfJd/l8m4z0Q8+bQvwOqkB+pIPNq9+IRK1fBD2kMFnP
tjnI2ErCwNhzJqRFMkWOSNj+iyizRHOQMxc61FH7hhbmb9W9sVuTgOJvH4bPGdEeBiDT
aarW+qK8HoZbJ0JDut+Wczz2rpq61ArqyeLOL7QD+grOyhpgOcyKorH8uw5AqWt/jy5q
Y5lWQrb1zJL02jgg1HiZRYH9vpWClyshfOiKGRZeNJbX9tDdiwlU9kU3uxS5pd/NvFgn
dG4Q==
X-Forwarded-Encrypted: i=2; AJvYcCVNrtXRXxh/vA3jMkZPqeiekcWYWBub52fEpzobjztZHGA8/1rm88VRX+xoEAv1QcpGPo0xkQlkkaGBjefWfbLrbbQkf40=
X-Gm-Message-State: AOJu0Yx3e3zRBgVtBnTIWK6mbUR7DpQ2i6B62zSvsABLJAEilaobaive
nID6/y0VLgZeCwe4WzBpKaJ0lEl87MNHW1pyniwI60L2pWTU8zNl
X-Google-Smtp-Source: AGHT+IH83SLC7HcXYllBDvah+DXvFvOfRGvB+4Na41LRACoX7ngbPK0CEBeib/EdI4UZzlR5TyKtGw==
X-Received: by 2002:a25:7492:0:b0:dee:994c:38c4 with SMTP id 3f1490d57ef6-dee994c3b7cmr3898275276.58.1715691614160;
Tue, 14 May 2024 06:00:14 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6214:4118:b0:6a0:d3ef:2b80 with SMTP id
6a1803df08f44-6a15d4457d5ls72439796d6.1.-pod-prod-07-us; Tue, 14 May 2024
06:00:12 -0700 (PDT)
X-Received: by 2002:a05:6214:250d:b0:6a0:a98a:481b with SMTP id 6a1803df08f44-6a1681f2194mr8883276d6.9.1715691612021;
Tue, 14 May 2024 06:00:12 -0700 (PDT)
Received: by 2002:a05:620a:190f:b0:790:ee24:5a3f with SMTP id af79cd13be357-792bcb6ec4ems85a;
Tue, 14 May 2024 05:43:12 -0700 (PDT)
X-Received: by 2002:a05:651c:19a6:b0:2d9:f00c:d2d5 with SMTP id 38308e7fff4ca-2e52039e2d3mr87753601fa.46.1715690591003;
Tue, 14 May 2024 05:43:11 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1715690590; cv=none;
d=google.com; s=arc-20160816;
b=QsDg4EJGETp2T4ZQpMPa9u32FEdtXOcoE7cFmhhmxsd3vXovNCcvSUqwNHBOQK6Lc8
qQvEXlmzecUDPv/+hP3nkiIs92M1saOUQP4FapY+5HHvULg0FLjAiyDIYYtEyPrQ18yX
VFwgjouHxdJB5OEHgA5AM7C4+UbwqndY0+RPBI26mKUgJWaHhbGziujZ804dmYN349Qd
rKI0GRsJVQx4ZtNsIjhID8Q/h57qdORO8UEwK3eo6uC/b6utj14mPTsjSxy8TjqYenbj
0xrwTqgrJkR4WKIEGtLgPkJdaS5TjIr+V9gBpCVvVmirHhSBMEA7eKTFaCYIdvU/V9MD
01Hg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=content-transfer-encoding:mime-version:feedback-id:references
:in-reply-to:message-id:subject:from:to:date:dkim-signature;
bh=tx1GykxQd6ohLoj06xC8ZIYKm5ZcQYh/6NxMYAJDyo0=;
fh=lhFSo2W/mHC0QoJ9oNg3A35n0DTltt3CQl1/0RggJlk=;
b=ErujlwraHmjGo/YhAULK60cGQUuGTjCA7ZQgHbtmjjb8/7PNPM8GCJXk9FdJmVTBOC
UM0xSKfIrS5yD5dU+xwc3u344N7dEwaoGFrZ+1Tvj6F3+za6sSvTvPGVjDJ+GMrHD0JY
tAFsMDMlStnlhH0GMNqwr3mxCRHxlDe0N7MFAdDAk6ktWS6Tb4GUz7NBB5JM+GZIbBlI
gs8GkLhj1oAG1jIaX1xlFdQQjRzuwmTCLPpF0ciFYGRrP5TG9o67EjEXUMICtg2USD/K
BAzv6abneSxYCjXKy/ryp5Fp8hQGltgc7Y7urq9b99VCToCB0GFCimL9Znw5Pa1BTI7R
79xQ==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@proton.me header.s=protonmail header.b=g4Swy9nN;
spf=pass (google.com: domain of ganrama@proton.me designates 185.70.40.137 as permitted sender) smtp.mailfrom=ganrama@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
Received: from mail-40137.protonmail.ch (mail-40137.protonmail.ch. [185.70.40.137])
by gmr-mx.google.com with ESMTPS id 38308e7fff4ca-2e6eb0f7cc8si88081fa.0.2024.05.14.05.43.10
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Tue, 14 May 2024 05:43:10 -0700 (PDT)
Received-SPF: pass (google.com: domain of ganrama@proton.me designates 185.70.40.137 as permitted sender) client-ip=185.70.40.137;
Date: Tue, 14 May 2024 12:43:07 +0000
To: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
From: "'Rama Gan' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39
seed phrases
Message-ID: <9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM=@proton.me>
In-Reply-To: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
Feedback-ID: 79991369:user:proton
X-Pm-Message-ID: 169ce271e080070ad3dac6b1aa57e4ec75281f66
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Original-Sender: ganrama@proton.me
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@proton.me header.s=protonmail header.b=g4Swy9nN; spf=pass
(google.com: domain of ganrama@proton.me designates 185.70.40.137 as
permitted sender) smtp.mailfrom=ganrama@proton.me; dmarc=pass
(p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
X-Original-From: Rama Gan <ganrama@proton.me>
Reply-To: Rama Gan <ganrama@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -1.0 (-)
In this message I'm going to briefly describe the cryptographic components of
Penlock.
I won't cover Shamir Secret Sharing here, as it is a well-known algorithm. Note
that A. Poelstra and R. O'Connor previously explained its implementation on
paper-computer, as well as other shenanigans, in codex32's mathematical
companion: https://secretcodex32.com/docs/2023-08-23--math.pdf.
## Overview
Penlock uses a composite secret splitting algorithm: 2-of-M splitting is
implemented with a "paper-friendly" algorithm, whilst for (K>2)-of-M it falls
back to Shamir Secret Sharing. In both cases, GF(29) is used (i.e.: all
arithmetic operations are modulo 29). Using GF(Prime) allows for optimizations
in the paper implementation that were not possible with fields in the form
GF(2^N).
## Character Set
Penlock uses a character set composed of the 26 Latin characters and the symbols
`-`, `=` and `+`. Each character represents a corresponding integer, that I will
write between square brackets in this document; for example: =[0], +[1], A[2],
Z[27], -[28].
## 2-of-M Splitting
The concept behind the 2-of-M algorithm is relatively simple: it encodes a
secret as the difference between two consecutive shares. For example, let's
split "B[3]" into 3 shares:
1. Pick a random character for Share A: say G[8]
2. Derive Share B by subtracting the secret from Share A: G[8] - B[3] = D[5]
3. Derive Share C by subtracting the secret from Share B: D[5] - B[3] = A[2]
We get: ShareA = G[8], ShareB = D[5], ShareC = A[2]
Note that each of the shares taken separately is merely a random number and
doesn't contain any information about the secret.
The secret can be recovered by computing the difference between two shares,
divided by the distance between these shares. For example, let's recover the
previous secret from shares A and C:
```
Secret = (ShareA - ShareC) / distance(ShareA, ShareC)
= (G[8] - A[2]) / 2
= E[6] / 2
= B[3]
```
In this example we did split only one character, but a complete phrase will be
split similarly by splitting its characters one after another.
Cryptographers might recognize that algorithm as a variation of Shamir Secret
Sharing. To summarize, Shamir's 2-of-M encodes the secret at a specific x of
`f(x) = ax + b`, while Penlock's 2-of-M encodes it as the `a` in
`f(x) = -ax + b` (Share A being `b`).
## Checksum
Additionally, Penlock uses a simple checksum that guarantees error-free
results despite potential manipulation errors. For any given piece of data, the
checksum will be composed of the differences between each two consecutive
characters. For example:
```
Data : C[04] O[16] I[10] N[15]
Checksum: Q[18] K[12] V[23] D[05]
Because : O[16] - C[04] = K[12]
I[10] - O[16] = V[23] (-6 % 29)
N[15] - I[10] = D[05]
C[04] - N[15] = Q[18] (-11 % 29)
```
This checksum has been specifically designed for Penlock needs. It is great at
detecting and locating errors, but unless bech32 it is bad at repairing missing
data. This trade-off seems acceptable because secret splitting already provides
data redundancy (i.e.: if one share gets damaged, it is possible to fix it using
the two other shares).
## Implementation
The arithmetic operations used for 2-of-M splitting and checksumming are
implemented within a single wheel that can be printed from
https://beta.penlock.io/2ofm-wheel.html. The outer rings of the wheel implement
the addition and the subtraction, and the spiral in the middle implements the
division.
A step-by-step guide for computing the checksum shown above, but with the wheel,
can be found in the example of "Generating the Checksums" at
https://beta.penlock.io/2of3-guide.html.
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM%3D%40proton.me.
|
