Re: Joint encryption?

[John Richard Moser <nigelenki@xxxxxxxxxxx>]

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

iD8DBQFCF3GqhDd4aOud5P8RAqcrAJ9wZd8iwfkhynmCmwpbXRcHYd5WCwCghCHj
eamxaMiaqMUHsYobyS3pq8o=
=kH/k
-----END PGP SIGNATURE-----