🚀 go-pugleaf

Thus said ted@nmsu.edu (Ted Dunning):
>perhaps a more interesting (in the sense of puzzle solving) problem is
>how to extend pgp so that you can send a message that ALL of a group
>have to agree to read.  of course, it isn't that much harder than the
>previous puzzle, but it is fun.

An interesting generalization of the above is how to cryptographically
create a situation whereby any m people in a group of n (of course,
the problem is only hard when n > m > 1) must cooperate to read a
message.  I seem to recall having heard that it's possible, but I
don't remember the details.
--
Marc VanHeyningen    mvanheyn@whale.cs.indiana.edu    MIME & RIPEM accepted


The number of millionares in the U.S. has increased fourteen fold since 1980.

In article <1993Jan23.192239.14870@infodev.cam.ac.uk> gtf1000@cus.cam.ac.uk (G.T. Falk) writes:

   I was talking to mathew <mathew@mantis.co.uk> today and the following
   topic came up. How could you make a PGP message which could be read by,
   say, any of certain people, but nobody else?

	... the straightforward answer deleted ...



perhaps a more interesting (in the sense of puzzle solving) problem is
how to extend pgp so that you can send a message that ALL of a group
have to agree to read.  of course, it isn't that much harder than the
previous puzzle, but it is fun.

** answer below **


for N recipients to have to cooperate to read a message, you can make
up a session key, and then make up N-1 random numbers each the length
of the session key.  you then follow Falk and Mathew's suggestion and
encrypt each of these random numbers with the first N-1 users' public
keys.  then you use the last users' public key to encrypt the XOR of
the N-1 random numbers and the true session key.  using this method,
all N of the readers must decrypt their parts of the key so that all
parts can be combined using XOR before the message can be read.
signature methods can be used to verify that each reader is willing, but
a bit of a trick is needed to assure that all readers gets just as
much information as any other.

PGP 2.2 *WILL* have multiple-recipient encryption!  The code is done.
The patches are in.  All that's needed is a 2.2 release to happen!

-derek

PGP 2 key available upon request, or via AFS:
	/afs/athena.mit.edu/user/w/a/warlord/pgp-pubkey.asc
--
  Derek Atkins, MIT '93, Electrical Engineering and Computer Science
      Chairman, MIT Student Information Processing Board (SIPB)
           MIT Media Laboratory, Speech Research Group
           warlord@MIT.EDU       PP-ASEL        N1NWH

In alt.security.pgp, article <WARLORD.93Jan24213831@snorkelwacker.mit.edu>,
  warlord@MIT.EDU (Derek Atkins) writes:
> 
> PGP 2.2 *WILL* have multiple-recipient encryption!  The code is done.
> The patches are in.  All that's needed is a 2.2 release to happen!
> 
While we're on the subject of new releases..:
- Nonblocking I/O is not undone when an interrupt signal is received.
- No gratuitious appending of suffixes for command-line arguments please.
  UNIX isn't DOS.
- Make pgp -kxaf work. Ditto pgp -kaf.
- When extracting a key, I'd like to select which certifications for
  that key get exported.
- How do I get pgp -fst/-fsat to not encode the message I want to sign?
- Thoughts about better MIME integration? The MIME multipart stuff
  would be a far better idea than these BEGIN PGP lines.
  Define an "application/pgp" subtype ?

-- 
No matter how subtle the wizard, a knife in the shoulder blades will
seriously cramp his style.
-- 
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.1

mQBYAitirlIAAAECWLA75SRTAZb8WsAB4kJCAmxM4h01UgErYLqOCOolntDCA502
Zr6rqV39QKwx6tton9AtTgPKrfdz6ufnAL9E45BJgO4zcJBNac3pMwAFEbQoTWF0
dGhpYXMgVXJsaWNocyA8dXJsaWNoc0BzbXVyZi5zdWIub3JnPg==
=FMCO
-----END PGP PUBLIC KEY BLOCK-----
-- 
Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/

In article <1993Jan24.213350.17257@news.cs.indiana.edu>, Marc VanHeyningen <mvanheyn@whale.cs.indiana.edu> writes:
> An interesting generalization of the above is how to cryptographically
> create a situation whereby any m people in a group of n (of course,
> the problem is only hard when n > m > 1) must cooperate to read a
> message.  I seem to recall having heard that it's possible, but I
> don't remember the details.

I suspect you're thinking of

@article{sharesecret,
   author = {Adi Shamir},
   journal = {Communications of the ACM},
   number = {11},
   pages = {612-613},
   title = {How to Share a Secret},
   volume = {22},
   year = {1979}
}

This relies on polynomial interpolation.  If you're missing even one
piece of the shared key, all possible values become equally likely.

A totally different way to solve the same problem is given in

