bugtraq - RE: Joint encryption?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sat, 19 Feb 2005 12:13:59 -0800
From: "David Schwartz" <davids@...master.com>
To: <bugtraq@...urityfocus.com>, <nigelenki@...cast.net>
Subject: RE: Joint encryption?



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

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

	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