Joint encryption?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I'd post this to security-basics, but I've tried subscribing to that
list through the web interface 3 times and still only managed to get
linux-focus and bugtraq.

I'm trying to solve a problem where I want to control access to highly
sensitive data in a hostile situation. The hypothetical situation could
be anything, such as secret military tactical data or engineering
designs for a high-end technology company. In such situations, I've
decided that it would be prudent to require multiple authentication to
access the data.

As this is an academic exercise, I think we can skip the lecture and
deeper analysis of what I would need; right now a simple problem has
arisen which is more interesting than the more abstract "protect the
most sensitive data in the universe" problem.

The problem that has arisen is that in my "worst case scenario," I have
accounted for a group of authenticated users having free access to the
equipment and being able to use their own operating system to access the
protected data. I would like to protect that data in such a case.

The authentication works as below:

- N users may authenticate to access the data
- A magnitude M of authenticated users is needed to access the data
- N >= 3 > M >= 2

The case where N = 1 is simple authentication; the case where N = M is
an easily solvable problem in the scope I'm looking at. I'm interested
in the case where N > M and the data is encrypted.

- Key is fragmented
- Fragments are indpendently encrypted
- Each user who can authenticate can decrypt PART of the key, but not
all of it
- M of the N users are needed to decrypt enough of the key to access
the key in total

The problem is that I need a guaranteed way to create data for any valid
N and M where N >= 3 > M >= 2 in which access to M fragments of the key
(each fragment is encrypted) can be used to gain access to the rest of
the fragments, which in turn allows any selection of M users to
authenticate and gain physical access to the key.

Reminder that the idea here is to use a physical method, not bare access
control that can be evaded by loading a modified kernel.

The most obvious methods I can think of create explosive data growth as
M and N increase. The amount of data needed in any way I can think of
grows linearly with M and exponentially with N.

Are there any known ways to do this?


<EXAMPLE>
N=3
M=2
Users X, Y, Z
Key: [xxxx][yyyy][zzzz]
X provides a key which decrypts xxxx
Y provides a key which decrypts yyyy
Z provides a key which decrypts zzzz

Authentications:
(X,Y): [xxxx][yyyy][????]
(X,Z): [xxxx][????][zzzz]
(Y,Z): [????][yyyy][zzzz]

In the case of (X,Y), [xxxx] and [yyyy] must provide enough data to
decrypt [zzzz]
In the case of (X,Z), [xxxx] and [zzzz] must provide enough data to
decrypt [yyyy]
In the case of (Y,Z), [yyyy] and [zzzz] must provide enough data to
decrypt [xxxx]

In the case of N=100 M=2, any unique [xxxx] and [yyyy] must provide
enough data to decrypt the other 98 chunks of the key.
In the case of N=100 M=3, any unique [xxxx] and [yyyy] must not provide
enough data to decrypt the other 98 chunks; a [zzzz] must also be
supplied, any unique.

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be
wasted on re-inventing the wheel when there are so many fascinating
new problems waiting out there.
-- Eric Steven Raymond
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCFZx0hDd4aOud5P8RAl70AJ0dVr5wYHu3ynVz8gyluX xNnc0R4gCfbjGQ
i7bqRwgdlQcosF7CcsW3oM0=
=9Q6x
-----END PGP SIGNATURE-----

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Damian Menscher wrote:
> On Fri, 18 Feb 2005, John Richard Moser wrote:
>
>> The authentication works as below:
>>
>> - N users may authenticate to access the data
>> - A magnitude M of authenticated users is needed to access the data
>> - N >= 3 > M >= 2
>>
>> Are there any known ways to do this?
>
>
> Google for secret sharing or secret splitting. In particular, look for
> Shamir's scheme, which seems to be the simplest. And there's always
> Wikipedia: http://en.wikipedia.org/wiki/Secret_sharing
>

:)

> A brief overview of Shamir's scheme (it's so cool I can't resist):
> Consider the M-th order polynomial:
> N = c_{M-1} x^{M-1} + ... + c_1 x^1 + c_0 x^0
> This polynomial is defined by c_0 .. c_{M-1}. So, M unknowns should
> require M unknowns, right? Now let's say I tell you that I'm using M=2
> (so N = c_1 x + c_0) and also tell you that:
> N(1) = -1
> N(2) = 1
> and ask you for the password: c_0, c_1. You have two equations and two
> unknowns, so you can solve it. What if person 2 was hit by a bus, and
> we had to call in person 3 to access the data?
> N(1) = -1
> N(3) = 3
> Either way, you can recover the coefficients (assuming you know
> high-school math). And yet each individual person has zero knowledge.
>

