Re: Secret sharing algorithm with chosen keys
- From: Peter Pearson <ppearson@xxxxxxxxxxxxxxx>
- Date: 24 Feb 2009 18:58:36 GMT
On Wed, 25 Feb 2009 00:13:48 +0700, James Taylor wrote:
Scott Fluhrer <sfluhrer@xxxxxxxxxxxxx> wrote:[snip]
A group of N persons
decide to each buy one of these token/key only for the purpose to
compute from these keys a shared secret that any T of the N persons
should be able to recompute later.
[snip]If N = T, it's easy: I could simply XOR the N keys to get the shared
secret. But I'd like to be able to reconstruct the shared secret even
in the case of a few missing shares. Does someone know of a secure way
to solve my problem?
it would appear necessary for either the
manufacturer's random key have more properties than just being a random
number, the scheme has some input beyond the random values on the tokens or
there needs to be trusted third party which can distinguish valid random
numbers from bad ones.
Couldn't Thomas do what he was proposing to do in the T=N case, but do
that for each possible set of T people where T<N do you think? He could
then protect the shared secret with multiple decryption keys, each key
being the XOR of one possible set of T people. This wouldn't scale well
to large numbers of N and T but might suffice for his purpose (depending
on the exact nature of his purpose, of course).
To assemble these good responses into a more complete
picture: If you can tolerate a share-combining algorithm
that involves a possibly large table of numbers, you might
be able to make something useful, but it wouldn't be
information-theoretically secure, as Shamir's original
secret sharing is.
For example, you might combine T shares thusly (forgive me,
James Taylor, if I turn your suggestion into something silly):
1. Sort the T shares into (say) alphabetical order and
combine them into one long string.
2. Apply some key-derivation function to that string.
(E.g., append it to itself several times and hash the result.)
Assuming the result is 256 bits long, separate it into Part A
and Part B, each 128 bits long.
3. Take Part A to a big table (containing N-choose-T rows) to
look up the value that you XOR with Part B to get the secret.
If Part A isn't in the table, you don't have T valid shares.
You kinda have to assume that the table is non-secret,
because if you have confidence in your ability to keep the
table secret, you don't need the tokens. But if an attacker
has the table and T-1 shares of the secret, he can
exhaustively search for the Tth share, so this is inferior
to real secret sharing, in which all secrets are equally
likely even to an attacker who has T-1 shares. (Hence
Scott's pointer to the ability to distinguish valid shares
from invalid shares.) Still, if each token contributes an
unsearchably large amount of information, you could make the
On a separate note, it's considered bad form for a security
token to reveal its secret. If, instead, each token uses
its secret as an AES key to encrypt an input value and export
the result, you could assign each token a non-secret serial number
(to establish an order in which they're applied), then compute
Part A by successive encryptions of 0 and Part B by successive
encryptions of 1.
To email me, substitute nowhere->spamcop, invalid->net.
- Prev by Date: Re: Requesting comments: SRP based IRC encryption
- Next by Date: Re: Secret sharing algorithm with chosen keys
- Previous by thread: Re: Secret sharing algorithm with chosen keys
- Next by thread: Re: Secret sharing algorithm with chosen keys