Feature #2: Verify Message Integrity

Description

We use a network protocol that encrypts all of the application messages using a proprietary scheme. The encryption scheme has a unique property, whereby the sequence of encrypted messages in a session appears to be in sorted order according to a secret dictionary. The communicating parties exchange this dictionary during a handshake process before the message exchange starts. Given the sequence of messages received in a session and the dictionary, we need to verify that the messages have not been tampered with. The key idea is that any tampering would result in messages in a session no longer being in sorted order, according to the dictionary.

The dictionary consists of all the letters used in the messages, and the letters may use a different lexicographic order than the regular English dictionary.

Note: For the sake of simplicity, we can assume that the encrypted contents of the messages only consist of English lowercase letters.

Let’s review a few examples below:

We need to be extra cautious with this edge case. In lexicographical ordering, we order the messages with different sizes but similar content in a way that the message with the smaller size comes before the one with the larger size.

The following illustration might clarify this behavior:

Solution

To verify the integrity of the messages, we can check the adjacent messages to see if they are in the correct order or not, that is, for each message, the message on its right should be lexicographically larger, and the one on its left should be lexicographically smaller.

One thing to notice here is that we do not need to compare all the messages. We can just compare each pair of adjacent messages instead. If all the pairs of adjacent messages are in order, we can safely assume that the integrity is intact. Conversely, if any of the pairs of adjacent messages are not in order, we can assume that someone ...