Splitting Secrets

December 20 2022
Home | Blog | Prev | Next
Public Domain · vim(1) No Babies

Secret splitting is splitting a secret, such as a password, into N shares such that recovering the secret requires combining m ≤ N of those N shares. It's a technique to ensure that no single person can unilaterally access the secret without other people's consent. It's the cryptographic equivalent of requiring multiple people to simultaneously turn keys in order to launch nuclear missiles.

There are a few widely-used secret splitting techniques, such as Shamir's secret sharing, but they invariably require computers because they operate on large numbers. This page introduces techniques that you can do by hand.

Why You Might Want to Split Secrets

Secret splitting is uncommon, but you could use it in a few situations:

  1. You want to write a password down (say, a master password for a password manager), but you don't want to write it plainly so that anyone can read it. So you decide to split it between yourself and your friends or family. But you don't trust any of them with the whole password. The following techniques can help you securely split your password and share the parts with your friends and family.
  2. You want to share some secret with your heirs, but you don't want them to know it until you die. If you use the following techniques to split the password into multiple shares, you can give the shares to your heirs and keep one for yourself (or put it in a secure location that your heirs can only access upon your death). Revealing the secret requires your heirs to retrieve your share and cooperate with each other.
  3. You have a business secret (say, a secret formula) that you want to record, but you don't trust anyone with the whole secret. By using the following techniques, you can split the secret into multiple shares and distribute them to, say, your business's board members. Recovering the secret requires all board members (all people with shares of the secret) to cooperate.

Naive Secret Sharing: Chunks

How could you split a password into N pieces such that all N pieces are required to recover it? Here's a naive solution:

  1. Break the password into N chunks of roughly equal length. Number each chunk in the order it appears in the password: the first chunk is 1, the second is 2, and so on. Each chunk is a share.
  2. Securely distribute the shares to their intended recipients.
  3. Reassemble all of the shares in the correct order to recover the password.

For example, if the password is

yummybunssleepstoneleafcord

splitting it into 3 chunks might look like this:

  1. yummybuns
  2. sleepstone
  3. leafcord

Reassembling the pieces in the correct order (1, 2, and 3) reconstructs the original password.

This solution has advantages:

  1. It's simple. Splitting and reassembly are easy.
  2. No math is required.
  3. The password's length is hidden.

However, there are significant drawbacks:

  1. Each share is readable. Collecting more shares reveals more information about the secret. An ideal scheme would completely hide the secret until all shares are gathered and combined.
  2. You cannot use this scheme if you want to be able to reconstruct the secret with fewer than N shares. (Use Shamir's secret sharing.)
  3. A malicious person could lie about his share to deceive others into giving him their shares. The malicious person could reassemble the secret, but the other shareholders would be left with nothing.

A Better Solution

A better solution is based on one-time pad encryption.

Splitting

To split a secret into N shares:

  1. Convert the secret into a sequence of decimal digits using a translation table. (See the CT-37c translation table on this website for an example. Note: The translation table doesn't have to be secret.) Let D be the number of decimal digits the translated secret has.
  2. Write the translated secret's D decimal digits on a sheet of scratch paper.
  3. Do the following for N-1 of the shares:
    1. Roll a 10-sided die D times and write the results. (If the die is labeled 1-10, subtract 1 from each roll.) The resulting D-digit number is a share.
    2. Write the share's D digits underneath the translated secret's D digits.
    When you're done, you should have written N-1 rows of D digits. Their digits should be aligned underneath the translated secret's D digits, forming a D×N grid.
  4. Compute the final share by doing the following:
    1. For each of the D digits in the translated secret, subtract all of the share digits lined up underneath it, modulo 10.
    2. The resulting D-digit number is the final share.
  5. Burn the original secret and any scratch paper you used.
  6. Securely distribute the translation table and the shares to their intended recipients.

For example, suppose your (very bad!) password is

a12345

and you want to split it into 3 shares. Suppose your translation table converts this password into these decimal digits:

298512345

Write this on a piece of scratch paper. There are D=9 digits. To generate the first share (step (3) above), roll a 10-sided die 9 times and write the numbers underneath the password's digits:

   298512345
1: 877130125

To generate the second share, roll the 10-sided die 9 more times and write the numbers underneath the first share:

   298512345
1: 877130125
2: 612357962

Finally, to compute the third and last share, read the password's digits left-to-right. For each digit, subtract all of the digits underneath it, modulo 10, and write the result under the second share:

   298512345
1: 877130125
2: 612357962
------------
3: 819135368

The three shares are 877130125, 612357962, and 819135368. Distribute these to their intended recipients securely and burn the scratch paper.

Reassembly

Anyone who has all N shares and the (non-secret) translation table can recover the original secret:

  1. Write the N shares on a piece of scratch paper. The order of the shares doesn't matter: The first share doesn't have to come first. Line their digits up vertically. This should form a D×N grid of digits.
  2. For each column of digits, add the digits in that column, modulo 10, and write the result underneath that column.
  3. The resulting row of D digits is the original secret. Convert the D digits back into readable language using the splitter's translation table. (See the CT-37c translation table on this website for an example.)

For example, suppose you acquire all three shares from the splitting example above. Write them on a sheet of paper, aligning their digits:

3: 819135368
1: 877130125
2: 612357962

In this case, the third share came first. The order doesn't matter. (Retry this example with different orders to see for yourself. Why doesn't the order matter?) Sum each column's digits modulo 10 and write the results below them:

3: 819135368
1: 877130125
2: 612357962
------------
   298512345

298512345 is the original secret. Using the same translation table as before, translate the digits into the original password:

a12345

Advantages

  1. Unlike the naive scheme, individual shares reveal no information other than the secret's maximum length. A malicious person cannot recover any piece of the original secret without all the shares.
  2. The math is simple. A grade schooler could do it.

Disadvantages

  1. This secure scheme requires lots of random numbers.
  2. Each share reveals the secret's maximum length.
  3. Knowing the same part of each share reveals that part of the secret. For example, if someone recovers the first five digits of each share, he can recover the first five digits of the secret. However, whether this is a weakness or a strength is debatable: Recovery is limited to the known parts of the shares.
  4. You cannot use this scheme if you want to be able to reconstruct secrets with fewer than N shares. (Use Shamir's secret sharing.)
  5. A malicious person could still lie about his share to trick others into revealing theirs.

Why It Works

The first N-1 shares are one-time pad keys — completely random. Adding their columns of digits together modulo 10 effectively forms a single one-time pad key. When you subtract it from the secret, you form a one-time-pad-encrypted ciphertext, which is the final share.

Reassembling the secret reverses this process. Adding the first N-1 shares' columns of digits together modulo 10 recreates the one-time pad key; combining the result with the final share — the ciphertext — decrypts the ciphertext into the original secret.

Without all of the N-1 random shares, you cannot reconstruct the one-time pad key. And without the final share (the ciphertext), you cannot recover the secret. Therefore, recovering the secret requires all N shares.