From: "'Rama Gan' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases
Date: Tue, 14 May 2024 12:43:07 +0000 [thread overview]
Message-ID: <9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM=@proton.me> (raw)
In-Reply-To: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
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.
prev parent reply other threads:[~2024-05-14 13:00 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-05-12 18:04 'Rama Gan' via Bitcoin Development Mailing List
2024-05-13 13:40 ` Andrew Poelstra
2024-05-14 12:03 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-14 13:42 ` Andrew Poelstra
2024-05-16 7:43 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-16 13:27 ` Andrew Poelstra
2024-05-16 17:24 ` Andrew Poelstra
2024-05-24 10:39 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-24 14:14 ` Andrew Poelstra
2024-05-24 15:02 ` 'Rama Gan' via Bitcoin Development Mailing List
2024-05-14 12:43 ` 'Rama Gan' via Bitcoin Development Mailing List [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM=@proton.me' \
--to=bitcoindev@googlegroups.com \
--cc=ganrama@proton$(echo .)me \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox