This site is now 100% read-only, and retired.

Interested in securely sharing a secret?

Posted by JacobAppelbaum on Fri 15 Sep 2006 at 08:14

I needed a method for sharing a secret that required multiple agents to coordinate before the secret could be recovered. This is useful for encrypting keys used in critical backups. I decided to use an implementation of Shamir's Secret Splitting Scheme (The S in RSA).

Currently I'm using a program called 'ssss' to do secret sharing.

There is a Debian package in unstable and testing.

sudo apt-get install ssss

It's simply to compile if you can't use the Debian package. The source package currently lacks an install target for make, you'll have to install by hand or patch the makefile.

sha1sum ssss-0.5.tar.gz
tar -xzvf ssss-0.5.tar.gz
cd ssss-0.5/
sudo apt-get install xmltoman libgmp3-dev libgmp3

Here is an article on the background of secret splitting with a (k, n) threshold scheme:

The secret being shared in this example could be a static key to an encrypted disk image.

Here's how we generated the split keys (this step can take a while):

ssss-split -t 4 -n 6 -w encrypted-backup-key -s 1024

Each line is a single key for distribution to the parties involved. This example means that we need four out of six people to give their keys over before we'll be able to decrypt the shared secret.

Here's how we'd recover the key with any four of the total six keys:

ssss-combine -t 4
Enter 4 shares separated by newlines:
Share [1/4]: 2-e1f1f289f1d152191144d5ddb6f8c588582a665a28a869103eddeda8fd066e56811c63b6259c71732dfceceaafb924f4e3790a862f82a293d64a7286fb00296fa3ef195a76d9d8aa91eeff5f679ba5458b84a8b823ea9a840acd36064f32b1b89dea519e2cb149359524735351cd676359f474beee2ecb7a7aafe45a5d2606f4
Share [2/4]: 5-c98f78d6472ea4d434736448bb71aa6e8696a58c1329278070ee89aa53cd721c8778f8b2d3ef7507610c3f1d4dce71f6b3febb2ac8e5c543d91c0854ab393c5d019d765fde02662203cb619ffe13647aa0e16708022880e94529f6af0b96b1a6dd5f99924a2c15cd09fd989e26353fe16ca9c80fe99ee0a9d1d3ca3202a7a0f7
Share [3/4]: 3-fdd3c734308ed001a06dd57cfb4e7810f3f3a853446e8a62323d7fe75c83e9d812bb6139ece18537be4a7104667b355b8ffe07e0ff78fe4ad4ffbff9aa5be670e5d3fa3f9f66a2a2f30d2383b62ac0bbe51c7f1a216fa2356cdfd775942d7249c404e05c012bddfc9ff548721b81ee270f6360c301463ad5f7545195b30024b8
Share [4/4]: 1-a10ed337cc73ea186d8d23c0df395b0aad8a7b01cae866eb5ea48d7767787cc55a0e41aa1ea4189f761f75cd2047f9a4c686b1a665a6af3ea2c5361fe48f1354ad9de19b4ea1ab6e6a84033274b862eca667c1700a91661e9a28267dd7687e3ed4798479f1e5c621662caac06027066df84a4d3477d2d9730b8c6f9e0f6a8ab6
Resulting secret: MyExampleSecret

Note that we stripped off the unique token of 'encrypted-backup-key-' and left the proceeding number. If we hadn't we'd get an error that looks like:

FATAL: invalid syntax.

Any 4 of the 6 keys may be combined to decrypt and reveal the secret. That secret is the password to the encrypted disk image that all parties involved have.

So what's a practical example that you can use?

Let's say that you have 6 system administrators on your site. Let's say that all 6 administrators have GPG keys. Let's also say you'd like to secure your backups.

Each night your system runs backups and encrypts them with a randomly generated secret. (I'll leave this process up to you). You could easily take the output of ssss encrypt each key from the resulting split to a different administrator and then email the encrypted data to each administrator.

To recover the backup key for last night, it would require that you entered the correct number of keys from threshold you specified when invoking ssss or another program like it.



Re: Interested in securely sharing a secret?
Posted by Anonymous (200.61.xx.xx) on Fri 15 Sep 2006 at 15:13
Great!, now of course, I read all the article but couldn't find the secret, when will you tell us about it? ;-)

[ Parent ]

Re: Interested in securely sharing a secret?
Posted by Steve (62.30.xx.xx) on Fri 15 Sep 2006 at 16:16
[ View Weblogs ]

It is given in the text!

Resulting secret: MyExampleSecret


[ Parent ]

Re: Interested in securely sharing a secret?
Posted by kecsi (195.56.xx.xx) on Mon 18 Sep 2006 at 09:23
I simple use gpg for securing backup files.
I cant see why this util is better.

[ Parent ]

Re: Interested in securely sharing a secret?
Posted by JacobAppelbaum (64.142.xx.xx) on Mon 18 Sep 2006 at 09:33
[ View Weblogs ]
You can use this tool with gpg. If you encrypt the larger data files with gpg, you may want to store the passphrase in a way that's more secure than just writing it down on a notepad. This allows you to do this. ssss not intended for splitting up large files to distribute between multiple parties.

[ Parent ]

Re: Interested in securely sharing a secret?
Posted by kecsi (195.56.xx.xx) on Mon 18 Sep 2006 at 10:13
Uhum getting closer. Thank you!

[ Parent ]

Re: Interested in securely sharing a secret?
Posted by Anonymous (121.44.xx.xx) on Sat 7 Oct 2006 at 07:46
Trying to accomplish needing any 4 out of 6 individuals to decrypt the backups is quite messy in gpg in comparision to ssss.

If you can't imagine a scenario where wanting t out of n shares available to reveal some secret is useful, then you sir have no imagination!

[ Parent ]