Disclaimer: I am aware that the question's title does not adequately describe what I am asking, but it is the best I could come up with. Any improvement is welcome.

I am a university student studying for an upcoming cryptography exam, and I came across this unsolved exercise. I have various questions that stem from it. Unfortunately, my professor is unavailable, and I cannot contact her. So I would appreciate some clarification as to whether my approach is correct and whether there are many right answers.

Consider the following system for the communication of a group of nodes. This group has a standard number of M members that each have a unique id. A central entity CE also exists for the facilitation of node communication.

When a member Mi is accepted into the group, they produce a key pair KiPUB and KiPriv, and share their public key and id with the CE.

When a member of the group wishes to communicate with another member, it sends the id of the intended receiving node to the CE and gets back the receiver's public key. The message is then encrypted with said public key and sent.

a. If you have access to the communication path of Mi with CE or any other node, but cannot meddle with the contents, can you decrypt messages sent by Mi?

My initial answer to that is no. The attack that makes sense to me is the man-in-the-middle attack, and it needs to be able to change the messages sent. However, it is unclear whether the man-in-the-middle has to be an entity "formally" incorporated into the system, into the communication process. If so, then it does not apply, and some other attack would be appropriate for this scenario.

b. You can now alter the contents of Mi's communication with other nodes and CE. Can you do that without being detected? Can you now decrypt the messages sent?

My answer to that can be easily derived from the one in question a. my problem is if man-in-the-middle does not have an effect here, my whole reasoning falls apart.

c. How would you change the system so that every node stores every other node's public key to protect from such attacks? What memory demands would that system have compared to the existing one?

It seems unlikely that all that is required as an answer is "have each member send all other members its public key via a secure channel," and at the same time, I'm not sure how much further beyond that I am supposed to go.

As for storage, compared to the $M$ number of keys CE would have to store, $M$ being the number of members, each member now has to store all member public keys, so it changes to $M^2$.

To clarify, this is not an exercise that will be graded, just one that I'm trying to solve to understand the material better and clarify my thinking on the matter. If you downvote my question, please provide a comment with the reason. I am looking for some pointers and explanations, as the theoretical approach doesn't seem to be enough for me to figure this out.


1 Answer 1


The exercise fails to cover how a sender is supposed to know the Id of an intended recipient, and how the CE is supposed to know that a KiPub it gets is that of the Mi with this Id. If the goal is just to get away with a high mark, ignore the issue or briefly mention we assume sender knows Id; and CE knows Id and KiPubwith, and acts honestly. Never insist that the question is lacking when it could be that the author is the grader!

Then the initial answer to (a) is correct: with only passive eavesdropping, there's no attack to the system proposed. I don't get what's meant by "formally" incorporated, but a Man in the Middle is an adversary assumed to go beyond passive eavesdropping, and that's excluded in (a) by "cannot meddle with the contents".

For (b), there's an attack possible by a MitM. Just describe that attack with enough details, like you are the mastermind explaining how it's done to a novice accomplice. Detail exactly what the MitM changes (and into what) in order to "decrypt the messages sent" [hint: "The message" won't cut it].

For (c), "every node stores every other node's public key" is a solution to the attack in (b) only inasmuch as it gets achieved, and the question asks how. One acceptable answer involves detailing how the CE makes public key certificates, how they are communicated and checked. I recommend to make another assumption explicit: that each member knows the CE's public key.

More hint: the first part of (c) ask how we prevent the attack in (b), and in my reading that requires explaining how we get a member to know another member's KiPub, rather than assuming that it happens [it did not in the attack of (b)]. Among the methods for this allowing new members (as required), matching (c), and close to the practice commonly taught, we'd rather use the one closest to the exercise's existing setup. That seems to be: keep the CE authenticating new members and their KiPub however it does that now, and tweak it's role: from distributing a KiPub on request, to distributing certified KiPub to each existing member as a new member enrolls.

The part of (c) about the storage required may be calling for a comparison with the storage required for secret-key cryptography, and a level of criticism of "every node stores every other node's public key".

  • $\begingroup$ Thanks a lot! A follow up for c, I took "every node stores every other node's key" to mean that the CE would be eliminated, pointing to a kind of peer-to-peer system. Is that not correct? Since all nodes storing every node's key is the given, then what is the purpose of the CE in that scenario and how do certificates come into play? Also, for b, does the MitM changing the messages content go undetected? $\endgroup$ Feb 11, 2021 at 16:07
  • $\begingroup$ @riverwastaken: it could be that you have not a clear enough view of the attack in (b). I added more hints, and why I think (c) is best solved with digital certificates. There are other ways with the CE eliminated, but they are complex. Unless you have been introduced to protocols without a central authority and with an evolving set of participants, I doubt that's what the exercise wants to lead you to. $\endgroup$
    – fgrieu
    Feb 11, 2021 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.