Been trying to figure out how to generate this on a fixed field so that
I can have all integer points, integer intercept, and integer
coefficients. I really want to store this reliably on disk :)

Looking at Shamir's scheme, I'm surprised I didn't come up with this
immediately, I mean f*** it's basic algebra I took in frickin' 7th
grade; I took calc 1 and 2 and stat in highschool, I should be able to
see this. Perhaps the fact that I've used no complex math since 2001
could account for me being stupid now.

Here's a question. As a recovery method in the case of an attacker
gathering a few shares, "If it is not practical to change the secret,
the uncompromised (Shamir-style) shares can be renewed. The dealer
generates a new random polynomial with constant term zero and calculates
for each remaining player a new ordered pair, where the x-coordinates of
the old and new pairs are the same."

Given this, is it important that the constant term i[0] (i[0]x^0 ==
i[0]) be 0? Is it simpler for example? It doesn't matter if it is; for
any Y intercept, 1 point is defined, and K more are needed to absolutely
define a polynomial of degree K. There's an infinite number of
polynomials of a given degree with a given point in them, even if you
restrict one of the terms.
>> <EXAMPLE>
>> N=3
>> M=2
>> Users X, Y, Z
>> Key: [xxxx][yyyy][zzzz]
>> X provides a key which decrypts xxxx
>> Y provides a key which decrypts yyyy
>> Z provides a key which decrypts zzzz
>
>
> Very bad idea: each person knows enough to reduce the brute-force search
> space dramatically.
>
>

I saw, I've been reading up on secret sharing since I posted this
message (a few hours later some ex-military dropped the term in front of
me; it was probably a part of her cryptography courses). I too find
Shamir to be brilliant.

> As a side note, you mentioned that malicious attackers might have access
> to the hardware. This is fine if they can only steal it and run their
> own attacks on it. But an intelligent attacker would simply install a
> keystroke logger, and grab a few keys. Guarding against this is left as
> an exercise to the reader, but might involve splitting the secret
> amongst multiple machines running different OSes in different locations
> adminned by different people, possibly even running the secret-sharing
> software written by different people. ;)
>

A USB keylogger :) *wields a 128 byte USB storage device* :>

If I were securing data like this (remote network access to the nuclear
football or something, since Clinton sometimes leaves it behind), I'd
probably be touching some really REALLY sensitive data. I'd be using a
static system to do the access (i.e. a LiveCD) rather than trusting the
system (trusted computing omgwtf) or expecting AdAware and ClamAV and
chkrootkit to clean out anything or even wasting 5 hours having a
technician do a thorough goingover.

In such a case of course the LiveCD would have to be trusted itself, but
at least your trust falls on the people creating it and the system at
the time of its creation, rather than the system at the time of
installation on to the present and all people ever accessing it.

.. . . wow, since when are LiveCDs security tools?


It's funny, I want this so bad even though I have no need for it, just
to do it and see it. What I really started out trying to do is create
an access control system that'll allow a user to very simply protect his
own data from himself (i.e. from viruses, worms, and trojans he runs,
and from his mistaken rm -rf commands), which needs significantly less.
Of course with me I have to look at the problem and say "well let's
see, what might be cool to have if there's some unrealistic situation. .
.." and I go berserk with it :>

At any rate i like physical access control, and encryption comes close
there (if you destroy the key, you pretty much destroy the data, barring
100 zillion year brute forcing and shor's algorithm on 4096 qubit
computers).

Is secret sharing even used in the real world?

> Damian Menscher
> --
> -=#| Physics Grad Student & SysAdmin @ U Illinois Urbana-Champaign |#=-
> -=#| 488 LLP, 1110 W. Green St, Urbana, IL 61801 Ofc:(217)333-0038 |#=-
> -=#| 4602 Beckman, VMIL/MS, Imaging Technology Group:(217)244-3074 |#=-
> -=#| <menscher@uiuc.edu> www.uiuc.edu/~menscher/ Fax:(217)333-9819 |#=-
> -=#| The above opinions are not necessarily those of my employers. |#=-
>
>

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be
wasted on re-inventing the wheel when there are so many fascinating
new problems waiting out there.
-- Eric Steven Raymond
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCF3GqhDd4aOud5P8RAqcrAJ9wZd8iwfkhynmCmwpbXR cHYd5WCwCghCHj
eamxaMiaqMUHsYobyS3pq8o=
=kH/k
-----END PGP SIGNATURE-----

