Deck modes

In a previous article, I made the bold claim that Deck functions provide 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 Deck functions.

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 indistinguishable from random 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, which is just XOR in GF(2). To build encryption oracle E1 on top of Deck function FK, we plug in nonce N as input and request |P| bits of output, which are then added to P:

E1(key K, nonce N, plaintext P):
    C ← P + FK(N)
    return C

D1(key K, nonce N, ciphertext C):
    P ← C - FK(N)
    return P

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

P1Plaintext
E1(K1, 0, P1) = Ciphertext
E1(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 indistinguishable from random. To build a MAC on top of Deck function FK, we plug in message M as input and request t bits of output:

MAC(key K, message M):
    T ← 0t + FK(M)
    return T

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
MAC(K2, P1) = A2 FC 2C 29 C4 5D 9C 22 A9 F1 E5 CC A9 C5 0F 45
MAC(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 E1(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:

When building on top of the Deck function abstraction, this is as easy as combining the stream cipher and MAC together:

E2(key K, nonce N, metadata A, plaintext P):
    C ← P + FK(N)
    T ← 0t + FK(C ∘ A ∘ N)
    return (C,T)

D2(key K, nonce N, metadata A, ciphertext C, tag T):
    T' ← 0t + FK(C ∘ A ∘ N)
    if T' = T then
        P ← C - FK(N)
	return P
    return ⊥

The sender transmits cryptogram (C,T) 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:

E2(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 cryptograms is very dense: every cryptogram is considered valid and will decipher without error. In this authenticated encryption mode, we are effectively making the space of valid cryptograms very sparse by adding an authentication tag. Just how sparse? Because the tag is 128 bits in length, in the space of all possible cryptograms, approximately only 1 in every 2128 cryptograms 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 perfectly secure, but is there a more robust solution?

Sessions

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

init(key K, nonce N):
    history ← N
    T ← 0t + FK(history)
    return T

wrap(metadata A, plaintext P):
    C ← P + FK(history) << t
    history ← C ∘ A ∘ history
    T ← 0t + FK(history)
    return (C,T)

unwrap(metadata A, ciphertext C, tag T):
    T' ← 0t + FK(C ∘ A ∘ history)
    if T' = T then
        P ← C - FK(history) << t
    	history ← C ∘ A ∘ history
	return P
    return ⊥

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 Deck functions, 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 (key, nonce) pair 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.

Deck functions provide 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:

init(key K, metadata A):
    history ← A
    T ← 0t + FK(history)
    return T

wrap(plaintext P):
    C ← P + FK(history) << t
    history ← C ∘ history
    T ← 0t + FK(history)
    return (C,T)

unwrap(ciphertext C, tag T):
    T' ← 0t + FK(C ∘ history)
    if T' = T then
        P ← C - FK(history) << t
    	history ← C ∘ history
	return P
    return ⊥

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):
T = F0 3E 7D 84 A2 30 72 DF 5A 56 22 90 DB B8 25 7A

wrap(P3):
C = 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
T = 5C 75 71 D1 FB 2D 22 FF FD 68 5B BA CB 49 69 05

wrap(P3):
C = 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
T = 9F C9 66 AB 45 AA 02 F0 31 C6 7A 18 BD 54 F4 14

wrap(P3):
C = 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
T = 84 20 D9 B5 C5 1F CA 42 75 78 DA 70 28 94 1C 4F

wrap(P3):
C = 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
T = BD F9 13 18 A0 A3 28 C9 F4 07 9B 8E FB 8E 03 8A

wrap(P3):
C = 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
T = 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 (C,T) cryptogram is different, even though we are 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 Deck functions provide the ideal level of abstraction.