Multikey

download, unpack. run ./compile.sh
create a secret file.

now with multikey you can create n files from which you must take at least k files to reproduce the original secret file. (k<n)

for example if you have an account number of a 100000$ account. you store the account number in a file. the one who can read the file can get the money. you have 10 persons. you want that if at least 3 of those persons want to get the money, they can go to the bank and get the money.
with multikey you can create 10 files out of your account number file. all of those files have absolutly no meaning. they are all like random data. only if you have 3 arbitrary of those files, you will be able to reconstruct your account number.

How does multikey work?

multikey consists of several programs.

randsplit

randsplit takes a file with a size of n bits. it creates k files that are also of size n bits. k-1 of the k files are pure random data. (the random data get's created by linux /dev/urandom entropy generator. the security of multikey bases on the security of randsplit which bases on the randomness of the entropy generator. keep this in mind) the last of the k files is the original file bitwise XORed with the k-1 pure random data files.
so what you get is k files which are all like pure random data.
an example: if k=10 it does not matter if you have zero, one, two, ... , nine of the 10 files, you always have pure random data. only if you have 10 of the files you get the original.

randjoin

randjoin reverses the effect of randsplit. it takes k files of n bits size. it creates one output file also of n bits size. each bit in the output file is the XOR of the bits of the k input files.

redun

the idea of "redun" comes from the stone-age of computer science. in those days you used floppy discs to carry data. often a single disc was too small. so it took let's say 10 discs to carry your data. you needed 2 hours to drive to your friend and give him your data. if one disc got damaged, the 2 hours have been wasted. so what could you do? carry 20 discs. then there are always 2 discs with the same data. but if just the right two discs crashed that carried the same data, you where lost again. the idea of the "redun" program is to take let's say 12 discs and then 2 ARBITRARY of the discs may crash. you can also take 15 discs. then 5 ARBITRARY of the discs may crash and you still have your original data.

you use redun like this: create some files. (EQUALLY SIZED) let'S say you created the files f1 f2 f4 now type

./redun f1 f2 f3 f4

"redun" looks and sees f1,f2,f4 exist, so it will READ those files. it sees that f3 does not exist, so it will WRITE this file. the order of parameters is IMPORTANT and must keep always the same. if you mix the keys to wrong positions in the parameter list, wrong results will be calculated.
now since we used 3 original files, we have only created one single redundancy file. so let's delete one arbitrary of the files.

rm f1

now let's reconstruct f1.

./redun f1 f2 f3 f4

redun will see f2,f3,f4 exist, so it will READ those files. it sees that f1 does not exist, so it will WRITE this file. easy ain't it?

how this works is nothing magic and is based on old known facts in mathematics. if you have a polynom of 9th degree, you need 10 points to fully specify it. lets say the 10 discs give us the 10 points in the polynom. then we can calculate other points in the polynom and store them on disc. now we can take an arbitrary set of 10 points from disc and recalculate the polynom. that's all. for calculating i use the GF(2^8) system. because there we can always divide without reminder. and we can use the bytes as y values in our polynom. so for every n-th byte in the discs i create a polynom and calculate the other n-th bytes for the other discs. if you need further information, don't try to understand my sourcecode ;) better read some books.

as explained "redun" is nothing new, and indeed you find other programs that do this job like http://www.cleaton.net/ras/.

makekeys.sh

makekeys.sh is just a rudimentary shell script that unites the above programs. give it a secret file, it will first use "randsplit" to create n files. then it uses "redun" to build additional redundancy files.

unlockdoor.sh

unlockdoor.sh is also just a rudimentary shell script that unites the above programs. give it a set of keys and tell it how many keys you need at minimum. (giving the wrong value here results in wrong results). it will first call "redun" to rebuild the needed first n keys. then it uses "randjoin" to recalculate the original file.

show me an example

erik@vulcain:~/prj/multikey/multikey > cat >secret
I am very important secret file
erik@vulcain:~/prj/multikey/multikey > ./makekeys.sh

Usage: makekeys.sh plainfile keyprefix numkeys numenoughkeys

Example: makekeys.sh plain key_ 10 7

erik@vulcain:~/prj/multikey/multikey > ./makekeys.sh secret key_ 5 2
Randomized splitting of your key into 2 keys.
Building redundant additional 3 keys.
all done. you now have the keyfiles
key_0 key_1 key_2 key_3 key_4
You only need 2 of those files to reconstruct your file "secret"

erik@vulcain:~/prj/multikey/multikey > ls -l key*
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_0
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_1
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_2
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_3
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_4
erik@vulcain:~/prj/multikey/multikey > rm key_3 key_0 key_2
erik@vulcain:~/prj/multikey/multikey > ls -l key*
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_1
-rw-r-----    1 erik     erik           32 Jan 24 20:50 key_4
erik@vulcain:~/prj/multikey/multikey > ./unlockdoor.sh

Usage: unlockdoor.sh keyprefix outputsecret numenoughkeys

Example: unlockdoor.sh key_ mysecret 7

erik@vulcain:~/prj/multikey/multikey > ./unlockdoor.sh key_ output 2
i found 2 keyfiles.
Thats enough keyfiles. proceeding...
Now rebuilding the eventually missing keys.
Now reuniting the keys to get the secret file.
all done. you now have the secret file "output"

erik@vulcain:~/prj/multikey/multikey > cat output
I am very important secret file
erik@vulcain:~/prj/multikey/multikey >

(erikyyy at erikyyy dot de, Erik Thiele)

back