[Damian Menscher]

On Fri, 18 Feb 2005, John Richard Moser wrote:

> The authentication works as below:
>
> - N users may authenticate to access the data
> - A magnitude M of authenticated users is needed to access the data
> - N >= 3 > M >= 2
>
> Are there any known ways to do this?

Google for secret sharing or secret splitting. In particular, look for
Shamir's scheme, which seems to be the simplest. And there's always
Wikipedia: http://en.wikipedia.org/wiki/Secret_sharing

A brief overview of Shamir's scheme (it's so cool I can't resist):
Consider the M-th order polynomial:
N = c_{M-1} x^{M-1} + ... + c_1 x^1 + c_0 x^0
This polynomial is defined by c_0 .. c_{M-1}. So, M unknowns should
require M unknowns, right? Now let's say I tell you that I'm using M=2
(so N = c_1 x + c_0) and also tell you that:
N(1) = -1
N(2) = 1
and ask you for the password: c_0, c_1. You have two equations and two
unknowns, so you can solve it. What if person 2 was hit by a bus, and we
had to call in person 3 to access the data?
N(1) = -1
N(3) = 3
Either way, you can recover the coefficients (assuming you know
high-school math). And yet each individual person has zero knowledge.

> <EXAMPLE>
> N=3
> M=2
> Users X, Y, Z
> Key: [xxxx][yyyy][zzzz]
> X provides a key which decrypts xxxx
> Y provides a key which decrypts yyyy
> Z provides a key which decrypts zzzz

Very bad idea: each person knows enough to reduce the brute-force search
space dramatically.


As a side note, you mentioned that malicious attackers might have access
to the hardware. This is fine if they can only steal it and run their own
attacks on it. But an intelligent attacker would simply install a
keystroke logger, and grab a few keys. Guarding against this is left as
an exercise to the reader, but might involve splitting the secret amongst
multiple machines running different OSes in different locations adminned
by different people, possibly even running the secret-sharing software
written by different people. ;)

Damian Menscher
--
-=#| Physics Grad Student & SysAdmin @ U Illinois Urbana-Champaign |#=-
-=#| 488 LLP, 1110 W. Green St, Urbana, IL 61801 Ofc:(217)333-0038 |#=-
-=#| 4602 Beckman, VMIL/MS, Imaging Technology Group:(217)244-3074 |#=-
-=#| <menscher@uiuc.edu> www.uiuc.edu/~menscher/ Fax:(217)333-9819 |#=-
-=#| The above opinions are not necessarily those of my employers. |#=-

[Casper.Dik@Sun.COM]

>The case where N = 1 is simple authentication; the case where N = M is
>an easily solvable problem in the scope I'm looking at. I'm interested
>in the case where N > M and the data is encrypted.
>
> - Key is fragmented
> - Fragments are indpendently encrypted
> - Each user who can authenticate can decrypt PART of the key, but not
>all of it
> - M of the N users are needed to decrypt enough of the key to access
>the key in total

When you fragment the key as you propose, there's a danger of making
the remaining fragment bruteforcable by "M-1" users as they're
left to guess only 1/Mth of the key.

I'd argue the best way is to give each of the M users a bit
vector the length of the key and XOR the M vectors to get
the key vector. This way, the security of the key is as strong
whether you have 1 , 2 .. upto M-1 fragments. (Of course,
you should also require each of the users to decrypt their
key vectors)

Effectively, none of the users know any key bits by themselves.

>The problem is that I need a guaranteed way to create data for any valid
>N and M where N >= 3 > M >= 2 in which access to M fragments of the key
>(each fragment is encrypted) can be used to gain access to the rest of
>the fragments, which in turn allows any selection of M users to
>authenticate and gain physical access to the key.

Exponentional might not be bad if you know that the numbers
will be small; in O(N^M) space a solution is trivial.

Casper

[devnull@Rodents.Montreal.QC.CA]

[As usual when I write to bugtraq, the from address in the headers
simply discards mail, so I don't have to deal with all the broken
autoresponder mail that would otherwise land on me. To reach me, use
the address in the signature.]

