sharesecret
.
sharesecret
.
If you (or the president of Yoyodyne, Inc.) knows an important password, such important that something awful happens if you cannot provide it. (E.g. to decrypt the telephone number of your new love, or the description of a new product which will get Yoyodyne megabugs.) Well, you can give the password to a trusty friend (or the vice president), but is (s)he really trustworthily enough?
Sharesecret gives you the solution. You can split your secret into
n parts with a threshold parameter t
(2<=t<=n).
Then you can distribute the parts to some of your friends (or the
vice presidents). If you forget the secret you can ask t friends
to help you. They (the t friends) can apply joinsecret n
to the parts and, voilá, the secret appears again.
If you use a good (i.e. cryptologically strong) pseudo random number generator, strictly less then t friends have in no way an advantage over arbitrarily guesses.
There are also schemes possible for remote friends (or normal managers) as a second level backup, e.g. with higher threshold.
Split a secret into 42 parts such that all parts are needed for
reconstruction using /dev/random
as pseudo random number
generator:
prng-random-splitsecret 42 42 part. < secret-data
splitsecret 42 42 part. 3< /dev/random < secret-data
Split a secret into 42 parts such that exactly 17 parts are needed for
reconstruction using /dev/urandom
as pseudo random number
generator:
prng-urandom-splitsecret 42 17 part. < secret-data
splitsecret 42 17 part. 3< /dev/urandom < secret-data
If you have the EGD - Entropy Gathering Demon you can use:
prng-egd-splitsecret 42 17 part. < secret-data
splitsecret 42 17 part. 3< ~/.gnupg/entropy < secret-data
If you don't have one of the upper pseudo random number generators or if
you are just playing around you can call:
prng-arcfour-splitsecret 42 17 part. < secret-data
Joining 17 parts can be done by:
joinsecret 42 part.0*[1-9] part.0*1[2-9] > joined-secret
The secret data is considered to be arbitrary binary data. A part
starts with a magic. This is a netstring (see
D. J. Bernstein's netstrings) of "FSS "
appended with the file format version
number^{1}. That is for this version "9:FSS 1.0.0,"
. If the part
is generated by the XOR-method there follows exactly as many bytes as
there are in the secret. Otherwise (using the polynomial method), there
are two bytes of the evaluation point (MSB first). Then follows the
result of the evaluation (MSB first) of the random polynomials.
sharesecret
.
"9:BSS 1.0.0,"
Security by obscurity is not a good idea. Once when the attacker know the code the security lowers or disappears. That's not a good idea for open source software. Therefore, I don't try to reach it. If you want some obscurity you should use steganography.
The security of sharesecret
depends of course on the quality
(i.e. cryptographic quality) of the pseudo random number generator.
The very best choice is /dev/urandom
if your operating system
provides this device with a good quality. Other good sources are
/dev/random
, the output of gpg --gen-random 2
and
~/.gnupg/entropy
if you have the EGD - Entropy Gathering Demon
(see EGD). A good fallback is prng-arcfour
which is part of sharesecret
.
The code avoids the problem of many operation system which allows only a low number (e.g. 256 for canonical Linux at 2000-12). It only needs to have 3 open files for splitting and two for assembling at the same time.
In future version the number of parts is limited only by the available
memory if the threshold for assembling is the same as the number of
parts (t=n).
Up to now sharesecret
uses the same limits as below.
Otherwise (1<t<n), the limit of parts is 65520 = 65521 - 1 ^{2}. If you have enough memory you (or I) may rewrite the program, but consider the space and time estimates (see Complexity).
Sharesecret is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation either version 2 of the License, or (at your option) any later version.
I don't know if it is allowed to export sharesecret from the US. The addresses given below, see Downloads, points to a computer in Germany, which don't have such an export restriction. (And the files have been put there in a legal way.)
To describe the complexity by formulas we need to introduce the following notation.
Of course we have the compatibility condition 1<t<=n. And we write l for the bit length ceil (log (n)/log (2)). Finally, we write a for the amortised effective length (= number of octets, i.e. bytes) L((1/p) + (2/(2^16-p))) see Value of p. ^{3}
For reasons of completeness we give the definitions of the complexity classes here.
Let X be a lattice, e.g. X=N. Further, let f:X->R be a function on X.
If t=n implementations are possible which need only O(l) space. But in the current implementation we use O(n*l) space. It's just easier to implement.
If t<n we need Omega(t*l), Theta(t*l),O(t*l) space for splitting. Moreover, a lower bound is t*l. E.g. t = 65000, n = 65520 => 1040000 Bit = 130000 Bytes =~ 130 kByte. but squaring the size (doubling l) gives t = 4294967200, n = 4294967296 = 2^32 => 137438950400 Bit = 17179868800 Bytes =~ 17 GBytes. If you do long long calculations you need about 34 GBytes of main or virtual memory.
If t=n then we need Omega(n*L), Theta(n*L), O(n*L) time.
If t<n then we need O(t*n*L) time.
If t=n then we need Omega(n*L), Theta(n*L), O(n*L) time.
If t<n then we need O(t^2*L) time.
If I have more time I check these estimates in detail. Up to know take them as intuitive values.
There is another program secsplit
somewhere. In the second
version a lot of ideas of secsplit are inserted into sharesecret. But
secsplit didn't optimise the case that the threshold is maximal,
i.e. the number of parts.
There is (maybe are) some programs which uses the XOR algorithm, i.e. they only provide splitting if the threshold is maximal, i.e. the number of parts.
Sharesecret
During joining sharesecret uses the Aitken-Neville algorithm for interpolating polynomials at a given point x, in this case at x=0. There are several other interpolation methods, e.g. Lagrange, Newton, which are useful if you want to evaluate the unknown polynomial at several points. Sharesecret needs only the value at 0, thus the Aitken-Neville method is the fastest^{4}.
If sharesecret would take the coefficients in the natural (or integer, rational, real) numbers it would need exact rational (or real) numbers in the Aitken-Neville algorithm. As this would take a lot of memory and time sharesecret uses another method. It does its calculations in a finite field, particularly in Z/pZ, i.e. the natural numbers modulo the prime p.^{5} As we need for n parts the different evaluations points x=1, ..., n it is required that n < p, otherwise sharesecret cannot recalculate the secret as it don't know enough points^{6}.
In the current version of sharesecret (0.4.0) it uses
p = 65521, i.e. the biggest prime smaller than
2^16 = 65536, and restricts the evaluation points to
1, ..., p - 1, see Limitations. Then sharesecret needs
two bytes (= octets) per part to store the evaluation point and can do
multiplication without overflow using unsigned long int
(32 bit). Now you ask, how sharesecret
splits a whole file, which is longer than 16 bits? Well, it's
quite easy. Sharesecret splits the whole file into small chunks of
16 bits. If a chunk c (seen as a binary number) is bigger
or equal than p - 1 = 65520, sharesecret splits it again into two
chunks of 16 bits where the first equals p - 1 = 65520 and
the second equals c - p. Finally, sharesecret can split the
resulting chunks by the above algorithm.
Well this is still not the whole truth. The above scheme would blow up
(at most double) files containing many bytes with all bits set,
e.g. 0xff
. To avoid this, the chunks are XORed with a
fixed pseudo random number stream before it may be splited
into two chunks. Using a fixed number instead of the fixed pseudo random
number stream would not be nice, as there may be many values repeated in
the file that become 0xff
after being XORed with the fixed
value. Using the stream tries to avoid this problem with repeating worse
constants. The stream is irrelevant to the security of the splitting
algorithm, so it can chosen to be a fixed one.
If the secret consists of an odd number of bytes, it is padded by
a zero byte. As the length of the parts is increased by another
byte. Sharesecret
can detect this situations during the joining
process and reconstruct the exact secret.
Sharesecret is prepared for download in different formats.
-----BEGIN PGP PUBLIC KEY BLOCK----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org mQGiBDkpfr8RBACK2ug2Cbbuu+e7ImTk6hKWmErIOjUQQCOViU2INlXJNqTZ0O2z 0n4mvJyBnb5HJlWoqqwV1saqHyEeMdAG28Ey7d9boPlXQomXPYGA6VEDo12b28+T pHjMwUsr65afTKYZsR7BvlUcS3EHJ9VAQk4Uu68Qi0ZDrmFgAfxBy0Z/BwCgrWZP uoEYEJ4WyHKbRoN1A6JEQVUD/iHvUw61jpIKP+6M/fS/bywtE3JRTfmKLv7RwHFW 5Hi3xBfgh65rCLPoa88grKAgndobW/sChDDbBCPlQO4csvZJZDUoCSD9lll7ENJy oVHRi/bCIi7KOoTaLmk6Sul4rsPrgNlvEOHKpFt3NbWS+FZ9BPI4mtRXc5SUytGA ET2hA/0YEQ9hFHzQXN9y1juSOOqcN6xvRWm3fnX5L6N/pjneIGf2jecctAiwGdxY Up1XIoNBbSVLlRlKQJFXy5upCbMbqkBQbCHrL0UqLy0PEKZoQtiFheM+4Icdx6F5 A4MBA2aLjljwYOXz1xRv779yU4Ams5PmvML/jJb02fOFgXUD4bQtU3RlZmFuIEth cnJtYW5uIChwcml2YXQpIDxTLkthcnJtYW5uQGdteC5uZXQ+iFwEExECABwFAjkp fr8FCQlmAYAECwoEAwMVAwIDFgIBAheAAAoJELFqJG9Vu5NFzBUAn0k6GG40Nwan 6LMgn1nvAf/78NpGAKCJObr/3AN+cXgYmmQznJycOfUnbbkCDQQ5KX+DEAgAz7vW B3Urbv7vaYNnLSBxfUyIcO88dGJD6RgXrbDrTVBFv7LEi1H+FtIciKYde/3LjTnI SmTvjsXMZMAZK69Cm849zujBJ+1RuAOmfvnjRvRburfntDG1SPz+zdYVNSq8GvHk sYZV9Apm9yz9W6V74T3tKb6QLn11EBNaLjbDt+OOJFYRUkEDGNn6Cn+cXtXAockY PF04VZBrO59DdiCOI52fp40qv/IzBwEvrH4IvUYaeUWM/A8dtZINHt7VyymtmQkP 9Ixfx1WlYCwlN7yYACbzDUCaBV8xZWnvNSuD7Np/mDdiF79fPKf5PDJwV80Z3xfK 59cr5ErJCXx/2PA0BwADBQf/RJXCCcIAMq1Nn6paicLCqDc7XTQED1A37zpomQc0 GQ0DFOIvJzUzuJiAy6nc0ovuXA9kG8+2B5F9OB9zoLl1wunl91nwKkXMY3kTTFYh 66Ihw+/LTcWdr4JwEU0ByaqK979135kISAAaylS9Hvucdqe+UatEMU8MHvG9GWvk ITODN+c0JIiOdByQuct7XlMcAo7M9K5liOlAzlUrOSI4SdgvekTyJZRU7yF7wy9e ZXASoL9zrMd/9Xfb+/el/YWlWD6HsoENm7ouKVa/JYGpmPVLyLzBPuwvYfJRxVJF 0/zbTkDlIm/PCA6IHsJ1EvEC5HiYWlgXQeItDzg2p56eo4hMBBgRAgAMBQI5KX+D BQkJZgGAAAoJELFqJG9Vu5NF+xEAn3T5zIlUxspHaiwYVaeuMAcWP+ANAJ4rUdWy mGhjpS5ZNt97tIlH+aLgeg== =4xHM -----END PGP PUBLIC KEY BLOCK-----
If you find a bug in sharesecret
, please send electronic mail to
S.Karrmann@gmx.net
with subject sharesecret
. Include
the version number. Also include in your message the
output that the program produced and the output you expected.
To avoid unsolicited commercial e-mails (also known as spam) I only accept
encrypted emails (see my homepage
or my public keys)
or mails of selected persons or mail with subject sharesecret
.
See also Abuse.net and
Spamcop.
If you have other questions, comments or suggestions about
sharesecret
, contact the author via electronic mail to
S.Karrmann@gmx.net
with subject sharesecret
. The
author will try to help you out, although he may not have time to fix
your problems.
Version 2, June 1991
Copyright © 1989, 1991 Free Software Foundation, Inc. 675 Mass Ave, Cambridge, MA 02139, USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.
The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too.
When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.
To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.
For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights.
We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software.
Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations.
Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.
The precise terms and conditions for copying, distribution and modification follow.
Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does.
You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee.
These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it.
Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program.
In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License.
The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.
If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code.
If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances.
It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice.
This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License.
Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation.
If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms.
To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found.
one line to give the program's name and an idea of what it does. Copyright (C) 19yy name of author This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
Also add information on how to contact you by electronic and paper mail.
If the program is interactive, make it output a short notice like this when it starts in an interactive mode:
Gnomovision version 69, Copyright (C) 19yy name of author Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. This is free software, and you are welcome to redistribute it under certain conditions; type `show c' for details.
The hypothetical commands show w
and show c
should show
the appropriate parts of the General Public License. Of course, the
commands you use may be called something other than show w
and
show c
; they could even be mouse-clicks or menu items--whatever
suits your program.
You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the program, if necessary. Here is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the program `Gnomovision' (which makes passes at compilers) written by James Hacker. signature of Ty Coon, 1 April 1989 Ty Coon, President of Vice
This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License.
Bruce Schneier, Applied Crypthography, first edition.
EGD - Entropy Gathering Daemon
GPL - GNU Public Licence
Copyright © 1999, 2000 Stefan Karrmann Last Updated: 2000-12-19 |
This need not be the version number of the sharesecret programs.
65521 is the biggest prime number lower than 2^16=65536.
Here we assume the Laplace distribution of the values of the octets.
As far as I know. Remarks are welcomed.
There are finite fields where the addition is slightly faster, e.g. fields with p^n elements where p is prime, in particular p=2 and n=2^m - H. Conway: On numbers and games. But the multiplication is normally not implemented in hardware as the modulo arithmetic. Thus, multiplication and inversion is slower and we stick to the prime fields.
A polynomial of degree k has k+1 unknown coefficients. To determinate the polynomial we need therefore k+1 evaluations points and the evaluation results using the results of elementary linear algebra.