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]

Message-ID: <Pine.LNX.4.60.0502191013500.20256@zeus.itg.uiuc.edu>
Date: Sat, 19 Feb 2005 10:32:17 -0600 (CST)
From: Damian Menscher <menscher@...c.edu>
To: John Richard Moser <nigelenki@...cast.net>
Cc: bugtraq@...urityfocus.com
Subject: Re: Joint encryption?

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@...c.edu> www.uiuc.edu/~menscher/ Fax:(217)333-9819 |#=-
-=#| The above opinions are not necessarily those of my employers. |#=-