> The problem is that I need a guaranteed way to create data for any
> valid N and M where N >= 3 > M >= 2 in which access to M fragments of
> the key (each fragment is encrypted) can be used to gain access to
> the rest of the fragments, which in turn allows any selection of M
> users to authenticate and gain physical access to the key.

You don't need the "...used to gain access to the rest of the
fragments..." part.

This is called "secret splitting", and there are a number of schemes by
which you can split a secret into N shares, any M of which can
reconstruct the secret, but any M-1 of which can discover nothing about
the secret. One of the simplest, at least to my mind, is based on
polynomials over a finite field. A handful of secret-splitting
schemes, including this one, are described in Schneier's _Applied
Cryptography_ (and doubtless many other places); the rest of this
message is a brief description of this technique.

Input: a secret S, and N and M as above.
Choose a prime P, larger than S.
Let c[0] be S.
Choose random values less than P for c[1] through c[M-1].
For i from 1 through N, compute (all arithmetic mod P)
h[i] = sum(j=0..M-1) (c[j] i^j) [^ is exponentiation]
Share #i is then the triple <P,i,h[i]>.

How the shares are stored is up to those charged with protecting them;
they can store them encrypted if they want. Only the h[i] value needs
to be protected.

Now, given any M shares, you can set up M equations

h[i] = sum(j=0..M-1) (c[j] i^j) (mod P, of course)

for the i and h[i] values in the shares. (Of course, if the P values
in the shares aren't all equal, at least one of the shares has been
corrupted.) This is a system of M linear equations in M unknowns (the
c[] values). Given how the coefficients of this system were chosen
(the i^j values), they will be linearly independent and the system thus
has a unique solution (since P is prime, division mod P works and
Gaussian elimination can be performed). Solve it, and c[0] will be the
secret. (You can throw away c[1] through c[M-1]; they were randomly
chosen at split time and carry no information.)

But if you have fewer than M shares, you can set up at most M-1
equations. Such a system is not solvable, and since we're working in
the finite field Z_P, you actually cannot discover anything about S; by
introducing a fictitious additional share with a suitable h[] value,
you can arrange to make c[0] come out to any value you please.

If you have more than M shares, the system is overdetermined. You can
pick any M of the shares, reconstruct the c[] values, and check that
what you get agrees with the redundant shares. (You actually don't
*have* to check, but it allows you to catch some cases of corrupted
shares.)

I've written software that implements this. See
ftp.rodents.montreal.qc.ca:/mouse/local/src/secretsplit/.

/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse@rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Casper.Dik@Sun.COM wrote:
>>The case where N = 1 is simple authentication; the case where N = M is
>>an easily solvable problem in the scope I'm looking at. I'm interested
>>in the case where N > M and the data is encrypted.
>>
>>- Key is fragmented
>>- Fragments are indpendently encrypted
>>- Each user who can authenticate can decrypt PART of the key, but not
>>all of it
>>- M of the N users are needed to decrypt enough of the key to access
>>the key in total
>
>
> When you fragment the key as you propose, there's a danger of making
> the remaining fragment bruteforcable by "M-1" users as they're
> left to guess only 1/Mth of the key.
>
> I'd argue the best way is to give each of the M users a bit
> vector the length of the key and XOR the M vectors to get
> the key vector. This way, the security of the key is as strong
> whether you have 1 , 2 .. upto M-1 fragments. (Of course,
> you should also require each of the users to decrypt their
> key vectors)
>

Yeah I noticed that on the wikipedia :)

http://en.wikipedia.org/wiki/Secret_sharing

> Effectively, none of the users know any key bits by themselves.
>
>
>>The problem is that I need a guaranteed way to create data for any valid
>>N and M where N >= 3 > M >= 2 in which access to M fragments of the key
>>(each fragment is encrypted) can be used to gain access to the rest of
>>the fragments, which in turn allows any selection of M users to
>>authenticate and gain physical access to the key.
>
>
> Exponentional might not be bad if you know that the numbers
> will be small; in O(N^M) space a solution is trivial.
>

I actually was looking around and found secret sharing and shamir's
scheme, which look interesting. :) I understand the math behind it
vaguely, which is good; how exactly to do finite fields and generate
polynomials I can regress of any arbitrary degree 1..+inf uhh.

Bearing in mind I have no practical use for this, it's still interesting.

