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 [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39 seed phrases '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 List2024-05-14 12:43 ` 'Rama Gan' via Bitcoin Development Mailing List [this message]

Be sure your reply has aReply 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-toswitches of git-send-email(1): git send-email \ --in-reply-to='9580J-OlDrkh-JivYUV3ziFhpJ8o5FbZhYz0U0sYL7_wPcy5y3EeRRKNKaPYPOh11A2QZgNNeo3QaOnP3OaMXamWjaY1YjXQiQ9EVEEI7NM=@proton.me' \ --to=bitcoindev@googlegroups.com \ --cc=ganrama@proton.me \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting theIn-Reply-Toheader via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox