Requiring a "supervisor" key pair and a "user" key pair to decrypt multiple-recipient messages

Question

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?

Answer 1

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.

Answer 2

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.

Let me also add Eve:

• 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 https://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.

What about padding?

I'm assuming you're using an off-the-shelf high-level implementation of symmetric-key encryption -- such as, for example, practically any program that supports AES-encrypted ".zip" files. I'm assuming you're using an off-the-shelf high-level implementation of public key encryption -- such as, for example, practically any program that supports the standard OpenPGP format.

That software should automatically use, by default, a good mode of operation -- the software should generate initialization vectors, handle padding, etc. with no extra effort on your part. If it doesn't, I recommend switching to some other code library that is easier to use.

Answer 3

Your original idea is the correct one:

1) Encrypt the message with a symmetric key. (EM1)
2) Encrypt the symmetric key with Alice's public key. (AM1)
3) Encrypt the symmetric key again with Mark's public key. (MM1)
4) Encrypt (EM1 + AM1 + MM1) with Jim's public key. (Final)

The final message will first require Jim's decryption, leaving him with three messages he cannot read. He the sends Alice EM1 & AM1, but denies Mark access to MM1, thus depriving him of the original message.

As for multiple levels of encryption, there is no need to be concerned.

Answer 4

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.