Lecture 15: Authenticated Encryption

Our goal for today is to construct two kinds of symmetric key primitives.

• Symmetric key encryption allows two parties to send messages to each other with confidentiality. Each party can both encrypt and decrypt.

• A message authentication code allows two parties to send messages to each other with integrity. It is the symmetric-key version of a signature scheme, where each party can both sign and verify.

These primitives are nearly always used together. So for convenience, we will construct a combined primitive called authenticated encryption that performs both of these tasks at once.

“Confidentiality xor authenticity is not possible.
If you don’t have both, often you don’t have either.”

– Prof. Matthew Green (Johns Hopkins)

Modern symmetric encryption schemes are designed using a pseudorandom permutation \(f: \{0, 1\}^n \to \{0, 1\}^n\). This function is deterministic but “acts random.”

A pseudorandom permutation (or PRP) is almost like a cryptographic hash function, except that:

• The input and output lengths are equal.
• There are no collisions: the function is a permutation, so each output occurs exactly once.

As a result, this primitive is somewhat easier to build, and therefore faster, than a cryptographic hash function.

In fact, AES is a family of many pseudorandom permutations, indexed by a key. To anyone who does not know the key, the function acts like a random oracle.

If an adversary [Mallory] has not explicitly queried the oracle on some point \(x\), then the value of \(H(x)\) is completely random… at least as far as [Mallory] is concerned.

– Jon Katz and Yehuda Lindell, Introduction to Modern Cryptography

I show below an example of the AES permutation (for a randomly-chosen key). Note that the function has a fixed input and output length of 16 bytes. Unlike a hash function, it does not work for any other size.

from Crypto.Cipher import AES
from binascii import hexlify, unhexlify
from os import urandom
key = urandom(16)

def permutation(x):
    cipher = AES.new(key, AES.MODE_ECB)
    return hexlify(cipher.encrypt(unhexlify(x)))

try:
    print(permutation(b'00' * 15))
except:
    print("Input too short")

Input too short

try:
    print(permutation(b'00' * 17))
except:
    print("Input too long")

Input too long

As one would expect from a random-looking function: making small changes to the input results in substantial changes to the output.

print(permutation(b'00' * 16))
print(permutation(b'00' * 15 + b'01'))

b'aed2f463e960198b11c05ae30a96e4d8'
b'a13339b8c43d1283dd4e9a371d6bb93d'

Question. Which of the following bitstrings “looks” random and unpredictable?

• 11111111
• 01010101
• 10100011

Answer. This is actually a trick question: if the strings were sampled uniformly at random, then each output is equally likely!

This brings us to an important insight:

• You cannot look at a single output string and determine its (un)predictability
• Our pseudorandomness definition instead evaluates the process of designing a pseudorandom function. This requires cryptanalysis and relies on Schneier’s law.

“Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break.”

– Bruce Schneier

Note that the message only touches the rate bits of the state. Meanwhile, the capacity bits are only influenced by the Keccak-\(f\) function itself, and therefore always remain “random-looking.”

By a birthday bound, two states with random-looking capacity bits are unlikely to collide.

In hash function lingo, this nonce is typically called a salt.

For this reason:

• Computers (and web servers) store a hash of the true password \(h(p)\) rather than the cleartext password.
• After you type a password \(p'\), the computer hashes it and compares against the stored hash.

Remember the preimage resistance guarantee provided by cryptographic hash functions: given a random \(y\), it is difficult to find any preimage \(x\) such that \(H(x) = y\).

As a result, password hash functions are specifically designed to be slow and resource-consuming.

• When executed once by the honest account-holder, a delay even in the 0.1-1 second range is perhaps tolerable.
• But for an attacker Mallory who tries to brute-force guess millions or billions of passowrds, the delays add up.

Question. How do you make a function deliberately slow, in a way that is impossible to speed up?

Keccak’s sponge function design provides an elegant way to design a computationally-slow hash function: simply absorb more data.

Newer password hash functions like argon2 are also designed to require a lot of memory, so that a brute-force attack is harder to execute on a GPU or dedicated hardware device.

We can use a sponge function to address these issues. Given only:

• A short cryptographic key, and
• A nonce called an “initialization vector” (IV),

we can pseudorandomly build a long key stream that Alice and Bob can XOR with their private data.

It is imperative that each IV be used only once. If an IV is reused, then we are back to the two-time pad problem. That said, the IV does not need to be kept hidden from the adversary.

In other words:

• The key is used to provide uncertainty.
• The IV is used to provide variety.

MACs are also precisely what we need in order to instantiate a key building block that we needed in the phase-king and Bracha reliable broadcast protocols.

Authenticated pair-wise channels: Every party is connected to every other party, and they somehow have a way to know who is communicating with them. In other words: no party can impersonate another, so a party Bob can be confident that he is receiving messages from another party Alice.

– This course, Lecture 9

Formally, suppose there is a message \(A\) that needs to be authenticated in transit over the Internet.

Definition. A message authentication code contains three algorithms:

• KeyGen: Alice and Bob jointly sample a symmetric key \(k\) from a distribution \(\mathcal{K}\) (say, a uniformly random bytestring of fixed length)
• MAC\((k, A)\): produces a tag \(T\)
• Verify\((k, A, T)\): returns true or false

All three algorithms should be efficiently computable. Moreover, the digital signature must satisfy two requirements:

• Correctness, meaning that validly-produced MAC tags will always successfully verify.
• Existential unforgeability under a chosen message attack (EU-CMA), which is defined in exactly the same way as for public-key digital signatures.

Note that the same key is used in both MAC and Verify. As a result:

• With a digital signature scheme, the entire world can verify the identity of the message sender.
• With a MAC, only the message receiver (who also holds the symmetric key) verify the sender’s identity.

Theorem. If there exists an adversary \(\mathcal{A}\) that forges the MAC, then it is possible to construct an adversary \(\mathcal{B}\) that can distinguish between pseudorandom and truly random permutations.

Question. Why is this theorem helpful to us? (At first glance, it sounds like it is helping Mallory: it provides her with a roadmap for how to break things.)

Question. Suppose there is a message \(P\) that we want to be private and authenticated. What is the best way to combine encryption and MACs?

If you don’t know anything about the specific symmetric key encryption and MAC constructions used, then the most important thing to remember is that the MAC does not provide data confidentiality.

This leads us to the right answer for this question, and more generally to the cryptographic doom principle.

“If you have to perform any cryptographic operation before verifying the MAC on a message you’ve received, it will somehow inevitably lead to doom!”

– Moxie Marlinspike

If you do know the specific encryption and MAC used, then it is possible to combine them in a more efficient manner. For instance, once again we can use the Keccak sponge function design to build a combined Enc+MAC.

Definition. Authenticated encryption with associated data (AEAD) contains three algorithms:

• KeyGen: randomly choose \(k\), as usual
• Enc\((k, P, A, N)\): produces a ciphertext/tag \(C\) of length \(|C| \geq |P|\)
• Dec\((k, C, A, N)\): returns the original private message \(P\)

The AEAD security game combines aspects of ciphertext indistinguishability and tag unforgeability. The simplest way to explain it is via the following thought experiment: Mallory cannot tell the difference between the two sides of this picture.

Why should we combine authentication and encryption?

• Better security: satisfies Moxie’s cryptographic doom principle
• Simplicity: developers have fewer decisions (i.e., opportunities for mistakes)
• Performance: save in time + space costs, also often only need 1 key

Next time, we will apply authenticated encryption in order to protect data at rest on your hard drive.