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: