2

I have the following setting: enter image description here Let A, A', A'' be different mobile devices. They want to sent a secret message M to all (or some of) the C,C', C''. The message is passed on to B that stores it for some time, and passes is on to the different C.

Now I am looking for an encryption scheme, such that A encrypts the message, and only the different C can decrypt it.

My first idea was to simply use the public keys of the different C. However, since B stores the encrypted messages for some time, and we have many copies of the message encrypted with the different private keys, this would not be efficient in terms of storage.

My next idea was to use a common key for the A and C, so that the message is encrypted with this secret key, and then passed on to B that does not posses this key. However, in this case I have the problem of how to generate a secret key between all these participants, that only communicate via B, and how to I handle the situation when a new A or C joins in.

Another idea is to use commutative encryption. However in this case the A and C will depend on the trustworthiness of B. Let A encrypt the message with the key of B, then B stores it encrypted. Then it encrypts it with the public keys of the C and decrypts with its own secret key. B never actually saw the message, would however been able to do so.

What will be the easiest scheme, so that we can easily update all key material, can easily have devices join in and store only one encrypted version of the secret messages without B being able to read it? Is there any efficient multi-party-encryption scheme with an easy handling of the key-material?

I was already referred to the Signal scheme. I am however lost in the scheme amount of algorithms they use. And I think the key-update process in my setting would be more complex, since all communication must pass by B.

If anyone understands my confusing explanation and has some idea of how I can solve this, any help or hint would be very much appreciated!

All the best,

Luca

Luca
  • 125
  • 4
  • Are `C, C' & C''` associated with the same account? If they are then how does A determine to which device of C message to be sent? From the figure it looks like B forwards the message to all of the devices of C. – defalt Aug 26 '19 at 13:58
  • The different C are different accounts. Somehow it must be tagged to the encrypted message to which C the message is sent. (my next problem ;) ) – Luca Aug 26 '19 at 14:43

1 Answers1

1

You can use the same way as WhatsApp group messaging does.

Heavily oversimplifying it, this is what you can do:

  1. Each member generates their own symmetric key called Sender key.

  2. Every member shares their sender key with each other through one-to-one encryption scheme. In your case, you can share this key by encrypting it with their public keys. So if there are n members, each member sends their sender key n-1 times encrypted with individual's public key. Total number of key exchange will be n(n-1).

Participants' public key can be obtained from B acting as key distribution server.

  1. If A wants to send a message to other members, A encrypts his message with his own sender key and sends it to B.

  2. B creates copies of A's message equal to the number of recepients and forwards this it to them. This is called server side-fanout.

  3. As recepient's already knows A's sender key, they can decrypt A's message.

  4. When someone joins, he generates his own sender key and shares it with others the same way. Other members also share their keys with him like before. Total number of key exchange will be 2(n-1) for n members including the new one.

  5. If someone leaves, every member clears their old sender key, generates a new one and shares their key again. Total number of key exchange will be n(n-1) for n existing members in the group.

  6. To prevent a malicious member impersonating as some other member, each member signs their message using their private key. The public component to verify the signature can be obtained from B.

How you implement one to one messaging, this can be used to share sender keys to initialise multiparty encryption. You can also use Diffie-Hellman to share sender keys but it also has to be done n-1 times if there are n members.

Here's a good article on reducing the distribution of keys for multiparty encryption: Better Encrypted Group Chat

defalt
  • 6,451
  • 2
  • 24
  • 38
  • thank you very much for your answer! This was helpful :) – Luca Aug 27 '19 at 06:50
  • I have another question. In this setting the server C needs to store all the sender keys of all the mobile devices. Assuming that we will have a lot of users (many thousand), is it a problem for C to handle this many keys? – Luca Aug 28 '19 at 11:59
  • 1
    @Luca Not at all. The sender key is 256-bit AES-CBC key. WhatsApp group members have max capacity of 250 members so when the group is full every member stores 250 sender keys in its device. The actual load is handled by B who has to create copies of the message and distribute them to the rest of the clients. Why C is a server in your question and not a client? – defalt Aug 28 '19 at 15:14
  • sorry, a client! I did not formulate precicely :) Let's say the client recieves messages from some million mobile devices, and thus needs to store some million symmetric keys. This sounds like a difficult and risky key management; is this easily and secure implementable? (My background is mathematics, so I feel rather safe concering the theory, but I am not yet experienced with the step to put this theory in practice) – Luca Aug 28 '19 at 15:20
  • 1
    @Luca You have to impose a group limit. Group management becomes difficult to operate if users are frequently joining and leaving the group. A group with thousands of members will take a long time to complete key exchange. Until the key exchange completes new messages which are already in transit cannot be decrypted. – defalt Aug 29 '19 at 05:27
  • even if my communication is one-directional? – Luca Sep 03 '19 at 08:39
  • 1
    @Luca One-directional is basically a broadcast communication. For that you don't need to enforce group limit. But have to generate a new key and share it with all the **listeners** everytime someone leaves. Also, you don't need others' sender keys in one directional communication because they can't message you back. – defalt Sep 03 '19 at 15:04
  • OK I see! I am now thinking about how to update the sender-key. (I posted another question https://security.stackexchange.com/questions/216452/updating-sender-keys-and-key-management). In short: Can I just send, along with the encrypted message some update information? However, then I might not have forward-security, since once the adversary learns a key and listens to the update information he could, himself, derive the new key-update. A different idea was to use some kind of simplified ratchet algorithm (since my communication is one-way). – Luca Sep 03 '19 at 15:10
  • If you have a moment I would be really happy if you could have a look :) – Luca Sep 03 '19 at 15:10