@article{sealing,
   author = {David K. Gifford},
   journal = {Communications of the ACM},
   number = {4},
   pages = {274--286},
   title = {Cryptographic Sealing for Information Secrecy and Authentication},
   volume = {25},
   year = {1982}
}

Gifford shows how to use a combination of symmetric and asymmetric
cryptography to implement things like Key-And, Key-Or, the problem
described above, etc.

-----BEGIN PGP SIGNED MESSAGE-----

gtf1000@cus.cam.ac.uk (G.T. Falk) writes:

> I was talking to mathew <mathew@mantis.co.uk> today and the following
> topic came up. How could you make a PGP message which could be read by,
> say, any of certain people, but nobody else? E.g. if you had a mailing
> list and wanted anybody on the list to be able to read the message, they
> could, without having to send out individually encrypted messages to
> everybody.

This has been discussed in alt.security.pgp. Yes, it can be easily
implemented and indeed in the way proposed by you. Version 2.2 of PGP
will have this feature. The only problem will be that such "multiple
encrypted" messages will not be readable by older versions of PGP
(just like a clearsig message is not verifiable with PGP 2.0).

Regards,
Vesselin

-----BEGIN PGP SIGNATURE-----
Version: 2.1

iQCVAgUBK2RBnTZWl8Yy3ZjZAQG4sAQAx2S6zmecm//Y+jvS5HKd1QlQoTTQiCMC
7wsBR/wETDAO1+7S4DgGkPAvEjHK/M5ldEtoWJOPoKCpV4enfUEOjve96gohQbJB
Cb2BsH84xQ5+i3P7zxu9Dwd3zxRF01O27W91Bhobax3bIA+2B7/ZxzEIpJ0DogO0
uPCzr171Y9E£Zs
-----END PGP SIGNATURE-----
--
Vesselin Vladimirov Bontchev          Virus Test Center, University of Hamburg
Tel.:+49-40-54715-224, Fax: +49-40-54715-226      Fachbereich Informatik - AGN
< PGP 2.1 public key available on request. > Vogt-Koelln-Strasse 30, rm. 107 C
e-mail: bontchev@fbihh.informatik.uni-hamburg.de    D-2000 Hamburg 54, Germany

In article <1k0d74$92c@smurf.sub.org> urlichs@smurf.sub.org (Matthias Urlichs) writes:

   While we're on the subject of new releases..:
   - Make pgp -kxaf work. Ditto pgp -kaf.

Done.  These will also be in 2.2!  :-)

   - When extracting a key, I'd like to select which certifications for
     that key get exported.

What do you mean?  What *kind* of certificates?  Signatures?  ID's?

   - How do I get pgp -fst/-fsat to not encode the message I want to sign?

pgp -fsat +clearsig=on

   - Thoughts about better MIME integration? The MIME multipart stuff
     would be a far better idea than these BEGIN PGP lines.
     Define an "application/pgp" subtype ?

I've heard people talking about this.  You want to do it?  ;-)

-derek

PGP 2 key available upon request, or via AFS:
	/afs/athena.mit.edu/user/w/a/warlord/pgp-pubkey.asc
--
  Derek Atkins, MIT '93, Electrical Engineering and Computer Science
      Chairman, MIT Student Information Processing Board (SIPB)
           MIT Media Laboratory, Speech Research Group
           warlord@MIT.EDU       PP-ASEL        N1NWH

urlichs@smurf.sub.org (Matthias Urlichs) writes:

>In alt.security.pgp, article <WARLORD.93Jan24213831@snorkelwacker.mit.edu>,
>  warlord@MIT.EDU (Derek Atkins) writes:
>>
>> PGP 2.2 *WILL* have multiple-recipient encryption!  The code is done.
>> The patches are in.  All that's needed is a 2.2 release to happen!
>>
>While we're on the subject of new releases..:

To add my own two problems:
1) The OS/2 port refuses to accept input from stdin, for stuff like "Y/N"
prompts this would be nice for those of us developing shells.  (I have my
suspicions why direct keyboard input is required to create the random seed(s),
but for ordinary input this shouldn't be necessary.)

2) Output to a pipe does not work - PGP tries to rename the "file" it finds,
when it cannot, it prompts for a new filename.  (Simply allowing an overwrite
option should work wonderfully... preferably as a default or a command line
parameter.)

Thanx,
Don
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Don Meyer     Network Manager, UIUC College of Ag Microcomputer Facility
internet:     dlmeyer@uiuc.edu
member:       NRA, ISSC, IL Farm Bureau	 "Don't blame me, I voted Libertarian!"
					    Nancy Lord in '96!

