Cryptographic modes

In a previous article, I made the bold claim that Farfalle provides the ideal abstraction for building every keyed symmetric cryptographic mode. In this article, I would like to demonstrate how we can effortlessly build a stream cipher, message authentication code and simple authenticated encryption mode on top of a Farfalle instance.

Stream cipher

A stream cipher generates an arbitrary-length stream of bits as a function of a secret key K and a public nonce N. This stream of bits, known as the keystream, has the property of being computationally indistinguishable from randomness to an adversary who does not know the secret key. To perform the actual encryption, we simply add the plaintext P and the keystream together in GF(2), which is just XOR. To build a stream cipher on top of Farfalle instance F, we plug in nonce N as input and request |P| bits of output, which are then added to P:

Stream cipher

Stream cipher

To demonstrate, let's use an uncompressed image as the plaintext and visualize the pixels:

P1Plaintext
Estream(K1, 0, P1) = Ciphertext
Estream(K1, 1, P1) = Ciphertext

As shown above, the two ciphertexts appear completely uncorrelated thanks to the nonce providing diversification. It is very important that a nonce is never reused, otherwise the adversary can calculate the sum of the plaintexts simply by summing the ciphertexts together to cancel out the keystream.

Message authentication code (MAC)

A message authentication code (MAC) generates a short authentication tag T as a function of a secret key K and an arbitrary-length message M. The tag T has the property of being computationally indistinguishable from randomness. To build a MAC on top of Farfalle instance F, we plug in message M as input and request t bits of output:

Message authentication code

Message authentication code

To demonstrate, let's calculate the MAC of P1 and represent the authentication tag in hexadecimal. To make things interesting, let's create a P2 such that it differs from P1 by only a single subpixel and MAC that as well for comparison:

P2Plaintext
EMAC(K2, P1) = A2 FC 2C 29 C4 5D 9C 22 A9 F1 E5 CC A9 C5 0F 45
EMAC(K2, P2) = CB AA 7D B9 C2 68 7E 79 85 EB 93 D8 26 42 0C 26

As demonstrated above, it does not matter how small of a change is made to the input message; the MAC function maps every possible input down to a much smaller space in a random-looking way. Due to the pigeonhole principle, there are an infinite number of inputs that map to each of the 2128 output buckets. How much effort would it take to craft a message that MACs to the same tag as P1? It would take 2127 attempts on average!

Authenticated encryption

In any situation where an adversary can actively tamper with a message, which I would argue is the vast majority of situations, a stream cipher by itself does not provide adequate security. The biggest problem is malleability: flipping a bit of ciphertext at location n flips the corresponding bit of plaintext at location n. The adversary can flip individual bits at any location, and the recipient has no way of detecting that this happened. To demonstrate this, I have crafted ciphertext C1 such that its decrypted plaintext contains a circle, using only Estream(K1, 0, P1):

C1Ciphertext
D1(K1, 0, C1) = Plaintext

Stated another way, plain encryption provides confidentiality, but does not provide any integrity or authenticity guarantees; we have no way of determining whether the ciphertext has been tampered with. The solution is to use authenticated encryption, which provides confidentiality, integrity and authenticity guarantees. We have the following inputs:

This is as easy as combining the stream cipher and MAC together:

AEAD

AEAD

The sender transmits the ciphertext and the receiver authenticates and decrypts it. If the ciphertext is not authentic, then it is thrown out and an error is returned. If the ciphertext is authentic, then it is decrypted and used. To demonstrate this, let's encrypt and authenticate P1:

EAEAD(K3, 0, "seth.rocks", P1) = Ciphertext
4A 35 16 33 20 75 82 03 EE E8 BE 68 3F 7F BC 5A

Just like with the MAC example, it would take about 2127 attempts on average to achieve a successful forgery. Why is this? Going back to the plain stream cipher, the space of valid ciphertexts is very dense: every ciphertext is considered valid and will decipher without error. In this authenticated encryption mode, we are effectively making the space of valid ciphertexts very sparse by adding an authentication tag. Because the tag is 128 bits in length, in the space of all possible ciphertexts, approximately only 1 in every 2128 ciphertexts is considered valid!

