Thursday, October 15, 2015

Backing up your master password and secret sharing

I created a tool implementing a cryptographic secret sharing algorithm, which I use for backing up my master password. The tool is at:

Here's the motivation and how it works:

Let's say you use a password manager to remember your passwords, and the password manager requires a master password. If you forget the master password, you loose access to the other passwords. So how do you backup your master password?

One possibility is giving your master password to trusted people such as family members. A problem with that approach is that one of the people you share it with might accidentally reveal it, post it on the internet, leave the piece of paper on which it is written somewhere a malicious person can see it, etc.

Another possibility is to write your password down, tear it in half and give each half to a trusted person. Then any single person doesn't know the entire password, so if they reveal it, your password still is not entirely revealed. However, if someone malicious sees one half of the password, it makes it much easier to guess the other half. Another problem with this approach is that if either of the two people loose the slip of paper, then you can no longer reconstruct your master password.

Enter Shamir's scheme for secret sharing, based on an old but neat paper. It shows how to divide a secret into a number of "shares" such that one share provides no information about the secret, and any two shares are sufficient to reconstruct the secret. It actually generalizes to any number of minimum shares, but we'll use the version that requires a minimum of two shares to reconstruct the secret.

The idea is that a line is defined by two points. Knowing one point does not help determine the slope or intercept of the line. Knowing two points is enough to determine both. So in Shamir's scheme each point is a share and the line slope or intercept is the secret. The equation for a line in 2D is: y = ax + b.

The tool I created uses this as follows. The user types in a secret. The tool generates a long (128-bit) random number for both of a and b (i.e., the slope and intercept of a line). The slope (parameter a) will be the encryption key used to encrypt the secret. Each share contains the coordinates of one distinct point along the line. Thus knowing one share doesn't tell you anything about the encryption key, and with two shares, it is straight-forward to figure out the slope and then decrypt to recover the secret.

The tool encrypts the secret with AES-128 using the 128-bit random key. Shares are represented in base-64. I took all the easy-to-generate characters on the keyboard, threw away a few confusing ones (such as o, O, l, and .), and that left 64. I could shrink the alphabet down to something like hex, but then the length of the shares would become longer.

The math to manipulate the shares and the secret key is done using a finite field based on the prime 2^128-159. Another note, I also threw in a few bits/bytes of checksum, both into the encrypted secret as well as the shares, to detect mistypes.

Feel free to browse the javascript source code of the tool, it is not minified. It uses the crypto routines in the Forge (client-side javascript library). It does not send any information over the network, except for Google analytics, though feel free to verify that for yourself. I'm happy to provide more details.

Lastly, anything crypto-related is notoriously difficult to get right, including this tool. Please use with care, and it'd be great to have another pair of eyes on the javascript source code if anyone cares to browse!