In article <C1Fqq9.1wG@ux1.cso.uiuc.edu> meyer@ux1.cso.uiuc.edu (Don Meyer) writes:

   To add my own two problems:
   1) The OS/2 port refuses to accept input from stdin, for stuff like "Y/N"
   prompts this would be nice for those of us developing shells.  (I have my
   suspicions why direct keyboard input is required to create the random
   seed(s), but for ordinary input this shouldn't be necessary.)

this is true on UNIX, too.  That is because the Y/N code opens the tty
to read the values.  I agree that there should be some way to override this.
Which particular cases are you trying to shell around?

   2) Output to a pipe does not work - PGP tries to rename the "file"
   it finds, it cannot, it prompts for a new filename.  (Simply allowing
   an overwrite option should work wonderfully... preferably as a
   default or a command line parameter.)

What do you mean?  I've never had much problem with this.

-derek

PGP 2 key available upon request, or via AFS:
	/afs/athena.mit.edu/user/w/a/warlord/pgp-pubkey.asc
--
  Derek Atkins, MIT '93, Electrical Engineering and Computer Science
      Chairman, MIT Student Information Processing Board (SIPB)
           MIT Media Laboratory, Speech Research Group
           warlord@MIT.EDU       PP-ASEL        N1NWH

warlord@MIT.EDU (Derek Atkins) writes:

>this is true on UNIX, too.  That is because the Y/N code opens the tty
>to read the values.  I agree that there should be some way to override this.
>Which particular cases are you trying to shell around?

I'm trying to cover as many bases as I possibly can.  Although for key
creation I'm afraid I'm going to be limited to bringing the child process to
the forground and letting the user interact on his/her own.  All others I
need to be able to feed as stdio, however.

>   2) Output to a pipe does not work - PGP tries to rename the "file"
>   it finds, it cannot, it prompts for a new filename.  (Simply allowing
>   an overwrite option should work wonderfully... preferably as a
>   default or a command line parameter.)

>What do you mean?  I've never had much problem with this.

Maybe this one is OS/2 implementation specific.  I'd bust out the source to
have a look, but I'm a bit constrained already as far as disk space...

Don
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Don Meyer     Network Manager, UIUC College of Ag Microcomputer Facility
internet:     dlmeyer@uiuc.edu
member:       NRA, ISSC, IL Farm Bureau	 "Don't blame me, I voted Libertarian!"
					    Nancy Lord in '96!

"Clinton/Gore -- The American people deserve what they voted for!"

-----BEGIN PGP SIGNED MESSAGE-----

Date: 28 Jan 93 09:09:46 GMT
warlord@MIT.EDU (Derek Atkins) writes:

>    - When extracting a key, I'd like to select which certifications for
>      that key get exported.

> What do you mean?  What *kind* of certificates?  Signatures?  ID's?

I'm not certain what he means, but I would like to be able to do the
following:

It should be possible to tell PGP to extract not only a single public
key (with its signatures), but also the public keys of all people who
have signed that particular public key, the public keys of the people
who have signed their public keys, and so on recursively. I.e., to
extract a whole "net of trust" from a public keyring. This way the
person who receives this will get as few "Unknown signator" messages
as possible.

And while I am in my "wish list" mode - it should be possible to
extract more than one public key. That is, the command

	pgp -kxa john

should extract all public keys that could be seen with the command

	pgp -kv john

just like

	pgp -kxa '*'

extracts the all public keys available in the keyring.

Regards,
Vesselin

-----BEGIN PGP SIGNATURE-----
Version: 2.1

iQCVAgUBK2ekPzZWl8Yy3ZjZAQFwswQAqysbTkfEb3tzTgVHAz7g9I6Q8yog1yNA
MldIc7WnRrTTnLEHjP58S5vsy0vMfc0DuW8bA4sIbcehOjvm10s3egUk6kfrgJdI
V+QC9H/2sUI1Vc61Js37tsiKcDwrkud/FsTylVBJV/PjFT2PnONJz73vaUbQjipY
h45jE3GPKac=nEnL
-----END PGP SIGNATURE-----
--
Vesselin Vladimirov Bontchev          Virus Test Center, University of Hamburg
Tel.:+49-40-54715-224, Fax: +49-40-54715-226      Fachbereich Informatik - AGN
< PGP 2.1 public key available on request. > Vogt-Koelln-Strasse 30, rm. 107 C
e-mail: bontchev@fbihh.informatik.uni-hamburg.de    D-2000 Hamburg 54, Germany

Marc VanHeyningen <mvanheyn@whale.cs.indiana.edu> writes:

>An interesting generalization of the above is how to cryptographically
>create a situation whereby any m people in a group of n (of course,
>the problem is only hard when n > m > 1) must cooperate to read a
>message.  I seem to recall having heard that it's possible, but I
>don't remember the details.

Wouldn't the Chinese Remainder Theorm be useful for this?  I don't have
details, but maybe someone can post the innards of the theorm.


David Willmore
willmore@iastate.edu
--
---------------------------------------------------------------------------
willmore@iastate.edu | "Death before dishonor" | "Better dead than greek" |
David Willmore  | "Ever noticed how much they look like orchids? Lovely!" |
---------------------------------------------------------------------------