> Casper
>

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be
wasted on re-inventing the wheel when there are so many fascinating
new problems waiting out there.
-- Eric Steven Raymond
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCFy5FhDd4aOud5P8RAlz2AJ0aitdjpF6vNAFIWqiNTp hiabd6MQCeIPhQ
XBKiKVWK6B0+s56JVvD13eM=
=hTx9
-----END PGP SIGNATURE-----

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



devnull@Rodents.Montreal.QC.CA wrote:
> [As usual when I write to bugtraq, the from address in the headers
> simply discards mail, so I don't have to deal with all the broken
> autoresponder mail that would otherwise land on me. To reach me, use
> the address in the signature.]
>
>
>>The problem is that I need a guaranteed way to create data for any
>>valid N and M where N >= 3 > M >= 2 in which access to M fragments of
>>the key (each fragment is encrypted) can be used to gain access to
>>the rest of the fragments, which in turn allows any selection of M
>>users to authenticate and gain physical access to the key.
>
>
> You don't need the "...used to gain access to the rest of the
> fragments..." part.
>
> This is called "secret splitting", and there are a number of schemes by
> which you can split a secret into N shares, any M of which can
> reconstruct the secret, but any M-1 of which can discover nothing about
> the secret. One of the simplest, at least to my mind, is based on
> polynomials over a finite field. A handful of secret-splitting
> schemes, including this one, are described in Schneier's _Applied
> Cryptography_ (and doubtless many other places); the rest of this
> message is a brief description of this technique.
>
> Input: a secret S, and N and M as above.
> Choose a prime P, larger than S.
> Let c[0] be S.
> Choose random values less than P for c[1] through c[M-1].
> For i from 1 through N, compute (all arithmetic mod P)
> h[i] = sum(j=0..M-1) (c[j] i^j) [^ is exponentiation]
> Share #i is then the triple <P,i,h[i]>.
>
> How the shares are stored is up to those charged with protecting them;
> they can store them encrypted if they want. Only the h[i] value needs
> to be protected.
>
> Now, given any M shares, you can set up M equations
>
> h[i] = sum(j=0..M-1) (c[j] i^j) (mod P, of course)
>

huh? No polynomial regression like in shamir's scheme? (as if I
actually understand the math here)

> for the i and h[i] values in the shares. (Of course, if the P values
> in the shares aren't all equal, at least one of the shares has been
> corrupted.) This is a system of M linear equations in M unknowns (the
> c[] values). Given how the coefficients of this system were chosen
> (the i^j values), they will be linearly independent and the system thus
> has a unique solution (since P is prime, division mod P works and
> Gaussian elimination can be performed). Solve it, and c[0] will be the
> secret. (You can throw away c[1] through c[M-1]; they were randomly
> chosen at split time and carry no information.)
>
> But if you have fewer than M shares, you can set up at most M-1
> equations. Such a system is not solvable, and since we're working in
> the finite field Z_P, you actually cannot discover anything about S; by
> introducing a fictitious additional share with a suitable h[] value,
> you can arrange to make c[0] come out to any value you please.
>
> If you have more than M shares, the system is overdetermined. You can
> pick any M of the shares, reconstruct the c[] values, and check that
> what you get agrees with the redundant shares. (You actually don't
> *have* to check, but it allows you to catch some cases of corrupted
> shares.)
>
> I've written software that implements this. See
> ftp.rodents.montreal.qc.ca:/mouse/local/src/secretsplit/.
>

*brain explodes* ouch. OK I won't read that right now. . . maybe I'm
better off trying to understand the math than the code.

> /~\ The ASCII der Mouse
> \ / Ribbon Campaign
> X Against HTML mouse@rodents.montreal.qc.ca
> / \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
>

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be
wasted on re-inventing the wheel when there are so many fascinating
new problems waiting out there.
-- Eric Steven Raymond
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCFzAThDd4aOud5P8RApzXAJ9d2ITFaRnp5aeZAvVChl n/VDSIpQCfbBvO
VuECaAj0Xqt4dA8iVgS5zDU=
=r0Jx
-----END PGP SIGNATURE-----

[Robert C. Helling]

On Sat, 19 Feb 2005, John Richard Moser wrote:

> Yeah I noticed that on the wikipedia :)
>
> http://en.wikipedia.org/wiki/Secret_sharing

