Authenticated encryption

Why use it?

Since the Counter mode of operation is used in between the Mixes and the client, it seems to be easy to extend that to the Galois Counter Mode to get the added benefit of authenticating the messages and checking not only if they were duplicated by an attacker, using the Replay Attack detection, but also if they have been modified.

Since it is possible to add associated data, that doesn't need or can't be encrypted, it would be possible to add the channel ID and the used counter prefix to the data authenticated by GCM.

When encrypting a message using GCM, additionally to the cipher text a tag is produced. A block of data identifying the cipher text and all additional data provided prior to encryption. This tag would also need to be transferred, in addition to the counter prefix.

What to do?

Given that meddling was detected by a Mix, the question arises what to do with that information. The message could be dropped, or relayed for later handling, for example by the last Mix.

If the message was dropped then and there, that could be observed by the attacker on the other end. Since there is a 1:1 connection between channel ids, which should be kept secret, manipulating a message and observing the lack of its counterpart emerging from the other end of the Mix could help in identifying which Channel IDs correspond to each other, whether channels in a batch change every time or stay the same.

What if only the last Mix checks to see, if the message was meddled with. That means, that the client only needs to use authentication once on the first encryption and on the last decryption, if we authenticate the replies as well. Dropping the package before delivering it "in the open" could also give clues to an attacker manipulating a message right after the client sent it. They could work backwards, wanting to find out who, for example, communicates with wikileaks.com and manipulating clients until the communication with wikileaks stops, since the last Mix recognizes them as manipulated. One could argue, however, that a manipulated packet would probably not arrive at its destination anyway, so that problem is not unique to authentication and needs to be dealt with anyway.

Essentially manipulating a message right after the client is identical to blocking the message entirely, with the added benefit, that the mix chain doesn't necessarily lose traffic concealing other users. That also means, that a scheme which allows error correction is not helpful in thwarting manipulation, in addition to the attacker changing one bit more than the scheme could correct.

When?

The way the channel initialization works is, that an initialization message with an unused channel id is sent to the next step in the chain, which recognizes the new channel and interprets the initialization data. Manipulation of any message could result in a change in the channel id plain text, making the mix believe, that a new channel is meant to be created. This could, in the best case, work and take up resources from legitimate channels and in the worst case lead to a crash of the mix. It is therefore necessary, that at least all channel initialization messages are authenticated. Since any message could be seen as a channel authentication message, when they are manipulated correctly, it follows that all messages would need to be authenticated by all mixes in the chain.