Date: Fri, 18 Feb 2005 02:42:44 -0500
From: John Richard Moser <nigelenki@...cast.net>
To: bugtraq@...urityfocus.com
Subject: Joint encryption?


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

iD8DBQFCFZx0hDd4aOud5P8RAl70AJ0dVr5wYHu3ynVz8gyluXxNnc0R4gCfbjGQ
i7bqRwgdlQcosF7CcsW3oM0=
=9Q6x
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists