I'm preparing for an introductory information security examination in university and this is one of the tutorial question on Network Protocol attacks. I tried (a) and came to this conclusion:

Since the EPbX() is a public key encryption operation, C can decrypt any encrypted message to get back its original message, m as though it is anyone in the pair of people exchanging messages.

However, when I re-read the question, the decryption requires the use of private keys, which means it might be impossible to get the message unless C impersonates as the other to each of A and B, and is involved in the key exchange, generating 2 pairs of private keys, which seems repetitive. This confusion prevents me from doing the later part (b).

Can anyone suggest the thought process and solution to the above problem?

Here is the question description. Sorry the actual paper document is not formatted such that it allows copy over.

webatk 1

webatk 2


The protocol does not mention any random padding, which means that E(P,m) is a deterministic function. It means that, given the same public key P and message m, the result of E(P,m) is always identical.

If the attacker C can sniff E(PA, m) and E(PB, m), then they can try all possible values for m, and see which m results in the same encrypted message.

The viability of this depends on the entropy of m. If the contents of m can be reasonably guessed, then this is a viable attack. If m has high entropy (e.g. a randomly generated encryption key), then this attack is not viable. In that case, I wouldn't know how C would be able to recover the message, though I would love to know.

Question (b) is asking how this attack can be prevented. The simple answer is by including a random padding, which is distinguishable from the actual message.

So by modifying the encryption algorithm to be like E(P, m||pad), with pad being chosen randomly, the encryption function can't be exploited in the same way anymore. The attacker C doesn't know the padding, so even if C would happen to have the correct m and calculate E(PA,m), the result would not be identical, as C does not know the padding being used.

In regards to the padding: The padding requires two things:

  • The padding must be sufficiently long and random so that is infeasible for the attacker to try every message with every possible padding. What this actually accomplishes is to guarantee that every message sent has high entropy.
  • The padding and the message must be sufficiently distinguishable. This can be accomplished by making the padding a fixed length. The recipient would know that the padding is this length (e.g. 256 bit) and can remove the last 256 bit, and before sending a new message, create a random 256 bit padding.
| improve this answer | |
  • Thank you for your answer. I want to clarify what you meant by "random padding". I would assume you meant adding any number of characters in any order behind the intended message and encrypting it together. It is easy for the decrypting recipient to know what is the padding. But to the attacker who is trying to brute-force the original message without any knowledge of their private keys, this is impossible because the length of the initial message cannot be determined. Am I correct in my explanation? – Prashin Jeevaganth Nov 21 '19 at 11:57
  • @PrashinJeevaganth Basically, yes. The answer assumes that a.) the padding is sufficiently random so that brute-forcing a message with every possible padding is infeasible, and b.) that the intended recipient of the message can clearly differentiate between message and padding. How exactly this is done in practice is implementation-dependent. – MechMK1 Nov 21 '19 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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