Message streams draft

Message streams are a more efficient way to send a lot of messages to the same recipient(s).

Stream structure

A message stream starts with a head message followed by any number of stream messages:

The head is a regular message, signed by the sender and encrypted for all recipients. Any such message may be used to start a stream.

Stream messages reuse the same AES key as their head, but a different CTR range within the encryption stream. A stream message can be thought of as an extension to the original message.

Stream messages are not signed. Instead, they carry a message authentication code (MAC) to ensure data integrity. Everyone knowing the AES key, i.e. sender and recipients of the head, may produce and verify MACs.

As opposed to regular messages, stream messages do not involve any RSA exponentiations, which makes sending and receiving far less computationally expensive. In addition, stream envelopes are just about 100 bytes in size, and therefore significantly shorter than regular message envelopes (~1 KB).

CTR ranges

Since all messages of a stream (including the head) use the same AES key, it is of utmost importance that their CTR ranges do not overlap, as this would undermine the security of the AES-256-CTR encryption scheme.

The total available CTR range is huge (0 to 2¹²⁸ - 1). The head message always starts at the beginning of that range (CTR 0), and requires 1 count for every block of 16 bytes of the content object. Note that the last block still requires one count, even if it is smaller than 16 bytes.

Stream messages require 8 counts for their MAC, and 1 count for every 16 bytes of their content object. To pick CTR start values for these messages, an application may use one of the following schemes.

Random

CTR ranges may be assigned randomly:

Each CTR start value is thereby simply 16 random bytes. Up to a total stream length about 1 PiB, the probability that two such ranges overlap is negligible.

Replies can be sent on the same stream. No coordination is necessary.

Sequential

CTR ranges may be assigned sequentially:

The CTR start value of a message is thereby calculated as follows:

// Initialization
used = ceil(head content object length / 16)

// Sending a message
ctr = used
used = used + 8 + ceil(content object length / 16)

With this scheme, the CTR start value can be used as message order. Over lossy message channels, missing messages can be detected.

To send replies on the same stream, coordination among sender and recipient(s) is necessary. It is generally easier for each actor to start its own stream.

In some applications, it may be easier to increment the CTR start value by a fixed (large enough) value rather than what is required by the message: