Nonces and authenticated encryption

Attempt 1

Let's work on solving just the encryption portion first. In the nonce-based stream cipher, we calculate the keystream as a pseudorandom function of the nonce. Without the nonce, we are left with the plaintext as input. One idea that comes to mind is to plug the plaintext into the Farfalle instance to generate the keystream:

Now, the keystream is a pseudorandom function of the plaintext. This would seem to solve the problem of not having a nonce. Embarrassingly, however, the receiver has no way of calculating the keystream since the plaintext is not yet known. Is there a way to work around this?

Attempt 2

The fundamental realization is that we need to generate the keystream from a quantity that both the sender and receiver have access to. One thing we can do is plug the plaintext into the Farfalle instance to generate a short non-invertible representative value (i.e., a tag), and then plug that tag into the Farfalle instance to produce the keystream. We then transmit that tag along with the ciphertext, to the receiver. Because the tag is calculated as a pseudorandom function of the plaintext, we can simply validate the tag in the decipher oracle to achieve authentication:

At this point, we have achieved full-blown authenticated encryption without requiring a nonce. If two different plaintexts are input into the encipher oracle, then two different sets of keystreams are used, provided the tags do not collide. Note that because we are now imposing a uniqueness requirement amongst pairs of tags, the birthday bound applies. Therefore, to achieve s bits of security we'll need to use a tag that is 2s bits in length.

Adding metadata

We haven't taken metadata into account yet. At a minimum, we need the authentication tag T to be a function of both the metadata and plaintext... but can we do better? For example, what if our metadata contains a nonce and we want to be able to take advantage of this to use a shorter tag? Thanks to the incrementality property of Farfalle, we can incorporate the metadata contribution into the keystream calculation as well, for free:

We have arrived at a powerful authenticated encryption mode with the following properties:

• Nonce reuse resistance
• Short tags safe as long as (A,T) pairs are not repeated
• Optimal support for metadata-only and plaintext-only messages
• Static metadata contribution can be factored out and reused across messages

Session support

SIV is an offline mode, meaning it needs to read the entire plaintext before it can produce any keystream. Clearly, this is impractical in applications that need to transfer large amounts of data. One way around this is to simply split up the plaintext into small chunks, and then run each chunk through the encipher oracle with a counter in the metadata. A better, more robust solution is to chain the blocks together; i.e., take the previous message's tag and plug it into the next message's metadata input. This way, if a message is corrupted, then the rest of the blocks are corrupted as well. More importantly, if a message contains a diversifier, then the entire chain of messages is diversified from that point forward.

We can do even better than explicitly chaining blocks together, thanks to the incrementality properties provided by Farfalle:

Bonus material

The mode described here can be viewed as a special case Feistel network: