Signing an exchanged symmetric key that is asymmetrically encrypted

Question

Consider the following implementation:

Bob wants to communicate long-term with his team over an unsecured channel. Bob and all members of the team generate individual public/private keypairs (ex. RSA) and store/share their public keys on an untrusted key server.

Bob, being the first member of the team, also generates a long-term random symmetric key for the team that he and all team members will use to encrypt their communications. Bob encrypts the team's symmetric key with his public key and also the public key of all current members of the team and stores them on the same untrusted key server.

When new members are added to the team, Bob (or any existing member of the team that can add new members) takes his own encrypted version of the team's symmetric key from the key server, decrypts it with his private key, then copies and re-encrypts it with the new member's public key, storing it back on the key server for the new member to use for future communications with the team.

The problem with this implementation is that the symmetric key can be forged by Eve, a bad actor with access to modify the key server. Since public keys are all available, Eve could take Bob's (or any and all members of the team) public key and encrypt a new symmetric key on the key server. Past communications would then fail to decrypt, however, if gone unnoticed by the team any future communications could be read by Eve. If the forgery occurred when the symmetric key was first stored, no member of the team would ever know that Eve has been reading their communications.

I think that we need some sort of signature on the symmetric key exchange, however, where would the key material for this signature come from? How could we produce a signature in a way that each member of the team could privately verify that their version of the team's symmetric key is authentic? Maybe some other way?

---

Update #1

One solution could be for Bob to compute a hash of the symmetric key whenever he first generates it, then sign the hash with his private key and store it on the key server. Whenever members retrieve their copy of the symmetric key from the key server, they could also obtain Bob's public key, verify the hash's signature and recompute the hash to verify the symmetric key.

However, the problem I see with this solution is that it seems Eve could still forge a new symmetric key, sign it with her private key, and replace Bob's public key with hers on the key server. This would allow her to impersonate Bob's signature while other team members verify and use the forged symmetric key.

Answer 1

Your scenario seems overly simplified but anyway:

Just have Bob sign the key that he uploads.

You're assuming that people know each other's public keys anyway. So everybody can verify that the key has been signed by Bob.

If you want to keep your one-to-one trust structure the people adding new team members could also sign the key again or just sign that they trust Bob.

Answer 2

I think it's helpful to analyze the social problem here as well: because any member of the team can incorporate a new member, it makes it inherently difficult for the team as a whole to verify whether the new symmetric key that was uploaded is authentic. Because Eve has access to everyone's public key, she can masquerade as a team member and in order for the team to discover the intrusion, they'd need to ask every member whether they incorporated a new member. This leaves me with two takeaways:

1) Make it so that only Bob can add new members. This makes it simple to detect an imposter but it takes for granted Bob is always vigilant and accessible, so it's not ideal.

2) If Alice (or any team member) wants to incorporate a new member, she generates an independent symmetric key, which she encrypts with her private key such that it can be decrypted with her public key. She broadcasts that to the team, which ensures this key was truly generated by her. She then gives that symmetric key to Tom, who encrypts it with his private key. Members of the team can decrypt using his public key and verify Alice gave Tom the symmetric key (i.e. permission to join the group). After this point, the independent symmetric key can be disregarded and the original team symmetric key can be re-encrypted with everyone's (including Tom's) public keys.