written by © Konrad Rosenbaum (konrad (AT) silmor (DOT) de), 2004 This code is protected by the GNU GPL version 2 or any newer see COPYING for details
DISCLAIMER: THIS IS A PROOF OF CONCEPT IMPLEMENTATION, YOU USE IT AT YOUR OWN RISK! NO WARRANTIES OF ANY KIND ARE GIVEN. NEITHER THAT IT DOES WHAT IT IS DESIGNED FOR, NOR THAT IT DOESN'T DO ANY HARM TO YOUR COMPUTER, YOUR HEALTH OR WHATEVER IS AROUND AT THE TIME.
WARNING: the AES-key-generation algorithm used here is BROKEN! The random number generator used to generate the key is flawed badly enough to break the secret within seconds. (Thanks to Reiner Wobst for pointing out.) DON'T USE THIS PROGRAM FOR ANY REAL DATA!
Secret Sharing is a cryptographic technology to split a secret message in a way so that n out of m shares (assuming each share is for a person: out of m persons) have to be available before the secret can be revealed.
This is a proof of concept implementation that uses this technique to share the encryption key to a file so that n of m persons are needed to decrypt the file.
secshare <amount> <file> <share-files...>
amount
Is the number n of shares/persons that are needed to reveal the secret. Prepend it with a dash "-" to do the decryption.
file
Is the file to encrypt or decrypt.
share-files
Is the files in which to store the shares, you must list at least amount files.
secshare 3 myfile.txt share1 share2 share3 share4 share5
Encrypts myfile.txt into myfile.txt.enc and splits the AES-Key to it into five shares. Any three of these five shares will be able to decrypt the file.
secshare -3 myfile.txt.enc share4 share3 share5
Will reveal the key from shares 3, 4, and 5 and then decrypt myfile.txt.enc into myfile.txt.enc.dec (Sorry for the filename, but that is still proof of concept - right?)
If you want one person to be more important than the others, give him/her more than one share...
You need libgmp version 4 and gcc installed, then just call "make" and it will generate secshare.
Warning: I have never tested to compile that on anything other than Linux/x86, so several things could go rather wrong:
If you come up with a good GNU Autotools setup for secshare, that fixes these problems, please mail it to me!
I use a set of linear equations to split the secret. These are of the form:
k=M + a*x + b*x^2 + c*x^3 + ....
where k and x are the content of the share, M is the message and a,b,... is a set of secret random constants that are deleted after splitting and recalculated during revealing, there is exactly n-1 constants in the equation system. All these equations are done in a modular field for practical reasons (read the wiki!). I generate a 129 bit prime number p so that all operations are done modulo p. I chose 129 bits so that p is always slightly bigger than the secret split (the AES-key).
There is a rather nice algorithm created by two chaps named Gauss (German mathematician) and Jordan (French mathematician). It is the Gauss-Jordan-Elimination, that works with some rather simple matrix operations(*).
(*)That doesn't mean I understand how they work, they were just simple to implement. See http://www.aspire.cs.uah.edu/textbook/gauss.html
AES-128, algorithm code was taken from libgcrypt out of the GnuPG project. Thanks Werner. AES-128 is the weakest form of AES, however it is good enough for the purpose of this project. Maybe I'll port to AES-256 when I'm bored somewhen...
SHA-1, algorithm code again from libgcrypt, which took it from glibc. Actually only the first 128 (of 160) bits are used, this is rather insecure. I promise I'll convert to SHA-256 when I convert to AES-256.
The used random should be good enough for most applications, but is definitely inadequate for multi-billion-dollar-secrets (so is AES-128 for that purpose). It uses the normal ANSI-C-random-generator, but hashes the random values before using them, 20 calls to rand() and one run through SHA-1 are done for 20 bytes of random. The random generator is initialized with the usec-value from gettimeofday (which is rather weak).
In order of their importance, as I can see them:
The file is encrypted with AES-128 in CBC mode, for reasons of simplicity the initialization Vector (16 random bytes) is encrypted first (while the CBC-buffer is still zero). This differs slightly from the normal operation of CBC where the IV is stored unencrypted and then transferred into the CBC buffer.
The file looks like that:
A 129-bit prime is generated and for each share this information is stored (in hex) in the file:
As you can see the hash is also split in a second secret.
The first n secrets are read and the matrixes are filled with the coefficients (1, x, x^2, x^3, ...) and the k's.
Both matrixes are solved and the two M's (the key and the partial hash) are copied to the decryption algorithm.
The file is decrypted using AES-128 and the hash values are compared.