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.

wget http://point-at-infinity.org/ssss/ssss-0.5.tar.gz
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
make

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
encrypted-backup-key-1-a10ed337cc73ea186d8d23c0df395b0aad8a7b01cae866eb5ea48d7767787cc55a0e41aa1ea4189f761f75cd2047f9a4c686b1a665a6af3ea2c5361fe48f1354ad9de19b4ea1ab6e6a84033274b862eca667c1700a91661e9a28267dd7687e3ed4798479f1e5c621662caac06027066df84a4d3477d2d9730b8c6f9e0f6a8ab6
encrypted-backup-key-2-e1f1f289f1d152191144d5ddb6f8c588582a665a28a869103eddeda8fd066e56811c63b6259c71732dfceceaafb924f4e3790a862f82a293d64a7286fb00296fa3ef195a76d9d8aa91eeff5f679ba5458b84a8b823ea9a840acd36064f32b1b89dea519e2cb149359524735351cd676359f474beee2ecb7a7aafe45a5d2606f4
encrypted-backup-key-3-fdd3c734308ed001a06dd57cfb4e7810f3f3a853446e8a62323d7fe75c83e9d812bb6139ece18537be4a7104667b355b8ffe07e0ff78fe4ad4ffbff9aa5be670e5d3fa3f9f66a2a2f30d2383b62ac0bbe51c7f1a216fa2356cdfd775942d7249c404e05c012bddfc9ff548721b81ee270f6360c301463ad5f7545195b30024b8
encrypted-backup-key-4-457ad2ea649ad65bda6779ab42f4e209017efacf19d7c8817488b595da68e6aaa823e1beb05ce1d07c6ccd37e9c88b9376ed4347450a8379cd13dd52e2866908ccb1607679cf96436bf16cb8cdb1f8a1702fd72f398816b91552a883b36ecc1fad661a99dad8ca5e084f8a812f11b6213e95aecbf26a6e5a73fcdc0751e775d1
encrypted-backup-key-5-c98f78d6472ea4d434736448bb71aa6e8696a58c1329278070ee89aa53cd721c8778f8b2d3ef7507610c3f1d4dce71f6b3febb2ac8e5c543d91c0854ab393c5d019d765fde02662203cb619ffe13647aa0e16708022880e94529f6af0b96b1a6dd5f99924a2c15cd09fd989e26353fe16ca9c80fe99ee0a9d1d3ca3202a7a0f7
encrypted-backup-key-6-a8df666bbf5bfdfbf6c0a8d0bad7df122b559a433d19309d019ab59599f346fe2592eda9bd4bddcc274379b219b97b33c528ea1c38ebfd2880e77c3f857f32f319ce64067a9f0134ed123e0529175198f1aec1ca591821b1b91f986a540302b0c76229e6eda40c6dec331371910f5fe7c44114f6995a0c18ff5906032a2ec222

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.

 

 


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 | Reply to this comment ]

Posted by Steve (62.30.xx.xx) on Fri 15 Sep 2006 at 16:16
[ View Steve's Scratchpad | View Weblogs ]

It is given in the text!

Resulting secret: MyExampleSecret

Steve

[ Parent | Reply to this comment ]

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 | Reply to this comment ]

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 | Reply to this comment ]

Posted by kecsi (195.56.xx.xx) on Mon 18 Sep 2006 at 10:13
Uhum getting closer. Thank you!

[ Parent | Reply to this comment ]

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 | Reply to this comment ]

Sign In

Username:

Password:

[Register|Advanced]

 

Flattr

 

Current Poll

What do you use for configuration management?








( 487 votes ~ 5 comments )