I would like to add that both schemes described there are essentially
equal as both make use of the fact that a T dimensional subspace U of an N
dimensional vector space V (for example a vector space of polynomials) is
encoded by giving T linearly independent vectors in U.


Data can now be encoded by thinking of it as a functional

f: T ---> F

that is a linear function that maps T into the field F over which T is a
vector space.

Now for each bearer i of a part of the secret give him a vector b_i in U
(in terms of T coordinates) and his share of the data is e_i = f(b_i).

If T bearers come together, they can combine their T vectors b_i into a
TxT matrix M and compute M^(-1) (if they are linearly independent).
Finally, acting with M^(-1) on the vector of the T e_i's recovers the
original functional f.

Note that if you want to share more data f1...fk you need to compute the
b_i and thus M^(-1) only once and then you pass on the f_n(b_i).

For a practical implementation you could for example use the unique field
F_256 of dimension 256 and do arithmetic using look up tables. See for
example the perl scripts

http://www.damtp.cam.ac.uk/user/rch47/split.pl

for the sharing/combining of the data and

http://www.damtp.cam.ac.uk/user/rch47/gf2.pl

for the finite field arithmetic.

Robert

--
..oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo.oOo. oOo.oOo.oOo.oOo.oOo.oOo.oOo.oO
Robert C. Helling School of Science and Engineering
International University Bremen
print "Just another Phone: +49 421-200 3574
stupid .sig\n"; http://www.aei-potsdam.mpg.de/~helling

[Gandalf The White]

Greetings and Salutations:

On 2/18/05 1:42 AM, "John Richard Moser" <nigelenki@comcast.net> wrote:
> In the case of (X,Y), [xxxx] and [yyyy] must provide enough data to
> decrypt [zzzz]
> In the case of (X,Z), [xxxx] and [zzzz] must provide enough data to
> decrypt [yyyy]
> In the case of (Y,Z), [yyyy] and [zzzz] must provide enough data to
> decrypt [xxxx]

This sounds like encryption blended with RAID striping, or (as is used on
the binaries for the newsgroups now) the PAR files or PAR2 files.

Ken

---------------------------------------------------------------
Do not meddle in the affairs of wizards for they are subtle and
quick to anger.
Ken Hollis - Gandalf The White - gandalf@digital.net - O- TINLC
WWW Page - http://digital.net/~gandalf/
Trace E-Mail forgery - http://digital.net/~gandalf/spamfaq.html
Trolls crossposts - http://digital.net/~gandalf/trollfaq.html

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



David Schwartz wrote:
>>The authentication works as below:
>>

[...]

>
> There's a ludicrously simple and incredibly brilliant way to do this. For a polynomial of order N, you need N points on the polynomial to find the equation that describes the polynomial. So if you want to share a secret amount 28 people such that any 1
5 are needed to know it, just make the secret the coefficients of a 15th order polynomial and compute 28 points that satisfy the polynomial.
>
> So, for the 28/15 example, pick 15 random coefficients (C1, C2, C3, ...), and then your 28 pieces of the key (K1 ... K25) are the solutions to:
>
> Kx = C1 + C2 * x + C3 * x^2 + C3 * x^3 ... C15 * x^14
>

Math check here, wikipedia seems to think:

If the players store their shares on insecure computer servers, an
attacker could hack in and steal the shares. If it is not practical to
change the secret, the uncompromised (Shamir-style) shares can be
renewed. The dealer generates a new random polynomial with constant term
zero and calculates for each remaining player a new ordered pair, where
the x-coordinates of the old and new pairs are the same. Each player
then adds the old and new y-coordinates to each other and keeps the
result as the new y-coordinate of the secret.

-- http://en.wikipedia.org/wiki/Secret_sharing

I'm confused: "polynomial with constant term zero" "The dealer encodes
the secret as the curve's y-intercept"

now after playing with my calculator I suddenly remember something about
any polynomial's Y intercept being the constant term. See, if all the
coefficients are 999999999999999999999999999999999999999999999999,
multiplied by X=0, the result is still 0.

Is wikipedia wrong here? Or do I have a misunderstanding of "constant
term"?

> For x=1 to 28.
>
> With any 15 solutions to the equation above, you can compute C1 through C15. With any 14, you can't even get started.
>
> DS
>
>
>
> DS
>
>
>

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be
wasted on re-inventing the wheel when there are so many fascinating
new problems waiting out there.
-- Eric Steven Raymond
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCF7bKhDd4aOud5P8RAjh+AJ4kiBsTrlQPQm3X91tJA1 SvzIZ/5ACfXsxU
Wy9zXBIuwYn88tfDqvh65iY=
=64ST
-----END PGP SIGNATURE-----

