# Requiring a “supervisor” key pair and a “user” key pair to decrypt multiple-recipient messages

I've been toying with some encryption scenarios recently. One of the hard ones I came across is a multi-party system.

So we have

1. Bob -- The person who sends the message (and knows it's recipients)
2. Jim -- The person who supervises who is capable of decrypting the message(but can not decrypt the message himself)
3. Alice -- The person who wants to receive the message
4. Mark -- The person who also wanted to receive the message, but after Bob sent the message his private key was compromised

For example sake, Bob must post his encrypted message on a public message board. Ideally, Alice and Mark would see the message and know it's intended for them, but they can't decrypt it by themselves. They must ask Jim to apply his decryption skills on the public data first. Jim trusts who is asking for the message because he knows their public keys(and asks for a dynamic signed piece of data or some such). Of course though, Jim won't apply his magic for Mark because he was notified that Mark had been compromised. So, Mark is left in the dark with an undecipherable message

Also, Jim is minimally trustable. So, if Jim wanted to hand the message to some untrusted party, it'd still be fairly useless, unless they themselves learned of one of it's intended recipient's private key as well.

I'm trying to work out the best way to actually do this. Here is one idea:

1. Bob encrypts his message with a symmetric algorithm.
2. Bob encrypts the symmetric key against Alice's and Mark's public key using his private key (two separate "key messages" are thus made)
3. Finally Bob encrypts both of the key-messages against Jim's public key using his private key

I think this would work. However, I have some concerns

• I'm double-encrypting things, which sounds like trouble
• I'd have to be encrypting basically the same piece of data against two different keys. Does this leave me vulnerable to cryptoanalysis? What about padding?

Ideally, the first algorithms that came to mind for symmetric encryption is AES. For asymmetric encryption, I was thinking RSA. Is there a better choice?

Is there any better way of managing such a scenario where you have a "supervisor" which mitigates the risks of a private-key compromise for messages sent to multiple recipients?

-
I think there's something wrong with your proposal. How does step 1 work, if Bob knows the message and Jim doesn't? What does it mean to encrypt with a private key? (Are you talking about signing? Signatures are not the same thing as encrypting with a private key.) When you say "his", who does that pronoun refer to: Jim, Bob, or Mark? –  D.W. May 23 '13 at 16:20
@D.W.: I'm fairly sure that "Jim" in steps 2 and 3 should be "Bob", and have edited the question accordingly. I'm not sure what, if anything, the phrase "using his private key" as a whole is supposed to mean, though (unless perhaps it means that Bob signs the messages he encrypts with his (Bob's) private key). –  Ilmari Karonen May 24 '13 at 18:16

Have you considered using Shamir's Secret Sharing algorithm?

First, Bob encrypts the message with a symmetric algorithm. Then, he divides the secret key into four parts using SSA such that it requires three parts to decrypt (a $(3,4)$ threshold). Bob then distributes one part each to Alice and Mark, and two parts to Jim.

When Alice wants to decrypt, she needs has to have both of Jim's parts plus her part. If Mark wants to decrypt, he similarly needs both of Jim's parts plus his part.

Alice and Mark cannot collude to cut Jim out of the middle, because they have only two parts between them, and decryption requires three. And because Jim has only two parts himself, he cannot decrypt the message unless Alice or Mark shares their part it with him.

Finally, Jim can withhold his parts from anyone he no longer trusts.

-
How would this work with N number of destination parties? –  Earlz Apr 23 '13 at 0:35
Actually that might not matter. I'm still interested in the answer, but in this scenario it might be better for if Jim died, then all the recipients could come together and unlock it or something –  Earlz Apr 23 '13 at 1:10
Jim has to have the same number of shares as the number of other people, p. The number of shares to decrypt must be p+1. The total number of shares must be p*2. Without at least one of Jim's shares, the secret is safe from everyone else. Jim does not have enough shares by himself. It's a "simple majority +1" scenario. –  John Deters Apr 24 '13 at 19:51
After pondering on this solution a while longer, I came to a bit of a stand-still. Mainly, I never want for any one person to have the complete key for unlocking the public message. Say Jim supervises over Alice and Matt. In this proposed method, the same key would potentially be encrypted with different private-keys, giving attackers a possible way in (since they know the text contained). Maybe double symetric encryption? I'm not sure –  Earlz Apr 27 '13 at 2:22
So this is still the solution you are looking for. No one person has enough shares to decrypt it. SSS is used to reveal only the one secret key, which is for a symmetric algorithm like AES, used to encrypt the sensitive data. AES has no known clear text attack, so it's safe. SSS leaks no info about the other keys, so it's also safe. –  John Deters Apr 27 '13 at 4:24

It doesn't seem like your goals are achievable.

You said you want Jim to be able to designate who can decrypt, but you don't want Jim to be able to decrypt himself. Those two requirements are not simultaneously satisfiable. If Jim can designate who can decrypt, Jim can designate himself (or, Jim can designate one of his friends/collaborators, Jane, who will decrypt and share the result with Jim).

Perhaps you might want to re-examine your requirements and revise them accordingly.

-
No, he said he wants Jim to be able to supervise (not designate) who can decrypt, $\hspace{1.4 in}$ without being able to decrypt himself. $\:$ The sensible interpretation of this is that Jim controls $\hspace{1 in}$ who among the people selected by Bob can decrypt. $\;\;$ –  Ricky Demer May 23 '13 at 20:50
Ahh, that makes a lot more sense. Thanks, @RickyDemer. If that is the intent, I think the question should be edited to be a clearer about the intent. –  D.W. May 23 '13 at 22:13
The SSS solution above gives Jim that ability. When he gives all his key parts to Alice, Alice now has the ability to decrypt - if Jim never gets a share in return (and why should he?) Jim still can not decrypt. It does give Alice enough shares to enable Mark to decrypt, but if she can be trusted with the message, she already has the level of trust required not to irresponsibly disclose the message or keys. It does imply that the SSS step has to happen on a per-message basis, though. –  John Deters May 24 '13 at 16:10

All too often I describe some process saying that "he" did something to "his" message, and it makes sense in my own head, but no one else can figure out which of the several people involved that those pronouns refer to. Or worse -- sometimes I say that "the message is encrypted", but I don't say who does it and with which key.

That's why all the good cryptographers describe processes using Alice and Bob, avoiding pronouns -- even if they have to use "Bob" six times in one sentence.

Have you considered maybe possibly editing your question by replacing all the pronouns with names? That would make it much easier for us to figure out what you're trying to ask.

• Eve stole Mark's private key.
• Bob wants to send a message to Alice and Mark, but Bob doesn't want anyone else to read it -- in particular, Bob doesn't want Jim or Eve to read it. However, Bob wants Jim to be able to block Eve from reading the message, even it means that Mark can't read the message after all. Also: Bob is in a remote location where every message Bob sends must go over a public network that people like Eve can read.
• Mark wants to receive the message, but after Bob sent the message, Mark found out that Eve stole Mark's private key, and Mark immediately informed Jim of the breach.
• Jim is pretty reliable, but he's in yet another remote location where every message Jim sends or receives must go over a public network that people like Eve can read.

The SSS system that John Deters describes sounds good. Another approach (similar to the TOR onion routing system) could be:

• Assume Bob, Jim, Mark, and Alice have previously shaken hands and traded public keys with everyone else in the group.

• Bob sends a message M1 to Jim, and M6 to Mark and Alice.

• Sometime after Bob sends his messages, Eve steals Mark's private key.

• Jim somehow learns of this key compromise before he gets the message from Bob.

• Jim authenticates that the message M1 really came from Bob, then decrypts it with Jim's private key, resulting in a partially decrypted message M2 that says something like "Please forward this message to Mark: " followed by an encrypted message M3 and "Please forward this message to Alice: " followed by encrypted message M4.

• Since Jim can't send anything to Mark any more (since if he does, Eve would also be able to read the message), he shreds M3.
• (optional) Jim authenticates that M4 really came from Bob.
• Jim sends M4 to Alice without change.

• (If Jim learns that Alice's key was compromised after he sends message M4 out, it's too late -- there's nothing anyone can do to prevent whoever stole Alice's key from recovering the plaintext message).

• Alice authenticates that M4 really came from Bob, then decrypts it with Alice's private key, resulting in a plaintext message M5.

• (optional) perhaps M5 is actually a symmetric key. Bob encrypts the original long plaintext message with key M5 and then signs the resulting ciphertext, sending the resulting signed message M6 directly to Alice and Mark. Once Alice authenticates that M6 really came from Bob, Alice uses M5 to decrypt M6 and recover the original long plaintext message.

Even after Eve collects all the public messages -- M1, M4, and M6 -- Eve still cannot recover the original long plaintext message, unless Jim colludes with Eve by leaking M3, or Alice colludes with Eve by leaking M5 or the original long plaintext message or Alice's private key.

• double-encrypting things, which sounds like trouble
• encrypting basically the same piece of data against two different keys

Neither one is really a problem in practice, assuming you are using a modern encryption system.

Generating many encrypted messages, each one a singly-encrypted ciphertext of the same data but encrypted using a different public key, is a key part of the standard way of generating standard OpenPGP encrypted files intended for more than one recipient. (It actually generates many short encrypted "packets", each one encrypted with a different public key, but all of them representing the same symmetric key).

Encrypting some plaintext with one key, and then encrypting the resulting ciphertext with some other key, and then encrypting that resulting ciphertext with yet another key, is a common operation in the TOR anonymity network.

There is a lot of confusion about both approaches -- see http://crypto.stackexchange.com/search?q=double+encryption .

Historically, some classic encryption algorithms had problems with one or the other or some similar-sounding setup. In particular, the infamous "two time pad".

However, modern algorithms generally use a mode of operation that makes such attacks just as difficult as the full brute-force attack -- i.e., infeasible.