This mode has a number of things going for it:

However, not all is perfect:

We could work around these issues by breaking up the plaintext into smaller pieces and then encrypting/authenticating each piece by appending a counter to the nonce. This would work fine and is secure, but is there a more robust solution?

Sessions

We can use the incrementality property of Farfalle to our advantage. Consider the following mode:

Session AEAD

At first glance, this may appear to be a totally impractical mode: do we really need to store a growing list of strings in memory? Not at all! Thanks to the incrementality property of Farfalle, strings are compressed into a fixed-size state. You could exchange a single message or a million messages and the state size remains constant. This stateful mode allows us to exchange a sequence of messages, and produce an intermediate authentication tag after each message. Thanks to the beauty of incrementality, each authentication tag authenticates not only the most recent message, but all messages up to that point in the session. This means that if any messages are dropped, duplicated, reordered or tampered with in any way, the authentication tag will not match and we can terminate the session immediately. Not only that, but the state would become corrupt as well, which scrambles all subsequent messages.

This mode solves the problems with the previous mode, and actually introduces an additional feature: a startup tag is generated at session initialization, which authenticates the nonce used to initialize the session. If an adversary tries establishing a session with a server, the tag will inevitably not match, and the server can drop the connection before any data is processed. This saves valuable CPU time.

Farfalle provides a powerful design tool. For example, consider that most applications need only process metadata at the beginning of a session. We can use this observation to simplify the mode:

Session AEAD

Now, the metadata and nonce are combined into a single string provided at session startup. The metadata is compressed into the state, which diversifies it and also produces the startup tag. To demonstrate, let's initialize a session and wrap an identical plaintext repeatedly:

P3 ← "Deck functions are amazing!"

init(K4, 0):
F0 3E 7D 84 A2 30 72 DF 5A 56 22 90 DB B8 25 7A

wrap(P3):
3D D8 38 F2 0B 93 0D B7 D5 0B 23 D9 60 10 55 81 4E F1 FC 24 75 DE 0B 1A 3A A3 48 5C 75 71 D1 FB 2D 22 FF FD 68 5B BA CB 49 69 05

wrap(P3):
FE 3D 50 BC 9C 76 A8 03 41 DB A9 23 99 78 5B EB 09 06 63 A1 3E D2 8C 9C 0D 6F C0 9F C9 66 AB 45 AA 02 F0 31 C6 7A 18 BD 54 F4 14

wrap(P3):
79 0A D1 FD 34 08 86 71 D3 76 85 7B 64 4D 48 C9 45 6D 3F 70 A1 C9 75 42 77 26 7B 84 20 D9 B5 C5 1F CA 42 75 78 DA 70 28 94 1C 4F

wrap(P3):
9A E6 06 D8 C7 DB 81 8B F6 F4 71 D5 95 7B D7 4B 44 C2 21 C1 8E E2 31 1B 61 92 D8 BD F9 13 18 A0 A3 28 C9 F4 07 9B 8E FB 8E 03 8A

wrap(P3):
9F 49 1E 1B D9 AA AD 85 51 42 6E 66 7E CF 9C 8E 8C 46 5C 11 CF 37 F5 DA DE 5F B7 C7 50 B2 14 C0 4B C2 C2 51 F1 26 BB 89 57 AF C8

One of the nice things about a stateful session mode is that inputting a nonce once at the beginning of the session diversifies the entire session. In addition, note how each ciphertext is different despite wrapping an identical plaintext repeatedly. This is thanks to the fact that strings are incrementally accumulated into the state. This means that each authentication tag authenticates everything absorbed up to that point. It is also possible to allow for optional metadata or optional plaintext throughout a session by using frame bits; this is left as an exercise to the reader. Hopefully it is clear by now why I claimed Farfalle provides the ideal level of abstraction.