[Valdis.Kletnieks@vt.edu]

--==_Exmh_1108880508_10838P
Content-Type: text/plain; charset=us-ascii

On Fri, 18 Feb 2005 02:42:44 EST, John Richard Moser said:

> The problem is that I need a guaranteed way to create data for any valid
> N and M where N >= 3 > M >= 2 in which access to M fragments of the key
> (each fragment is encrypted) can be used to gain access to the rest of
> the fragments, which in turn allows any selection of M users to
> authenticate and gain physical access to the key.

Schneier's 'Applied Cryptography' discusses "secret sharing" schemes, and
chasing the references from there should be sufficient.

> Reminder that the idea here is to use a physical method, not bare access
> control that can be evaded by loading a modified kernel.

Not sure what you mean by "a physical method", unless you go to something like
the old "2 keys must be inserted at the same time in slots more than an arm's
reach apart" type of scheme.

--==_Exmh_1108880508_10838P
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Exmh version 2.5 07/13/2001

iD8DBQFCGCx8cC3lWbTT17ARAgbzAKDZBUMET4n9o8zlouSzsG 2YFqvynwCgvE2d
S8rLrKO81sOcTv/8S51scSE=
=bSkf
-----END PGP SIGNATURE-----

--==_Exmh_1108880508_10838P--

[Ruud H.G. van Tol]

John wrote:
> The most obvious methods I can think of create explosive data growth
> as M and N increase. The amount of data needed in any way I can think
> of grows linearly with M and exponentially with N.

The data remains encrypted, until the key is known. So only the key needs to
be distributed. Keywords: Reed-Solomon, FEC, Vandermonde matrices, PAR2.
Extra requirement is, that you don't want 90% of the key known when M=10 and 9
key-secrets are collected, so you need an extra 'layer'.

A change of 1 bit in one 'layer' should change in average 50% of the bits in
the next 'layer', because basically you want each key-bit to remain unknown
(and unguessable) until (at least) M secrets are known.

--
Grtz, Ruud

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Valdis.Kletnieks@vt.edu wrote:
> On Fri, 18 Feb 2005 02:42:44 EST, John Richard Moser said:
>
>
>>The problem is that I need a guaranteed way to create data for any valid
>>N and M where N >= 3 > M >= 2 in which access to M fragments of the key
>>(each fragment is encrypted) can be used to gain access to the rest of
>>the fragments, which in turn allows any selection of M users to
>>authenticate and gain physical access to the key.
>
>
> Schneier's 'Applied Cryptography' discusses "secret sharing" schemes, and
> chasing the references from there should be sufficient.
>
>
>>Reminder that the idea here is to use a physical method, not bare access
>>control that can be evaded by loading a modified kernel.
>
>
> Not sure what you mean by "a physical method", unless you go to something like
> the old "2 keys must be inserted at the same time in slots more than an arm's
> reach apart" type of scheme.

In essence, if you encrypt something, and destroy the key, you destroy
the data. At least, the point of encrypting something is so that it
"can't" (reasonably) be accessed without the key (or a 4096 qubit
computer) (in the life of the universe). There's no point to cyphering
something if it can be retrieved without the key in some interval which
ends within the period that the data is supposed to remain secret.

Because of this, I consider encryption to be a physical barrier. You
can get the disk, you can use another OS on it, you can hardware hack
the machine, you can take it apart, you can do a MFM examination, splice
it in a chemical vat, spectral analyze it, put it in a tractor beam and
try to extract the data that way, fire phasers at it, whatever, you
don't get to the data without the key.

(note too that a lock is a physical barrier; but a good sledgehammer
will shatter the mechanism if it's bigger than the lock)

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Creative brains are a valuable, limited resource. They shouldn't be
wasted on re-inventing the wheel when there are so many fascinating
new problems waiting out there.
-- Eric Steven Raymond
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCGNBThDd4aOud5P8RAtQGAJ0UJ3rtj6G7YHtcgIvrFw MGw+rVrQCgiVd6
C0IM1xhECUl9Yuh5F71ExDs=
=+BN2
-----END PGP SIGNATURE-----