Re: Secret sharing algorithm with chosen keys

On Wed, 25 Feb 2009 00:13:48 +0700, James Taylor wrote:
Scott Fluhrer <sfluhrer@xxxxxxxxxxxxx> wrote:
lethal.possum@xxxxxxxxx wrote:
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?

[snip]
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).
[snip]

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

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

Relevant Pages

  • Re: Joint encryption?
    ... simply discards mail, so I don't have to deal with all the broken ... You don't need the "...used to gain access to the rest of the ... This is called "secret splitting", and there are a number of schemes by ... How the shares are stored is up to those charged with protecting them; ...
    (Bugtraq)
  • Re: Joint encryption?
    ... > simply discards mail, so I don't have to deal with all the broken ... >>the key can be used to gain access to ... > reconstruct the secret, but any M-1 of which can discover nothing about ... > How the shares are stored is up to those charged with protecting them; ...
    (Bugtraq)
  • Re: Newbies questions about secret sharing schemes
    ... What's the simplest way to convert the secret S into an integer number ... reinterpret that as a series of GF field elements, ... tweak certain some of their shares; when you reconstruct the shared secret, ... reconstructed to something other than the actual value, but the characters ...
    (sci.crypt)
  • Re: Efficient Exponentiation of a Shared Secret
    ... shared among a number of parties. ... Shamir's scheme this is the case). ... Is there a scheme in which the secret s can be expressed as a product ... using any k out of n shares the secret x can be reconstructed, ...
    (sci.crypt)
  • Re: hardware disk encryption?
    ... >> RAID card that requires a passphrase as the computer boots up. ... i didn't mean to imply that secrets are _better_ than tokens. ... in general i trust myself more with a secret than a token. ...
    (sci.crypt)