Silmor . de
Site Links:
Impressum / Publisher

Secret Sharing Tool

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!

What is it?

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.

How to use it?

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.

Example

 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?)

Hint

If you want one person to be more important than the others, give him/her more than one share...

Compiling it

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!

Algorithms used

Secret Sharing

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).

Secret Revealing

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

Symmetric Encryption

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...

Hashing

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.

Random

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).

Attack vectors

In order of their importance, as I can see them:

Protocol

Encryption

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.

Decryption

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.

Links


Webmaster: webmaster AT silmor DOT de