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.
This article can be found online at the Debian Administration website at the following bookmarkable URL:
This article is copyright 2006 JacobAppelbaum - please ask for permission to republish or translate.